Since april, I’ve been creating my own implementation of a true navigation mesh pathfinding within Unity3d. Having no background in 3d game at all, I started from the beginning. So I wanted to post my understanding of the concept since I saw a few people looking for such explanations.
Here is my lengthy post about the basics of pathfinding. There is no code, this is only the concept to understand how to (a) build your own implementation, (b) use an implementation.
I’ll release my own implementation when I’ll be happy with my tech demo.
Nice. I will read it later. I am also interested in the concept of pathfinding, just didn’t have the time to read up on it. And i only have basic idea on how it works meaning how a simple pathfinding works but no idea how to go bout scripting it and implementing it. And i wanna ask is pathfinding considered resourse intensive? Like CPU intensive because of all the calculation it is going to make per seconds/per update. And what it i am making something like an rts with dozens of units. Hahaz. Just some after thoughts. But Thanks for the length post. Gonna read it later.
And knowing that Recast is now the norm in the industry (plus it’s MIT licensed), I would bet my money on it. And thank you for your input on my tech demo. It’s actually a internal tech demo of a game my team and I are making.
Pathfinding, and pretty much everything, can be resource intensive if misused! If we take a look at Aron v3.0 Stress Test or Alex King Stress Test (don’t you notice a resemblance?), with the proper strategy, you could achieve RTS with a decent amount of units.
Great article, I thoroughly enjoyed it. The next time I see someone asking about pathfinding, I’ll be sure to link them here.
The only part I was sad to see (or not see) is a mention of Dijkstra’s algorithm (the basis of A*). In some cases, though very very rare (only when you have room for the extra overhead), Dijkstra is the way to go.
For those of you wondering, Dijkstra’s algorithm goes through every possible path to ensure it returns the best option. A* will return the first time it reaches the goal (or you can let it go through a few more iterations depending on the implementation)
There is not one definite solution for every case, and in my experience, in Most cases, Dijkstra is the way to go. Which results with a solid and optimal path and calculation is (depending on the situation) oftentimes cheaper than using Heuristics.
And offcourse you can tweak it alittle bit to make things faster.
Especially in the case of navmeshes, the resulting graph is way too big to effectively run Dijkstras on as an alternative to A*. Note that in games, AI usually only has a handful of milliseconds to do everything in. Simulation is of course different.
Dividing into hierarchies in A* is indeed an effective approach for speeding up calculations. However it hardly covers the immense comparative overhead of Dijkstras vs. A*.
Regarding Path, I hardly see much point in spending resources maintaining it now - with built in pathfinding officially announced for 3.5. I would rather spend what little spare time I have on Behave.
