Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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.

share|improve this question
    
Hey, author of the library here. Are you using the latest version from github? github.com/bgrins/javascript-astar/blob/master/astar.js. It is much faster than the old list-based implementation. –  Brian Grinstead Apr 19 '12 at 19:53
add comment

3 Answers

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.

share|improve this answer
    
Thanks for this. I've modified my code so that each node looks up the pixel at its coordinates and stores it as a cost. Unfortunately, I did a test pathfind between two points on my 800x500 grid and my browser crashes. :/ There are several factors in this: the astar code might need optimization; my canvas size is huge; maybe my graph initialization is wrong; and maybe the colors on characters' avatars are messing things up. What should I do? :( –  user422318 Apr 7 '12 at 20:11
    
When you say 'stores the pixel', you do mean that it stores the terrain cost of the pixel, yes? Because some RGB value is unlikely to match the actual cost of that piece of terrain. You should probably be storing something between 1 and 10 (1 being a road, 10 being a swamp), though exact values of course depend on your precise game. –  Myrddin Emrys Apr 9 '12 at 5:56
    
Hey, author of the library here. Are you using the latest version from github? github.com/bgrins/javascript-astar/blob/master/astar.js. It is much faster than the old list-based implementation. –  Brian Grinstead Apr 19 '12 at 19:17
2  
@Brian You should put this comment to the question, rather than to my answer, so that the person actually using the library will get the notification in their email rather than me. –  Myrddin Emrys Apr 19 '12 at 19:19
add comment

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.)

share|improve this answer
add comment

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!

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.