A* Pathfinding Project

Comparing A* to NavMesh for a school project


#1

Hi! I’m a game dev student who is also from Stockholm, and for my final school project, I have chosen to compare an AI using A* to an AI using Unity NavMesh. However I’m a little worried that maybe I’ve misunderstood the way that both of these things work, since I haven’t used them before. What are the differences between A* and NavMesh? Can I even compare them? I mainly wanted to see to which degree you can customize and optimize both of them, and what the fps difference is between the two, to ultimately figure out which one is the best choice. And is there any difference to downloading the free A* asset vs following Sebastian Lague’s tutorial and making your own?


#2

Hi

They are different in many ways. Mostly in terms of features.
You can find one comparison list here https://arongranberg.com/astar/freevspro

In veeery broad strokes: this package is a lot more flexible (more graph types, custom movement scripts, different modifiers etc.), unity has better support for off mesh links, scanning a recast graph in Unity’s system is faster (because c++, both Unity’s system and my package are based on the same base project called Recast). I’m not sure how runtime updates compare. This package can save graphs to files and load them during runtime, which I don’t think is possible with Unity. Penalties and tags are more flexible with this package than what Unity has. I think raw pathfinding in this package is faster (I am not 100% sure though), among other things because I think Unity only has the option to use a single thread for pathfinding while this package can use any number of threads. This package has different path types that are useful for some games (e.g FleePath and RandomPath).

The underlaying pathfinding algorithms are mostly the same (it’s all A*). However this package has some algorithms (like euclidean embedding) to optimize the pathfinding in ways Unity’s package cannot do at all.

Worth noting is that Unity’s pathfinding and this package’s Recast graph are both based on the same open source project called Recast: https://github.com/recastnavigation/recastnavigation

The free version of this package contains vastly more features than you would get from following a tutorial to write your own A* algorithm. But then, in some games you may not need a lot of features.


#3

Okay. By Unity’s package, you mean their standard NavMesh agents, right? I’m not sure what graph types and modifiers are, or mesh links, or recasts, or penalties. I’m very worried that I chose a project that was way beyond my experience. I think it needs to all be done by December. Mostly interested in how much I can customize the A* and NavMesh agent by myself, such as adding raycasts to detect hinders to jump over. And then comparing and documenting the performance during runtime based on different factors like how many agents are being used, what model is being used, the different map layouts, etc. It sounds easy in theory, but I’m sure I’m just being naive.

It would help a great deal to have someone guide me a bit through this. I understand if you are busy though. I have so many questions and I’ll definitely feel like a bother, asking them all here.


#4

Yes

Sounds like you might want to read the docs: https://arongranberg.com/astar/docs/

You might want to do the tutorial for implementing your own A* though, to understand how things work under the hood.