Gridpath is a MIT licensed multithreaded 2D implementation of A*
Gridpath is a MIT licensed multithreaded 2D implementation of A* aimed at 2D games with just an X,Y axis in Unity3D. It is meant to be small, simple enough that you could modify yourself, and 2D centric. It is reasonably fast and not a ton of code. It also includes a visual debugger and an example scene containing most of the math needed to setup an isometric scene in Unity3D.
There is a working example in the project in the Example folder:
A couple of notes about the demo
Add a Pathfinder component to an object in your scene
Access the pathfinder somewhere in the scene and configure the grid like so:
Pathfinder.Instance.Init(20, 20, GridGraph.DiagonalOptions.DiagonalsWithoutCornerCutting, 4);
This will create a 20,20 grid with 4 threads, allowing diagonals, but not allowing the entities to cut corners. For diagonals several options are supported, they are:
You can now calculate paths like this:
// Create this method or one like it on your MonoBehaviour
public void OnPathComplete(Path p)
{
foreach (var error in p.Errors)
{
Debug.LogWarning("The path had the error: " + error);
}
if (p.Found)
{
Debug.Log("Received path!");
_path = p;
_pathIndex = 0;
}
else
{
Debug.LogWarning("No path to that exists...");
}
}
Now call the pathfinder, (Start, or update or wherever)
PathFinder.Instance.StartPath(_myPosition.X, _myPosition.Y, _targetPosition.X, _targetPosition.Y, OnPathComplete);
Your method will be executed in the main unity thread whenever the path calculation is complete.
You can now iterate the path, and move your object to the path nodes as usual: First we'll declare a Move coroutine:
IEnumerator Move()
{
while (true)
{
if (_path != null && _pathIndex < _path.Nodes.Count)
{
var nextNode = _path.Nodes[_pathIndex];
_myPosition.X = nextNode.X;
_myPosition.Y = nextNode.Y;
_pathIndex++;
}
yield return new WaitForSeconds(1f);
}
}
Then we will Activate that in the start method of our MonoBehaviour
void Start()
{
StartCoroutine(Move());
}
Set tile at 0,0 to false:
Pathfinder.Instance.Grid.SetWalkable(0,0,false)
Set weight on the tile at 0,0 to 50:
Pathfinder.Instance.Grid.SetWeight(0,0,50);
If you want, you can use the pathfinder in your own threads, or with your own manager by simply creating the grid yoursef, and passing it to a pathsolver. This wont be multithreaded(unless you do it yourself), and you wont get the debugger etc, but it might be desirable in some cases, this is all that is required:
GridGraph graph = new GridGraph(20,20,GridGraph.DiagonalSetting.DiagonalsWithoutCornerCutting);
graph.SetWalkable(1,0,false);
graph.SetWalkable(1,2,false);
graph.SetWalkable(1,3,false);
PathSolver solver = new PathSolver();
solver.FindPath(startX, startY, endX, endY, graph);
Astute readers may not that the basic API calls bear some semblance to Aran Granberg's A* implementation this is because I wrote this project as a 2D replacment for for my game as I needed something a bit more 2D friendly, so a few of the API methods bear a bit of a semblance. Though they're quite a bit shorter and simpler under the hood. If you need a more complete solution out of the box or a 3D implmentation, you might consider checking out his project.
Clint Bellanger's artice on isometic math
Patrick Lester article on A* pathfinding
BlueRaja Concurrent min-Priority Queue implementation
email: corymichaellee at gmail.com