I’m trying to implement a procedural generation algorithm in Godot. The details aren’t terribly important, it just matters that in order to have a world seed that gives me repeatable generation every time, I need to be able to run a lot of inter-dependant, highly entropic 3d vector operations in a completely deterministic way, ideally with a high precision.
So although I could do everything with integer mathematics, that’s a last resort because it means rolling my own… everything.
One method I’ve been looking into is fixed point mathematics, like with the FixedMathSharp library. One roadblock I’ve hit with that is that it really has no documentation, and even just getting a randomly generated number with a given seed from it has stumped me. I don’t even see any method that gives a randomly generated Fixed64 value - the library’s principle type - much less one from a given seed. Plus then I would need to implement my own octree with their Fixed64 data type.
Another thing I’m looking at is the deterministic version of the Rapier3d physics engine. If I can use vector operations that are deterministic, as well as piggyback on the physics engine’s octree and collision detection functions, then that gives me everything I need right out of the box. I just don’t know how to do that. Like when I select the deterministic physics engine, does that affect all of the vector operations and make them automatically deterministic or is there more to it?
Also, given that I’m going to need to do a huge number of collision tests and put a huge number of objects into the octrees, Is there any reason why I wouldn’t want to use the built in physics engine for that? Is it maybe a better idea to make my own octree rather than put that job onto the physics engine, or would the physics engine still be more performant because it’s all c++ code?
I think you are conflating two different things. There are two types of determinism of concern here. One is the algorithm deterministic, and the other is, are two computer systems deterministic with eachother.
When considering your case, if you run your algorithm multiple times with the same seed on the same machine, and it is a different outcome each time then its an algorithm problem where no library will help. If you are concerned with the outcome differences between two computers then the libraries will help.
(if its a physics simulation then the algorithm could be fixed with an implementation like Rapier, but you are saying procedural generation is the concern so… Not sure what you are meaning/needing in that case)
I’m not really conflating them, I know how to make the algorithm deterministic, and I need it to also be deterministic across systems, it’s a matter of having the correct tools to make it happen. So I need both kinds of determinism, I’m just trying to figure out how to do it.
So if I used a fixed point math library, I can definitely make it work, but it’s a lot of work to add all the supporting parts.
However, given that rapier is deterministic, that implies that it’s able to make floating point arithmetic deterministic, which I understand is possible depending on the implementation. I’m asking if I can somehow access that deterministic arithmetic for my generation algorithm, or if that’s something that happens below the level that I’m able to directly access in the engine. That’s probably something I need to ask the rapier devs directly, I just thought I’d check here in case people had ideas.
Alternatively if there’s another option that I haven’t considered I’d be interested to hear about that. I’m really early in the prototyping so I’m looking at all my options here.
Okay, but from the stand point of your generation algorithm, is it deterministic now? Determinism can be tested on one machine without any fancy libraries.
If it is deterministic now on one machine, determinism across systems will be easier since all we only need to do is utilize libraries that guarantee the math operations behave in the same way.
Yeah, this is really the information I’m looking for. If I can’t access the math library then it just won’t help me for this, so I won’t pursue it right now.
Do you know anything about Parry, if there is a way to get that working in Godot? It looks like it does literally just the job of collision detection which is a large part of what I’m working on, but there’s no information on whether it’s deterministic.
As it stands I’ve just heard back from the FixedMathSharp dev that they’re going to implement a seedable Fixed64 random generator which will address what I need in the long term, so I think I’ll work on the assumption that I can use that.
I’m sure an octree won’t be that hard to implement.
I feel like if I’m selecting the APIs that I use, and they are deterministic and don’t enable an option that explicitly breaks the standard, then I should be safe.
--ffastmath is an optimization for several C/C++ compilers (and has equivalents in others) that offers faster math in exchange for potentially going out of spec. If Godot is built with that…
You may well also find (depending on your platform, and what parts of it get used – think float pipe vs. SIMD) that the same computation produces subtly different results (possibly more below the decimal) on different hardware. Particularly if you have something cyclic that can accumulate error.
Im not an expert of all the variations of compilers and options that would be needed to guarantee determinism, but if it where known and you had a list of platforms you intend to release on, i wonder if it would be easier to compile the Godot engine with such build options and save you the time to rewrite the algorithm to avoid any float math in Godot. But i understand the allure of a fixed point implementation would avoid the guess work.
I did spend a little time looking at godots random number generator implementation, and it surprisingly limits its values to 32 bit ranges since godot uses PCG32 under the hood. And learned that the global rand* functions are shared(and used by some parts of the engine, like random pitch for audio streams, and a blur rendering algorithm), so it would be advised to create your own instance whenever you need to control the determinism of a seeded random number generator.
Yes, I know what the option is, and I’m saying that since rapier itself boasts of being deterministic, it doesn’t sound relevant. I am using a known version of godot and would build my game from that version, and the players wouldn’t be building their own versions of the game with exotic builds of godot. Unless you’re telling me that godot is built with that option enabled, then I don’t really see what it has to do with anything.
As for the cyclic stuff, yes, it would accumulate errors quite rapidly, so I know I need something actually deterministic. I’ve settled on using the fixed point library for now.
Thanks yes, I think I’m going to stick with fixed point math for the part of the algorithm that needs to be deterministic. Once the underlying geometry is built then the rest of the work can be transferred to the normal engine which doesn’t have to be deterministic.
Also, looking at the types of spatial partitioning I’m going to need, it looks like an octree will probably be overkill. I’ll be generating reasonably uniform fields of randomised points which my algorithm will use as the noise to generate the geometry, so I can actually partition them on a static grid which can be culled extremely efficiently, which means the roll-your-own part of the project is very easy in the end.
I must admit I find it hard to imagine a generated world that needs to be so deterministic that it cannot tolerate floating point imprecision. Are you sure you absolutely need such determinism for a game?
I know it does seem strange, but it arises because I’m doing simulations to create the very complex structures I need for my game to work. This means that it runs into the problem where a small difference in one early part of the simulation can have big snow-ball effects by the time it’s done.
If I were only doing typical generation that relies purely on analytic functions like perlin/simplex noise then I could plug in a world coordinate and get back exactly what the terrain should be in a single step. I will be using them for the base terrain and a few other things, but not for the main event.
I’ve made similar algorithms before, but without putting in the work to make them deterministic they’ve always been non-repeatable so harder to work with. Obviously seeded generation gives you the ability to reproduce the structures exactly on other computers, and also I want to be able to see apples-to-apples comparisons of any changes I make in the algorithm. Seeded generation allows me to do that.
I understand doing a simulation like this has huge performance implications, but it is actually necessary for what I’m making. I’m going to have to make the simulated structures happen relatively infrequently and in discrete chunks, but they are also a core part of the world I’m building so I’m not willing to take shortcuts. I also have a few design tricks in mind to mitigate the performance issues.
I don’t want to say too much more until I have something to show for my work, but I plan to post here once I have something I think is interesting. Suffice to say I’ve never seen what I’m making in a game before, and I’m honestly only doing it because I’m sick of waking up every morning longing to see the thing that’s in my head and remembering that it doesn’t exist.
Also I’ve never optimised the space partitioning in my previous prototypes, so each iteration of the simulation has had up to millions of distance checks, chugging the simulation terribly. With space partitioning I’m hopeful I can get it down to a few thousand checks in the worst cases, the difference really is that dramatic.
I wouldnt bother with the ‘best’ way, but i’d think about the nature of computational random numbers - historically they could be implemented as a lookup table or a deterministic mathematical function. So i’d work with the lookup table idea. The seed would jump the function through the table (wrapping at the ends). I dont have any evidence of this.
The easiest way i can think of is writing random floats to a texture then just indexing them with a counter and a seed, with the values wrapping at the end.
If its square texture then you retrieve the random number with something like:
var count = 0
@export var width
@export var height
func seed_rand(_seed:int):
count +=_seed
if count > max_allowed_int:
count = 0 # or something
func public_random_function()->float:
var rnd = get_random(count, width, height)
count += 1
if count > max_allowed_int:
count = count - max_allowed_int
return rnd
func get_random(index : int, width: int, height: int) -> float:
var p = index
var size = width * height
if index > size:
p = index - size
#var Index = j *width + i
var j = floor( p / width )
var i = p - j * width
return texture_lookup( i, j )
Sorry didnt notice it was c#, the concept is the same.
Also you have to check ‘if count > size:’ in the seed rand function. (Cough).
Of course i am missing the point … yeah the instant answer is to use software defined fixed point math to generate your tables and permutations etc that you then use to seed the generators. If the table is always the same, thats a good start point … the question is more like how can you be sure the generating functions will produce the desired output on different platforms with different processors.
You could design generator functions that can not break under floating point precision issues and still have many millions of possible choices.
The difficulty isn’t in getting repeatable seeded pseudorandom numbers. Virtually every standard RNG is capable of doing that, and I have ways of getting unique seeds for the different features in my world, it will give a lot more variation than a table could produce.
The issue is making sure the maths that I do with those numbers is repeatable, and with a fixed point library I can do that.
If you’re interested in how I’m getting repeatable but non-duplicated seeds for the different grid sections in my world, I’m using a prime sieve.
So for each large grid coordinate which will hold several thousand points, the world seed is modified with an integer given by x*2 + z*3 + y*5 + RegionX*7 + RegionZ*11. This gives a unique integer signature to each grid position which I then pass to the random function as FeatureKey.
The feature key was actually part of the functionality that mrdav30, the dev of FixedMathSharp, added when I asked about it. He says he needs it too but this particular variable seems tailored to my use case. The key is then mixed with the random seed using a special bit-mixing function that mixes the numbers up even further, ensuring that the resultant seeds are not adjacent to one another even if the grid signatures are.
If the locations in the world grew large enough the seeds could over/underflow and wrap around, and then there might be seed duplicates, but the nature of the algorithm is such that this still wouldn’t result in identical features.
Yeah you just need to be 100% sure the fixed function math is completely platform independant then the generated world would be the same accross all devices.
I have actually been working on shaders that index noise on a global scale for texture variation, blending two textures on walls for example for grunge maps etc, but so far they have been simple quick efforts that just lookup from a fast noise lite texture and the quality is dependant on the texture scale.
I havent tried to multiply two together to produce a local mask but im sure it would show repeating patterns (i.e. the top left corner might be visible or not, and it its always the same it would be noticable)
So i am thinking of blending multiple fast noise lite textures based on a global splatmap. Possibly using world triplanar textures but with the noise based on the XZ grid tile. So perhaps there could be a unique splatmap for each tile (i.e. large chunk or world units, say 64×64 per tile)
The problem is that each added texture layer / texture upload slows down the game.