So I have a proceduraly generated world. The world is tile based, with characters being able to move along the grid. Characters can be an infinite distance away from each other, and there can be upwards to 100 number. The world only exists where characters are. The problem, of course, is that means each character essentially needs their own graph. Since 100 characters can be in 100 different locations, that would mean 100 graphs. My question is how to go about this.
Some ideas I had:
Chunks are 16x16 tile sets, I could simply create 100 graphs and when a chunk is loaded in a free graph moves to that chunk and updates on it.
Each character gets their own grid. This could be even more costly, as two characters that are in the same area should be using the same grid.
Thoughts?
Hi
Key information that is going to be required is.
What is the maximum required length of a path, i.e in how large area around the characters does a graph need to exist?
How quickly do characters move across a whole 16*16 chunk? I.e how often to graphs have to be updated.
Also. If your world is infinite, keep in mind that floating point coordinates loose precision after a while. I recommend that you try to keep your characters within ±10000 units on all coordinates (or at least ±16000) to avoid issues.
The maximum length is potentially infinite. I would think that it would compute a path within a small area around itself, then compute another one to keep bringing it closer. In terms of how large a graph needs to be I would say 16x16 wouldn’t be unreasonable, but 96x96 would probably be more accurate. Characters move fairly slowly, so it wouldn’t have to update that often. Maybe a full 10-20 seconds.
Ok.
How complicated can long paths be? Because if the world is relatively open it can be a reasonable approximation to just have a small graph and if the characters requests a path to a point outside the graph the character will just move towards the best point on the border of the graph and then recalculate the path after a while. 96*96 is doable (might be too much since you have many agents though), the smaller the graph is the faster it will be to update and move it. Likely what you would have to do is to override the GridGraph’s UpdateNodePositionCollision method and make that simply get the data from your internal representation (i.e setting the walkable flag and penalties if necessary). Then you could use the ProceduralGridMover script, one for each character. It would need some small modifications because the ProdeduralGridMover script only picks the first grid graph it can find, not a specific one. Similarly when requesting a path you can use a graph mask to specify which graphs are valid to search on, but that is just a bitmask which has 32 bits, so you would have to extend that to support more graphs. It shouldn’t be very hard (I know one user that did it a few weeks ago), see the NNConstraint class.
Well actually, since each chunk is 16x16 and there is no way to get a grid without the data its based on to be there, then ideally the size of each grid would be 16x16. I just tried creating 200 16x16 graphs and it didn’t seem to eat up TOO much memory, around 20MB. Not sure if that is an accurate test though.
Also, if you have two graphs next to each other and tell someone to move from a position in one to a position in the other, would it work? Or is there some setup involved in that?
Hi
I generally discourage linking graphs like that. There are many edge cases.
So I would recommend that you use a (3x3)x(16x16) graph and when a character enters a new tile you recalculate the graph.
There are some optimizations that can be applied to bring down the memory usage a bit, but we can handle that later.
Also note that the memory usage is dependant on the number of threads that you use.
What platform are you targeting btw? It sounds like a server from what I can tell.
Windows, Mac, and Linux. It is a proceduraly generated world. It is a Survial RTS game. Ok so here is a scenario:
I have chunks that are 16x16. Character’s A, B, and C are on the chunk at position (8, 12). Character D is on the chunk at position (-30, 20). Character E and F are on the chunk at position (121, -359). They are all given the order to move to the chunk at position (1000, 1000). Chunks only exist when a character is standing on them.