Ignore connection costs and use ITraversalProvider only

General Point graph
#1

I have a custom graph generator based off Point Graph that creates the graph I use. I’d like the pathfinder to ignore the normal “distance”/“connection” costs and rely entirely on the ITraversalProvider I wrote when computing paths.

I attempted to make this happen by setting cost = 0 whenever I add a connection in the custom graph generator. However, this doesn’t seem to work, as the ABPaths I ask for still seem to put some weight on going “straight” in addition to minimizing the custom traversal costs.

I know it’s putting “some weight” on going straight because if I use really small costs in my ITraversalProvider (1 vs 2 for cheap vs expensive nodes), it ignores my costs and just goes straight. If I use really large costs (1 vs 20000 for cheap vs expensive nodes), it obeys my custom costs.

Using really large costs seems like a hack that won’t always work and will be ugly to maintain & be unreadable. Is there some way to actually set the connection costs to 0 or tell ABPath to ignore everything but my ITraversalProvider?

Here is the custom graph generator code:

public class HexGraph : PointGraph
    {

        /// <summary>
        /// Scans world hexes and ensures their existence in hex graph for pathfinder
        /// </summary>
        /// <param name="statusCallback"></param>
        /// <returns></returns>
        protected override IEnumerable<Progress> ScanInternal()
        {
            int hexradius = World.instance.hexRadius;
            List<PointNode> pointNodes = new List<PointNode>();
            Dictionary<Int3, PointNode> nodeDictionary = new Dictionary<Int3, PointNode>();

            for (int x = -hexradius; x <= hexradius; x++)
            {
                for (int y = Mathf.Max(-hexradius, -x - hexradius); y <= Mathf.Min(hexradius, -x + hexradius); y++)
                {
                    int z = -x - y;
                    PointNode pn = new PointNode(active);
                    Int3 pos = new Int3(new Vector3(x, y, z));
                    pn.SetPosition(pos);
                    pn.Walkable = true;
                    pointNodes.Add(pn);
                    nodeDictionary[pos] = pn;
                }
            }

            nodes = pointNodes.ToArray();
            nodeCount = nodes.Length;

			List<Connection> connections = new List<Connection>();

            foreach (PointNode pn in nodes)
            {
                connections.Clear();
                foreach (Vector3i v in HexNeighbors.neighbours)
                {
                    Int3 offset = v.ToInt3();
                    Int3 pos = pn.position + offset;
                    if (nodeDictionary.ContainsKey(pos))
                    {
						connections.Add(new Connection { node = nodeDictionary[pos], cost = 0 });
                    }
                }

                pn.connections = connections.ToArray();
            }

			yield return new Progress(1.0f, "Done");
        }
    }

Here is the ITraversalProvider’s GetTraversalCost fucntion

    public uint GetTraversalCost(Path path, GraphNode node)
    {
        var tile = TileOfNode(node);
        if (tile.TerrainType == TerrainType.Hills || tile.TerrainType == TerrainType.Wetland)
        {
            return 2; 
        }
        return 1;
    }
#2

Still haven’t figured out how to rely entirely on ITraversalProvider costs, but via trial and error I think I have discovered that the pathfinder:

  1. Prefers going though two nodes with GetTraversalCost=0 to going through a single node with GetTraversalCost return of 1036
  2. Prefers going though a single node with GetTraversalCost return of 1035 to going through two nodes with GetTraversalCost=0.

So the “distance” cost of travelling between nodes in my graph appears to be between 1035 and 1036. Still not sure where this number comes from, but I think I can work with this by making all GetTraversalCost returns a multiple of 1035. Super ugly solution, will probably fail in edge cases, but will due until I understand this stuff better.

#3

Hey,

It’s an interesting goal for sure.
The number ± 1000 is about the default cost of traversing a Graph node. I’m not 100% sure about this. But I believe this comes from the original creation where this is the distance to the a node next to it.

I’ll try to work out a way to achieve the ITraversableProvider only route in my free time later tonight. I’ll keep you posted

#4

Awesome, thanks for thinking about it :slight_smile:

The bigger picture here is I’m making a turn-based hex grid game where entering a tiles should have costs equal to an integer between 1 and 10 depending on a variety of context-specific variables such as terrain, unit modifiers, roads, etc. It’s all whole numbers on an abstract map, so the “in-unity” physics-based distances between tiles are irrelevant.

In my head the cleanest way to do this would be having everything in a custom ITraversalProvider and ignore everything else (hence this thread). But there may be some other way to do this I’m missing.

#5

@travlake

Since you are adding the connections with a cost of 0 (in your first script) then the only cost would come from your ITraversalProvider.

Though… You might want to open the ABPath.cs script and change the GetConnectionSpecialCost method to always return currentCost.

1 Like
#6

tldr: don’t worry about it anymore @aron_granberg and @ToastyStoemp - I found a simple C# A* implementation on github that works on grids and was easy to adapt to my project. Probably not as fast and definitely not as feature-rich as this project, but my setting is turn-based so doesn’t care about a few ms and is simple enough that a basic grid-based A* algorithm can work with no dependence on Unity and only a few small modifications to the code.

What I found trying to using your package, in case you care: I tried setting GetConnectionSpecialCost to always return currentCost, no change in behavior. It still has the same behavior, namely:

  1. Prefers going though two nodes with GetTraversalCost=0 to going through a single node with GetTraversalCost return of 1036
  2. Prefers going though a single node with GetTraversalCost return of 1035 to going through two nodes with GetTraversalCost=0.

One thing I noticed is that when it takes the “too short” route it only searches the 3 nodes it actually traverses. So perhaps the problem is that the heuristic the code uses in the A* algorithm is not robust to connections with cost 0 and instead assumes some minimum. If my intuition’s right, this should make the algorithm too reluctant to search for alternatives.

Anyway, thanks for all the help, I learned a lot from thinking this through and will hopefully be able to use the Pro version I bought for a different project.