In the last few weeks we reworked the pathfinding system in the world map scene. In this article we are going to explain how we implemented the new pathfinding system, and what are the improvements we got from it.

The old, tile-based pathfinding

As many other devs do, we used A-Star algorithm to traverse the navigation graph and pick the fastest route between two points in the map.

The navigation graph was generated using an offline process which defined nodes and edges following these rules:

• The world map was split in squared tiles
• We added a node in the graph for each traversable tile
• We added an edge between two adjacent nodes

The graph looked like this, with the nodes represented by blue circles and edges by red lines:

The issues

We analyzed the problems we had with this system and came up with the following:

• Too many nodes and edges, which led to poor performances
• Rough choice of routes along the coast

The solution

To solve those issues we wanted to find a way to generate the graph differently, in order to:

• Reduce the number of nodes and edges, especially in open areas, to improve performance
• Move the nodes closer to obstacles, to achieve smoother routes around corners

The graph generation

We ended up changing the rules of generation of nodes and edges in the navigation graph. We defined obstacles as polygons and defined the new graph with the following rules:

• Add a node per convex vertex of the obstacle polygon
• Add an edge per couple of nodes visible in line of sight

Inspired by this article we generated the obstacle polygons by following these steps:

1. Draw the obstacles using the Graphics editor of your choice

2. Insert the obstacle image in a GameObject and add a PolygonCollider2D component to automatically define the outline.

3. Generate nodes and edges of the pathfinding graph

Since our obstacles are static the process is done offline, and data stored in a ScriptableObject.

The path calculation

When a route between given source and destination points has to be calculated the only computations left to be performed at runtime are:

1. Add a node on the position of the source point
2. Add edges from source node to every visible node in line of sight
3. Repeat steps 1 and 2 for the destination point
4. Calculate the best path using A-Start algorithm from source to destination node

Here is the pathfinding in action, you can notice how the graph changes when moving source and destination points:

The optimization

In order to improve the performance and let the pathfinding not impact the framerate, we implemented few optimization techniques.

We added a visibility cache, we used the tiles we had in the previous implementation, and stored all the visible nodes in line of sight for each tile. This let us save computation time when adding the edges between source and destination nodes, instead of performing a lot of expensive line of sight checks, we just use the nodes cached in the tile the node is in.

We reduced the number of edges by removing all edges between nodes of different polygons, except for special nodes marked by hand. We won’t go in detail about this, since is strictly tied to the nature of the map, and we didn’t find a way to automatically choose special nodes.

We then moved all the runtime part of the algorithm in a different thread to further save computation time.

The final result

Despite having hundreds of nodes and edges, the overhead is minimal and improved ~100 times over the previous implementation. It runs smoothly on all the machines we tested it in, and we are now able to run it every frame to show the potential route the player can currently set.

Here is the final result in Nantucket:

Hope you enjoyed this technical article, I thought it would be useful to share it since I didn’t see anything like that implemented in Unity.

Nantucket is in the late stages of development, we are putting the final content and internal testing is giving us useful feedback on game usability and balance. We’ll soon show more gameplay in a video on our Youtube Channel. Meanwhile don’t forget to follow us on Twitter and Facebook.