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(R) and find all possible moves that it can make. In this example to keep things simple 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
frontier.push(start);

//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
visited.push(node);

//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.

How to implement a Node for use in a graph

Today I'd like to discuss a very basic construct called Node which is the basic building block of graphs, as well as a few other more advanced data structures. In future posts I'll discuss in more depth what data structures it is used in as well as how and why one would use them. For today though, I'm just going to introduce the concept of a graph and what a node actually is, along with a little bit of code to demonstrate.

What is a Node?

A node is an individual object that can be connected to one or more other nodes. If you are familiar with social networking such as facebook, then your profile is a node within the network and each of your friends are their own nodes. You are connected to your friends and we call those connections edges between nodes in the network, and the network is often referred to as a graph. 

This is a fairly simple concept, so let's take a look at what a node might look like when put into code. For this example I've chosen javascript, however you should be able to do this in just about any language.

First off, we need a node object so that it can encapsulate and store it's value as well as any connections to other nodes. To do this we'll give the node it's own node value and we'll also create a list to store any connections that might exist for a given node. The code for this looks like the following.

function Node(node){

    this.node = node;

    this.connections = [];

}

Now that we have a basic node object set up, we need some functions to help access the values. In Javascript adding in the functions isn't really necessary since all values of the object can be accessed via dot notation. For the sake of a little clarity as well as anyone looking to do this in other languages that may be a little more strict, we'll add methods to the Node class that will return the instance variable values. 

var this.getNode = function(){

    return this.node;

}

var this.getConnections = function(){
    return this.connections;
}

This is all great, but how do we create connections? To do that we simply need to add a function to the class that will take a node as argument and push it onto the connections array. But since we will be adding connections, we should probably also enable removing connections. So we'll implement both of these like so:

var this.addConnection = function(node){

    this.connections.push(node);

}

var this.removeConnection = function(node){

    var idx = connections.indexOf(node);

    connections.splice(idx, 1);

}

That's all there is to it. So now our Node class in it's entirety should look like the following:

function Node(obj){

    this.node = obj;

    this.connections = [];

    var this.getNode = function(){

      return this.node;

    }

    var this.getConnections = function(){
      return this.connections;
    }

    var this.addConnection = function(node){

        this.connections.push(node);

    }

    var this.removeConnection = function(node){

      var idx = connections.indexOf(node);

      connections.splice(idx, 1);

    }

}

Now we have a fully functional node class that can have a connection to any number of nodes.