Feature idea: Add weighting to graph nodes

[bgrins]

Any interest in this feature? Basically, you can have a graph with different weights on locations. This would factor into the distance cost of a particular path and change the recommended path.

How what would the desired way to represent cost in the function call be? Currently (1 is inaccessible, 0 is open):

var graph = new Graph([
        [0,0,0,0],
        [1,0,0,1],
        [1,1,0,0]
]);

Proposed (anything 0 is inaccessible, anything > 0 is a fixed cost based on the value - so a 2 node would simply add 2 onto the distance instead of 1):

var graph = new Graph([
        [0,0,0,0],
        [1,0,0,2],
        [1,3.5,0,0]
]);

Obviously this would break compatibility with the old implementation (since the meaning of walls change), but that could be documented for people updating.

[spellfork]

Yes this is the exact thing that I'm looking for. To top it all of, it would also be neat to be able to pass along a max distanceWeight that (like movement points in a game). So say I have a game character that has 8 points of movement, and it costs 1 point to move on roads, 2 points for movement in forests and say 3 points for movement through mountain terrain. That would mean that my absolute maximum number of nodes I can move through is 8 (if the whole path is made up of road), but I could only move 2 nodes if I where in a mountain surrounding.

This could also be usefull if I would have a huge array of nodes (say 1000x1000) and make a path calculation since I'd be limited to an offset of the huge array corresponding to only the nodes within my range.

[spellfork]

Hi Brian

I've experimented a lot with your code and the ideas I mention above. I thought I'd share some of my results with you. I have only tested and debugged my code in chrome so far, so keep that in mind if you're gonna test anything.

As you mentioned in your blog I've used:

var gScore = currentNode.g + currentNode.cost;

Since I have a large grid of about 200x200 nodes or squares I've written a function to separately create a smaller grid, this is kind of straight forward and I use an offset value stored in my movable game object in order to position it correctly in the larger grid. Also since I didn't want to modify your base code to much I still use a grid of ones and zeros for walls. When using my terrain map I create one grid for obstacles and one for movement costs and pass them both into the graph creation function:

var graph = new Graph( obstacleGrid, costGrid );

function Graph(grid,costs) {
    this.elements = grid;
    this.nodes = [];

    if(costs && costs.length){
        for (var x = 0, len = grid.length; x < len; ++x) {
            var row = grid[x];
            this.nodes[x] = [];
            for (var y = 0, l = row.length; y < l; ++y) {
                this.nodes[x].push(new GraphNode(x, y, row[y], costs[x][y]));
            }
        }
    } else {
        for (var x = 0, len = grid.length; x < len; ++x) {
            var row = grid[x];
            this.nodes[x] = [];
            for (var y = 0, l = row.length; y < l; ++y) {
                this.nodes[x].push(new GraphNode(x, y, row[y]));
            }
        }
    }
}

function GraphNode(x,y,type,cost) {
    this.data = { };
    this.x = x;
    this.y = y;
    this.pos = {x:x, y:y};
    this.cost = cost || 0;
    this.type = type;
}

This could be managed a bit better in Graph function than my crude if else check, but as for now it works. A fun fact is that your search is still crazy fast, it takes about 6 to 8 ms for me to make all the path checks that my game object is able to move to (ex I use a 13x13 grid to search for all available nodes within my game objects movement range, so ultimately the code will evaluate the best possible path to 84 squares in that time).

[bgrins]

Sweet, glad to hear you got this working!

I actually don't have any problem with changing the code to have 0 mean wall and anything > 0 mean the cost. I think that may be a little easier to read, and hopefully easier for your calling code to use. In this case, 2 could be forest, and 3 could be mountain or whatever terrains you wanted. Do you think this is the best way to handle it? I think as long as we document it, it should be a fine change to make.

If you would like to do a pull request for the cost stuff in particular, I would definitely be happy to merge that in along with documentation changes.

[bgrins]

I wrote a post asking for more feedback about this feature: http://www.briangrinstead.com/blog/astar-graph-search-variable-costs

[peter-m]

I came up with a custom mapping solution like this (a modified init function):

    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.visited = false;
            node.closed = false;
            node.parent = null;

            switch(grid[x][y].type) {
                case 0:
                    node.cost = 1;
                    break;
                case 1:
                    node.cost = 1;
                    break;
                case 2:
                    node.cost = 3;
                    break;
                default:
                    node.cost = 1;
                    break;
            }
        }
    }

(i also added this to graph.js)

OPEN: 2

but this is kinda hacky as it has to be applied manually after every update - your proposed implementation is more generic too so this would be pretty cool!

[bgrins]

Thanks for sharing this, I feel like the options here are getting a little more clear. It seems like we could change the init function to something like

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.visited = false;
        node.closed = false;
        node.parent = null;

        // User defined cost function taking in indices (falls back to 1 if no cost function defined)
        node.cost = getCost(x, y);
    }
}

Or take in two separate arrays and map it manually in the init function:

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.visited = false;
        node.closed = false;
        node.parent = null;

        node.cost = costs[x][y];
    }
}

Another idea is to change the API entirely by making -0- mean WALL and everything else be a weighted cost (.5, 1, 2, 10, etc would just directly be the cost). This would break backwards compatibility, but also might be the nicest way to handle it going forward.

[peter-m]

personally i wouldn't like to keep 2 seperate map arrays - when scripting something like a GUI (so the average user can build his own maps for the game) this will get pretty complicated... (just outlining the drawbacks, of course there are benefits as well, but they've already been outlined ;)

[bgrins]

Peter, that is a great point. Would you ideally just change API to make -0- mean WALL and everything else be a weighted cost (.5, 1, 2, 10, etc would just directly be the cost)?

This would break backwards compatibility, but also might be the nicest way to handle it going forward. I'm actually OK with doing this, if it means that the algorithm will be easier to use going forward. We could make that v1 and if you update you would need to change your code.

[bgrins]

Peter, Or are you suggesting that we extend your custom mapping solution to be more configurable?

[peter-m]

• i wouldn't bother too much about backwards compatibility as the pathfinding algorithm as such is pretty stable right now (as far as I can tell, great job btw ;D) so you are not forced to update in order to get rid of existing errors/...
• I like your idea of storing the cost directly in the array pretty much (it's somewhat semantic), mine was rather a pretty hacky workaround (actually just the first one I could think of) - so I'd go in for your solution ;)

[maritz]

+1

[Hankus]

I forked the code and implemented weighted based nodes based on the very original post. Its working quite well from what I can tell and very little was changed to make it work.

I still have a weee bit of work to do like a live demo and so on but its all go for me on my machine :)

https://github.com/Hankus/javascript-astar

[bgrins]

Great, thanks for taking this on! We will just need to change the documentation and demo to show this feature off. Really looking forward to seeing the demo!

You should be able to just push to the gh-pages branch to publish whatever is on your machine out to http://hankus.github.com/javascript-astar

[Hankus]

I see, thanks for the help - Quite new to Github...

The demo is now live at http://hankus.github.com/javascript-astar/ but all the documentation and so on needs updating.

But for now see how it goes!

[bgrins]

Looks awesome, this is great! On the demo it would be nice to have some kind of key for the weights. Another idea on the demo if you are up for it is to be able to toggle the weighting on and off (or toggle the % of weighted nodes).

Once you get everything tied up feel free to make a pull request and we can review the changes and get it merged in. Looking forward to getting this feature in.

[bgrins]

In fact, it would be great if you added a checkbox just like the "Allow diagonal movement?" one that said "Add different weighted nodes?" that would toggle this feature on or off in the demo.

[Hankus]

Done done and done.

I have done a pull request too.

Enjoy!

[bgrins]

Thanks so much @Hankus! Great job on this, the weighted search is now live at: http://bgrins.github.com/javascript-astar/demo/.

[bgrins]

http://www.briangrinstead.com/blog/astar-graph-search-variable-costs