How to create wrap-around pathfinding?

Question

I've created a planet and obstacle grid and want to move units through this grid using A* or any other algorithm. The only problem is wrapping. I need a simple example of how to handle this unusual pathfinding requirement. I prefer C#/XNA rather than C++.

Answer 1

NOTE: The source code referenced in this answer is located at: http://nine.codeplex.com/

Here is a version of GetEdges that manages wrapping. The important part is the computation of x2 and y2 which are wrapped around the torus. I also removed the incredible level of code duplication that was in that method:

/// <summary>
/// Gets all the adjacent edges of the specified node.
/// </summary>
public int GetEdges(int node, GraphEdge[] edges, int startIndex)
{
    int count = 0;
    int x = node % SegmentCountX;
    int y = node / SegmentCountX;

    GraphEdge edge;
    edge.From = node;

    for (int dy = -1; dy <= 1; dy++)
    {
        for (int dx = -1; dx <= 1; dx++)
        {
            if (dx == 0 && dy == 0)
                continue;

            int x2 = (x + dx + SegmentCountX) % SegmentCountX;
            int y2 = (y + dy + SegmentCountY) % SegmentCountY;

            if (data[x2 + y2 * SegmentCountX] == 0)
            {
                edge.To = x2 + y2 * SegmentCountX;
                edge.Cost = (dx * dy == 0) ? 1.0f : 1.4142135f;
                edges[startIndex++] = edge;
                count++;
            }
        }
    }
    return count;
}

And here is the new GetHeuristicValue:

/// <summary>
/// Gets the heuristic value used by A star search.
/// </summary>
public float GetHeuristicValue(int current, int end)
{
    int dx = Abs(current % SegmentCountX - end % SegmentCountX);
    int dy = Abs(current / SegmentCountX - end / SegmentCountX);

    int xx = Min(dx, SegmentCountX - dx);
    int yy = Min(dy, SegmentCountY - dy);

    return (float)Math.Sqrt(xx * xx + yy * yy);
}

Answer 2

Assuming you already have a way to move objects in a looping world, you just need to implement a wrapping heuristic function for A*. Normally in a tile-based world the heuristic function is something like H = sqrt(dx*dx + dy*dy) or H = abs(dx) + abs(dy), where dx and dy is the difference between the current tile and the goal tile: dx = targetX - currentX. Replace that with something that takes the wrapping into account such as dx = min(abs(dx), abs(width + dx), abs(width - dx)) and same for dy. Also make sure your A* implementation gets the neighbours from the other side of the world on the edges.

Edit: When using the source code given in the comments, modify the following parts:

Function GetEdges: Remove all if-statements, but keep their content. Change all usages of (x +- var) to (x +- var) % SegmentCountX and same for y. Below are the required changes in the code:

edge.To = y * SegmentCountX + x - 1; // Change this line to ...
edge.To = y * SegmentCountX + (x + SegmentCountX - 1) % SegmentCountX;

and

edge.To = y * SegmentCountX + x + 1; // Change this line to ...
edge.To = y * SegmentCountX + (x + 1) % SegmentCountX;

And similar change for y direction and diagonals.

Function GetHeuristicValue: Before the return statement add lines:

xx = Min(Abs(xx), Min(Abs(SegmentCountX + xx), Abs(SegmentCountX - xx)));
yy = Min(Abs(yy), Min(Abs(SegmentCountX + yy), Abs(SegmentCountX - yy)));

You need to replace Min and Abs functions with the ones provided by your framework.

I'm not sure what SegmentCountX and bounds are in this code, but you might need to replace SegmentCountX or SegmentCountY with something from the bounds.