Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

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++.

share|improve this question

2 Answers 2

up vote 2 down vote accepted

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);
}
share|improve this answer
    
Wow thank you. Its works ? I need change GetHeuristicValueManhattan and GetHeuristicValueDiagonal located in this source ? lemme few minutes.. I will test it on included pathfinding source tutorial... –  ChaosDev Feb 20 '12 at 14:05
    
Oh thank you ! I think It work ! –  ChaosDev Feb 20 '12 at 14:22
    
@ChaosDev note however that the above code implements torus wrapping which is different from sphere wrapping. –  Sam Hocevar Feb 20 '12 at 16:52

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.

share|improve this answer
    
I need at least code example for mark it answer. ( –  ChaosDev Feb 20 '12 at 10:36
    
@ChaosDev: maybe you could show code for what you already have, so that someone can explain how to add wrapping to your current implementation. –  Sam Hocevar Feb 20 '12 at 12:29
    
@SamHocevar I using this open-source engine nine.codeplex.com/SourceControl/list/changesets Author said what I must do but I dont understand how... Heres source code - nine.codeplex.com/discussions/327668 –  ChaosDev Feb 20 '12 at 12:50

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.