5
\$\begingroup\$

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

\$\endgroup\$

2 Answers 2

2
\$\begingroup\$

NOTE: The source code referenced in this answer is located in Engine Nine. However, CodePlex will be going offline soon & that project may no longer be avaiable; the source code may also be available in the follow up project Nine.Graphics

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);
}
\$\endgroup\$
2
  • \$\begingroup\$ 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... \$\endgroup\$
    – ChaosDev
    Feb 20, 2012 at 14:05
  • \$\begingroup\$ @ChaosDev note however that the above code implements torus wrapping which is different from sphere wrapping. \$\endgroup\$ Feb 20, 2012 at 16:52
8
\$\begingroup\$

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.

\$\endgroup\$
3
  • \$\begingroup\$ I need at least code example for mark it answer. ( \$\endgroup\$
    – ChaosDev
    Feb 20, 2012 at 10:36
  • \$\begingroup\$ @ChaosDev: maybe you could show code for what you already have, so that someone can explain how to add wrapping to your current implementation. \$\endgroup\$ Feb 20, 2012 at 12:29
  • \$\begingroup\$ @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 \$\endgroup\$
    – ChaosDev
    Feb 20, 2012 at 12:50

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .