Show HN: Open-source shooter which made it to AC: Valhalla and Skydio drones (github.com)
So just for fun, I wrote a complete multiplayer game in pure C++. I even wrote my own texture atlas packer, which is now used by Assassin's Creed, 2 scientific publications as well as a drone manufacturing company - each of these basically mentions the name of my game. There is even a claim that Unity patented some of the ECS ideas that originate from this project. See https://github.com/TeamHypersomnia/Hypersomnia#tech-highligh... for details.
By the way the game is pretty darn good. 10 people connected yesterday to test a new map: https://www.youtube.com/watch?v=CHLPzZqANlM
It took me well over 10 years to code it all by hand, but the journey was truly worth it.
46 comments
[ 4.8 ms ] story [ 106 ms ] threadIt's nice to see it so advanced. Congrats!
Is floating point arithmetic not fully specified or something?
Edit: should have searched the web first: https://stackoverflow.com/questions/49471943/floating-point-...
Floating point arithmetic is not associative. That is, (a+b)+c != a+(b+c) and (a*b)*c != a*(b*\c).
Multiplying by the reciprocal is not equal to dividing by the value. That is, x*(1/y) != x/y. An optimizing compiler may, when you attempt to divide by a constant, will optimize that to multiplying the reciprocal instead, that is, if you have code that divides by the constant 3 it will multiply by 0.33333333333333333, because it's a lot faster.
FMA (fused multiply-add) instructions are more precise and therefore not equal to the same calculation without FMA. That is, a*b+c != a*b+c if one compiler will output FMA instructions and the other one does not. (this will be true even in the same compiler with different flags)
Special functions are fucky. sqrt, sin, cos etc might not always give equal values. Or even in the same compiler if minor alterations to the code are made. A compiler might use one algorithm to compute sin(x), but a different algorithm if it needs to compute both sin(x) and cos(x) at the same time.
Floating point rounding mode is a thing. Sometimes a plugin changes your floating point rounding mode. Sometimes this plugin will be inserted into your runtime without your knowledge, such as an antivirus program, or malware that hijacks your browser to give "better"/"customized" shopping/search recommendations. There was a bug writeup about a crash in Chrome several years back, but I can't find it.
Basically you should assume that floating point math is non-deterministic. If you think you need deterministic floating point math, try to reformulate the problem so that you don't need deterministic floating point math. If you really* need deterministic floating point math, understand that you're signing up for a lot of pain.
[1] https://stackoverflow.com/questions/55974090/clang-gcc-only-...
There is no sqrt instruction. So you stard with a taylor approximation, then maybe do a few rounds of Newton's method to refine the answer. But what degree is the taylor series? Where did you centre it (can't be around 0)? How many Newton's methods did you do? IEEE 754 might dictate what multiplication looks like, but for sqrt, sin, cos, tan you need to come up with a method of calculation, and that's in the standard library which usually comes from the compiler. You could make your own implementations but...
Floats are not associative: (a+b)+c != a+(b+c). So even something like reordering fundamental operations can cause divergence.
- sqrt actually can be a single instruction on x86_64 for example. Look at how musl implements it, it's just a single line inline asm statement, `__asm__ ("sqrtsd %1, %0" : "=x"(x) : "x"(x));`: https://github.com/ifduyue/musl/blob/master/src/math/x86_64/... Of course, not every x64_64 impl must use that instruction, and not every architecture must match Intel's implementation. I've never looked into it, but wouldn't be surprised if even Intel and AMD have some differences.
- operator precedence is well-defined, and IEE754 compliant compilation modes respect the non-associativity. In most popular compilers, you need to pass specific flags to allow the compiler to change the associativity of operations (-ffast-math implies -funsafe-math-optimizations which implies -fassociative-math which actually breaks strict adherence to the program text). A somewhat similar issue does arise with floating point environment though, as statements may be reordered, function arguments order of evaluation may differ, etc.
The fact that compilers respect the non-associativity of program text is a huge reason why compilers are very limited in how much auto-vectorization they will do for floating point. The classic example is a sum of squares, where it bars itself from even loop unrolling, never mind SIMD with FMADDs. To do any of that, you have to fiddle with compiler options that are often problematic when enabled globally, or __attribute__((optimize("...")) or __pragma(optimize("...")), or probably best of all, explicitly vectorize using intrinsics.
This is just plain wrong. IEEE 754 defines many common mathematical functions, sqrt and trig included, and recommends them to return correct values to the last ulp. Most common cpus have hardware instructions for those, although Intels implementation is notoriously bad.
Furthermore there are some high-quality FP libraries out there, like SLEEF and rlibm, and CORE-MATH project that aims to improve the standard libraries in use.
That word is really important because it means you can’t rely on it for real determinism.
I think rounding up/down can vary across architectures. Mixing arm/amd/intel here should result in non-deterministic behavior potentially. https://en.wikipedia.org/wiki/IEEE_754#Reproducibility
Ah... I see. The game is using a software implementation of floating point maths to avoid this issue :). Smart. That in combination with the unified compiler should get you out of most of the trouble.
https://docs.oracle.com/cd/E77782_01/html/E77791/z4002282485...
Another issue is that FP uses some amount of invisible global state, e.g. rounding modes. Iirc for example DirectX likes to change the flags behind your back.
https://www.freeinfantry.com/
https://en.m.wikipedia.org/wiki/Infantry_(video_game)
https://en.wikipedia.org/wiki/Attack_Retrieve_Capture http://armorcritical.com
The game didn’t make it to AC:Valhalla, a texture-packing library that was made during its creation did[1] (not wanting to downplay that achievement, it’s worthy of a post in its own right, IMO).
It’s also a bit of a stretch to claim it was the source of the ECS system used in Unity. I was using a game engine which used ECS prior to 2010. In the game engine world it seems to originate with Operation Flashpoint[2] (post from 2007).
[1] https://github.com/TeamHypersomnia/rectpack2D
[2] https://t-machine.org/index.php/2007/09/03/entity-systems-ar...
In a fully, brutally data-oriented ECS, you would allocate all components of the same type in the same memory block, so you'd effectively end up with a std::vector<TransformComponent> and a std::vector<PhysicsComponent>, etc. Each entity then holds ids, such as a pair of `what` component and `index` into the respective vector. This ensures that, like your approach, the cache is used well, and that memory fragmentation is minimal.
I find your project(s) very, very inspiring as I love working on similar problems among others (github.com/lionkor), thank you for sharing!
struct player { components::transform transform; components::health health; };
struct box { components::transform transform; components::physics physics; };
Then my ECS simply holds a std::vector<player> and a std::vector<box> rather than having a vector per each type of component. I also use the integer identifiers like you describe but with a twist - there is one more indirection involved so that deleting from the vectors does not invalidate existing indices pointing to vector elements. It's still exactly O(1). See the section on the Memory pool in the game repo's README.
Very common way of optimizing for CPU caches.
Springrts[0] has been doing all that has been described here for the same reasons in late 2000s and I guess countless RTS games also, they just weren't open source. Not to say it isn't an achievement because it is indeed damn hard.
[0] https://springrts.com/
Also, we don't speak about PA.
BAR looks really promising, also: https://www.beyondallreason.info
To the author:
What else have you been working on commercially to support the project?
Do you plan to release it in steam?
How does the persistent world effect gameplay?
With your clever rebuild physics when a new player joins technique, what does that functionality look like for existing players? Do bullets shift position for example?
- I have done various gamedev jobs over the years, the most recent being gameplay programming for this minigame in PUBG: https://www.youtube.com/watch?v=tSP5P0QGWa4 I managed to successfully invest my savings too which let me focus entirely on Hypersomnia.
- Yes, I'd love to release on Steam before 2024.
- For now there is no persistent world at all, I just mentioned it as a teaser for where the game might be heading if it becomes successful.
- Rebuilding the physics should not at all shift positions. What is rebuilt is merely the "hot state" like contacts and trees - the only moment where hot state matters is during the process of advancing the simulation from one state to the next, it does not influence how state is later rendered etc. The only impact on the existing players could be a single framerate drop in case the physics world to be rebuilt is massive, but in practice all our maps are still rather small, best suited for 3v3 matches.
Secondly, I've caught a big ol' bug for you on MacOS. When on the pause screen/settings, mouse input is offset significantly. It's to the point that the main menu options aren't even clickable. I've gathered screen capture of the problem here for you, with the logs and a System Report.
https://youtu.be/O4OoMdeFAt0