Contact Home

Archive for April, 2015

Nodal Pathfinding in Unity 2D with A* in Non Grid Based Games

Posted on: April 4th, 2015 by admin 16 Comments

In a typical 2D grid based game, you restrict your level to fit into predefined squares. This makes it pretty easy to process this data with an A* pathfinding algorithm. But what happens if you are not creating tile-based levels?

Consider a level that resembles the following:

nodal1

The black squares are walls. The white circle is our movable character. Our goal is to provide a mechanism that will allow us to calculate A* paths in a Unity level such as this.

The first step, is to define an area that we will use to generate and calculate the nodal map. In this demo we do this by creating a GameObject (Grid gameobject), and setting its position and scale. This will be the area we will use to generate our Nodes.

These Nodes will serve as way points to help your character maneuver the map. Once these way points are generated, it resembles like this:

nodal2

I opted to generate the nodes in a diamond shaped pattern, as it provides a much better nodal mesh than a square pattern.

The distance between each node also matter. You need to match up your character’s size with the distance between nodes, otherwise you will not know if your character will be able to fit in between some holes. As long as your character is smaller than a half-unit, it will be able to fit. You could always generate multiple maps, if you have characters that vary greatly in size.

Here is how I setup my unit size for the demo. This circle should be able to pass between any two nodes:

nodal3

The next step is to generate the Connections between each node. For each Node, we raycast in all 8 directions, to determine if the path if valid or not. If the raycast hits a wall, or if the raycast is traveling outside of the defined area, then we mark the connection as bad (red). If the check passes, we mark the connection as valid (green). Each Node will then have 8 connections.

This gives us our starting connection map that resembles this:

nodal4

Removing the red lines from our output, we can then look at the valid paths that were generated from this simple base check:

nodal5

You can immediately notice that some of the paths are bad, as the circle cannot navigate between the two top-most walls for example. Also, there are some paths that lead to dead-ends, which we don’t want. We need to cull these bad paths, in order for our pathfinder to work properly.

We first start culling some Nodes, based on its connections. If a Node does not have at least 3 valid connection points, we remove them. In the following image, we mark these Nodes by coloring them red:

nodal6

Now that we have all of the bad Nodes, we remove any of the connections traveling to and from them. This gives us a much nicer Nodal map than what we had previously:

nodal7

Then it is just a matter of plugging in each connection as a neighbor in your A* pathfinding algorithm. Your A* neighbors are all defined by your Nodes and their Connections.

nodal1

Feel free to try the Demo.

Download the Unity 5 source code and project files here.



Update:

A friend of mine has expanded on this nodal pathfinding model, and has pusblished his code over on his Github

Example gif