Posted on Apr 2, 2011

Pathfinding 101

Ever wanted to build a game where AI could move around in a not-so-dumb-manner? This is where Pathfinding come to play. It can be difficult to learn how to do it because every literature on the subject is no easy to understand. I’ve come along a great website listing a bunch articles and posts on pathfinding: Amit’s Game Programming Information.

So today I’ve read it all (almost) to have a basic understanding of A*, AStar, navigation mesh and optimizations. I’ve managed to create a work-in-progress navigation mesh using A* at its core. Here a snapshot of it inside Unity with some custom gizmos.

Navigation mesh in Unity3d

Navigation mesh in Unity3d

Blue lines: actual network; Pink lines: adjacent edges; In the console you can see the log of the pathfinding.

Basically, you need a planar mesh that will define the area where it is possible for the AI to walk. Internally, a mesh already has information on witch nodes (triangles) are connected. Once you have built the network based on the mesh, you can already run a pathfinding algorithm (A*) to find the shortest path between two point.

Now, I’ll need to find a way to smooth the resulting path greatly; triangles in a mesh form a very unnatural zig-zag-ish path.

Latest Tweets