I am currently working on an RPG using XNA and I was wondering if anyone has implemented a shortest path algorithm on XNA. I need some shortest-path collision-avoiding code that I can use on a grid. I have looked at A* and Dijkstra's algorithm, but I think both may be outside my capabilities as a programmer. Any help is greatly appreciated.
That's it! You need to have a Set and a PriorityQueue, though, and you need an ability to find the neighbors of a given cell, and you need to be able to calculate the actual cost between two neighbors, and to estimate the cost between a position and its goal, without that estimate being an over-estimate.
Jon Watte wrote:
Pos p = startPos;
Pos g = theGoal;
PriorityQueue<Pos, Cost> open = new PriorityQueue<Pos, Cost>();
Set<Pos> closed = new Set<Pos>();
while (!open.Empty) {
closed.Add(p);
if (p == g) {
Success();
break;
}
foreach (Pos n in p.Neighbors) {
if (!closed.Contains(n)) {
n.ActualCost = p.ActualCost + CalcCost(p, n);
open.Add(n, n.ActualCost + EstimateCost(n, g));
}
}
p = open.DequeueFront();
}
That really is the simplest A* I've seen, but I haven't been able to implement one yet, so still have some questions.
1. Could you give a little more insight on some particular points, namely, the difference between calculating the cost and estimating the cost. If two tiles are adjacent (for instance, (3,3) and (4,3)), is the cost "1", or it's a different way of approaching it? And I'm guessing that estimating the cost between n and g would be using Pythagoras. Is that correct?
2. A Neighbour is every adjacent tile that isn't blocked, or should I also add blocked tiles to the neighbour list? Also, in my game, the character can't walk diagonally, so should I add only the N S E and W tiles to the neighbour list, or add the diagonals too?
3. At the start the open list is created, and then you have "while(!open.Empty)". So if open isn't empty when starting, then what should be the initial value?
Sorry if these are terribly simple questions, I'm fairly new at game programming, and it's the first time I'm trying to implement something like this, so I need to know the details.
A-star is not specific to regular grids, but regular grids are often used as examples. In the case of a regular grid, the "neighbors" are your N,E,W,S neighbors (that are actually reachable). You can handle blocked paths by saying that that is not a neighbor, or by setting an infinite cost (so they will be pushed to the end of the chain).
Calculating the cost uses actual cost of traversal -- in a regular grid with no terrain types, this will always be 1. If traveling uphill is more expensive than traveling downhill, downhill cost might be 1, but uphill cost might be 2.
Estimating the cost uses a heuristic. This can be pythagoras, but surprisingly, manhattan distance (abs(delta-X) plus abs(delta-Y)) will also work (as long as you can only walk N,E,W,S). The important bit is that the heuristic must not over-estimate the cost of the remaining path to the goal. If it does, A-star may not find the cheapest path, but it will still find a path.
