Performance considerations with Tile-Based Path Finding - any Ideas/Tipps?

Unity Engine
1

Hey guys,

I am programming a Pathfinding System for a simple Tile-Based game. I am facing heavy performance problems with my code to find a path from the start to the target tile, so I am asking myself if this is caused by the way I am handling it or actually by missing computation power (my CPU is pretty good).

I will keep it simple and short:
The tiles are set up like this but eventually will become more complex:

1024×1024 770 Bytes

My idea was to just check all the neighbouring tiles of the start tile and then all their neighbouring tiles, and so on, until I find the target tile. Each branch gets the distance assigned it took to reach the target and finally the fastest one of them is chosen. Branches, where the target was found, are skipped further on. In code something like:

foreach (Neighbour1 in StartTile)
{
if  (Neighbour1 == target) AddPath to list, continue with next neighbour
else
{
foreach (Neighbour2 in Neighbour1)
{
if (Neighbour2 == target) Add Path to list, continue with next neighbour
else
{
......And so on.......
}
}
}
}

This construction of code leads to a 1-second delay whenever it is executed. I know that there are complex algorithms and much more sophisticated ways of doing this. My question is simply: is the problem just my code specifically or my general approach itself?

Hope someone has a tip and everything is understandable.

2

You’re effectively searching ALL possible paths and then picking the shortest. This is like the most ineffective pathfinding algorithm.

A* is the usual go to node based pathing algorithm (your tile map is a node based, where each tile is a node).

There’s tons of implementations of A* out there, packages you can get for Unity, or even examples of how to roll your own in Unity.

Here is my personal self-rolled version:

(note - you can ignore the code in the region called ISteppingResolver Interface… it’s just an alternate version used for spreading a calculation over multiple frames if threading isn’t a possibility).

3

It’s something!

But seriously, I actually own A* Pathfinding Pro. I just thought that I would prefer to not use too many third-party assets. I knew that my solution is extremely inefficient. I assume I just underestimated the exponential effects and thought it would be fine for such a small grid.

Thanks for the tip, anyway!

4

You can roll your own A*, it’s an algorithm that existed for a long time predating most video games (1968).

So you don’t have to use 3rd party to get A*. You just have to use A*.

There’s even an earlier (1956) version that is less efficient (though more than yours), and that’s Dijkstra’s algorithm:
https://en.wikipedia.org/wiki/Dijkstra’s_algorithm

It’s useful because A* basically builds on Dijkstra. So if you start with one you can use it to help understand the second.

I also implemented Dijkstra here: