Could A* bring some love to our project?

Hello, and sorry for the odd question in the topic.I get that the question have already been asked around for various project but with the current sale on the pro version and our very very tight budget I need a specific answer :3. So, sorry if the topic is a bit dull ^^.

So our game will take place in a 8000x8000 unit map (with a lot of mountain that reduce a lot the walk surface). We plan to have a lot of npc (has many as the pathfinder will be able to process with decent performance). On top of that we would like the player to be able to construct buildings. So far, the solution using unity navmesh is to only construct specific buildings in specific places. We just bake the map with all the buildings active, and place obstacles (like rocks) instead of the building, using navmesh cutting.

So with that said, could A* improve the situation? I saw that it can update specific part of the graph, but I’m worried about the performance cost of that. On the other hand, I’m also worried about the pathfinding performances of unity navmesh (well to be honest I’m worried about everything in term of performances for this project x) ).



Well… Those are not really the easiest constraints to satisfy, but I can at least outline what you had to do to potentially get something that would work.
For such a huge map, a recast graph is really the only option (this is similar to what Unity uses). You can recalculate individual tiles, it happens partially on a separate thread, but it is still not really cheap. If this is only done on a server it might be more viable since a sever does not have a requirement of a high FPS. If you can use navmesh cutting for everything that would be best. Also I would recommend that you use the beta version and that you switch off ‘rasterize meshes’ for maximum performance when updating the graph during runtime.

Thanks for this quick answer =)

Alright so I found in another thread saying that, while updating the graph, no pathfinding can be done. Did you mean on the whole graph or just for the tiles that are been updated? I guess we might stay on the navmesh cutting solution, updating the navmesh seems to be a lot of trouble compare to the possibilities it would give us.

Also, you’r pathfinder seems to be a lot quicker than what unity can do with navmesh agent (even if I couldn’t find any number regarding unity performance), so I guess it would be wise to choose your project.

Yes, pathfinding needs to be stopped in the whole graph while a graph update is being performed. The pathfinder wouldn’t like running pathfinding on nodes that were not completely updated. In the future there is the possibility that I can calculate most of what is needed for the update while pathfinding is still running, and then only pause pathfinding while the update is being applied (which should be relatively quick), but this would require quite large changes unfortunately.

Awesome! I haven’t really got numbers for Unity’s system either, so I can’t say if you are correct or not. I have spent a lot of time optimizing the pathfinding, but of course Unity runs their pathfinding algorithm in C++ and have a huge advantage just because of that.

I don’t know if I’m correct. It’s just an assumption based on various comment I could find on various places. But thanks again for the intel, now I have to choose which one to use ^^.

Also. I’m positive that for Unity’s pathfinding system they will also have to pause pathfinding while the graph is being updated (of course navmesh cutting takes less time, so it is not much of a problem).

Well I guess it make sense. But are you referring to the navmesh components for the 5.6? (actually I think I saw somewhere a github repo with the components for the 5.5 so I’m a bit confuse).

5.6? Where do you get information about 5.6?
I’m not in the beta group (I was previously, but I got removed when they culled around 50% of the members that were not very active in the group).

On the roadmap. It’s still on uncertain color, but their is a link for some experimental code.


No I was just referring to navmesh cutting (or carving as they call it).

Yeah they’ve got a bunch of nice features there. Most of it (except wide connections) is already supported in the A* Pathfinding Project (rotated recast graphs are supported in my dev branch since a few weeks ago, but it is not released yet). However I must say they have a more slick API (looking at that experimental code).

Well I tested the project a bit, and it’s very interesting. Having navmesh bound to a component that can move around is very handy. I didn’t test it much more, but spawning building with their piece of navmesh and cutting the original underneath would remove the need of “updating” the navmesh itself (don’t know if it could work that way).

Right now, I’m gonna stick with unity navmesh, But i’ll keep an eye on your project and probably buy it when I’ll finally have some extra money (to be honest that anniversary sale couldn’t happen at a worst time for me).

Yeah that is pretty handy. That is in fact how we solve pathfinding in the game Folk Tale which I am working on ( However I will not port that solution to the A* Pathfinding Project because it just had soo much issues with floating point errors (we connected the navmeshes directly and automatically, not by using off mesh links).

Ok. Good luck with your game! :slight_smile:

Thanks you for your time, and good luck with the future of your project too!