Hello,
I’m currently working on a project where I generate at runtime a very wide and completely flat terrain made of 1x1 cells, let’s say a square of 1000x1000 cells. I have entities walking around all over this terrain, so I need a pathfinding grid that covers all of it, because entities will have to move around even when the player is nowhere near them.
However, I’m assuming having such a huge grid and compute paths on it would take a large amount of resources.
Do you have any advice on how I could achieve something like that in an efficient way ?
Thanks in advance
There shouldn’t be any long path requests. Most entities will just be moving around their position. They can end up far from where they started, but it’ll never be in a single straight path. Is your code optimized so you won’t necessarily check the entire grid for a path between two points that are closeby ?
I guess I could also reduce the search path frequency for all entities that are far away from the camera.
About the texture thingy, that might be quite useful. Since I generate everything at runtime (and already draw textures of my terrain), it’d be a lot easier to just set walkability / penalties this way. I’ll look into it !
Thanks for your answers, it’s been very helpful !
Use a recast graph is my suggestion (if it is really large, try the beta, it will behave better). It will give you a high load time, but superior performance during the rest of the game.
Thanks for the quick answer.
High load time is alright, I don’t mind that. I’ll give recast graphs a try then. It’ll require me to upgrade to Pro version though, so I’ve got a few more questions so I’m sure this will be a good solution for me :
If I have a terrain of 1000x1000 cells, I don’t actually have all these cells in my Unity scene. I just have big arrays holding all the data I need, and I draw only a small portion of my terrain (what’s visible by the camera). So, in order to simulate a terrain for the pathfinding, I guess I’d have to create a super large invisible plane that covers all the surface of my terrain.
For the pathfinding algorithm, my terrain would just be a big flat plane. I guess the navmesh generated will be very simple. Will I be able to set some areas to unwalkable at specific locations on that plane ? For example, if a cell is occupied by a rock, or if I have a river or a lake ? Would I be able to do that by using a texture map for the entire plane ? Or with 3D positions somewhere on my plane ?
Will it let me add/remove obstacles at runtime aswell ? My terrain is gonna be filled with objects the player will be able to move around / build / destroy.
Sorry for asking so much. I’m familiar with how grid graphs with square cells work, but I’ve never used other types of graphs before.
Thanks in advance
Hm… actually it seems like what you want is a grid graph after all. It fits all the characteristics, it is a bit large. But I think it can work if you try to limit the number of really long path requests. Multithreading will help a lot as well.
I know of at least one game which has used a 1000*1000 grid and run at a good framerate. It did not have a huge number of units (usually less than 50), but still.
See other threads in this forum about manipulating grid graphs.
If you want it simple, there is an option (in the pro version only though) to take walkability data (and other data if needed) from a texture (found under the Extras tab in the Grid Graph settings).
The A* algorithm will not search the whole graph for a short path.
It works something like this: http://en.wikipedia.org/wiki/File:Astar_progress_animation.gif
