Searched whole area but could not find target (PointGraph)

General Point graph
#1

I am attemping to compute a path between two nodes in a PointGraph I computed in run-time (which I need to do because maps are random).

I have start and end positions as Int3, the exactly values I used to create the PointGraph initially. I am able to find the nearest nodes to both and they are correct. When I ask for the path, though, the path fails with errorLog “Searched whole area but could not find target”

Here is the code in my “Move” method:

// These are Int3 coordinates I used to create the nodes and connections originally
            var startPosition = (Vector3) Tile.coordinates;
            var endPosition = (Vector3) DestinationTile.coordinates; 
            
            // This shows that it can find the correct nodes in the graph
            Debug.Log("Goto from " + startPosition + " to " + endPosition);
            Debug.Log("Nearest node to startPosition = " + AstarPath.active.GetNearest(startPosition).node.position );
            Debug.Log("Nearest node to endPosition = " + AstarPath.active.GetNearest(endPosition).node.position );

            // Methods to call when complete
            var pathDelegates = new OnPathDelegate(path =>
            {
                if (path.error) { OnPathFailed(path); } // it always goes here because path fails
                else { OnPathSuccess(path); }
            });

            // Construct the ABPath
            var pathDesign = ABPath.Construct(startPosition,endPosition, pathDelegates);

            // I also get same error when constructing the path this way
            // var pathDesign = ABPath.Construct(AstarPath.active.GetNearest(startPosition).node.position,AstarPath.active.GetNearest(endPosition).node.position, pathDelegates);

            // Start finding
            AstarPath.StartPath(pathDesign);
#2

Could you share more details of how you generate your point graph?

1 Like
#3

In brief, I first generate a random hex map with radius hexRadius and positions on the map indexed by Int3 (x,y,z) using the cube coordinate system described here https://www.redblobgames.com/grids/hexagons/

I then generate nodes using one work item, and connections using another. The code is

// This creates a Point 
var aStarData = AstarPath.active.data;
graph = aStarData.AddGraph(typeof(PointGraph)) as 

AstarPath.active.Scan(graph);

var nodeDictionary = new Dictionary<Int3, PointNode>();

 // Make sure we only modify the graph when all pathfinding threads are paused by using AStarWorkItem
AstarPath.active.AddWorkItem(new AstarWorkItem(ctx =>
{
        // create nodes
        var hexRadius = World.instance.hexRadius;
        for (var x = -hexRadius; x <= hexRadius; x++)
        {
             for (var y = Mathf.Max(-hexRadius, -x - hexRadius); y <= Mathf.Min(hexRadius, -x + hexRadius); y++)
             {
                 var z = -x - y;
                 var pn = new PointNode(AstarPath.active);
                 var pos = new Int3(new Vector3(x, y, z));
                 pn.SetPosition(pos);
                 pn.Walkable = true;
                 Debug.Log("Creating node with pos = " + pos);
                 var addNode = graph.AddNode(pos);
                 addNode.Walkable = true;
                 nodeDictionary[pos] = pn;
             }
       }
})); 
            
AstarPath.active.FlushWorkItems();

// Make sure we only modify the graph when all pathfinding threads are paused by using AStarWorkItem
AstarPath.active.AddWorkItem(new AstarWorkItem(ctx =>
{
       // create connections
                
       // Add 2 nodes and connect them
       foreach (var pn in graph.nodes)
       {
           if (pn == null) continue;
           foreach (var v in HexNeighbors.neighbours)
           {
                 var offset = v.ToInt3();
                 var pos = pn.position + offset;
                         
                  if (nodeDictionary.TryGetValue(pos, out var neighborNode ))
                  {
                     // Eventually need to mess with costs here
                      var cost = (uint) (neighborNode.position - pn.position).costMagnitude; 
                      pn.AddConnection(neighborNode,cost);
                  }
           }
      }
}));

“HexNeighbors.neighbors” is an array of Int3 (stored in a wrapper class with some convenience stuff, hence the v.ToInt3() call to make it literally an int3) representing changes that go to neighboring hexes in the cube coordinate system, so (1,0,-1), (1,-1,0) etc.

When I run this code to generate the PointGraph, the Debug.Log messages indicate the right Nodes and Connections are being added. As I mentioned in my previous post, I also seem to be finding the right nodes as nearest to both startPosition and endPosition. But somehow that still translates to “Searched the whole area but could not find target”

In case it helps, if I add pathDesign.calculatePartial = true, the behavior changes: I get “Path Completed : Computation Time 0.00 ms Searched Nodes 7 Path Length 2 Path Number 1 (unique id)” no matter how far away the destination is. Like before, it finds the correct end node I set when I call “GetNearest”, I just only searches the 7 immediate neighbors and finds the one closest to the target (aka in the right direction). I didn’t want to focus on this particular unexpected behavior, though, because from other posts it seems the calculatePartial feature is beta.

Sorry for the long post and what I’m sure is an amateur mistake I’m making. Thanks for the help!!

#4

Hi

It really looks like there are some connections that are not being added properly. I would guess that there are rounding errors somewhere.

Just a note though, if you want hexagonal graphs they are built-in to the package. Just create a grid graph and set the Shape to Hexagonal.

#5

Ok cool, I’ll look into that more. At least visually, it looks like all the connections are added correctly, but I’ll try different variations to poke around the rounding.

graph1
graph12380×1768 941 KB

I’ll also try a grid graph with Hexagonal Shape. How do I do that in a graph generated at run-time? I don’t see a Shape property https://arongranberg.com/astar/docs/gridgraph.html or https://arongranberg.com/astar/docs/runtimegraphs.html

In case it’s not obvious, what I’m trying to do is create a hex graph for a turn based game with randomly generated maps of different sizes – my understanding is this means I need to do runtime graph generation.

#6

inspectorGridMode is the variable you’re looking for. :slight_smile:

#7

Are you sure? The documentation says inspectorGridMode “Determines the layout of the grid graph inspector in the Unity Editor. This field is only used in the editor, it has no effect on the rest of the game whatsoever.”

When I run this code (lightly modified from https://arongranberg.com/astar/docs/runtimegraphs.html)

// This holds all the graph data
            AstarData data = AstarData.active.data; 
            
            // This creates a Grid Graph
            GridGraph gg = data.AddGraph(typeof(GridGraph)) as GridGraph;
            
            // Set up a grid graph with some values
            var width = mapSettings.TileRadius * 2 - 1;
            var depth = width;
            var nodeSize = 1.0f; 
            
            gg.center = new Vector3(0,0,0);
            
            // Updates internal size from the above values
            gg.SetDimensions(width, depth, nodeSize);

            gg.inspectorGridMode = InspectorGridMode.Hexagonal;

            // Scans all graphs
            AstarPath.active.Scan(gg);

The inspector shows a hexagonal grid graph … but it looks like this in the Scene

gridgraphfail
gridgraphfail1645×1528 884 KB

Aka a square. I can reshape those 49 nodes properly by choosing Grid (instead of hexagon) in the inspector, changing it back to Hexagon, and scanning manually in the inspector. My interpretation of all this is the documentation is right, inspectorGridMode only affects what is displayed in the inspector not the graph itself.

#8

Hi

Yeah, currently it is a bit tricky to configure a hexagonal graph from code.
In the next version I will include a method called SetGridShape which does this much more easily. Here is the source code, which I think should help you a bit.

/** Commonly used value for #isometricAngle */
public static readonly float StandardIsometricAngle = 90-Mathf.Atan(1/Mathf.Sqrt(2))*Mathf.Rad2Deg;

/** Commonly used value for #isometricAngle */
public static readonly float StandardDimetricAngle = Mathf.Acos(1/2f)*Mathf.Rad2Deg;

/** Changes the grid shape.
 * This is equivalent to changing the 'shape' dropdown in the grid graph inspector.
 *
 * Calling this method will set #isometricAngle, #aspectRatio, #uniformEdgeCosts and #neighbours
 * to appropriate values for that shape.
 *
 * \note Setting the shape to #InspectorGridMode.Advanced does not do anything except set the #inspectorGridMode field.
 *
 * \see #inspectorHexagonSizeMode
 */
public void SetGridShape (InspectorGridMode shape) {
	switch (shape) {
	case InspectorGridMode.Grid:
		isometricAngle = 0;
		aspectRatio = 1;
		uniformEdgeCosts = false;
		if (neighbours == NumNeighbours.Six) neighbours = NumNeighbours.Eight;
		break;
	case InspectorGridMode.Hexagonal:
		isometricAngle = StandardIsometricAngle;
		aspectRatio = 1;
		uniformEdgeCosts = true;
		neighbours = NumNeighbours.Six;
		break;
	case InspectorGridMode.IsometricGrid:
		uniformEdgeCosts = false;
		if (neighbours == NumNeighbours.Six) neighbours = NumNeighbours.Eight;
		isometricAngle = StandardIsometricAngle;
		break;
	case InspectorGridMode.Advanced:
	default:
		break;
	}
	inspectorGridMode = shape;
}
1 Like