Brian Grinstead

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 was 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: ,
    WALL: 1
};

// 0 represents an open node, 1 represents a wall
var graph = new Graph([
    [,,,],
    [1,,,1],
    [1,1,,]
]);

My initial plan for adding weighting was something like this:

var GraphNodeType = {
    WALL: ,
};

// Anything > 0 represents the cost to travel to that node, 0 represents a wall
var graph = new Graph([
    [2,1,3,4],
    [,1,1,],
    [,,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([
    [,,,],
    [1,,,1],
    [1,1,,]
],[
    [2,1,3,4],
    [,1,1,],
    [,,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!

Comments

1. Marc Devol Says:
   

   May 8th, 2012 at 1:40 pm

   Hi,
   thank you for amazing work, it helped me very much.

   I’m currently working on a automatic walking for the game. When I was creating the grid for view, I have did some usefull prototype for Array of Arrays. Some of my prototype can solve your problem.

   You could create very fast “obstacle map” for inter use whit this:

   function isFunction(object) { return !!(object && object.constructor && object.call && object.apply); } // chack if the array is full arrays with same length Array.prototype.isAoA = function () { var height = this.length, width = height ? this[0].length : 0, i;   if (height && width) { for (i = 0; i < height; i += 1) { if (!this[i].length || this[i].length !== width) { return false; } } return true; } return false; }   // create new array // if callback return true then fill 0 otherwise 1 Array.prototype.aoaMask = function (callback) { var result = [], height, width, i, j;   if (!isFunction(callback)) { callback = function (value) {return !!value;}; }   if (this.isAoA()) { height = this.length; width = this[0].length;   for (i = 0; i < height; i += 1) { result[i] = []; for (j = 0; j < width; j += 1) { result[i][j] = !!callback(this[i][j]) ? 1 : 0; } } } return result; }   // how to use var terrainMap = [ [2,1,3,4], [0,1,1,0], [0,0,3,10] ], // everything smaller then 2 is wall obstacle map = terrainMap.aoaMask(function () {return value < 2;}); // obstacle map is now // [ // [0,1,0,0], // [1,1,1,1], // [1,1,0,0] //]

   I hope, it will be heplfull.

   Underline note:
   When I viewed your code, I found some global variable (it could rewrite some value of another script use on page). You should check out your code with http://www.jslint.com/ or http://www.jshint.com/ for basic mistake.

2. Brian Says:
   

   May 8th, 2012 at 1:55 pm

   Marc, this is an interesting approach to generating the obstacle map and terrain map! So, do you typically start with a terrain map in your game, rather than obstacle, or do you have them in the same map? How are they represented? I think I am having some trouble with deciding how to do this because I’m not sure how most people are needed to transform their input data.

   Maybe this aoaMask could be provided as a utility in the library for people who do want to generate the obstacle map separately, assuming we went with the second option (2 separate maps).

   Also, where is the global variable in the code? Definitely shouldn’t be there!

3. Marc Devol Says:
   

   May 8th, 2012 at 8:07 pm

   Except the terrain value (1 to 6) and wall (0), I have an active cell (-1 to -3). All active cell are not walkable. So I need to do transform to positive and zero (simillar way like I wrote above).

   If you do not need to find path an array of arrays with zero and one, it will be better solution add new parameter to search function – callback. The callback will decided if the cell is walkable or not.

   // define callback function as parameter (wall = zero and negative) astar.search(graph.nodes, graph.nodes[0][0], graph.nodes[2][0], false, false, function (value) {return value -less or equal- 0} );   // use callback for isWall method function(grid, begin, end, diagonal, heuristic, callback) { ... if(neighbor.closed || neighbor.isWall(callback)) { .... } ... }   // apply callback to type of cell GraphNode.prototype.isWall = function(callback) { return callback ? callback(this.type) : this.type == GraphNodeType.WALL; };

   OR

   I realy understand why you use node.cost (every time is 1 and it couldn’t be change without change your code) and node.type (value of original array of arrays) separately. For example, if the callback function is use in init function (not in isWall), it will be use once for all cell and it will reflect the node.type to node.cost trought user filter.

   // define callback function as parameter (wall = zero and negative) astar.search(graph.nodes, graph.nodes[0][0], graph.nodes[2][0], false, false, function (value) { if (value -less or equal- 0) { return 0; } return value; } );   // if callback was not set then cost = type, otherwise the type go trought callback (filter) and assigned to cost init: function (grid, callback) { 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.cost = callback ? callback(node.type) : node.type; ... } } }   // use callback for isWall method search: function(grid, begin, end, diagonal, heuristic, callback) { astar.init(grid, callback); ... // !neighbor.cost replace isWall method (both means 0 = wall) if(neighbor.closed || !neighbor.cost) { continue; } ... // now cost reflect type (value of original array of arrays) var gScore = currentNode.g + neighbor.cost; ... }

   And at the end.
   Sorry, I did wrong court about global variable, I overlooked same comma. But you should rewrite all var statement to one at the begin of function. The reason why should, you can find there http://uxebu.com/blog/2010/01/09/variable-declarations-and-scope/ and it will be more readable.

4. Brian Says:
   

   May 9th, 2012 at 1:58 pm

   Marc,
   Great to see how you are using this in your example! I like the idea of having an isWall callback – though I would definitely want to precompute that before entering the loop in the algorithm. This could be an interesting way to still only require one grid (essentially a terrain grid), and allow each user to define what a wall (or any other obstacle) is using whatever logic they want.

   And I do like your second method, but that would break backwards compatibility since right now, 0 signifies an open node. That could be a legitimate option going forward though, since people would need to modify their code anyway to update for traversals one way or another. If it is the most sensible way to handle it, it might be best to draw a line between version .9 and version 1 or something.

5. Hankus Says:
   

   July 4th, 2012 at 1:27 am

   Hi I would love to see this feature, and I think the cost-weighted graph method would be superb. Is there any chance you have made a working script for it?

6. George Aslanis Says:
   

   January 26th, 2013 at 9:42 am

   This is a great educational value and learning tool! I need full coverage planning algor? Is possible/practical to modify instead of shortest distance to “End”, calculate most efficient full coverage path to “End”? Any ideas or other javascript examples to accomplish this?
   Thanks for your insight and help!

Comments are closed. Please contact me instead.