TurnBased blocking nodes while moving on precalculated path

General Grid graph
1

This is the question for the turn based game where each entity moves at once one by one. I utilized provided BlockManager and SingleNodeBlocker, and I succeeded to wire everything up.

The problem came up with implementation of the simple random movement.

What i basically do is that for each entity:

  • Check if entity can move
  • Create a random path with RandomPath.Construct, then
  • Move blocker node to the next tile
  • Move entity to that tile
  • Repeat for all others

So basically all entities will move in one direction at once if they can move, by one tile.

The problem is that since I move them along the precalculated path, I may end up with two entities being at the same position. How can I check if the target position is blocked or not? Or what is the optimal solution here?

And what would be a good solution for preventing entities to move one through another?

thanx in advance

2

I tried to:

 public bool NodeFree(Vector3 worldPos) {
            var node = AstarPath.active.GetNearest(worldPos).node;
            if (node == null) return true;

            blocked.TryGetValue(node, out var blockersInNode);
            return blockersInNode == null || blockersInNode.Count == 0;
        }

but unfortunately that doesn’t guarantee that the node is blocked since:

/// The node will not be blocked immediately. Instead the pathfinding
/// threads will be paused and then the update will be applied. It is however
/// guaranteed to be applied before the next path request is started.
3

Are you moving all your units together? Or are they just all executing their own individual orders, but at the same time? If it’s the second option, I recommend taking a look at NearestNodeConstraint, maybe the filter property, so you can set your own parameters for what a “blocked” node looks like.

This part makes me believe that you don’t want them to be able to walk over each other though, is that correct? If this is the case, NearestNodeConstraint may not be your best option– if this is the behavior you want, in your case I would try making my own movement script that created a node-by-node path to follow, then moved one node at a time, waiting until a node is cleared before moving forward.

This is an example custom movement script. This wouldn’t fit for the use case you may be describing but it gives an example on how to write one.

4

Yeas, I am moving all my units together. It’s: player moves one tile, all other units move one tile you can see that in action here: https://imgur.com/gallery/scaledeep-devlog-new-enemy-new-vegetation-JsX3Y1p#muzerOQ) . I created a simple custom movement script, something similar to what you linked.

But as I said it fails due:

// <summary>
/// Register blocker as being present at the specified node.
/// Calling this method multiple times will add multiple instances of the blocker to the node.
///
/// Note: The node will not be blocked immediately. Instead the pathfinding
/// threads will be paused and then the update will be applied. It is however
/// guaranteed to be applied before the next path request is started.
/// </summary>
public void InternalBlock (GraphNode node, SingleNodeBlocker blocker) {

because I block x,y then move unit to x,y, block and move second unit to x1,y1, block and move third unit to x2,y2, and after movement started then the first call creates block on the node at x,y, second at x1,y1 and third block at x2,y2.

So it is useless to check if node is blocked before I start to move since the node blocks are not updated.

I tried a custom move script with following logic:

  • turn 1 (these happens immediate one after another)
  • unit1: create a random path, save destination position
  • unit1: move blocker node to the next position on path
  • unit1: move unit to the next position on path
  • unit2: same as unit1
  • turn 2 (after 1 sec for example)
  • unit1: check if there is saved destination
  • unit1: create new ABPath to destination (this should satisfy this point: ”It is however guaranteed to be applied before the next path request is started.")
  • unit1: move blocker node to the next position on abpath (this would block node on next path request)
  • unit1: move unit to the next position on ab path
  • unit2: same as unit1

Not so nice approach, since I would create a ton of request each turn, but I needed to see if it is working at all. It dosn’t. This is the code:

        public (string, bool) MoveSingleTile(MapType mapType, Transform transform)
        {
            if (mapType != MapType.kWander)
                return ("", false);

            if (_destination != Vector3.zero)
            {
                // go rather AB
                UseAB(transform.position, _destination);
                return ("", true);
            }
            
            UseRandom(transform);
            return ("", false);
        }

        private void UseRandom(Transform transform)
        {
            var searchLength = 5000;
            var spread = 5000;
            var aimStrength = 0;
            RandomPath rp = RandomPath.Construct(transform.position, searchLength, OnPathComplete);
            rp.traversalCosts.traversalProvider = _ai.Traverse(null);
            rp.spread = 5000;
            rp.aimStrength = aimStrength;
            rp.aim = Vector3.Scale(transform.position, transform.position * 5);
            rp.calculatePartial = true;
                        
            AstarPath.StartPath(rp);
            rp.BlockUntilCalculated();
        }

        private void UseAB(Vector3 start, Vector3 destination)
        {
            var rp = ABPath.Construct(start, destination, OnPathComplete);
            rp.traversalCosts.traversalProvider = _ai.Traverse(null);
            rp.calculatePartial = true;
            AstarPath.StartPath(rp);
            rp.BlockUntilCalculated();
        }

        void ClearPath()
        {
            _blockedTimes = 0;
            _destination = Vector3.zero;
        }

        private void OnPathComplete(Path p)
        {
            if (p.error || p.vectorPath.Count <= 1) 
            {
                ClearPath();
                return;
            }

            var v0 = p.vectorPath[0];
            var v1 = p.vectorPath[1];
            var direction = v1 - v0;
            
            var back = p.vectorPath[^1];
            _destination = back;

            _ai.BlockNode(v1);  // it's SingleNodeBlocker.BlockAt(worldPos); 
            
            var nd = new Vector2Int(Math.Sign(direction.x), Math.Sign(direction.z));
            if (_moveController.TryTriggerMove(nd) != MovementResult.kOk)
            {
                _ai.BlockNode(v0);
                if (_blockedTimes++ == 2)
                {
                    ClearPath();
                }
            }
            
            if (v1 == _destination) {
                ClearPath();                
            }
        }

but this also works badly, I don’t have a clue am I doing something wrong or not.

MoveSingleTile is called each time when enemy should move.