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

Monday, August 11, 2014

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.

Wednesday, February 5, 2014

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.