[Solved] GridGraph.Linecast does not return if an obstacle was hit

General Grid graph
#1

Hi,

I have the following code:

bool hitsObstacle = graph.Linecast(start, end, out GraphHitInfo _, _tracedPathCache);

if I now debug and print out in the immediate window the walkability of each element in tracedPath as well as the return value, I get this:
hitObstacle
as you can see, it hit an obstacle but the return value was false.

–

SOLUTION:
when changing the nodes of a grid graph, the neighboring connections need to be updated. Seems like the graph doesn’t check for walkability but for traversability (ignoring walkability).
here an example fix:

        public void MarkChange(GraphLayer layer, Vector2Int position, bool isWalkable)
        {
            AstarPath.active.AddWorkItem(new AstarWorkItem(() =>
            {
                var gg = this[layer];
                var node = gg.GetNode(position.x, position.y);

                node.Walkable = isWalkable;
                
                // by calculating connections, Linecasts can return if there is an obstacle in the way
                gg.CalculateConnectionsForCellAndNeighbours(node.XCoordinateInGrid, node.ZCoordinateInGrid);
            }));
        }
#2

Hi

Would you mind posting the full code that you use?
Also, which version do you use?

#3

Here you go (fixed version of our code):

        public static bool IsStraightMovePossible(Vector3 start, Vector3 end, GraphMask graphMask)
        {
            for (int i = 0; i < AstarPath.active.graphs.Length; i++)
            {
                int mask = 1 << i;
                if ((mask & graphMask.value) == 0)
                    continue;

                if (AstarPath.active.graphs[i] is GridGraph graph)
                {
                    _tracedPathCache.Clear();


                    // NOTE: [Bug in Astar Pathfinding Project?]
                    //       the return value of Linecast does not indicate if an obstacle is in the way
                    graph.Linecast(start, end, out GraphHitInfo _, _tracedPathCache);
                    bool hitsObstacle = _tracedPathCache.Any(o => !o.Walkable);

                    // An empty traced path means we are linecasting from a node which is marked
                    // not walkable, which results in an early out in the AStar Linecast implementation
                    if (_tracedPathCache.Count == 0)
                        return false;

                    if (hitsObstacle)
                        return false;
                }
                else
                {
                    throw new NotSupportedException("Only Grid Graphs are supported.");
                }

            }

            return true;
        }

Edit: we recently updated to version 4.2.18

#4

Are you updating the graph manually in some way?

#5

yes, but they were not updated during the linecast (loaded a savegame, map didn’t change, then the characters spawned).

Edit: To make it clear: the graph is changed directly after loading the savegame.

#6

How do you do these updates?

#7

by using PathGraphManager.MarkChange()

#8

That’s not an api that is part of this package.

#9

Ha, you are right… that’s a helper class we wrote…
Here is the API:

        public void MarkChange(GraphLayer layer, Vector2Int position, bool isWalkable)
        {
            AstarPath.active.AddWorkItem(new AstarWorkItem(() =>
            {
                var gg = this[layer];
                var node = gg.GetNode(position.x, position.y);

                node.Walkable = isWalkable;
            }));
        }

Edit: and this for initialization:

                AstarPath.active.AddWorkItem(new AstarWorkItem(ctx =>
                {
                    for (int y = 0; y < gg.depth; y++)
                    {
                        for (int x = 0; x < gg.width; x++)
                        {
                            var node = gg.GetNode(x, y);
                            node.Walkable = true;
                        }
                    }
                    gg.GetNodes(node => gg.CalculateConnections((GridNodeBase)node));
                }));
#10

On grid graphs, this will leave the node in a partially invalid state.
You need to make sure to update the neighbouring connections as well.

E.g. using

gg.CalculateConnectionsForCellAndNeighbours(node);
#11

like this?

gg.CalculateConnectionsForCellAndNeighbours(node.XCoordinateInGrid, node.ZCoordinateInGrid);

Edit: Tested it. Seems to work now :partying_face:

1 Like
#12

Hmm… after connecting the cell neighbors, I encountered the opposite behavior at another Linecast spot:
grafik
here “hitsObstacle” should be false, but isn’t…

Edit: the equation in GridGenerator line 2822 does not become 0 but -1024:
if (error + xerror/2 * (neighbourXOffsets[ndir] + neighbourXOffsets[d]) + zerror/2 * (neighbourZOffsets[ndir]+neighbourZOffsets[d]) == 0)
therefore the nextNode remains null and true is returned.
Unfortunately, The code is too complex to understand what it does, so this is all information I can provide.

Edit2:
Sorry, I’m stupid: I do a line cast into a blocked tile.

1 Like