0
\$\begingroup\$

I'm currently implementing an A* Algorithm for my Unity project. I found this entry on stackoverflow, but its not telling me how to solve my problem.

https://stackoverflow.com/questions/32205891/a-star-algorithm-in-a-3d-configuration-space

I'm not sure about the math required to calculate the distance cost correctly. How to properly implement this in 3-dimensional space?

In 2D space it is clear how to implement:

public static int CalculateDistanceCost(int3 a, int3 b) 
{
    int xDistance = math.abs(a.x - b.x);
    int yDistance = math.abs(a.y - b.y);
    int remaining = math.abs(xDistance - yDistance);

    return 14 * math.min(xDistance, yDistance) + 10 * remaining; 
}

However in 3d space it is unclear to me how to calculate it:

public struct AStarMath
{
    public static int CalculateDistanceCost(int3 a, int3 b)
    {
        int xDistance = math.abs(a.x - b.x);
        int yDistance = math.abs(a.y - b.y);
        int zDistance = math.abs(a.z - b.z);
        int remaining = math.abs(xDistance - yDistance - zDistance);

        return 14 * math.min(math.min(xDistance, yDistance), zDistance) + 10 * remaining;
    }
}

My neighbour cells are set up as follows:

int3 neighbours = new int3[]
{                         
                            //X(width),y(height),z(depth)
    new int3(-1, -1, -1), //Left, Bottom, Front
    new int3(0,  -1, -1), //Middle, Bottom, Front
    new int3(+1, -1, -1), //Right, Bottom, Front

    new int3(-1, 0, -1),  //Left, Middle, Front
    new int3(0,  0, -1),  //Middle, Middle, Front
    new int3(+1, 0, -1),  //Right, Middle, Front

    new int3(-1, +1, -1), //Left, Top, Front
    new int3(0,  +1, -1), //Middle, Top, Front
    new int3(+1, +1, -1), //Right, Top, Front

    new int3(-1, -1, 0),  //Left, Bottom, Middle
    new int3(0,  -1, 0),  //Middle, Bottom, Middle
    new int3(+1, -1, 0),  //Right, Bottom, Middle

    new int3(-1, 0,  0),  //Left, Middle, Middle
    //Middle, Middle, Middle (0,0,0) -> dont add, were already here
    new int3(+1, 0,  0),  //Right, Middle, Middle
    
    new int3(+1, +1, 0),  //Left, Top, Middle
    new int3(0,  +1, 0),  //Middle, Top, Middle
    new int3(+1, +1, 0),  //Right, Top, Middle

    new int3(-1, -1,+1),  //Left, Bottom, Back
    new int3(0,  -1,+1),  //Middle, Bottom, Back
    new int3(+1, -1,+1),  //Right, Bottom, Back

    new int3(-1,  0,+1),  //Left, Middle, Back
    new int3(0,   0,+1),  //Middle, Middle, Back
    new int3(+1,  0,+1),  //Right, Middle, Back
    
    new int3(-1, +1,+1),  //Left, Top, Back
    new int3(0,  +1,+1),  //Middle, Top, Back
    new int3(+1, +1,+1),  //Right, Top, Back
};

As you can see in this image, my enemy (magenta) now takes a weird path, but will always find a path towards target (blue).

my enemy now takes a weird path, but will always find a path towards target.

\$\endgroup\$
4
  • \$\begingroup\$ Have you considered simply using Euclidean distance, sqrt(x^2 + y^2 + z^2) ? \$\endgroup\$ Commented Sep 10, 2020 at 23:08
  • \$\begingroup\$ return math.sqrt(math.pow(a.x - b.x, 2f) + math.pow(a.y - b.y, 2f) + math.pow(a.z - b.z, 2f)); Assuming it would be coded like this. but this also changes my return type from int to float, so should i switch all my cost data types from int to float? Or is there something im missing to calculate the cost \$\endgroup\$ Commented Sep 10, 2020 at 23:16
  • \$\begingroup\$ Also sqrt calls are usually slow and this gets called inside an update method because the target can be moving, so if there is another way that would be great. If not, ill take this approach \$\endgroup\$ Commented Sep 10, 2020 at 23:23
  • \$\begingroup\$ @EternalColor Well... in that cause just dont do the sqrt part? Why do it anyways - it is bounded and monotonic. Personally I would be more concerned about the pow, depending on size of the world. \$\endgroup\$ Commented Sep 11, 2020 at 6:43

1 Answer 1

Reset to default
4
\$\begingroup\$

The code you have here has nothing to do with A*. It's just a way to get an integer approximation of 10 times the Euclidean distance between the two points.

You can think of it as breaking down your travel into a diagonal portion, min(xDistance, yDistance), and an axis-aligned portion, remaining.

enter image description here

It scales the axis-aligned portion by 10 and the diagonal portion by 14 to approximate the \$1:\sqrt 2 \approx 1:1.414...\$ ratio between the width of a square and its diagonal.

You can make an analog of this in 3D, we just have three components to sum up:

  • The diagonal component along all three axes x, y, and z (scaled by \$\sqrt 3 \approx 1.732...\$)

  • The diagonal component along the two remaining axes, after the smallest distance has been taken care of (scaled by \$\sqrt 2 \approx 1.414...\$ as before)

  • The remaining axis-aligned distance

Here's one way to compute these:

minimum = min(xDistance, yDistance, zDistance)
maximum = max(xDistance, yDistance, zDistance)

tripleAxis = minimum

doubleAxis = xDistance + yDistance + zDistance
           - maximum - 2 * minimum

singleAxis = maximum - doubleAxis - tripleAxis

approximation = 10 * singleAxis
              + 14 * doubleAxis
              + 17 * tripleAxis

If your pathfinding agents are actually allowed to make only these three specific moves:

  • moving to a face neighbour at a cost of 10,
  • moving to an edge neighbour at a cost of 14,
  • moving to a corner neighbour at a cost of 17

...then this heuristic is admissible (never over-estimates the cost), and a tight lower bound on the potential cost to reach the goal. Just be aware that if your agents actually use different costs or have different moves available, then this heuristic could give you an incorrect estimate and affect the speed or accuracy of your pathfinding.

\$\endgroup\$
3
  • \$\begingroup\$ Thanks a lot, i accepted your answer. The a star part was not included here, but its there, i use the Diagonal Cost to calculate the HCost. This was exactly what i searched for \$\endgroup\$ Commented Sep 11, 2020 at 10:13
  • \$\begingroup\$ Distance* instead of Diagonal \$\endgroup\$ Commented Sep 11, 2020 at 10:43
  • 1
    \$\begingroup\$ I don't doubt that you're using this for A*, what I mean is that that doesn't matter. This style of distance calculation is the same whether you're using it for A* or something else entirely. And A* doesn't always use this distance calculation either. So saying it's for A* doesn't describe your problem as well as just talking about your tile movement costs. \$\endgroup\$ Commented Sep 11, 2020 at 11:44

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.