Archive for the ‘Algorithms’ Category

Astar Graph Search – Variable Costs

Tuesday, May 8th, 2012

I’ve been working on updating my A* Graph Search Algorithm (A* on Github) and toying with the idea of adding variable costs to the grid, also known as weighted paths.

I opened an issue to add weighting to graph nodes a while ago, but am a little stuck on the implementation details. My initial thought was to change the semantics of the graph. Right now, here is a sample graph:

 
var GraphNodeType = { 
    OPEN: 0, 
    WALL: 1 
};
 
// 0 represents an open node, 1 represents a wall 
var graph = new Graph([
    [0,0,0,0],
    [1,0,0,1],
    [1,1,0,0]
]);

My initial plan for adding weighting was something like this:

 
var GraphNodeType = { 
    WALL: 0,
};
 
// Anything > 0 represents the cost to travel to that node, 0 represents a wall
var graph = new Graph([
    [2,1,3,4],
    [0,1,1,0],
    [0,0,3,10]
]);

One major issue with that is that it breaks backwards compatibility with the plugin. A user, spellfork, on the Github issue came up with a neat solution, basically passing in two separate arrays to the graph function, where one represents the “obstacle map” (walls), and the second represents the “terrain map” (costs).

 
// First array: 0 represents an open node, 1 represents a wall 
// Second array: movement costs are represented by numeric value 
var graph = new Graph([
    [0,0,0,0],
    [1,0,0,1],
    [1,1,0,0]
],[
    [2,1,3,4],
    [0,1,1,0],
    [0,0,3,10]
]);

This is nice because the terrain map is optional, but not as nice if you need to do a lot of work to generate the two separate maps.

Maybe there is a better solution that I am not thinking of? Any ideas about the best way to implement this? Drop a comment here or over in the Github issue to help get this implemented!

Inverse Rectangle Intersection In JavaScript

Monday, February 27th, 2012

Given a parent rectangle and a collection of children rectangles on a 2D plane, how do you find a collection of non-overlapping rectangles that cover the inverse of the original set?

For instance, given the container rectangle along with the set [A, B] -> we want an output similar to [1, 2, 3, 4, 5].

         +----------------------------------------------------------------+
         |                                                                |
         |                                                                |
         |       +------------------+        +--------------------+       |
         |       |                  |        |                    |       |
         |       |                  |        |                    |       |
         |       |        A         |        |        B           |       |
         |       |                  |        |                    |       |
         |       |                  |        |                    |       |
         |       |                  |        |                    |       |
         |       +------------------+        +--------------------+       |
         |                                                                |
         |                                                                |
         |                                                                |
         |                                                                |
         |                                                                |
         +----------------------------------------------------------------+


         +----------------------------------------------------------------+
         |                                                                |
         |                               1                                |
         +-------+------------------+--------+--------------------+-------+
         |       |                  |        |                    |       |
         |       |                  |        |                    |       |
         |   2   |                  |   3    |                    |       |
         |       |                  |        |                    |   4   |
         |       |                  |        |                    |       |
         |       |                  |        |                    |       |
         +-------+------------------+--------+--------------------+-------+
         |                                                                |
         |                                                                |
         |                              5                                 |
         |                                                                |
         |                                                                |
         +----------------------------------------------------------------+

Solution

Enter the inverse-intersection JavaScript project. It is a kind of micro library. No dependancies, just the math required to solve this problem!

You can grab the JavaScript file from Github.

wordsolver.js

Thursday, February 10th, 2011

I was playing around with unscrambling words recently, and decided to implement a solver in JavaScript. I called it wordsolver.js.

Demo

There is a wordsolver demo on my site. Try typing in URESMTA or something to see all the words that get unscrambled.

Code

All code can be found in the wordsolver repository on github. In particular, here is the file that does all the heavy lifting. It is all available under the MIT license.

How does it perform?

Smoother than I expected it to. The load time for the dictionaries can be pretty slow (they are anywhere from 1.7MB to 2.6MB depending on the dictionary), but once it loads, it finds words pretty fast and tries to cache results. Warning: it will probably crash an iPhone while trying to load the dictionary array into memory

A* Search Algorithm in JavaScript (Updated)

Wednesday, September 15th, 2010

See the updated pathfinding demo of A* Search in JavaScript.
Get all the updated source code from github.

When I first wrote the A* Search in JavaScript article I knew there were some things that could make the pathfinding faster. I didn’t know realize that it would be this much faster. Here are my (totally unscientific) results:

Observed Speed of A* Search on Chrome 6.0.472.55 on OS X
# rows original updated
100 700-2500ms (wildly variant) 5-10ms
50 160ms 5-10ms
15 0-5ms 0-2ms

Here’s What Changed

I got some feedback about using a heap or a priority queue instead of a list (basically keep the open items in sorted order the whole time so we can just grab it off of the top instead of needing to traverse the whole list every time. As predicted, this makes a huge difference as the number of nodes goes up, but may actually be a little slower for a very low number of nodes because of the overhead of keeping them sorted. I found a binary heap implementation from http://eloquentjavascript.net/appendix2.html and put it in.

Also, I realized two places that I was traversing lists that could be avoided. Getting rid of extra traversals (especially ones that ran inside nested loops) made a very big difference in performance.

  1. I was keeping all of the nodes inside a closed list, which required traversing that list every time to see if it was already closed. This was replaced with a simple bit on the node to track if it had been closed.
  2. I was checking to see if a node was visited already by seeing if it was in the open list. This was replaced by a simple bit to see if it had been visited.

Old Pseudocode

  push startNode onto openList
  while(openList is not empty) {
     currentNode = find lowest f in openList
     if currentNode is final, return the successful path
     push currentNode onto closedList and remove from openList
     foreach neighbor of currentNode {
         if neighbor is not in openList {
                save g, h, and f then save the current parent
                add neighbor to openList
         }
         if neighbor is in openList but the current g is better than previous g {
                 save g and f, then save the current parent
         }
     }

Updated Pseudocode (* lines have changed)

  * push startNode onto openHeap
  while(openList is not empty) {
     * currentNode = pop from openHeap
     if currentNode is final, return the successful path
     * set currentNode as closed
     foreach neighbor of currentNode {
         * if neighbor is not set visited {
                * save g, h, and f then save the current parent and set visited
                * add neighbor to openHeap
         }
         if neighbor is in openList but the current g is better than previous g {
                 save g and f, then save the current parent
                 * reset position in openHeap (since f changed) 
         }
     }

I also did some general cleanup, getting rid of dependancies on the demo, and I split out the code so that the search function can be used standalone (taking a two dimensional array as a parameter), so if someone just wanted the optimized astar search, you could call it like so:

<script type='text/javascript' src='astar.js'></script>
<script type='text/javascript'>
var graph = new Graph([
	[1,1,1,1], // 1 is open, 0 is wall
	[0,1,1,0],
	[0,0,1,1]
]);
var start = graph.nodes[0][0];
var end = graph.nodes[1][2];
var result = astar.search(graph.nodes, start, end);
// result is an array containing the shortest path
</script>

What Could Make It Better?

Last time I posted about this, I got a lot of feedback (mostly about how slow it was). If anyone reading this knows of anything that could make it better, let me know.

Source Code (direct links)

astar.js |
graph.js |
demo.js |
astar-list.js (old implementation with open and closed values swapped)

A* Search Algorithm in JavaScript

Wednesday, June 3rd, 2009

Note that this code has been updated. I have an updated blog post detailing what changed. The new source code is available at https://github.com/bgrins/javascript-astar, and the code as of the original post is still available here: https://github.com/bgrins/javascript-astar/tree/0.0.1/original-implementation

View the online demo

I first implemented the A* algorithm for a research group I was in through school (Computer Graphics and Image Understanding). A* is a best-first, graph search algorithm. Some basic information can be found on the Wikipedia page for A* and the external links contained in it. Please refer to that page for general reference about the algorithm, I will simply explain in my own words how it works and how I got it working.

A* algorithm in JavaScript

A* algorithm in JavaScript

Why JavaScript?

Because it was easy to deploy!

Since I know JavaScript pretty well, and most of the examples you can find are in C, Java or a similar language that you cannot run without downloading source code or executables, I thought it would be a good idea to program it on an html page. This way, people could see what was going on and view the source very easily by using the online demo.

My hope was to build a page that could be extended with other search algorithms by separating the UI code (that generates a graph with walls and animates the path that is determined by an algorithm), and the algorithm that finds the path. Maybe I will get around to plugging in some more algorithms sometime and making it into a little resource for graph search algorithms.

How?

search.html

Just a basic html file that includes jQuery, the excellent JavaScript library, main.css, graph.js, and astar.js. Also, I have a JavaScript block that initializes the page.

graph.js

The point of this file is to build the graph, call the search function, and animate the results after the search has returned. It also has an option to show the debugging information created by the search algorithm. I won’t get too into the code here, since it distracts from the search algorithm.

Please take a look at it, be aware that there are some improvements I would make if I was to rewrite this today. There are some performance issues that could be addressed, and It modifies the Array.prototype to add on specific methods (findGraphNode and removeGraphNode) for search algorithms, which may not be ideal for bigger projects. For this little page, I’m not too worried about it, but if I do get around to adding in more algorithms, I will probably improve this code.

astar.js

This is the actual implementation of the algorithm. I will do my best to explain what is going on, but feel free to just look at the source of the example, or just download astar.js.

There are three functions that we keep track of for nodes that we look at:

  • g(x): The total cost of getting to that node (pretty straightforward). If we reach a node for the first time or reach a node in less time than it currently took, then update the g(x) to the cost to reach this node.
  • h(x): The estimated time to reach the finish from the current node. This is also called a heuristic. We online need to update this if it is not set already, since the distance to the finish will not change even if the path we took to arrive at a node changes. Note: There are many different ways to guess how far you are from the end, I use the Manhattan distance in this implementation.
  • f(x): Simply g(x) + h(x). The lower the f(x), the better. Think about it like this: the best node is one that takes the least total amount of time to arrive at and to get to the end. So, a node that took only 1 step to arrive at and 5 to get to the end is more ideal than one that took 10 to arrive and and only 1 to get to the end.

Here is some high level pseudocode of what is happening in the algorithm. Also see the Wikipedia pseudocode for another example.

  push startNode onto openList
  while(openList is not empty) {
     currentNode = find lowest f in openList
     if currentNode is final, return the successful path
     push currentNode onto closedList and remove from openList
     foreach neighbor of currentNode {
         if neighbor is not in openList {
                save g, h, and f then save the current parent
                add neighbor to openList
         }
         if neighbor is in openList but the current g is better than previous g {
                 save g and f, then save the current parent
         }
     }

Here is the JavaScript for the list implementation:

 
var astar = {
	init: function(grid) {
		for(var x = 0; x < grid.length; x++) {
			for(var y = 0; y < grid[x].length; y++) {
				grid[x][y].f = 0;
				grid[x][y].g = 0;
				grid[x][y].h = 0;
				grid[x][y].debug = "";
				grid[x][y].parent = null;
			}	
		}
	},
	search: function(grid, start, end) {
		astar.init(grid);
 
		var openList   = [];
		var closedList = [];
		openList.push(start);
 
		while(openList.length > 0) {
 
			// Grab the lowest f(x) to process next
			var lowInd = 0;
			for(var i=0; i<openList.length; i++) {
				if(openList[i].f < openList[lowInd].f) { lowInd = i; }
			}
			var currentNode = openList[lowInd];
 
			// End case -- result has been found, return the traced path
			if(currentNode.pos == end.pos) {
				var curr = currentNode;
				var ret = [];
				while(curr.parent) {
					ret.push(curr);
					curr = curr.parent;
				}
				return ret.reverse();
			}
 
			// Normal case -- move currentNode from open to closed, process each of its neighbors
			openList.removeGraphNode(currentNode);
			closedList.push(currentNode);
			var neighbors = astar.neighbors(grid, currentNode);
 
			for(var i=0; i<neighbors.length;i++) {
				var neighbor = neighbors[i];
				if(closedList.findGraphNode(neighbor) || neighbor.isWall()) {
					// not a valid node to process, skip to next neighbor
					continue;
				}
 
				// g score is the shortest distance from start to current node, we need to check if
				//	 the path we have arrived at this neighbor is the shortest one we have seen yet
				var gScore = currentNode.g + 1; // 1 is the distance from a node to it's neighbor
				var gScoreIsBest = false;
 
 
				if(!openList.findGraphNode(neighbor)) {
					// This the the first time we have arrived at this node, it must be the best
					// Also, we need to take the h (heuristic) score since we haven't done so yet
 
					gScoreIsBest = true;
					neighbor.h = astar.heuristic(neighbor.pos, end.pos);
					openList.push(neighbor);
				}
				else if(gScore < neighbor.g) {
					// We have already seen the node, but last time it had a worse g (distance from start)
					gScoreIsBest = true;
				}
 
				if(gScoreIsBest) {
					// Found an optimal (so far) path to this node.	 Store info on how we got here and
					//	just how good it really is...
					neighbor.parent = currentNode;
					neighbor.g = gScore;
					neighbor.f = neighbor.g + neighbor.h;
					neighbor.debug = "F: " + neighbor.f + "<br />G: " + neighbor.g + "<br />H: " + neighbor.h;
				}
			}
		}
 
		// No result was found -- empty array signifies failure to find path
		return [];
	},
	heuristic: function(pos0, pos1) {
		// This is the Manhattan distance
		var d1 = Math.abs (pos1.x - pos0.x);
		var d2 = Math.abs (pos1.y - pos0.y);
		return d1 + d2;
	},
	neighbors: function(grid, node) {
		var ret = [];
		var x = node.pos.x;
		var y = node.pos.y;
 
		if(grid[x-1] && grid[x-1][y]) {
			ret.push(grid[x-1][y]);
		}
		if(grid[x+1] && grid[x+1][y]) {
			ret.push(grid[x+1][y]);
		}
		if(grid[x][y-1] && grid[x][y-1]) {
			ret.push(grid[x][y-1]);
		}
		if(grid[x][y+1] && grid[x][y+1]) {
			ret.push(grid[x][y+1]);
		}
		return ret;
	}
};

And here is a faster implementation, using a Binary Heap instead of a list. This is a lot faster and also includes the option to search diagonally – 8 directional movement. Head over to the astar graph search project page to get the latest version of the code!

var astar = {
    init: function(grid) {
        for(var x = 0, xl = grid.length; x < xl; x++) {
            for(var y = 0, yl = grid[x].length; y < yl; y++) {
                var node = grid[x][y];
                node.f = 0;
                node.g = 0;
                node.h = 0;
                node.cost = 1;
                node.visited = false;
                node.closed = false;
                node.parent = null;
            }
        }
    },
    heap: function() {
        return new BinaryHeap(function(node) { 
            return node.f; 
        });
    },
    search: function(grid, start, end, diagonal, heuristic) {
        astar.init(grid);
        heuristic = heuristic || astar.manhattan;
        diagonal = !!diagonal;
 
        var openHeap = astar.heap();
 
        openHeap.push(start);
 
        while(openHeap.size() > 0) {
 
            // Grab the lowest f(x) to process next.  Heap keeps this sorted for us.
            var currentNode = openHeap.pop();
 
            // End case -- result has been found, return the traced path.
            if(currentNode === end) {
                var curr = currentNode;
                var ret = [];
                while(curr.parent) {
                    ret.push(curr);
                    curr = curr.parent;
                }
                return ret.reverse();
            }
 
            // Normal case -- move currentNode from open to closed, process each of its neighbors.
            currentNode.closed = true;
 
            // Find all neighbors for the current node. Optionally find diagonal neighbors as well (false by default).
            var neighbors = astar.neighbors(grid, currentNode, diagonal);
 
            for(var i=0, il = neighbors.length; i < il; i++) {
                var neighbor = neighbors[i];
 
                if(neighbor.closed || neighbor.isWall()) {
                    // Not a valid node to process, skip to next neighbor.
                    continue;
                }
 
                // The g score is the shortest distance from start to current node.
                // We need to check if the path we have arrived at this neighbor is the shortest one we have seen yet.
                var gScore = currentNode.g + neighbor.cost;
                var beenVisited = neighbor.visited;
 
                if(!beenVisited || gScore < neighbor.g) {
 
                    // Found an optimal (so far) path to this node.  Take score for node to see how good it is.
                    neighbor.visited = true;
                    neighbor.parent = currentNode;
                    neighbor.h = neighbor.h || heuristic(neighbor.pos, end.pos);
                    neighbor.g = gScore;
                    neighbor.f = neighbor.g + neighbor.h;
 
                    if (!beenVisited) {
                        // Pushing to heap will put it in proper place based on the 'f' value.
                        openHeap.push(neighbor);
                    }
                    else {
                        // Already seen the node, but since it has been rescored we need to reorder it in the heap
                        openHeap.rescoreElement(neighbor);
                    }
                }
            }
        }
 
        // No result was found - empty array signifies failure to find path.
        return [];
    },
    manhattan: function(pos0, pos1) {
        // See list of heuristics: http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html
 
        var d1 = Math.abs (pos1.x - pos0.x);
        var d2 = Math.abs (pos1.y - pos0.y);
        return d1 + d2;
    },
    neighbors: function(grid, node, diagonals) {
        var ret = [];
        var x = node.x;
        var y = node.y;
 
        // West
        if(grid[x-1] && grid[x-1][y]) {
            ret.push(grid[x-1][y]);
        }
 
        // East
        if(grid[x+1] && grid[x+1][y]) {
            ret.push(grid[x+1][y]);
        }
 
        // South
        if(grid[x] && grid[x][y-1]) {
            ret.push(grid[x][y-1]);
        }
 
        // North
        if(grid[x] && grid[x][y+1]) {
            ret.push(grid[x][y+1]);
        }
 
        if (diagonals) {
 
            // Southwest
            if(grid[x-1] && grid[x-1][y-1]) {
                ret.push(grid[x-1][y-1]);
            }
 
            // Southeast
            if(grid[x+1] && grid[x+1][y-1]) {
                ret.push(grid[x+1][y-1]);
            }
 
            // Northwest
            if(grid[x-1] && grid[x-1][y+1]) {
                ret.push(grid[x-1][y+1]);
            }
 
            // Northeast
            if(grid[x+1] && grid[x+1][y+1]) {
                ret.push(grid[x+1][y+1]);
            }
 
        }
 
        return ret;
    }
};

Conclusion

This A* search implementation could be used as a component to larger system (like a game – maybe tower defense or puzzle), or just for learning purposes. I have done my best to make the code understandable and to present the concepts in a way that would help someone who has never seen the algorithm before, or someone who is not very familiar with JavaScript.

Feel free to view the demo, or download the latest version of the astar.js file to mess around with it. Check out the javascript-astar project page on Github for the latest code and documentation