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 using some 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.

Determine your cell location

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 could increase 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

Failed "radius" point-in-cell check

Looked neat though!

Failed Voronoi diagram

uhhh... what

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.