a* algorithm path finding

Newbie & Debugging Questions
#1

Hi, I’ve implemented a class of Enemies (enemygood) with random movement.
Now I want to implement a new class of Enemies (enemyhunter) that chase the player with an A* algorithm:
http://www.policyalmanac.org/games/aStarTutorial.htm

I’ve writed the Node class, it represent a single node from the map, on this class I’ve:

  • The x coordinate of the node
  • The y coordinate of the node
  • The cost of the node
  • The precedent node

Now, I want to know if it’s correct to write the rest of A* algorithm in a new class (for example AI class)
or I can write it into the enemyhunter class??

#2

i suggest having a look at the article by david brackeen at http://www.peachpit.com/articles/article.asp?p=101142&rl=1
its very good and best of all its written java.

#3

You should defenitely write an A* Pathfinder in a seperate class to use it for different purposes and to reuse it. You might want to find a path for something else later, too.

Generally, Pathfinding is not a part of an actor or any specific actor of the game. Its more a service class with knowledge of the map. You can make your A* class very abstract and flexible and it can perform a lot of tasks.

-JAW

#4

As said, implement the algorithm in its own class. But also set up an interface that the algorithm will work with, such as a Node interface. Then you can make it easy to use anywhere just by have other classes implement the Node interface.

#5

What the guys mean is, implement the strategy pattern and make the A* Algorithm a concrete strategy. This way you can easily implement new Pathfinding algorithms without having to change your current code. (http://en.wikipedia.org/wiki/Strategy_pattern). You’ll have to define a method in your interface which you then override in the concrete subclasses (one of which is AStarPathfinder, other could be something like a hillclimbing algorithm (http://en.wikipedia.org/wiki/Hill_climbing), and so on).

For the pathNode in A* you will have to divide the cost of the node into heuristic cost and movement cost.
The formula for calculating the total cost is this; F = G + H

G = the movement cost to move from the starting point A to a given node on the grid, following the path generated to get there.
H = the estimated movement cost or heuristic cost to move from that given node on the grid to the final destination, point B.
F = total cost = movementCost + heuristicCost.

As i said, total cost is something you can calculate so you dont include that into the model itself. You can also think of storing the x and y position in a Dimension, but that is personal preference :slight_smile: