Contact Home

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

16 Responses

Jeremy Friesen commented on July 9, 2016 at 1:05 pm

Does this work to make an enemy follow the player?

    admin commented on July 12, 2016 at 1:20 pm

    Yes, however, the logic that will move your enemies is not provided. This source code will provide you with a path (step by step position of each node you can traverse to get to a location). It is up to you to write the implementation of your character’s movements.

Gordon Fenning commented on September 17, 2016 at 6:01 pm

I’m trying to decrease the size of the diamonds but struggling. I’ve managed to decrease the size of the diagonal ones but its the next ones which are still 1 unit away.

How would I go about shortening these?

Josh commented on October 7, 2016 at 10:42 pm

Man, this would have been nice if you werent stuck with the grid in the center. Was hoping I wouldnt have to make my own grid, but it looks like I will lmao

Mauro commented on January 11, 2017 at 7:19 pm

Some questions…
– The “Nodemesh” resolution is based on the player size, so if i change my Focus to a Player 2 that has diferent size and colider, it shall be needed to redraw the entire Grid/Nodes. How can we trigger that in run time?
– Same thong Dinamic Objects qith Coliders on the Scene… if they move, the Mesh shall be re-calculated…. Witch is the best way to trigger that in run time?

    admin commented on January 12, 2017 at 2:41 pm

    The unfortunate issue with this approach is exactly that — you would require a different nodemesh for each entity size that you have. Essentially, you would pre-generate a nodal-mesh for each size, and associate that nodal mesh to each entity that shares that size.

    For dynamic objects, you would have to update the nodes that are active based on the location of your objects. You could re-scan the entire nodal map, but that wouldn’t be very efficient. One option would be to first lock the nodes that are contained inside static objects. This will eliminate a lot of nodes.

    Storing your nodes in some sort of spatial organization structure, such as a Quadtree, could also benefit you. When moving your dynamic objects, you could query your Quadtree for the nodes it is touching, instead of having to loop through every single node in your map.

    Ultimately when it comes down to optimizing, it will be pretty dependent on your game and how you are moving your objects, and what those objects are.

Maximilien Breughe commented on April 11, 2017 at 12:39 am

JGallant, I can’t find this project on your GitHub.

I like the idea, but I had to fix a couple of issues when plugging it into my game. I’d like to contribute. Please let me know if you have any place I can add my changes to.

Thanks,
Max

Radamirez commented on July 9, 2017 at 12:18 am

I have a doubt, how can i choose the initial nodel? If they are too large, the path cannot be the shortest, or not?

vbdev commented on July 22, 2017 at 6:12 pm

Thanks, you save my day.

gino commented on July 29, 2017 at 12:17 pm

really good, I like it. thanks for your demo, I learned very much from your code.

Arnas C commented on January 8, 2019 at 3:46 pm

Hey Jon, just wondering if there is any license attributed to this work?

Respond

Leave a Reply

You must be logged in to post a comment.