Monday, August 18, 2014

Adventures in Path finding: general algorithm

In my last post I discussed what nodes are and how you could go about implementing them. In this post I'll be going over how to nodes fit into the whole problem of path finding. There are actually a number of algorithms that can be used for path finding, however this post will cover just the basics on implementing the basic algorithm.

The algorithm:

In any path finding algorithm there is a basic structure used. The goal is to find a path from the current state to a given goal state. In order to do this let's imagine we have a robot that inhabits a cell in a table and needs to get to some other cell that we have designated as the goal like so.

R . .
. . .
. . G

Now in order to find the path we must start with making a move of some sort. So we examine the current cell for the robot(denoted as 'R' above) and find all possible moves that it can make. In this example to keep things simple the we'll allow the robot to move in only 4 directions(up, down, left, right). To get started we'll use an array that is called the frontier, which is intended to store the nodes that are potential moves but haven't yet been expanded. Since the starting position hasn't been expanded it belongs on the frontier. We'll also use another array called 'visited' that will hold all nodes that have been expanded already.

Now that the starting position has been added to the frontier, we will remove it from the frontier and place it into the visited array as well as retrieving all possible moves that the robot can make. Each of the possible moves is then added to the frontier if it doesn't currently exist within either the frontier or visited arrays. So far so good, but where do the nodes come in? Well in order to keep track of the path we will create a new node for every position in the table and link it to the node currently being expanded. In order to track how the robot gets to the new position/node I added a field called 'last' to the Node object. Now when a new node is added to the frontier the node that the robot came from is added to the new node by setting last to the old node.

After doing all of this we just rinse and repeat. Now that the start node has been expanded and produced 2 new nodes to be expanded, we pull a new node off of the frontier, place it into visited and expand. Once again only adding nodes to the frontier that don't yet exist in either the frontier or the visited array, and so on and so fourth until the goal state is reached. Once the goal state is reached the algorithm has found a path and all that is left is to trace the path back to the start and return that path. Since the nodes have been keeping track of where they came from, all that needs to be done is to grab the value of 'last' from each node and add it to an array, pushing each last node into the beginning of the array such that the first node put into the array will be the last node examined by the robot. The code looks something like the following.

                var goal_x = goal_y = 2;
var start = new Node(new Cell(0,0));
var goal = new Node(new Cell(goal_x, goal_y));
var nodes = null;

var visited = [];
var frontier = [];

var node = start;

//add start node to frontier

//do while the current node isn't the same as the goal node
        while(!areNodesEqual(node, goal)){

//if frontier isn't empty then get first entry
                if(frontier.length > 0){
node = frontier.shift();
//add the current node to the list of visited nodes

//add all squares reachable from current node to frontier list
this.addAllReachableNodesToFrontier(board, node, frontier, visited);

return node;

That's all there is to it. Granted the explanation is a lot less wordy than the implementation(code coming soon). I would like to point out that while this will get the job done, it isn't very efficient, and may expand almost every node before finding a solution. On top of it's obvious inefficiency this algorithm also doesn't guarantee that the path returned will be the shortest. In the example above this won't be obvious, however if you were to increase the size of the table to be traversed as well as adding in obstacles(cells that can't be occupied by the robot) then it would become much more obvious that the robot doesn't always choose the shortest path. In future posts I'll be discussing other algorithms that can be used to improve efficiency by reducing how many nodes have to be examined and expanded in order to find a solution.

No comments:

Post a Comment