Posted on May 7, 2011

Pathfinding + Steering behaviors

If you’ve been following me on twitter, you know that I’ve made some progress with my navigation mesh + steering behavior. For the past month or so, I developed a pathfinding solution using a navigation mesh for Unity3D (previous posts herehere and here). It was quite challenging at first and then became an obsession. I wasn’t satisfied by the solution currently available on Unity3D, A* Pathfinding by Aron Granberg and others A* script on the Unity Community Wiki. So I needed to build my own solution, lightweight and simple.

NavMesh + Steering behavior

48 agents moving around on the navigation mesh with a time-step under 1ms. For my game, it’s pretty close to what I called lightweight. For the simple part, I’ll come to that in the next weeks.

So what it’s at work in the demo?

Navigation Mesh pathfinding
I’m sure you can find better explanation of this subject on the web (like here and here), but here my understanding. In most case, an AI doesn’t need complex logics to find his way around your level (line-of-sight, waypoints patrol, move-to-target can be enough), good example by Subvert Games. When your level has big obstacles (cliffs, bridges, etc.), you need a system to describe the walkable areas in the level. The most simple and straight forward solution is the waypoints network, like Hasho’s one. Waypoints network are reliable for car-on-rail-movement and when you want some sort of smooth-line or crowd, the network doesn’t possess enough information for the AI and it can very well ends up in a wall or a ditch. Then, your solution is a navigation mesh: meshes are a simple way to describe a complex network with enough information to allow smooth path and multiple agents.

Mesh simplification, network initialization, heuristic calculation, A* pathfinding are all working asynchronously across a maximum timestep so it can split the process across frames, thus allowing your game to work harder on graphics, physics, networking, etc.

Steering behavor
Following my last post, I tried UnitySteer but could not work my way through this big (and complete) library. Once more, I ended up with my own simple solution. For the demo above, a simple path follow, separation and mesh containment is at work, thus producing the nice crowd-path-follow behavior I was looking for since the beginning of my journey.

I still have tweaks to play with, and I’ll try to submit it on the Asset Store by the end of this month, no promises.

Latest Tweets