How can I tweak this A* search pathfinding algorithm to handle different terrain movement values?

Question

I'm creating a 2D map-based action game with similar interaction design as Diablo II. In other words, the player clicks around a map to move their player. I just finished player movement and am moving on to pathfinding.

In the game, enemies should charge the player's character. There are also five different terrain types that give different movement bonuses. I want the AI to take advantage of these terrain bonuses as they try to reach the player.

I was told to check out the A* search algorithm (http://en.wikipedia.org/wiki/A*_search_algorithm). I'm doing this game in HTML5 and JavaScript, and found a version in JavaScript: http://www.briangrinstead.com/blog/astar-search-algorithm-in-javascript I'm trying to figure out how to tweak it though.

Below are my ideas about what I need to change. What else do I need to worry about?

• When I create a graph, I will need to initialize the 2D array I pass in passed on with a traversal of a map that corresponds to the different terrain types.
• in graph.js: "GraphNodeType" definition needs to be modified to handle the 5 terrain types. There will be no walls.
• in astar.js: The g and h scoring will need to be modified. How should I do this?
• in astar.js: isWall() should probably be removed. My game doesn't have walls.
• in astar.js: I'm not sure what this is. I think it indicates a node that isn't valid to be processed. When would this happen, though?
• At a high level, how do I change this algorithm from "oh, is there a wall there?" to "will this terrain get me to the player faster than the terrain around me?"

Because of time, I'm also debating reusing my Bresenham algorithm for the enemies. Unfortunately, the different terrain movement bonuses won't be used by the AI, which will make the game suck. :/ I'd really like to have this in for the prototype, but I'm not a developer by trade nor am I a computer scientist. :D

If you know of any code that does what I'm looking for, please share!

Sanity check tips for this are also appreciated.

Answer 1

You need to pay attention to a very specific line in the algorithm:

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

This is the cost of that particular node. You would want to modify it to something like

var gScore = currentNode.g + currentNode.cost

This will cause the path to avoid expensive terrain and prefer cheap terrain; it is your responsibility to make 'currentNode.cost' return something appropriate for your terrain. It is the fact that not all terrain has a cost of 1 that you are paying attention to... some terrain is cheaper than others. There are other considerations, but this specific point in the code should be the focus of your attention.

Answer 2

This is exactly the sort of thing A* is for. All you need to do is assign the vertices between the nodes costs based on the terrain types. (It looks like your examples uses a graph where all vertices have a cost of 1.)

Answer 3

This implementation is a little specific to the on/off right now. As Myrddin Emrys says, you will need to modify the g score based on the cost (rather than just by 1). There was a discussion about this over here: https://github.com/bgrins/javascript-astar/issues/3.

I'd love to get this solution ported back to the main library if you get it working!