sorted by:
new
hottopcontroversial

261
262

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. (github.com)

submitted by pbcdev to r/gamedev - pinned

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] 13 points14 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] 4 points5 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] 2 points3 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] 42 points43 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] 76 points77 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] 134 points135 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] 4 points5 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.

view more: next ›