A* Pathfinding Project

Turn-Based Grid Difficulties


#1

Hi! I’m currently working on a game that uses a 25x25 node grid graph, and the player and the opponent can each give their character a position to travel to during their turn. However, I need the player to be able to pathfind around the opponent, and vice versa, and most of the agent types take up more than one node (1x1, 3x3, 5x5, etc, using erosion tags). I’ve tried multiple approaches, such as temporarily turning the AIs into obstacles, and using node blockers plus traversal providers, but none have worked. Specifically, for the former option the “inactive” agent pathfinds out of its own obstructed nodes, and for the latter, if the active agent tries to use the other one as its pathfinding target, the path fails, stating that “the node closest to the end point could not be traversed” (even with partial path calculations). I’m starting to run out of ideas, what’s the best way of going about this? If it helps at all, I only have the free version, so I won’t be able to use anything like local avoidance. Thanks!


Finding a Suitable Destination Node
#2

Hey,

Using the ITraversableProvider sounds like the best option here.

It’s important to remove the blocked nodes of the current agent that wants to move from the list before starting the pathfinding calculation.


#3

Switched over to that, and it’s working pretty well! It’s a lot more efficient than the hacky workarounds I had before, storing blocked nodes as a list in it that I can then add to on the fly using GridGraph.GetNodesInRegion. However, I’m still getting the issue where setting the destination to a node blocked using the ITraversalProvider fails the path. I found this thread which seems to have the same issue, but it’s from almost a year ago, and I can’t make sense of what’s supposed to be in the “your code here” boolean of the solution code. Any pointers?


#4

Nice to see that you are making progress.
Finding the nearest node using an ITraversableProvider isn’t possible. To modify the get nearest you can make use of the NNConstant. https://arongranberg.com/astar/docs/class_pathfinding_1_1_n_n_constraint.php

Here is an example custom constraint with the addition of a blocked node list.

public class CustomPathNNConstraint : PathNNConstraint
	{
		private HashSet<GraphNode> blockedNodes;
		
		public new static CustomPathNNConstraint Default =>
			new CustomPathNNConstraint {
				constrainArea = true
			};

		public virtual void SetBlockedNodes(HashSet<GraphNode> nodes)
		{
			blockedNodes = nodes;
		}
		
		public override bool Suitable (GraphNode node) {			
			if (!base.Suitable(node)) return false;

			if (blockedNodes != null && blockedNodes.Contains(node))
                        return false;

			return true;
		}
	}