Pathing Excursions - more natural paths
Printer-Friendly Version
April 23, 2014
Press Releases
April 23, 2014
PR Newswire
View All

If you enjoy reading this site, you might also want to check out these UBM TechWeb sites:

Pathing Excursions - more natural paths
by Sven Bergstrom on 01/09/14 09:08:00 pm

The following blog post, unless otherwise noted, was written by a member of Gamasutra’s community.
The thoughts and opinions expressed are those of the writer and not Gamasutra or its parent company.

This is a cross post from my personal development blog , about a day or two spent jamming on path finding.

I enjoy messing with path finding algorithms and finding interesting ways to obtain the results, this is about a few more recent attempts.

Paths and "I hate grids"

This post covers approaches I have been messing with to confront some of the issues I have with path finding on grids, usually this is that the path results always look really rigid and unnatural. Even with path smoothing and all that, you still get these less than human looking movement patterns that always bothered me.

## Graph theory

Graphs are interesting, and so is the theory surrounding them.

When it comes to path finding, like A-star, you can apply the algorithm to graphs as well. You can see a really nice live demo of graph based path finding on this Polygonal lab page, until I have what I am making in demo form. Essentially it is about connecting points to each other.

This makes traversing the nodes quite a bit cheaper than grid based path finding because there are less nodes (though there can be more, obviously) but the other benefit is that the neighbors and their nodes can be determined ahead of time, and using other algorithms - like Voronoi diagrams - you can insert/remove cells from the landscape dynamically.

### Voronoi Diagrams and Delaunay Triangulation

While I was getting ready to move to Canada I wanted to distract myself from thinking too much and worked on implementing pathfinding across large areas using zones, using Voronoi diagrams.

You may know what they look like, and their uses and scope are outside of this article (though the link to Wikipedia is fairly thorough) - but they have a lot of fascinating properties including Delaunay Triangulation by connecting their center points.

## Back to paths!

What I was working on was a small procedural stealth prototype usingsome code from ctrlr (a post about this generation is forthcoming), to generate a large random space to explore with guards and cameras for interest sake. A procedural stealth playground.

Looking closer you can see there are some guards and some cameras and the building shapes are all random.

#### The pathing setup

So, to have a guard meaningfully run from one side of the world to another was an interesting challenge, there is of course more than one viable approach - I went with zones (larger cells, like broadphase) and then smaller phase, using the graphs.

At first I tried making the areas a single mesh, but there were just too many nodes for my liking and on larger areas this just got slower and slower. Not ideal.

The first step would be to section off areas, and do path finding on the large scale grid, when travelling across boundaries. Like this :

Now the AI can path first on a coarse grid, find the sub grids to navigate, and only ask those sub grids for a path on arriving at their boundary.

This also means that when a destination changes, it is often not significant enough to affect their sub grid path and they won't "suddenly change their mind" and run in a different direction, they will continue until their next boundary arrives unless their next boundary location changes.

Now we have split section boundaries, a decent amount of nodes to generate paths with, and "global" vs "local" navigation running.

Clicking on a cell (or deciding where your exact cell location is), in order to find a path, I also used the broadphase cell split approach. Break down each local section into a grid, calculate which grid you are in, and at creation of the grid, store every point and center point of the cell that lies inside the grid in a list. I stored these as list of vertices (to use with a "point in polygon" algorithm).

So when you click on the bottom, you get something like row 6, and column 2. Work out the position in world space, add it by the cell sizes (simple grid math) and check the list of cells for the on it lands inside.

The blue lines are any cell that has a vertex inside of the chose grid location (the third one from the bottom left). The vertices highlighted show the polygon selected, and the white point is the click position. To the path finding!

#### Neighbors and heuristics

A-star is simple in that it works on a lot of stuff, it's just an algorithm and can be applied to multiple situations. Here we have a start cell, and an end cell - and thanks to Voronoi cells being the basis, we now have Delaunay Triangles (connecting the center of each cell to the other center points) we have the information we already need - the neighbors and the distance for finding a path.

So as you can see, we have a possible direction to go from here. Voronoi can be tweaked to have less or more cell sides, depending on the complexity of your diagram and source points (which is covered later on). The key here is that everything you need to find a path, is sort of inherent to having it being built as a graph in the first place!

#### Finally, a path

Here is what a path looks like from A to B on this grid (A bit dark, sorry but that was because I was jamming on the code and just taking screenshots along the way).

### The drunken stealth guard

So cool, we have a path. It looks a whole lot more natural than a normal grid based path, to me. It is quite rough still, but you couldincrease the fidelity of the graph and make it higher resolution so that the path is smoother. Like this :

That's one approach, but what if you had ... almost a grid? And what if that almost-grid used the same graph theory, just on a more concise set of points? Well, this is what happens :

I REALLY like this path compared to grids. It's basically a grid! But the results are so much better, and cheaper (thanks to the graph theory having all the data on hand for me).

I still like the results with a messier grid :

But I really like the results of the slightly neater grid as well :

## Generating the graph

To generate these spaces, for the Voronoi looking cells - simply place points randomly in the area, and then run a smoothing algorithm over the points using something similar to Lloyd's Algorithm, this neatens up the really random placements into more uniform placements.

Before smoothing :

After smoothing :

To make the "almost grid" it is as it sounds, generate a set of points on a grid but add a slight amount of randomness to their position. Generate a uniform grid, and then add some noise.

`point.x += (-0.5 + Math.random()) * noise_scale;`

would give you ~2 pixels of randomness of noise_scale was 2. The -0.5 will make it + / - instead of just + so that the randomness is not shifting the grid to the right and downward. For those unfamiliar, `Math.random`returns a random number between 0 and 1 (like 0.23953148096).

## Other pathing experiments

I have a few more path experiments that I have been exploring over time, some of which I stumbled upon due to buggy Heap algorithm code, and followed the rabbit hole because the results were pretty interesting.

The interesting thing about the following experiments, is that they all still reach the destination (the pathing is 100% ok) but the resulting paths are fascinating.

The path starts at the top left, and ends bottom right. The orange is the grid, the black are obstacles, the white is the path.

Some of the comments on these images were interesting as well, mentioning the last one looking like an optimal tower defense layout. My thoughts once digging into the results were around guard patrol routes, where your job is as a stealth security patrol, instead of being completely predictable you could be more interesting and varied while still maintaining your destination.

## Explosions

Things don't always go according to plan (the above is one of those times it works out for the better) but these are some images of when the pathing or graphs were going crazy.

#### Bad point in cell collection

Looked neat though!

## Conclusion / resources

I also really like the paths from Theta* path finding, it is a nice way to generate smoother more sensible looking paths.

Alex May linked to an interesting video using tree like paths. This makes me wonder about using L-system generated paths as well... Something I may mess with in future.

### Related Jobs

Digital Extremes — London, Ontario, Canada
[04.23.14]

Programmers
Square Enix Co., Ltd. — Tokyo, Japan
[04.23.14]

Programmers
Treyarch / Activision — Santa Monica, California, United States
[04.23.14]

Production Coordinator (temporary) - Treyarch
Vicarious Visions / Activision — Albany, New York, United States
[04.23.14]

Senior Software Engineer-Vicarious Visions

 Arnaud Clermonté
Increasing the resolution of the graph to make the path smoother seems like a very expensive solution to me...
A cheaper solution would be to do the opposite: simplify the navigation geometry to the bare minimum ( a triangle mesh that corresponds to the navigable area ),
then use the triangle edges as the A* "nodes" ,
then allow the AI agent to walk though several edges in a row in a straight line whenever possible.
http://mgrenier.me/2011/04/pathfinding-103/

 Sven Bergstrom
 My goal is not shortest, nor straightest paths as I don't like how these look :) Good reading though. (I also mentioned that I *didnt* just increase resolution as a fix)

 Robert Basler
You can calculate the straightest path using the funnel algorithm from http://digestingduck.blogspot.ca/2010/03/simple-stupid-funnel-alg
orithm.html

 Sven Bergstrom
 I commented above, but my goal was not shortest or straightest paths - also a great resource (I have used recast and detour before also :))

 Christofer Stenberg
Instead of making the grid wobbly, why not make the path wobbly?
To clarify, instead of making an "almost grid" why not just offset the nodes in the path a bit.
And remember that two drunk guards walking suit would have the exact same wobbly behaviour.

 Sven Bergstrom
 This is an implementation detail, what I do is set the weights of the cells of a path "in use" to something other than 0, making other path finding entities use other cells. If you had really dense sets of AI walking across each path found can split the voronoi cells easy (the nature of the algorithm) and it will yield more distinct paths in tight paths without them overlapping (and maybe even share nodes, based on weighting). The goal wasn't wobbly paths, something to code on a above-path level - the goal was simply to use simple A* on simple graphs to generate _better_ looking paths without having to do anything more on top of it. Remember it was a short jam, just for fun and exploring possibility space :)

 none Comment: