Game Development – A* on Triangulated Spaces: Part 1

Following my last post about 4 Interesting Data Structures and Algorithms, I thought that doing a more focused article looking at just one of them in depth would be an interesting challenge.

I have chosen to show how A and spacial partitioning can be used to create an effective and efficient pathfinding engine during game development,* similar to what you would find in a modern video game.

Above is a codepen snippet which allows you to create simple triangulated environments and pathfind through them.

You can add vertices to the graph above by right clicking. You will see that sometimes when adding vertices, the graph will change the way large areas are divided up. This is because it is trying to preserve a Delaunay triangulation.

A Delaunay Triangulation is a special kind of triangulated area with a few special properties you can read more about here. Basically it means that minimum angle of all the angles of the triangles, is maximised, reducing the number of skinny triangles on the graph and giving us nicely partitioned area. It also happens to have the property of creating an efficient spanning tree which makes it appropriate for performing pathfinding over.

The graph maintains the Delaunay triangulation by ensuring no vertices exist with the circumcircle (a circle with it’s circumference passing through each vertex of a triangle), of any triangle in the graph. You can observe that this property has been maintained by left clicking on any triangle. If the addition of a vertex breaks this constraint, the triangles are flipped, in this case it means the common edge of any pair of violating triangles are flipped around in an attempt to retain the property. This will result in a chain of flips in some cases.

Here’s an example showing a single flip:

Now that we know how to partition space in an effective way, lets see how A* pathfinding works upon it. First we can create some obstacles for the pathfinding system to navigate, hold shift (or control) and click on the triangles in the graph. They should turn green denoting that a path cannot run through it.

After creating some obstacles, click (optionally drag) one of the small brown circles – these represent the start and end of the path. After clicking or dragging the path will be drawn.

There will actually be two paths drawn. One is a red line, this represents an A solution over a uniform grid.* The other path will be a path of triangles highlighted in yellow, this shows the result of A* being performed where the path points are the triangles themselves.

You can observe some significant differences between the paths generated on the grid and on the triangles.

The triangulated path (yellow) is more general, it shows a bounding area rather than a linear line, it’s also a bit less accurate due to the very simple distance measurements used to find the path distance between triangles as well as the distance between triangles and the goal.

The grid path (red) is usually more direct and will almost always get a more accurate route in this example. This is because the path distance between each node is perfectly accurate and the fact that the grid is much less coarse than the triangulation. (The red path may also cheat sometimes by jumping over skinny obstacles).

The big thing to observe is how many nodes A visits on each the grid and the triangle graph*. In most cases, performing A* on the triangulated graph will visit orders of magnitude less nodes than doing the same on the grid, this is because the number of nodes in the triangle graph is roughly proportional to the number of obstacles created, rather than a fixed number determined by the size of the area pathing is taking place. The big thing here is that clever spacial partitioning can reduce the problem space dramatically, while also being flexible. Pathing over a grid will consume too much resources if the grid is too fine or will be inaccurate if it is too coarse. Triangulation results in meaningful partitions with little redundancy.

That’s all I’m going to cover this time, next time I’ll cover how we can improve the heuristics and path-length estimations for the triangulated path, as well as how we can take advantage of the path we are given to navigate the environment effectively.

Raygun is an error reporting software system covering all major programming languages and platforms including game development languages and frameworks like Unity3D. Check out Raygun’s free trial today and find software errors before your users do.