A* Search Algorithm in JavaScript

Note that this code has been updated. I have an updated blog post detailing what changed. The full source code is available at https://github.com/bgrins/javascript-astar

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

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 graph.js and astar.js to mess around with it. Check out the javascript-astar project page on Github for the latest version

Tags: algorithm, astar, javascript, programming

This entry was posted on Wednesday, June 3rd, 2009 at 10:29 am and is filed under Algorithms, All, Plugins, Web Development. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

53 Responses to “A* Search Algorithm in JavaScript”

Jelle Says:
June 12th, 2009 at 11:25 am
You’re using A* instead of Dijkstra for some reason, I assume speed. So why do you loop through the open list instead of using a heap? Boom, N^2 instead of NlgN.
brian Says:
June 12th, 2009 at 12:12 pm
Jelle, thanks for the feedback. I built it using a linked list because it was the most straightforward way to understand the code. This was more of a learning exercise for myself with the hope of being useful to anyone else.

However, I would be interested in optimizations. I am not aware of a JavaScript heap object that is provided from the standard library, but I found a couple of examples online in case anyone is interested.

It would be interesting to implement that and compare the performance between the two.
Zack J. Says:
June 12th, 2009 at 12:26 pm
I’ve got an Actionscript implementation of A* that I’ve been cleaning up recently. I also added a smoothing step at the end to remove unnecessary nodes at the end; it makes it much more useful for game AI.
brian Says:
June 12th, 2009 at 12:33 pm
Zack, could you go into a little more detail about removing the unnecessary nodes or provide a link to your code so I can look at it?

By the way, A* Pathfinding for Beginners, which you linked to from your site, is a great resource for anyone looking for more information about the algorithm.
Zack J. Says:
June 12th, 2009 at 12:44 pm
Here’s an example running. I haven’t posted it on the site or posted the source because I’m not sure what we’re going to do with it yet:

http://pixelwelders.com/experiments/Pathfinder2/

It could obviously be optimized even further, but this example shows the search process (yellow), and then the final path (blue line). It eliminates the stairstep and wall-hugging, as well as some other strange-looking paths that you sometimes get with A*.
Justin Says:
June 12th, 2009 at 3:14 pm
That’s neat!

I have a tutorial and C++ implementation of A* which uses an STL priority queue and has various optimisations.

http://code.google.com/p/a-star-algorithm-implementation/
http://www.heyes-jones.com/astar.html
Harvey Wasyliszyn Says:
March 4th, 2010 at 6:39 pm
Hi, I found this article while searching for help with JavaScript. I’ve recently changed browsers from Chrome to Internet Explorer 7. Now I seem to have a issue with loading JavaScript. Everytime I browse website that requires Javascript, the page does not load and I get a “runtime error javascript.JSException: Unknown name”. I cannot seem to find out how to fix the problem. Any aid is greatly appreciated! Thanks
Van Schutze Says:
March 30th, 2010 at 1:38 am
Thanks for sharing the information!
Learn Drums Says:
April 14th, 2010 at 9:51 pm
Hello, I read all your articles, keep them coming.
Ronald Nannen Says:
May 16th, 2010 at 5:19 am
I am definitely bookmarking this page and sharing it with my friends.
A-Star Algorithm using JavaScript « Blog by Gagan Says:
May 17th, 2010 at 11:31 pm
[...] vector data are available. One of these is finding shortest path for road network. I have taken Brian Grinstead JavaScript code for A-Star [...]
A* Search Algorithm in JavaScript | Extra Future Says:
June 12th, 2010 at 7:06 pm
[...] Looks like a good implementation, be sure to check out the demo. [...]
Shortest Path with Geometric Network « Blog by Gagan Says:
August 29th, 2010 at 12:49 am
[...] This is based on A-Start Algorithm . A JavaScript implementation of A- Star is nicely done by Brian Grinstead, same code I have included in my project. Actually scalability of the graph and related [...]
nota fiscal eletronica Says:
September 8th, 2010 at 9:31 am
How can i subscribe to your channel ? i really like to see more of what you can
b Says:
September 9th, 2010 at 6:30 pm
Nice work!! Your script is really nice. I’m digging through it now :) Thanks!
Pathfinding | Tim's Blog Says:
September 14th, 2010 at 12:41 pm
[...] http://www.briangrinstead.com/blog/asta … javascript [...]
Brian Grinstead » Blog Archive » A* Search Algorithm in JavaScript (Updated) Says:
September 15th, 2010 at 2:52 pm
[...] I first wrote the A* Search in JavaScript article I knew there were some things that I knew could be improved to make the pathfinding faster. [...]
Locksmith Knoxville Says:
September 27th, 2010 at 6:19 pm
For reasons uknown i’m ending up with a blank page whenever i make an attempt to post a comment,do you know the reason why its transpiring?i’m using oprea web-browser
using jquery Says:
October 31st, 2010 at 9:13 am
Excellent read. Proper search algorithms are a difficult thing.
Drusilla Nacke Says:
October 31st, 2010 at 2:04 pm
I’d come to engage with you here. Which is not something I typically do! I enjoy reading a post that will make people think. Also, thanks for allowing me to speak my mind!
David Says:
November 2nd, 2010 at 3:49 pm
I wish someone could teach me some JavaScript.
Mixed Martial Arts Says:
December 13th, 2010 at 10:34 am
Thanks for your clear-cut explanation of the A* search algorithm. Cleared up some issues I’ve been having.
as3isolib and A* Pathfinding | silverbase.net Says:
January 9th, 2011 at 5:22 pm
[...] in integrating A* algorithm. One of them is by AJ Piergiovanni (Rocketman) and the other one is by Brian Grinstead (JavaScript). I recommend both of them as well as A* Pathfinding for Beginners by Patrick [...]
Luca Says:
January 27th, 2011 at 12:41 am
Thank you! What’s about the copyright?
Brian Says:
January 27th, 2011 at 6:11 pm
Luca,
The code is available under an MIT style license. All source code can be found at https://github.com/bgrins/javascript-astar.
Age of empire browser versie (poc) | svenn.d Says:
February 22nd, 2011 at 10:26 am
[...] gebruikt, de villagers mogen niet door objecten heen lopen toch ?! Ik heb hier gekozen voor het A*pathfinding algoritme. Een bijkomstig probleem is dat het pathfinding iedere stap moet herhaald worden, gezien het pad [...]
as3isolib and A* Pathfinding | shiftArray() Says:
April 18th, 2011 at 8:56 pm
[...] in integrating A* algorithm. One of them is by AJ Piergiovanni (Rocketman) and the other one is by Brian Grinstead (JavaScript). I recommend both of them as well as A* Pathfinding for Beginners by Patrick [...]
felix Says:
May 6th, 2011 at 8:55 am
Hi im trying to build a html/javascript browser RTS game engine .. so the first pathfind javascript i found wa this one and it works well :)
but before i searcht for finished pathfind scripts i have started my own witch is now almost finisht .. if you want to, you can add this here .. (if it is good enough ;) ) you can find it here http://ronco.packagecloud.com/path/
your a* is also in this demo to compere..
A* Search Algorithm in JavaScript | Just thoughts Says:
July 7th, 2011 at 7:59 am
[...] via Brian Grinstead » Blog Archive » A Search Algorithm in JavaScript. [...]
genduet Says:
July 8th, 2011 at 2:20 am
how used A Search Algorithm in google maps,,,? can u help me? thanks a lot … :)
Mentifex Says:
August 11th, 2011 at 12:30 pm
Nice to find this AI-related JavaScript resource!
host then profit Says:
September 22nd, 2011 at 11:17 am
An impressive share, I simply given this onto a colleague who was doing a little analysis on this. And he in actual fact bought me breakfast because I discovered it for him.. smile. So let me reword that: Thnx for the deal with! However yeah Thnkx for spending the time to debate this, I feel strongly about it and love studying extra on this topic. If attainable, as you grow to be experience, would you mind updating your blog with extra particulars? It’s highly useful for me. Big thumb up for this blog submit!
Junior Schrope Says:
October 3rd, 2011 at 4:01 pm
I just added this webpage to my google reader, fantastic stuff. Can’t get enough!
Pokemon Tower Defense Says:
October 10th, 2011 at 4:41 pm
Exellent read! I loved Tower Defense Games so much i made one based on the Pokemon TD game.
autism recovery Says:
November 12th, 2011 at 6:47 am
autism recovery…

[...]Brian Grinstead » Blog Archive » A* Search Algorithm in JavaScript[...]…
Johnnie Furber Says:
November 18th, 2011 at 5:20 am
Strong work always good to come across a really thoughtful website – I’ve bookmarked it. Add article to my site.
Michale Says:
November 30th, 2011 at 10:54 pm
Submitted to Stumbleupon as well as got you with a plus 1!
Loan Consolidation Plan Says:
December 8th, 2011 at 6:15 am
Hello, everyone, I just came here, nice to satisfy you, welcome to visit my site and space, happy to be friends to you, love your little Tom
Spellfork Says:
December 12th, 2011 at 6:00 am
Hi to everyone! I’ve been trying out things with this astar implementation and it works really well. I was however wondering if there is someone who has used this code and extended it with weighted paths? To clarify what I mean: Say that all the squares in the grid have a weight that can differ and the search will try to find a successful path from point A to point B that has the least weight value based on the weights of the squares. Think of it as a game where movement on roads costs less than movement in mountains? Maybe there is another type of algorithm that is more suitable, so if anyone can provide some input to point me in the right direction I would be ever so thankful.
Brian Says:
December 12th, 2011 at 8:14 am
Spellfork,
This would not be too difficult to add in. Basically just allow the grid to have different costs (other than 1), the the line
```
var gScore = currentNode.g + 1;
```
would become something like:
```
var gScore = currentNode.g + currentNode.cost;
```
Where ‘cost’ is a property that is initialized in astar.init based on the input grid.

Please add a comment to the following issue expressing that this would be useful to you: https://github.com/bgrins/javascript-astar/issues/3. We can talk more there about what it would take to get it added into this implementation.
Spellfork Says:
December 13th, 2011 at 2:43 pm
Thanks for your reply Brian, I will try and experiment with this for a bit and also head over to the github page.
website Says:
December 19th, 2011 at 11:37 pm
2 potato
sarah Says:
January 24th, 2012 at 5:48 pm
thanks for a wonderful i want to ask some help. i want to code astar in c.sharp on map(vector shape file). i don’t know how to do this? and where to start. i want to use postgis at backend. but i am confused in programming i couldn’t find any libraries etc

kindly help me and guide me.

Regards,

Sarah
cosmeticsaresafe.org Says:
March 18th, 2012 at 2:02 am
cosmeticsaresafe.org…

[...]Brian Grinstead » Blog Archive » A* Search Algorithm in JavaScript[...]…
Dan Says:
May 4th, 2012 at 12:00 am
This is great! I got it working… one thing… my Graph() prints out 10 x 15.. 10 rows downs.. 15 columns across.

However, after 10×10… the right 5 on each row will not work.. here is what I am using… inside this paste.. I also included a link to an online example.

How do I make it work past the right 5 columns?

http://pastebin.com/KZGhD1zD
Astar Graph Search – Variable Costs - Brian Grinstead Says:
May 8th, 2012 at 6:02 am
[...] 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 [...]
2D Game – Progress | LiamBateman.net Says:
June 28th, 2012 at 2:42 pm
[...] A Star Path Finding Simple Inheritence [...]
Can’t Implementing A* on IE? | Jisku.com Says:
October 18th, 2012 at 9:20 pm
[...] I’m using the astar code from this website: http://www.briangrinstead.com/blog/astar-search-algorithm-in-javascript [...]
Marcel Says:
March 4th, 2013 at 11:40 am
Hey there,
this is a really interesting article, and also an interesting topic.
I’m doing some path-finding experiments and i am facing a problem using your code.
The returned result array is always undefined.
The coordinates are correctly while pushed in the array, but after returning it, the array
is undefined. I didn’t change your source :(

Here is the snippet, where i am trying to get the coordinates:

var graph = new Graph([
[0,1,0,0,0,0,0,0,0], // 0 is open, 1 is wall
[0,1,0,0,0,0,0,0,0],
[0,1,0,0,0,0,0,0,0],
[0,1,0,0,0,0,0,0,0],
[0,0,0,0,0,0,0,0,0]
]);

var start = graph.nodes[0][0];
var end = graph.nodes[4][4];
var result = astar.search(graph.nodes, start, end);

alert(“Result: ” + result[1]);

Does anyone know the error?

Greetings,
Marcel
Sam Says:
May 20th, 2013 at 5:02 am
Hi there,

at Marcel, did you try to use 1 for free and 0 for wall? ;)

at brian, first of all great code! :)
Are there any settings for the Euclidean find type?
I mean like on http://devpro.it/examples/astar/index2.html
there is euclidean and euclideanFree – mode, there is a difference between them.
euclidean can´t move as free as euclideanFree which is much better for realistic move of units is a RTS game in my case.

Thank you for the answer!
Greetings
Sam
Brian Says:
May 20th, 2013 at 5:42 am
Sam,
If you use the `diagonal` option it can move similarly to Euclidean Free. Basically, pass true as the 4th parameter to astar.search. By default it uses the Manhattan heuristic, but if you’d rather use Euclidean, you could write your own callback and pass it in as the 5th parameter.
Sam Says:
May 20th, 2013 at 9:32 am
hey :) the basic code worked like “EuclideanFree”, so I extended the ifs for “Euclidean” like in the exsample post before
im not 100% for mistakes but the test looks good ^^

all you have to do now is to say “Euclidean” oder “EuclidianFree” at the 4th parameter

if (diagonals == “Euclidean”) { //new mode

// Southwest
if (grid[x-1] && grid[x-1][y-1])
{
//push if no wall in the south and no wall in the west
if(!(grid[x][y-1].closed || grid[x][y-1].isWall()) && !(grid[x-1][y].closed || grid[x-1][y].isWall()))
{
ret.push(grid[x-1][y-1]);
}
}

// Southeast
if(grid[x+1] && grid[x+1][y-1])
{
//push if no wall in the south and no wall in the east
if (!(grid[x][y-1].closed || grid[x][y-1].isWall()) && !(grid[x+1][y].closed || grid[x+1][y].isWall()))
{
ret.push(grid[x+1][y-1]);
}
}

// Northwest
if(grid[x-1] && grid[x-1][y+1])
{
//push if no wall in the north and no wall in the west
if (!(grid[x][y+1].closed || grid[x][y+1].isWall()) && !(grid[x-1][y].closed || grid[x-1][y].isWall()))
{
ret.push(grid[x-1][y+1]);
}
}

// Northeast
if(grid[x+1] && grid[x+1][y+1])
{
//push if no wall in the north and no wall in the east
if (!(grid[x][y+1].closed || grid[x][y+1].isWall()) && !(grid[x+1][y].closed || grid[x+1][y].isWall()))
{
ret.push(grid[x+1][y+1]);
}
}

}
else if (diagonals == “EuclideanFree”) { //basic mode

// 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;
}
};
Rachel Says:
May 31st, 2013 at 12:47 pm
Hi

Great code.

2 Questions:

How can I make the path line stay viable

How can I automatically make the path display when I pass an “end” value?

Thanks

Brian Grinstead