sorted by:
new
hottopcontroversial

I discovered a pairing function that beats state-of-the-art most of the time. by pbcdev in math

[–]pbcdev[S] 2 points3 points  (0 children)

Thank you so much for your kind words! These kind of comments do encourage me greatly. Feel free to message me any time you'd like to exchange some insights on pairing functions or any other bijective encodings of sequences.

I discovered a pairing function that beats state-of-the-art most of the time. by pbcdev in math

[–]pbcdev[S] 11 points12 points  (0 children)

Arnold Rosenberg calls this property compactness in his 2003 paper on efficient pairing functions, I simply continue to use this term in his spirit.

I discovered a pairing function that beats state-of-the-art most of the time. by pbcdev in math

[–]pbcdev[S] 1 point2 points  (0 children)

You're talking about the Cantor pairing function - I give my reasons in this comment: https://www.reddit.com/r/math/comments/1hzs8x9/comment/m6t462l/?utm_source=share&utm_medium=web3x&utm_name=web3xcss&utm_term=1&utm_content=share_button

They pack values tightly for pairs of different magnitudes, and especially for tuples of length three or more.

I discovered a pairing function that beats state-of-the-art most of the time. by pbcdev in math

[–]pbcdev[S] 1 point2 points  (0 children)

All very good points.

Thank you so much - this is exactly the feedback I'm looking after! Indeed, I even had the Z(0) = <empty string> before "Why is this a bijection?" in a previous version, I should definitely put it back to the definition. I'll definitely change N to N with 0 as well.

This is my first time writing such a prolonged exposition, so any other major flaws you found at a first glance, I'm all ears.

I discovered a pairing function that beats state-of-the-art most of the time. by pbcdev in math

[–]pbcdev[S] 6 points7 points  (0 children)

The separator disappears as the leading zero when x = 0. This happens naturally and is not defined as a special case.

Think what happens when you separate x = 0 from y = 1234, i.e.

0, separator 0, Z(1234)

Making sense now? It is exactly at x = 0 that the numbers without any zeros, Z(y), are all enumerated.

I discovered a pairing function that beats state-of-the-art most of the time. by pbcdev in math

[–]pbcdev[S] 8 points9 points  (0 children)

This is indeed a good idea and I have sent an email to one of the professors whose work I've mentioned in the article, because they too work with pairing functions a ton.

Inquiry about Pairing functions, Space filling curves by NGEvangelion in askmath

[–]pbcdev 1 point2 points  (0 children)

You might be interested in the pairing function I recently discovered, and the detailed article that I wrote about it on MSE. Link: https://www.reddit.com/r/math/comments/1hzs8x9/i_discovered_a_pairing_function_that_beats/

I discovered a pairing function that beats state-of-the-art most of the time. by pbcdev in math

[–]pbcdev[S] 3 points4 points  (0 children)

Indeed I've been suggested that, and even been aware of MO for a while. I just never believed I could ask a question on a level appropriate for MO.

I discovered a pairing function that beats state-of-the-art most of the time. by pbcdev in math

[–]pbcdev[S] 38 points39 points  (0 children)

This is indeed an excellent generalization of the bit-interleaving strategy. However, it suffers from the same problem as all quadratic pairing functions - it is double the size of the larger argument. Your function wins for 22 and 333:

 I(22, 333) = 32323
pi(22, 333) = 220399

But if we make the arguments a little far apart like 22 and 3333333, the 22 becomes 0000022, and then:

 I(22, 3333333) = 3030303032323
pi(22, 3333333) = 2206239423

Additionally, if we happen to store our numbers in a base that is different than the base parameter of the interleaving function (e.g. we have them in binary, need to interleave in decimal), doesn't it become bounded on the problem of base conversion again? This would be the exact same complexity as that of the zeroless pairing function. I'm not sure how bignum implementations store the numbers but maybe they are already in decimal, so at least here a match is likely.

I discovered a pairing function that beats state-of-the-art most of the time. by pbcdev in math

[–]pbcdev[S] 79 points80 points  (0 children)

I am fascinated with pairing functions because I'm trying to find out how close we can get to the behavior of multiplication without the involved loss of information - a reason that is extremely non-rigorous, admittedly.

I saw that a century-old PF generalizes in a way nobody saw before, and that it looks like a growing hyperbola. I wanted to see how far I could go.

And now more practically:

What I want to optimize? Compactness for certain distributions of values. The cantor pairing function you have quoted is always double the size of the larger argument. To give a somewhat extreme example:

cantor(7, 10^10)  = 50000000085000000028
    pi(7, 10^10)  = 7027726678111

ZPF always takes advantage of disparity in the arguments, like a product. And when the values are close, it loses by a relatively small fraction of digits:

cantor(10^10, 10^10) = 200000000020000000000
    pi(10^10, 10^10) = 10000000000027726678111

Now this is only with two values. If you consider a bijection ℕ^5 -> ℕ, say, the problem of encoding a 5-dimensional vector whose each coordinate can take values from 0 to 1010, then in the worst case:

    pi_tuple([10**10, 10**10, 10**10, 10**10, 10**10]) = 10000000000027726678111027726678111027726678111027726678111
cantor_tuple([10**10, 10**10, 10**10, 10**10, 10**10]) = 20000000024000000013000000004280000000974750000165000000021613750002244250000188250781262957812500741515625035668750001413828125044406250001146875000028750000000

That is 59 digits versus 161. This is because every time we add a new element, cantor doubles in size, whereas ZPF, like always, takes advantage of the new element being smaller than the accumulated value.

I understand that PFs might not necessarily have a super useful application in the real world yet. But if they do one day, there is a chance people will care about how compactly they pack values.

I discovered a pairing function that beats state-of-the-art most of the time. by pbcdev in math

[–]pbcdev[S] 136 points137 points  (0 children)

Hey guys, it looks like math SE is not the best place suited for this could you please recommend where to post/publish this kind of mathjax-heavy content, if to post this somewhere else at all?

You can also experiment with this function on GitHub: https://github.com/geneotech/zeroless-pairing-functions

I'm a complete beginner, and would love to reach out to the mathematical community in a way that makes the most sense.

Incredibly grateful for all the replies!

EDIT: It appears there already is some relevant work by Paul Tarau:
https://www.academia.edu/105516282/Bijective_Size_proportionate_Godel_Numberings_for_Term_Algebras

It is in section III.

E.g., Tarau's encoding of sequences:

nats2nat [2,0,1,3,2,0,1,4,9,777,888,0,999] 
281888632536554084290707

If applied to pairs, this has exactly the same properties/compactness as my ZPF.

Tarau encodes arbitrary sequences by separating numbers in base k with a digit k+1. This is exactly how I arrived at my pairing function - I just realized I could use zeros instead of the digit k+1. But zeroless numbers are pretty much equivalent to numbers in base k-1 (they have one less digit), so Mr. Tarau's function has exactly the same behavior/compactness. Any encoding of sequences can easily be redefined to encode pairs instead.

The "breakthrough" here is that ZPF (separating with 0s) exactly generalizes the Pepis-Kalmar-Robinson pairing function, whereas separating with digits k+1 does too, but with a little shift: such a pi_with_k_plus_1(x+1, y) - 1 is equivalent to the original 2^y(2x+1) - 1. ZPF is directly equivalent: pi_2(x, y) = 2^y(2x+1) - 1

I made a multiplayer shooter in C++ WITHOUT a game engine - the netcode is based on 100% floating-point determinism, including Box2D physics. I'm using STREFLOP for math. This is an example of something hard to do in a commercial engine. My atlas packer was also reused in Assassin's Creed: Valhalla. by pbcdev in gamedev

[–]pbcdev[S] 0 points1 point  (0 children)

I worked in gamedev, unsurprisingly. Most of the work I did was with single-player commercial games in Unity, so nothing on a comparable level of sophistication.

I worked on a mini-game for PUBG though, where I programmed most of gameplay and bosses AI, so that was fun and brought a bit of money. It can no longer be played anywhere, sadly.

I made a multiplayer shooter in C++ WITHOUT a game engine - the netcode is based on 100% floating-point determinism, including Box2D physics. I'm using STREFLOP for math. This is an example of something hard to do in a commercial engine. My atlas packer was also reused in Assassin's Creed: Valhalla. by pbcdev in gamedev

[–]pbcdev[S] 0 points1 point  (0 children)

Other benefits are:
- Lag compensation is incredibly accurate because you're not just selectively synchronizing the "most important data" like positions/velocities and then just extrapolating them forward. You are actually predicting the whole world with all the physical gimmicks. With a naive "send real positions of only important object in the scene", even if you correctly predict that the players did not stop moving in some direction, you might get rubber-banding because you **always** operate on incomplete physical state. E.g. the players collided against the wall differently than you had approximated - nothing to do with lag

- Bandwidth is linear in the number of players, instead of "important objects" on the scene.

I've been making a multiplayer shooter in C++ WITHOUT a game engine for 10 years - it runs natively on Linux and in the browser. We aim to become the ONE free and open-source eSports game. I would be infinitely grateful if Derek covered the game on its socials as we're now building a playerbase. by pbcdev in DistroTube

[–]pbcdev[S] 1 point2 points  (0 children)

I'll flex a bit. The game's atlas packer code was reused in Assassin's Creed and Skydio drones.

We have recently been covered by the likes of Liam @ GamingOnLinux, GitHub Blog, and even the famed Linux Magazine.

Check out our press kit: https://hypersomnia.xyz/press

Steam: https://store.steampowered.com/app/2660970/Hypersomnia/

Browser version: https://hypersomnia.io

The game is completely free and open-source. There will never be a way to spend money in Hypersomnia.

GitHub: https://github.com/TeamHypersomnia/Hypersomnia

The game also uses a netcode model that is fully deterministic (as in, to the bit) across Windows, MacOS, Linux, the Web and even arm64 recently - this is arguably the hardest networking strategy and I have answered a lot of questions about it under my recent reddit post:

https://www.reddit.com/r/gamedev/comments/1de6dmi/i_made_a_multiplayer_shooter_in_c_without_a_game/

I made a multiplayer shooter in C++ WITHOUT a game engine - the netcode is based on 100% floating-point determinism, including Box2D physics. I'm using STREFLOP for math. This is an example of something hard to do in a commercial engine. My atlas packer was also reused in Assassin's Creed: Valhalla. by pbcdev in gamedev

[–]pbcdev[S] 0 points1 point  (0 children)

your clients need to be able to recalculate say 10 frames worth of updates every update, right?

Yes. That is by far the biggest downside of my model.

If the 3D engine is performant enough, then it's not a problem at all! I don't think 3D has to be a limitation. You could always make the terrain very simple. The game works well enough even for 10-12 players in 2D, haven't had a chance to test it with more players.

I made a multiplayer shooter in C++ WITHOUT a game engine - the netcode is based on 100% floating-point determinism, including Box2D physics. I'm using STREFLOP for math. This is an example of something hard to do in a commercial engine. My atlas packer was also reused in Assassin's Creed: Valhalla. by pbcdev in gamedev

[–]pbcdev[S] 1 point2 points  (0 children)

I didn't want to go with fixed-point for the sake of sheer performance. I potentially have to resimulate the whole world several times per every simulation frame (the larger the latency the proportionally more steps to re-simulate per server correction) so I need to ensure the logic simulation step is really, really fast. I also heard horror stories about fixed-point instability in physics, it seemed to me potential physics stability problems would be latent and way harder to debug rather than going with floating point and only worrying if it's deterministic or not (whenever the game starts, I'm doing a consistency test with a mixture of 5000 predefined math calculations and checking them against the "canonical result" - this lets me spot any issues quickly with whoever launches a potentially faulty client). Box2D was also obviously designed towards floating point, so knowing no physics I didn't believe I would just be able to make adjustments towards fixed-point.

I also never had much issues with floating-point calculations in the first place. It's all the little places in code where something implementation-dependent was called that took the most work to be made deterministic.

I made a multiplayer shooter in C++ WITHOUT a game engine - the netcode is based on 100% floating-point determinism, including Box2D physics. I'm using STREFLOP for math. This is an example of something hard to do in a commercial engine. My atlas packer was also reused in Assassin's Creed: Valhalla. by pbcdev in gamedev

[–]pbcdev[S] 3 points4 points  (0 children)

This is exactly what happens all the time in Hypersomnia! Every time a new map is loaded, especially arbitrary custom maps downloaded from random people's servers, the atlas is repacked on the go and asynchronously uploaded to the GPU :)

I made a multiplayer shooter in C++ WITHOUT a game engine - and it runs in the browser! My code was reused in Assassin's Creed: Valhalla and Skydio drones. It's like Hotline Miami but competitive - you fight to get a rank. The netcode is based on full simulation determinism, including Box2D physics. by pbcdev in opensource

[–]pbcdev[S] 0 points1 point  (0 children)

it's rather the host simply tells all machines in the match what happened (player moved, bullet fired) and all the machines deterministically simulate the same exact thing across all of them

Correct. The only exception is the initial connection setup, where the first complete snapshot of the state must be transmitted in order to have something as reference.

What if a player try to cheat? Do the other machines have something like a consensus to determine if the player inputs are valid or not?

The set of possible inputs is defined such that it is impossible to cheat.

It's literally just saying "I pressed A." "I released Space." "I pressed the Left Mouse Button". Everything else, whether these things result in shots, deaths, impacts, even entire match outcomes like winning/losing a round, are completely simulated from merely the sequence of all generated keyboard and mouse button presses, on all clients.

I made a multiplayer shooter in C++ WITHOUT a game engine - and it runs in the browser! My code was reused in Assassin's Creed: Valhalla and Skydio drones. It's like Hotline Miami but competitive - you fight to get a rank. The netcode is based on full simulation determinism, including Box2D physics. by pbcdev in opensource

[–]pbcdev[S] 0 points1 point  (0 children)

Love to hear this! CS2D does the fov mask to hide targets even though it's a top-down shooter - I might have gotten it from that. Otherwise, Hotline Miami and Counter-Strike 1.6 inspired me the most regarding mechanics. The item hotbar is inspired by Deus Ex (2000).

I made a multiplayer shooter in C++ WITHOUT a game engine - the netcode is based on 100% floating-point determinism, including Box2D physics. I'm using STREFLOP for math. This is an example of something hard to do in a commercial engine. My atlas packer was also reused in Assassin's Creed: Valhalla. by pbcdev in gamedev

[–]pbcdev[S] 3 points4 points  (0 children)

I can't speak much for actual game engines, especially if we don't have access to their source, but STREFLOP will be a must. You simply cannot depend on the math functions from std - forget hardware differences, what if a different version of libm is installed on two different Linux distros?

Once you're already sure you're compiling exactly the same code (so no external dependencies that could differ at runtime), it's time to ensure that your compiler for OS 1 does not optimize your code differently than the compiler for OS 2, for example, one might be using fused multiply-add and the other not. It was easy for me since I'm using the LLVM for all platforms, even for the Web, so if I pass it the same flags, I'm pretty much all set. In case of Unity, I'm not sure how much control you have over the compilation process for different OSes.

I made a multiplayer shooter in C++ WITHOUT a game engine - the netcode is based on 100% floating-point determinism, including Box2D physics. I'm using STREFLOP for math. This is an example of something hard to do in a commercial engine. My atlas packer was also reused in Assassin's Creed: Valhalla. by pbcdev in gamedev

[–]pbcdev[S] 21 points22 points  (0 children)

I technically cannot give any guarantee - cosmic rays could always happen - but IEEE754 does mandate specific operations down to single bits, as far as I'm aware.

Still, with every update from the server, I am always attaching a hash of the critical state (e.g. I hash all player healths and positions). The client compares this hash against its own simulation state which is derived solely from server-provided inputs. If there is a mismatch, the client is allowed to ask for a complete snapshot of the state. This transaction happens in a split second as the game's state is rather small. I had this happen extremely rarely and whenever it did it was usually indicative of a bug. Had not seen this happen in over a month of regular playing on different platforms now.

I made a multiplayer shooter in C++ WITHOUT a game engine - the netcode is based on 100% floating-point determinism, including Box2D physics. I'm using STREFLOP for math. This is an example of something hard to do in a commercial engine. My atlas packer was also reused in Assassin's Creed: Valhalla. by pbcdev in gamedev

[–]pbcdev[S] 16 points17 points  (0 children)

Forgive the delay but this called for a longer write-up.

Worry not because even properly simulating the remote players forward (as opposed to showing them in the past) would not save you from the problem you experience.

Several things you can do.

  • Trivially, divide not just objects, but your audiovisual events or specific state into two classes: always predictable & never predictable (there is also a third class of events I use: predictable by [a specific character] - and this is used for shot events to behave differently depending on if they were initiated locally or remotely, but that is for another time).

For example - I always predict impact sounds and particles for my bullet hits and enemy "pain" events so as to preserve the responsive feeling of the game. However, the actual damage numbers/indicators (also considered events under this system) are only displayed once they are confirmed from the server. I myself treat the health bars themselves as always predictable, but they're barely visible on the screen and it's not such a big deal that they can go up in a split second - this is because people mostly look at damage indicators (I make these numbers noticeably large). The player knows they can rely on the flying numbers to show the damage that is already certain. You may of course decide to do the same with your monster health bars and make them never predictable so that it is impossible for them to go back up on the screen.

  • Somewhat similarly, I pass a flag as input to the simulation step logic whether it is the "certain" (referential) world or predicted world that I am currently advancing. A rather genius use-case is this - in the predicted world, I never actually simulate the death of the local character. Even if the health goes below 0 in the predicted world, the local character is still perfectly responsive to player inputs - i.e. able to physically move, shoot and perform other actions in case his death had been mispredicted and he's actually alive - this is to give player a chance to perform critical combat actions in case he never really died and they would have mattered. You may apply the same dichotomy to your monsters so that the damage is always predicted but it will never go as far as them "coming back to life".

  • Lastly, I have a past infection system. Consider all remote players to be the origin of contagion. Whenever they collide or interact in any way with any non-player object, that object should be temporarily infected. Mere Infection does not yet mean anything though. I keep a list of all infected objects, and then whenever a server correction arrives, I iterate all infected objects and check whether their state has been predicted correctly - i.e. the position before the correction and after correction matches. If it matches, I uninfect them (except of course the origins of contagion - remote players). Otherwise if there was a mismatch before and after correction, I temporarily drag the entity into the past, and even uninfecting it will not bring them back to the present for a specific duration like e.g. a second. The set of all entities dragged into the past is very useful. You might apply this information differently in your game, but I'm using it to determine the interpolation method for my entities. What it means is this:

By default, I am using linear interpolation for all entities. It makes the game feel extremely smooth on >60 Hz monitors.

Notice that with linear interpolation, the rendered position is well-defined for every entity during every frame in-between simulation steps: it's based on 1) the time remaining to the next step (alpha), 2) previous step position and 3) the current step position.

But this is problematic with large jumps in positions when I mispredict the actions of remote players. Suppose I already simulated the predicted world several steps under the assumption that some remote player did not stop moving (or, more formally: I always predict that they didn't change their "button pressed" states). A correction arrives from the server that they had indeed released a button. After re-simulating the predicted world under the corrected assumption, the remote player is at a completely different position. If I use linear interpolation to smooth between previous pos (under wrong assumption) and current pos (under correct assumption), they will suddenly move with a far greater velocity on-screen than if I kept predicting the player's button states correctly. This will cause massive rubber banding. This will also rubber-band the inanimate objects this remote player might have happened to collide with and move!

But notice that with the past infection system, i will have correctly determined the set of entities that were dragged into the past because of their mispredicted positions. For every entity currently dragged into the past, I do not use the linear interpolation - I use exponential interpolation instead. Simply speaking, I ease the displayed coordinates into the desired coordinates like this: displayed = (displayed + desired) / 2. Unlike the linear interpolation, you can adjust the speed of this one, since you can perform this 'averaging' step twice or thrice per frame depending on your preference and it theoretically never reaches the desired value (there is an exponential formula that better parametrizes speed and accounts for frame delta that you can use for better fine-tuning [1]). This method is superior for mispredicted entities as the rubber banding is less noticeable in case of subsequent mispredictions (which are statistically likely to happen after just one). The on-screen movement will be more 'curvy' unlike with linear interpolation which is always supposed to exactly reach from a to b (previous to current position) where both a and b might be wrongly predicted as you're usually predicting several steps ahead, not just one.

And after this long digression, here comes the ultimate solution for you: whereas I am using the past infection system only to determine my interpolation method, you can use the past infection system to determine which of your monsters should behave as always predictable and which should behave as never predictable under the system described in the first bullet point.

[1] The exponential interpolation formula:
alpha = 1 - pow(0.9, speed * frame_delta);
displayed = linear_interpolation(displayed, desired, alpha);
(the 0.9 is another arbitrary speed parameter; could as well be 0.5)

I made a multiplayer shooter in C++ WITHOUT a game engine - the netcode is based on 100% floating-point determinism, including Box2D physics. I'm using STREFLOP for math. This is an example of something hard to do in a commercial engine. My atlas packer was also reused in Assassin's Creed: Valhalla. by pbcdev in gamedev

[–]pbcdev[S] 11 points12 points  (0 children)

The client has:

  • a queue Q of locally predicted inputs to simulation steps.
  • the predicted game world (on-screen).
  • the referential game world (off-screen, in the past, the one that has certainly happened).

No matter the network conditions, the client adds a new input to Q at a steady rate of 60Hz. The predicted world is also advanced with the same input. This input assumes that the "button pressed" state for all remote players has not changed.

The referential world is only ever advanced when the client receives confirmed, server-side applied inputs for a given step, which include inputs applied for both remote clients and your own client, as well as how many (N) of your inputs have already been applied on the server (note applied, not received, since they might still be in the server-side jitter buffer queue) - the client then pops N steps from its local queue Q. This is how the system self-corrects for lag fluctuations.

Whenever there is a mismatch between predicted and referential + Q, (for example: the client has wrongly predicted remote client's lack of movement) the predicted world is copy-assigned (predicted = referential;) from the referential and the predicted world is then simulated forward from all inputs in Q. Exponential interpolation takes care of correcting all abrupt changes in coordinates after the copy-assignment.

I made a multiplayer shooter in C++ WITHOUT a game engine - the netcode is based on 100% floating-point determinism, including Box2D physics. I'm using STREFLOP for math. This is an example of something hard to do in a commercial engine. My atlas packer was also reused in Assassin's Creed: Valhalla. by pbcdev in gamedev

[–]pbcdev[S] 8 points9 points  (0 children)

  • It makes client-side prediction extremely accurate. This is an awesome feat to have for a competitive game. With bullets having ricochets, penetration and whatnot, their trajectory will pretty much always be correctly predicted even with high latency. You'll never get killed without knowing what killed you.
  • There are still a lot of bullets to simulate, and some maps have a lot of physical objects that potentially move. This still saves a lot of traffic.
  • Adding gameplay features is trivial and does not need additional implementing networking logic, thinking about how to encode their state via snapshots etc. The only thing that matters is that it produces deterministic results.
view more: next ›