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.

Simple genetic algorithm

Today I took a few minutes to do a simple little genetic algorithm that works toward a given statement. This is a fairly simple concept where the program randomly reassigns the value of a random set of indexes repeatedly until the goal is met. I first started with a simple non-directed algorithm where a string is constructed by indiscriminately and randomly reassigning a set of indexes in the hopes that it would eventually reach the goal statement. Well needless to say this worked wonderfully, with the exception that it took forever(I let it run for about 2 hours before becoming impatient). I didn't much feel like waiting for possibly days to see if it would even come close. So I decided to add direction. to do this I simply added a check to see if the current state in any way matched the goal state and if so, the indexes of the 2 strings that matched wouldn't be altered. The result of doing this was instead of it taking more than the 2 hours, the algorithm would instead finish within a few seconds.

What is a genetic algorithm:

A genetic algorithm is based on the concept of evolutionary biology where a sequence is randomly mutated, either for better or worse. For example let's say that you have a binary string of 0's and 1's like so:

1010001010011101

you will randomly pick a number of indexes within the string to be flipped. So let's say that we only want to mutate a single value, we select a random index between 0 and 15 for this string and mutate it. In this scenario mutating is going to be defined as randomly selecting a random value to reassign that index to. Since we are working with binary, the available set of values for mutation is {0, 1}. So let's say we randomly choose index 3 and when we randomly select a value to replace it with we get a 1. When we do this the original string of

1010001010011101 -> 1011001010011101

As I said earlier, this method on its own lacks direction and it may take literally forever to reach your goal state. So to make the path a little shorter, you can check the current state against the goal and see if the index you have randomly chosen to modify matches the same index within your goal state and if so then you don't make any changes. This is a bit of a short cut way of saying that you already know that switching the given index will result in a state that is further from the goal state than the current state, thus behaving something like a tree pruning algorithm. This was a fun little exercise for me to do, and I hope you enjoy it too. You can find the code here.

Web UI development principles for simplified testing

Today's topic is not only simple but quite important. While some projects have a dedicated UI developer that will make sure that templates are kept in pristine condition, there are many that don't. Instead the developers are left to create the UI and all it's niceties. As a developer I can say we generally aren't all that great at making things look pretty, but we are capable of setting up the necessities. With that said, there are some very basic things that should be kept in mind during UI development so that later on, testing is simple to create and maintain.

1. HTML tag ID's:

Ask any person who has ever created an html template, and they will tell you just how important it is to use IDs for things that appear only once. For example lets say you have a page with 2 tables, it is very important that you give each of those tables a unique id that can be used to identify them. The syntax is simple and it makes finding these elements easier when creating tests for the UI, by making the information simple to find in the DOM.

2. Don't repeat yourself(DRY)

When creating UI's it can be easy to duct tape in something simple, but it might not be the best choice. I recently had the experience of working on a project where the developers would regularly make something simple into multiple components, when one would have been cleaner and easier to test. The problem with trying to test such a system is that you are then exposed to multiple components with different ID's, names, content, etc. So when you interact with the component, you find yourself having to figure out which one is now displayed so that you can get your test to pass. Mind you that having multiple components in general is bad practice, so don't do it. Find a way to simplify your work so that you don't repeat yourself, and you'll find a project that is much easier to test and maintain.

3. Don't reinvent the wheel

If there is a simple way to do something that fits your needs, do it that way. Don't waste your time recreating it in some new way. When you are dealing with HTML for example, use a select/option like the rest of us. Whatever you do, don't go crazy and decide that you are going make drop down boxes with a series of divs. Seriously, don't recreate standard features in overly complex ways unless you are working on something so mind blowing that the standard doesn't fit your needs.

4. Use a templating framework

Whatever you do, don't use a library that is "amazing" because it offers UI development for programmers. This is just a fancy way of saying you'll do 10 times the work to get a simple template laid out than you would have if you had just used a templating framework that relies on HTML. You'll also spend 10 times more time trying to figure out how to add an ID to that one tag should you find you need to.


That's really about it. I may add to this list in the future, but these are the things where I've seen non UI developers go wrong the most. I do realize these are obviously pretty standard practice in most development and probably shouldn't need saying, but I did it anyway. Just remember, if you are a developer on a team, someone else is likely going to be testing your code. So construct your UI and code like the next person testing it is a violent psychopath that knows where you live.

Implementing a simple factory

Ok so let's talk design patterns for a minute. To be specific the infamous factory. There is no doubt that the factory is quite handy, but what is it used for? Well, there arises a point when you are building an application and realize that you have a lot of similarly classified objects that need to be instantiated at some point in your code, but you don't know which one should be instantiated until the user or some other function implements it. Well a factory can allow you to instantiate those objects without worrying a whole lot about their actual implementation. Which is cool because then your objects become compliant with open-closed principle. But how exactly does this magical pattern work? Let's assume you have you have a system designed for selling different vehicles. Your company currently has objects set up for the busses, sedan and motorcycles it sells.


    public class Bus{
      public Bus(){
        //instantiation code here
      }

      //..
    }

    public class Sedan{
      public Sedan(){
        //instantiation code here
      }

      //..
    }

    public class Motorcycle{
      public Motorcycle(){
        //instantiation code here
      }

      //..
    }


This is great except then you realize that you are calling these individually throughout the business logic, meaning that each object is coupled to it's instantiating class pretty solidly. Sadly this makes your code fairly brittle and you end eventually updating code in dozens of locations when your requirements change. We've all been there and it isn't fun. What you want instead is to be able to replace all those areas with a more simple, more flexible solution that will allow you to get the object you want without necessarily having to be overly concerned about the implementation. So in swoops an interface to allow you to create a level of abstraction between you and the objects.



   public interface Vehicle{
     public String getVehicle();
   }


This means that each of your objects now look like the following.


    public class Bus extends Vehicle{
      public Bus(){
        //instantiation code here
      }

      public String getVehicle(){
        return "If you don't know what a bus is, look it up";
      }
      //..
    }

    public class Sedan extends Vehicle{
      public Sedan(){
        //instantiation code here
      }

      public String getVehicle(){
        return "A sedan is a car with 4 doors...sometimes";
      }
      //..
    }

    public class Motorcycle extends Vehicle{
      public Motorcycle(){
        //instantiation code here
      }

      public String getVehicle(){
        return "A motorcycle has 2 wheels.";
      }
      //..
    }


As you can see all you are doing is returning a String representation of the class name. Now that you are to this point you see that implementing these is just as easy as creating a factory using an class that will allow you to choose between them. So you code it up and get something like the following.



  public class VehicleFactory{
    public Vehicle createVehicle(String type){
      Vehicle vehicle = null;
      if( type.equals("bus"))
        vehicle = new Bus();
      else if( type.equals("sedan"))
        vehicle = new Sedan();
      else if( type.equals("motorcycle"))
        vehicle = new Motorcycle();

      return vehicle;
    }
  }


Now that we have everything in place let's make sure everything works.



public class FactoryMain {

public static void main(String[] argv){
Vehicle vehicle = VehicleFactory.createVehicle("bus");
System.out.println(vehicle.getVehicle());

Vehicle vehicle2 = VehicleFactory.createVehicle("sedan");
System.out.println(vehicle2.getVehicle());

Vehicle vehicle3 = VehicleFactory.createVehicle("motorcycle");
System.out.println(vehicle3.getVehicle());
}
}


There you go, now you have a factory implementation for your vehicles and all is right in the world.

Lists: A brief explanation

So recently I've been asked to try to explain a series of topics needed to have a decent understanding of programming and its constructs. I don't exactly consider myself an expert in all that is programming and this will likely challenge me as well. So where do we start? I thought I'd jump right in and go with Lists, hence the title, surprising right?

So what are lists? I'm sure that you have used lists for a number of things in your everyday life, such as grocery lists, or task lists, or Christmas lists. So to sum it up lists as you know are just a collection of items that can be either ordered or not. At this point if you have a basic understaning of programming you are likely thinking. Well that sounds like an array. And you would be correct. A list and an array are one in the same thing when we talk about programming. Now there are other types of lists that aren't arrays. This brings up so to our actual topic of today.

In the "lists" world we have a few different types of lists that exists. Today I am going to focus on linked lists. In the world of linked lists there are 3 types, single link, double link and circular. Circular isn't exactly a list type as much as a variation on single and double link lists. All this means is that the last element (tail node) is connected to the first element(head node) in such a way that when you attempt to access an element beyond the end of the list that you start back at the beginning. If the list is a circular double link list, then you are also permitted to access the end of the list by attempting to access an element before the start of the list. So lets see what this means exactly.

Single Linked Lists
A single link linked list is a list in which you can iterate from beginning to end and only in that direction. Each node is connected to the next node through a pointer. Lets take a look at an example. Lets say that we have a 3 element(A,B,and C) single linked list that is ordered. You end up with the following list.

A -> B -> C

You can see here that you start at node A and end with node C. This is very important, since unlike arrays, a linked list cannot begin iterating from arbitrary points within the list. They must start with the head or tail node. Unfortunately unless you are looking for value in the tail node in a single linked list, starting there is a bit pointless since you can't iterate backwards through the list. Now I'm sure you are thinking, 'what about circular linked lists? Certainly those would make the end node a reasonable place to start?'. While, you can start with the tail node in a circular single linked list, if you aren't looking for the end node it makes more sense to start with the head node and save yourself an iteration.

Now what if we want the ability to move backwards through the list? Yup, you guessed it, double linked lists. Now this is gonna be hard to understand so bear with me, we need to make sure that the nodes connect to the node before them. This would be represented with a similar graph to the previous example except it now goes in 2 directions.

A <-> B <-> C

That's insane right? Also notice here that we can start at the head or tail nodes and iterate over the list. We can still only start at the head or tail nodes, but now the list can be iterated over in 2 directions.

So now we understand the basic concept of the linked list. But how in the world do we translate that into code? Well first of all, the best way I know of to translate this is by using and Object Oriented approach. I'm sure its possible to accomplish using a non object oriented approach but I'm not sure it would look nearly as nice. For this example I will go with how to implement this in Java. If that's not your flavor worry not, for I will be adding implementations of this in other languages later on. Now for the linked list that in this example we are going to have it hold integer values to keep it simple. There are better ways to do this but those topics are beyond the scope of this post.

Java


class Node{
private Node prev;
private Node next;
private int val;

public Node(Node prev, Node next, int value){
this.prev = prev;
this.next = next;
this.val = value;
}

public void setValue(int value){
this.val = value;
}

public int getValue(){
return this.val;
}

public void setNext(Node node){
this.next = node;
}

public Node getNext(){
return this.next;
}

public void setPrev(Node node){
this.prev = node;
}

public Node getPrev(Node node){
return this.prev;
}

public void remove(){
this.prev.setNext(this.next);
this.next.setPrev(this.prev);
}

public void addAfter(Node node){
this.prev = node;
this.next = node.getNext();
this.prev.setNext(this);
}
}


Perl Sessions...filling in the gaps

I recently had to utilize the perl CGI::Session module and found the documentation a little odd and somewhat vague in certain areas. So for my sanity and hopefully anyone else that runs across this, I'm going to take a moment to explain how to use this module so that you too can get up and running quick.

Sessions...How do they work?

Sessions are fairly basic, the goal is to store some information on the client that will allow us to work around the Internet being stateless. Now there are only a couple ways to do this. The first way is the most common method of storing the user's session id in a cookie. But what if the user doesn't accept cookies? Well that would make the first method a bit hard now wouldn't it? Luckily we can always fall back on storing the user's session id in a hidden variable within the page. The Session module handles sessions in this way as well by defaulting to using cookies. Now I'm sure you are thinking, well great so you have an id for the user's session. But how do we use it? At this point you need to track the user on the server. To do this you can either:

• save the session data to a file
  or
• store the session data in a database table with the session id as the primary key.
  

Getting started:

Before we can use the Sessions module we need to make sure we have included both the CGI and the CGI::Session module. We also need an instance of the CGI object. The code to this is as follows:

use CGI qw/:standard/; # for parsing form data
use CGI::Session qw/-ip-match/;
my $cgi = new CGI();

Now that we have added the modules we can start a session. First, we usually want to make sure that the user doesn't already have a session open. To do this we use the following.

my $session_id = $cgi->cookie('session_name') || $cgi->param('session_name') || undef;

You see in the first thing we check is if there is a cookie in place with the name assigned to identify it with $cgi->cookie('session_name'). If there isn't one then we may want to check to make sure that there wasn't a hidden variable passed to the server with the session_id. Now that we know that we have the session_id set we can create a new session.

my $session = new CGI::Session("driver:File", $session_id, {Directory=>'/tmp'});

Here we are passing a few parameters to the Session() function.

1. Driver : This parameter is used to define how the data will be stored. In this instance the data will be stored in a file.
   
2. Session ID : The users session id. If the user already has a session open then this will use that users session. If it doesn't however, then the module will start a new session.
   
3. Directory : This is used to specify what directory the module should save sessions to.

There is a lot more to the module than what I have explained here. You can get the full CPAN documentation here .