Path Finding Tutorial

Create the Grid

The first thing you need to do is create the grid. This can be done by creating a GridGraph object, given an object that supports the GridSampler interface. The GridGraph queries the GridSampler for node and edge data between grid squares.

MyGrid grid = new MyGrid(...);
GridGraph graph = new GridGraph(grid);

Create the Path Finder

The next thing you need to do is create the path finder object. In this example, we will use the A* algorithm (best-first search using a heuristic estimate for the cost to the goal). The path finder interface and implementing classes take two generic type parameters. The first is the node type and the second is the edge type. Here we aren’t going to need any extra data, so we are using the GridNode and GridEdge types directly.

PathFinder search = new ASearch(Heuristic);

Defined elsewhere in the class is the heuristic which returns the euclidean distance from the current node to the goal. Keep in mind that for most search algorithms to function correctly, this heuristic must be less than or equal to the actual cost to the goal. The edge costs should be at least the same as the distance between the grid cells for this heuristic to work properly.

float Heuristic(GridNode node, GridNode goal)
{
    return new Vector3(goal.X - node.X, goal.Y - node.Y, 0f).magnitude;
}

Now you may simply execute a search on this graph using the path finder you have created. In this example, we will search from the start grid cell at (0, 0) to the goal grid cell at (10, 15). Also note that the Path class takes the same two generic types parameters as the path finder.

Path path = search.Search(graph.GetNode(0, 0), graph.GetNode(10, 15));

Now you have a path object which you can use directly or feed into the coherent path follower.

  1. No comments yet.
(will not be published)
*

Switch to our mobile site