I recently needed a path finding algorithm for a prototype I was making. I found a couple of good plugins in Unity store, but they either had some setbacks or were super expensive.

So i thought i will pull in some snippets of code from couple of free plugins and make my own. So heres how it ended up.

So what is PathFinding ?

Pathfinding is finding of the shortest route between two points. It is a more practical variant on solving mazes.

There are different types of path finding algorithms, of which Dijkstra’s & AStar algorithm being quite famous and mostly used. I will be going through basics of these algorithms.

Dijkstra’s Algorithm

Dijkstra’s algorithm is basically about finding the shorting path between Node A and B

We calculate the cost ( based on distance & complexity ) to move from Node A to every other node. The lesser the cost, the easier it so to use that route. This way they will also find multiple routes between A to B with multiple costs. We will filter out the route with least cost. The essentially the gist of it.

If you want to dig more into it:

A* ( A Star ) Algorithm

A* is a variation of Dijkstra’s algorithm designed to make it faster. Dijkstra’s algorithm tries to find cost for every node from A ( or starting node ). This can be time consuming and espensive.

Eg: if you are trying to find a path from new york to mexico, it is meaning less to find costs of all path which are leading through canada.

So A* uses heuristic distance to make this faster. heuristic distance is computed using the physical distance of the nodes. This is different w.c.t the cost we used in Dijkstra’s algorithm.

So instead of calculating costs for all Nodes, we calculate for nodes which are closer to B. If we find any node with Heuristic distance higher, we will completely ignore that route. Thus, the computation cost is significantly lower.

If you want to dig more into it:

Note: that I had given only a gist on the topic and there is a lot more to it if you interested.

QPathFinder

QPathFinder is the name of the plugin i have developed for Unity 3D. It uses A* algorithm to find the shortest path across the game. It supports for 2D games as well as 3D games with varying terrian heights.

Find my PathFinding algorithm at Unity3D asset store here