ITraversalProvider - Can traverse, but not end

I have a custom ITraversalProvider that is doing a great job doing it’s thing. However, I have come across a case that I am not sure how to solve. In this, as most turn based, a character can travel through a node if it contains an ally, but it cannot end its movement. In this case, I am working on the enemies - so blocking the node from being clickable isn’t a viable solution (I do this in a different way for characters).

public bool CanTraverse(Path path, GraphNode node)
        {
            if (_nodeInfo.IsNodeOfType(node, UnitType.ClosedDoor))
                return false;

            //this
            if (path != null && path.path != null &&  path.path.Count > 0 && path.path[^1] == node)
            {
                if (_unit.LevelGrid.IsGridPositionOccupied(
                        _unit.LevelGrid.GetGridPositionFromWorld((Vector3)node.position)))
                    return false;
            }
            
            if ( (_isFlying || _isJumping) && node.Walkable)
            {
                GridPosition gridPos = _unit.LevelGrid.GetGridPositionFromWorld((Vector3)node.position);
                if (_unit.LevelGrid.TryGetUnitAtGridPosition(gridPos, out Unit unit))
                {
                    return unit.UnitType != Units.UnitType.Ally && unit.UnitType !=  Units.UnitType.Summon;
                }
            }

I thought the code marked as “this” would provide the solution, but it doesn’t :cry:

Any suggestions would be greatly appreciated!

Hi

The ITraversalProvider cannot distinguish between nodes that are walkable in general, and nodes that can be used as the final node in a path.

Could you provide some more details, though, as I don’t quite see what you are trying to do.
Are you running a ConstantPath from your enemies and then pick a final target node?

Sort of. I am doing kind of a weird algorithm for picking a final target.
I do a MultiTarget path to gather all paths adjacent to the player. Then, i sort the paths based on my own scheme.

I am not using the built-in tags system or anything like that. I have a custom registration of where things are on the map, and I am using the traversal provider to apply penalties or flag nodes as traversal/not traversable there.

Picking nodes (works fine - note the tile registry is basically just a dictionary of GraphNode to Registered Type)

private void FindFocus()
        {
            //First find pathfinding cost to each player
            var players = _gameService.PlayerUnits;

            //This weeds out any adjacent position that we cannot stand in! 
            TargetPathfindingData =
                players.SelectMany(player =>
                        player.AdjacentNodes.Where(adjacentNode =>
                            {
                                //This was added to solve the issue we are talking about. However, we were really hoping we could encapsulate this into the ITraversalProvider instead of doing it here in the LINQ, as this just gets more complicated as we go.
                                if (TileRegistrationService.TryGetUnitOnNode(adjacentNode, out Unit unit))
                                {
                                    return unit == this;
                                }

                                return true;
                            })
                            .Select(adjacentNode => new TargetPathfindingData
                            {
                                GraphNode = adjacentNode,
                                WorldPosition = (Vector3)adjacentNode.position,
                                Unit = player
                            }))
                    .ToList();

            Seeker.StartMultiTargetPath(transform.position,
                TargetPathfindingData.Select(hex => hex.WorldPosition).ToArray(),
                true, OnPathComplete);
        }

private void OnPathComplete(Path callbackPath)
        {
            MultiTargetPath p = callbackPath as MultiTargetPath;
            if (p == null || p.error) {
                Debug.LogError("Error calculating path: " + p.errorLog);
            }
            
            DrawPathData(p);
            
            //Determine how many negative hexes are on each path
            for (int i = 0; i < p.nodePaths.Length; i++)
            {
                TargetPathfindingData[i].SetTargetPathCost(p.nodePaths[i].Count);
                for (int j = 0; j < p.nodePaths[i].Count; j++)
                {
                    if (TileRegistrationService.DoesNodeContainAnyOfType(p.nodePaths[i][j], TileType.Icy))
                    {
                        TargetPathfindingData[i].DecreaseTargetPathCost();
                    }

                    if(!TileRegistrationService.IsNodeNegativeTile(p.nodePaths[i][j])) continue;
                    
                    TargetPathfindingData[i].AddNegativeHex();
                    
                    if (TileRegistrationService.DoesNodeContainAnyOfType(p.nodePaths[i][j], TileType.Difficult))
                    {
                        TargetPathfindingData[i].IncreaseTargetPathCost();
                    }
                }
                
                //For display only
                var path = p.vectorPaths[i];
                var lastNode = path[^1];
                lastNode.y = 0.2f;
                pathCosts.Add((lastNode, p.targetPathCosts[i]));
            }
            
            TargetPathfindingData.Sort((a, b) =>
            {
                int compare;

                // Order by least amount of negative hexes
                compare = a.NegativeHexes.CompareTo(b.NegativeHexes);
                if (compare != 0) return compare;

                // Then by fewest movement points
                compare = a.MovementPointCost.CompareTo(b.MovementPointCost);
                if (compare != 0) return compare;

                // Then by closest range
                compare = a.Distance(transform.position).CompareTo(b.Distance(transform.position));
                if (compare != 0) return compare;

                // Then by lowest initiative
                compare = b.UnitInitiative.CompareTo(a.UnitInitiative);
                if (compare != 0) return compare;

                // Then by highest health
                compare = b.UnitHealth.CompareTo(a.UnitHealth);
                if (compare != 0) return compare;

                // If all criteria are equal, maintain the original order
                return 0;
            });

Traversal provider:

        public bool CanTraverse(Path path, GraphNode node)
        {
            if (TileRegistrationService.DoesNodeContainAnyOfType(node, TileType.ClosedDoor))
                return false;
            
            if ( (_isFlying || _isJumping) && node.Walkable)
            {
                return true;
            }
            
            if (TileRegistrationService.DoesNodeContainAnyOfType(node, TileType.Obstacle))
            {
                return false;
            }
            
            //Check if its an ally or summon, because we cant walk through them if we are not flying
            if (TileRegistrationService.TryGetUnitOnNode(node, out Unit unit))
            {
                if ((unit.Faction & (Faction.Player | Faction.Summon)) != 0)
                {
                    return false;
                }
            }
            
            //Default implementation
            if (!node.Walkable || (path != null && (path.enabledTags >> (int)node.Tag & 0x1) == 0)) {
                return false;
            }

            return true;
        }
        
        public bool CanTraverse (Path path, GraphNode from, GraphNode to) {
            return CanTraverse(path, to);
        }
        
        public uint GetTraversalCost (Path path, GraphNode node) {

            if (_isFlying || _isJumping)
            {
                return 0;
            }
            
            //Most expensive to least expensive
            if(TileRegistrationService.DoesNodeContainAnyOfType(node, TileType.Trap))
            {
                return TileRegistrationService.COST_FOR_ONE_NODE * 100;
            }
            else if(TileRegistrationService.DoesNodeContainAnyOfType(node, TileType.Hazard))
            {
                return TileRegistrationService.COST_FOR_ONE_NODE * 50;
            }
            else if(TileRegistrationService.DoesNodeContainAnyOfType(node, TileType.Difficult))
            {
                return TileRegistrationService.COST_FOR_ONE_NODE * 2;
            }

            return 0;
        }

That is all working out fine. The trouble comes when we execute the path. At that point, we pass the target node (for movement, this is a node adjacent to the player). All units use the AIPath movement script.

Our Seekers are set to never recalculate paths automatically.

 public override async UniTask Execute(Unit unit, GraphNode target, List<ActionPart> rollOvers)
        {
            Debug.Log("Executing simple move!");
            var path = ABPath.Construct(unit.transform.position, (Vector3)target.position);
            unit.Agent.SetPath(path);

            await UniTask.WaitUntil(() => unit.Seeker.IsDone());
            await UniTask.WaitUntil(() => unit.Agent.reachedDestination);

            unit.UnitMoved();
            Debug.Log("Done moving!");
        }

(We go back and forth between using the seeker destination, seeker.startpath, and the AB path)
The trouble comes in that when we gather adjacent positions, positions that are occupied by a unit is excluded (so the enemy unit won’t stop on a node that is already occupied). That is fine.

There are a couple of areas where this causes issues.

  1. flying/jumping. While it is OK for them to traverse through an obstacle, they cannot stop their movement on an obstacle.
  2. partial movement. If the target is 7 hexes away, but they can only move 2 hexes this turn, they should move towards the target. However, this can cause them to land on the same hex as another enemy (because the provider is saying “yes, you can move through that hex!” … which is true, but they can’t stop on that hex).

    Example image above, the unit on hex 432 moved two hexes to the south west towards the player (on 337). Then the enemy on 431 went, moved two hexes towards the player (on 337). If that enemy had had 3 movement, it would have been fine to move through the enemy already on the hex. However, it only had 2 movement, so it should have ‘gone around’ and stopped on 371 – it appropriately went around 398 (hazard) and 499/400 because we explicitly tell it to not step on them if it can help it.
if (actions[0].actionType == ActionType.Move)
            {
                //FIRST, let's handle the movement items
                var moveAction = actions[0];
                int range =  moveAction.range;
                if (moveAction.useBase)
                {
                    range += unit.ActionController.BaseMove;
                }
                
                //Now we only want to move to the closest node, stopping if we need to
                if (data[currFocus].MovementPointCost <= range)
                {
                    Debug.Log("We can reach the destination, so let's do it!");
                    await actions[0].PerformAction(unit, data[0].GraphNode);
                }
                else
                {
                    Debug.Log("Can't reach, let's get closer!");
                    await actions[0].PerformAction(unit, data[0].NodePath[range]);
                }
            }
            else
            {
                await actions[0].PerformAction(unit, data[0].Unit.CurrentNode);
            }