How can I tweak this A* search pathfinding algorithm to handle different terrain movement values?
- by user422318
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.
