Saturday, 20 October 2012

Navigating Circles

In my short time as a game developer I've come across a number of way to represent accessible areas for AI on a map. However I'm yet to find way quite like this one, perhaps there's something inherently wrong with the technique that I've overlooked. Nevertheless I'd like to shed some light on it, but first lets take a quick look at some the other methods.


Grids are just about as simple as you can get when it comes to navigation, a section of map (or the whole map) is subdivided multiple times providing a lovely grid of squares, the centre of each square represents a walk-able point (alternatively you can use the corners of each square). Actors in the world are able to move between neighbouring squares. The problem here is you end up with a jaggy unnatural looking path. Some techniques can be used to then simplify that path, and using some spiffy interpolation and curve generation you can fix it up to look quite nice, but who the hell wants to waste time implementing that?

Waypoints (nodes)

An improvement from grids (unless you're making X-Com), Waypoints represent arbitrary locations for where actors can travel. One way or bidirectional edges are drawn between nodes allowing actors to move between them. Actors are considered to 'arrive' at a node when they get to within a certain distance (a fixed radius around the node). They're great for level editors (the person not the tool) as they give great control. Despite their advantages, they do have the problem of not being able to cover large areas without reverting back to a grid.


One of the more complex implementations. Nav-meshes are pretty cool (just say'n) ; you can easily define and edit large, shifting and maze-like traversable areas, not limited to single points. Put as simply as I can, a mesh (much like one you'd use for a 3D model) is first laid out on a map, actors are only allowed to walk on the mesh. Coding 'good' path-finding for nav-meshes is reserved for people with neck beards. Strange witchcraft is applied to the mesh to give you a sequence of points then various curves need to be calculated to get a nice smooth path; it can be difficult to understand and implement. If you do a poor job at implementing your path find then you'd just about be better off going back to way-points like the little girl you are. Also making a nav-mesh to begin with can be a massive pain, do you get an artist to manually model a mesh for walk-able areas manually (not great because they could end up making something horrid and or high poly) or do you implement some kind of procedural algorithm to fill out a map (if you're a leet haxor and have afore mentioned neck-beard). There are also tools available to help you build and use nav-meshes if you don't want to do all that heavy lifting yourself.

Variably sized waypoints (or circles)
I really find it odd that I haven't seen any documentation or hint that someone else has used this technique before. Basically it's waypoints, but each node is given its own radius to determine whether or not it has been reached. What's the advantage of this? Isn't it obvious? To show you properly, lets have a look at the walk enabled areas normal waypoints provide:

And then circles:

How is this so? Magic that's why.
The advantage of circles? Well, you can cover large areas much like you can with a nav-mesh, and with that you get the simplicity (in both use and implementation) of just regular way points. Plus it's pretty easy to get your AI to follow nice smooth dynamic paths about the terrain, but I'm still writing that blog post.

No comments:

Post a Comment