Why is A* running paths that are not from the position in the GridGraph that I give it?

General
1

image
image1968×373 47.8 KB

d
d864×1155 55.7 KB

Please/thanks for any help with this one: I have a script that is meant to run one path going across a map made of squares, from one numbered spawn point to one exactly across of the same number. The paths that are being ran are saved into that array you see ‘finalPaths’, which is of the size of the width of the A* grid. The squares ‘terrainSqs’ in the code are a 2D array of a class which is just meant to represent each node in the grid. The squares are of the exact same size and number of squares as the grid, everything is the same size, proportionally the squares are 2 units just like the graph squares in Unity distance. The squares even have their position (which is a Vector3) set to the Int3 positions of each node in the A* grid (and yes, it’s divided by 1000 when it’s set). The program waits till all paths are complete before moving on.

Here’s the most important part: the code here used to work, and worked perfectly for a long period of time before (I suspect) updating A* recently.

So before, when I would run these paths, I would see that (after they all finish) the first path’s first GraphNode (which I cast to a GridNodeBase, so I can see the XCoordinateInGrid), that XCoordinateInGrid would correspond to the position of the square I thought it was running from. The first path would start at XCoordinate in grid 0, the next 1, the next 2. And they would all go to the opposing number correctly as well: opposite side 0, opposite 1, etc.

Now however, there is for some reason multiple paths, sometimes as many as 4 or 5 that end up being ran starting from the same starting square more than once. Like, I will go through the array, which has its initial loop supposed to ABPath.Construct from each index up ONCE only, there will for instance be 3 paths that come from XCoordinateInGrid 7. The ending positions also do not even match, they are again just nodes nearby. And there are multiples like 100% of the time too.

image
image1137×752 63 KB

Why is A running paths from adjacent GraphNodes when I am telling it to run from the position of a specific GraphNode? Typically it looks to me like I am running a path using the Vector3 position of what I think is GraphNode at X, but it uses nearby X coordinates now 100% of the time.

Here’s a last shot of me logging the Vector3 positions of each square in my project, and its corresponding Int3 / 1000: as we go up the width of the graph, so you can see the position should be close enough (I thought?)

image
image766×686 49.5 KB

2

Hi

Which version are you using?

3

@aron_granberg Hi aron, thanks for your reply, I am using 4.2.19 (Current).

4

How are you adjusting the grid graph? Are you using a node size of 0.001? Or do you mean that each node has coordinates like (0, 0, 0), (1000, 0, 0) etc.?
Are all points/nodes at the same y coordinate?

5

The node size is of size 2. No, the graph has terrain which has height added to it, and some paths do fail. Which, was always happening back when this was working, paths with error would just fail but it still increments on to the next path as it calculates more (keeps moving over). I added a shot of me logging the first row of start positions, 0, 1, 2, 3, 4, from the bottom side of start positions, which shows you the (Int3 / 1000) of each node, with the Vector3 of the square that I am trying to use to start a path from there. With a node size of 2, it seems like the difference in those numbers isn’t even close to being accidentally outside the node’s square I feel like, right?

6

Does your points that you pass to the path account for this terrain height?

I believe the GetNearest method has been changed so that it does a more thorough search for the actual closest node using euclidean distance. If the terrain has a lot of height changes, this may result in it picking a node to the side.

7

@aron_granberg

You can see here this is the method that sets the position of what is supposed to be the corresponding path.
image

And I am using GetNode(x, z) to get the Int3 Position of that node here, for every single square in the graph, to my associated terrainSquare array:

terrainSqs[x, z].SetWorldPosition(AstarPath.active.data.gridGraph.GetNode(x, z).position);

So yes, the y position of this node, wherever it is, should be conserved in the Vector3 for that square. The fp3 struct you see is a fixed-point equivalent of the Vector3 and has more digits of precision than a Vector3 by a long shot.

[EDIT] So again, that’s interesting what you say about GetNearest, but I don’t believe there is any usage of GetNearest in the project…just GetNode()

8

But then why are these different?
bild

The path uses GetNearest on the start and end points of the path, to get the closest nodes.

9

@aron_granberg Ah, yes that’s interesting, I think its losing precision because I am simply taking the Int3 and dividing it by 1000, when converting, which loses precision there. When I log out the entire Int3 there is some digits lost for square 8 here for example:

image
image988×252 29.7 KB

Taking each int, turning it into a float first has fixed this element of it, so you can see they are perfectly the same now at least:

image
image776×253 15.4 KB

10

I’d recommend that you experiment with AstarPath.active.GetNearest. Do something like:

void Update () {
    var n = AstarPath.active.GetNearest(transform.position).node;
    Debug.DrawLine(transform.position, (Vector3)n.position, Color.red);
}

to check what you get. This might help you debug it.

11

image
image1139×557 22.4 KB

@aron_granberg Wow, ok so yeah I changed the max nearest node distance to .1 instead of 100. Looks fixed, every path goes from one spawn across to the correct one, with no duplicates anymore.

I suppose for some reason A* found some starting nodes themselves were not passible? Otherwise I don’t see why it wouldn’t find the node which is directly at the starting position really, so I am a bit curious about that. All of my spawn squares are supposed to be passible I thought…I guess I could be wrong about this too though.

Thanks a lot for your help man!

12

That’s strange. Reducing the max nearest node distance shouldn’t change which nodes are the closest ones…
I can’t quite remember how things were configured in the latest release. In the beta, I have worked a lot on making sure the GetNearest methods work properly. You can even specify that you want the search to ignore the y axis, if you want. See DistanceMetric - A* Pathfinding Project

1 Like