Getting started with A* :x

Game Mechanics Artificial Intelligence
#1

So I recently implemented basic mouse movement into my game, and I put in VERY basic path finding. I knew that this wouldn’t work for the final game, and I had already heard of A*, so I thought I would look into it.

However, I can’t seem to find a good explanation of how it works and how to implement it.

Any chance I could get a good explanation (or get linked to one) from you guys?

Thanks.
-Nate

p.s. You can see said game here.

#2

Beep, boop, da-be-da-boop.

Ahem! A* is probably not what you want to start out, with you don’t already understand how to do Dijkstra’s and all of that.

Anyway, what A* star does is…

  1. Keeps track of visited nodes and the ‘best cost’ to get to that node. (Typically called the closed list).
  2. Keeps track of nodes that can be visited during the next iteration, sorted by (And this is important) the distance from your start to that node plus a guess as to how far it is away from the goal.

Then, the algorithm works as follows:

  1. Put the starting node in the ‘open’ queue.
  2. Pop the top off your open queue.
  3. Put it in the closed list.
  4. Check if it’s the goal. If you haven’t reached it yet, set it as the best, otherwise check if it’s the best (Meaning least ground covered).
    4.1) If it’s not the goal, get all of its adjacent nodes.
  5. For each adjacent…
    5.1) Check if getting to that node would take longer than your current best path. If it does discard it, otherwise…
    5.2) Then, check whether it’s in the closed list. If it is, check if it’d be a shorter path to get to it.*** If it is, compute the ‘expected distance’ then add it to the open list.
    5.3) If it’s not in the closed list, compute the ‘expected distance’ then add it to the open list.
  6. If there’s a node in the open list, go back to 2.
  7. The best path is your best path.

*** Depending on how you want to implement it, and how “good” your guess of distance remaining is, you might be able to skip this part.

The guess depends on your map and various other stuff. Typically, you use something like a Manhattan distance (Think adding the opposite and adjacent sides of the right angle formed by the line between the two positions) or the Euclidean distance (Straight line distance). These are ‘good’ for a given value of good.

If you want some real code for this, give me a poke and I’ll write up something.

#3

Yes please! I have also been looking around for a couple of weeks and have started multiple time to try to implement this but I cant. I understand how the theory works its just the actual code that screws me up. :wink: I would really enjoy it if you could come up with a little example.

Thanks,
Longarmx

#4

Also, a priority queue is a good data structure for A* when you select nodes to expand (depending on heuristic and current cost).
I use a binary heap for this.

#5

Well, since (More than one) person asked for it, here’s a link to my rather basic A* pathfinder.

It’s not very well implemented, 'cause I did it in like thirty minutes, however Here. It’s currently just a basic ‘one cost’ tile thing, which makes it rather trivial and it’s not really commented, but…

#6

These two threads should be able to help you out :slight_smile:


http://www.java-gaming.org/topics/introduction-to-pathfinding/25158/view.html

Mike