Dynamic 2D Navigation Mesh Generation using Medial Axis and Voronoi Regions

Hi all,

2D navigation mesh generation is something that I’ve been playing with for some time now. To be completely honest, I don’t even know if there are nice, affordable options that you can get online. I know that they exist in 3d, but, through my minimal searching I haven’t found one for 2D games. First and foremost, what is a Navigation Mesh? A navigation mesh is usually a 3D mesh object that defines traversable space in a game. This is where the problem occurs for us in 2D. 3D objects don’t exist in 2 dimensions. So, to combat this issue, the game designer can generate a map of connected waypoints, thus creating a navigation graph. Where the real trick is, is creating a “navigation mesh” for dynamic 2D environments. In my youth I was fascinated by the AI in Lionhead’s Black and White.

Lionhead's Black and White 2

In Black and White you play as a “god”, and you are overseeing a world below you, answering prayers, and helping townsfolk. I would watch the people in these little towns walk around and go where their AI tells them to. What I found was most interesting was when I were to drop rocks, or build a house in front of them, they would know exactly how to get around it and continue with their daily lives. With this, I set off trying to create my own implementation of it.

Preliminary Implementation

In Flash, I tried to create a graph of interconnected nodes, and my method of generating paths between houses was to firstly keep an array of all points that create the house (each house was a polygon). I would then find the center point between every node in the game. Upon generation of the center point, I would then determine if the node was inside another polygon, if wasn’t, then the node was officially created and added to the list of nodes. After all nodes were found in the game, I would then proceed to draw a line from every node to every other node essentially creating a mesh network. As the nodes were being evaluated I would check to see if the line crosses through any houses, if it didn’t then that node was reachable from that particular node. This was not ideal because it takes a long time to update the map, handle the nodes, and obstacles could not move in real time.

In the sample above, you can see some tests of generating houses and the accompanying nodes. It’s not terribly fast, in fact, it’s really slow. However, there are better options to generating navigation maps.

Alternate Methods

Delaunay Triangulation

Triangulation of an object is exactly as it sounds. Given a polygon of 4 (If you want to be technical, 3) or more sides, the maximum amount of triangles that can fill the provided polygon is generated. The speed of a standard triangulation of a polygon is O(n log n). Which is pretty fast, and some faster implementation have been generated, with one that performs at nearly O(n) speeds. Delaunay Triangulation not standard triangulation. Delaunay Triangulation is the triangulation of any set of points P such that no point in P is within any circumcircle of any triangle in DT(P). Take the following image into consideration:

Delaunay Circumcircles

You can see that there are circles drawn that connect every set of 3 points of every triangle. You can also see that no circle is generated such that there is any other point within it. This methods usually provides a rather equal looking triangulation of a set points. This is useful because it helps in creating an organized and useful navigation map. Another great thing about Delaunay Triangulation is that when connecting the center points of every circle, you are given a Voronoi Diagram

Voronoi Diagrams

Lets say you have a set of points P, and you want to create a graph where the lines are always perpendicular to the direction of any 2 nearest points in the set of points P. The Voronoi diagram is a way of dividing space into regions. There are many applications for Voronoi including space parsing, geometric partitioning, skeleton generation, and more! Voronoi tesselation is often associated with medial axis.

Medial Axis

The medial axis, sometimes referred to as a topological skeleton, is the process of skeletonization of an object. The Medial axis or Voronoi Skeleton of a polygon is the set of all the points with 2 or more closest points on the polygon’s boundary. Another way of putting this is that it is the locus of the center of all the maximal inscribed circles [1].

The medial axis is a way of generating paths between objects for pathfinding in a dynamic world. As you can see in the .gif above, the medial axis is recomputed in realtime, and  then adjusted accordingly.

 

Generating the Medial Axis

There are numerous ways of generating the medial axis of an object. We are going to observe the method created by Harry Blum in 1967. His method is the Grassfire algorithm.

The way that it works is an image of a polygon or shape is given, after algorithm is run on it the resulting image has the look that it had “caught on fire” and burned into the center [2]. The purpose of this algorithm is to end with with a skeleton of the object, or medial axis. Other methods exist of calculating the medial axis that don’t involve parsing an image. An algorithm created by DT Lee is detailed in the work of Francis Chin. He elaborates the efficiency of the algorithm is O(n log n) [3]. The basic concept behind it is that a simple polygon is broken down into histograms, then in mono-histograms. Then the Voronoi diagram of the histogram is calculated and the results are merged together to create the medial axis [3].

Pulling it all together

Once you have the graph that makes up in the inner skeleton as the map, you can use a k-d tree to find the nearest point when pathing. For those that don’t know, a k-d tree (short for k-dimensional tree) is a sorted tree that allows you to find the nearest points to a given point. Once that is created, and you’ve found the nearest point, traversal is very easy as all you need to do is use your favorite pathfinding algorithm to walk the map.

References

[1] http://spacesymmetrystructure.wordpress.com/2009/10/05/medial-axes-voronoi-skeletons/

[2] http://pageperso.lif.univ-mrs.fr/~edouard.thiel/rech/1967-blum.pdf

[3] http://www.google.com/url?sa=t&rct=j&q=&esrc=s&source=web&cd=8&cad=rja&ved=0CGgQFjAH&url=http%3A%2F%2Fciteseerx.ist.psu.edu%2Fviewdoc%2Fdownload%3Fdoi%3D10.1.1.18.7259%26rep%3Drep1%26type%3Dpdf&ei=MkHHUJzmFdSI0QGo3oDAAg&usg=AFQjCNG5xjwpV6grH8AIrTt7QYDQxTJ7QA

Leave a Reply

Your email address will not be published. Required fields are marked *