A* Pathfinding Project

Rerouting agents when a node is in use


#1

Hey guys, I’ve been trying to figure out how i can ‘occupy’ nodes in a grid graph so when an agent is given a command to walk to it, any other agents that try to walk to it will instead find the nearest ‘unoccupied’ node, im sorry if i have worded this wrong or if i’ve missed a solution thats easily available. please point me in the right direction if thats the case. :smiley:

Edit:
for anyone that finds this post trying to find a similar solution, This solution will have the effect of blocking a node when a unit is on it, ideally to stop other units from trying to occupy the same node.

The below code is for the CustomNNConstraint.

public class CustomPathNNConstraint : PathNNConstraint
{
	protected 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;
	}
}

And this code is what you would to have when you call the GetNearest function.

public void SetPath () {
    RaycastHit _hit;

    if (Physics.Raycast (cam.ScreenPointToRay (Input.mousePosition), out _hit, Mathf.Infinity)) {

        CustomPathNNConstraint myConstraint = CustomPathNNConstraint.Default;

        foreach (Transform _target in target) {
            Pathfinding.GraphNode _node = AstarPath.active.GetNearest (_hit.point, myConstraint).node;

            _target.transform.position = (Vector3) _node.position;

            blockedNodes.Add (_node);
            Debug.Log (blockedNodes.Contains (_node));

            myConstraint.SetBlockedNodes (blockedNodes);
            seeker.StartPath (transform.position, _target.transform.position, OnPathComplete);
        }
    }
}

#2

Hey,

If you take a closer look at the GetNearest you can see we can overwrite the the NNConstraint . This allows us to block certain nodes from being used for this specific call.
You’ll want to change the Suitable method.


#3

I don’t think i fully understand that, it was one of the first things i found that seemed like an answer, how do i create a new constraint, and how would the system know if one is occupied?


#4
public class CustomPathNNConstraint : PathNNConstraint
{
	protected 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;
	}
}

BlockedNodes would be a HashSet (Unique List) of nodes you want to block.


#5

Hello again,

I believe i understand everything in that code and i have used it, I just don’t know how SetBlockedNodes() works. Do I call this function? and how do i get a hashset of currently used nodes? are they equal to the graphnode i get when i use the GetNearest() function? i’m sorry if my questions seem stupid i for some reason cannot work out the constraints myself. it’s like they’re clear but i still scratch my head :sweat_smile:


#6

Hi

There is nothing in the pathfinding system that keeps track of which nodes agents occupy, so you have to fill that in yourself. You can call the SetBlockedNodes method with a HashSet that contains all nodes (that you can get using the GetNearest method without using your constraint) which you want to prevent the system from picking.


#7

ohhhhh, so i should have a hashset of all nodes occupied and update the custom constraint with it when i get the nearest node?, is there a way to make it update during pathfinding or only when the path is being set? i am confident i could create said function, i am just asking if there is one already for that purpose


#8

also, thank you so much for this extension, the best money i have spent on the asset store to date.


#9

I’m not sure what you mean by update during pathfinding?


#10

sorry, so as the agent is moving is there a way to update it so it can change its destination say, if another agent fills that node before it arrives


#11

Hi

Sure, you just update the hashmap. Just keep in mind that the pathfinding system doesn’t know anything at all about occupied or unoccupied nodes that you handle like this. The only thing it knows is the destination you will give it after having found the nearest free node (using the constraint above).
For this kind of behavior it usually works best if you only mark nodes as occupied after the agent has actually reached them.


#13
{
    protected HashSet<GraphNode> blockedNodes = new HashSet<GraphNode>();

    public new static CustomPathNNConstraint Default =>
        new CustomPathNNConstraint
        {
            constrainArea = true
        };

    public virtual void SetBlockedNodes(HashSet<GraphNode> nodes)
    {
        blockedNodes = nodes;

        Debug.Log(blockedNodes.Count);
    }

    public override bool Suitable(GraphNode node)
    {
        Debug.Log("Test");
        if (!base.Suitable(node))
        {
            Debug.Log("BaseNotSuitable");
            return false;
        }

        if (blockedNodes != null && blockedNodes.Contains(node))
        {
            Debug.Log("NodeOccupied");
            return false;
        }
        if (blockedNodes == null)
        {
            Debug.Log("ItsEMPTY");
        }
        Debug.Log("Suitable");
        return true;
    }
}

my console prints
“Test”
“Suitable”
“Test”
"Suitable:
“1”
and with each new node i select the number increases. if i select a node that is already added the number won’t increase, but the node is still considered suitable. i may be doing something wrong and the blockedNodes in the customNNConstraint, and the nodes are correctly added in my blockednodemanager that holds the actual hashset of the blockednodes. i am lost


#14

A Hash Set is like a list, but with only unique elements. So adding an already added node won’t make a difference.

Here is some pseudo code you might find useful.

Clear blockednodes
Sort agents => distance to player 

foreach agent in agents
    CustomNNConstraint.setBlockedNodes

    Agent.seeker.CalculatePath( destination, Custom NNConstraint) 
    Blockednodes.add astar.getclosestNode(Agent. Pos)

This will block the node under each agent. For the next agent.


#15

Sorry I may not have been clear, the hashset that I have that nodes are added to identities the node correctly and the ‘contains’ function returns true, but when the suitable function gets called the hashset in the custom constraint returns that it does not contain the node


#16

so this is how i have it set up

target = a list of transforms

public void SetPath()
    {
        RaycastHit _hit;


        if (Physics.Raycast(cam.ScreenPointToRay(Input.mousePosition), out _hit, Mathf.Infinity))
        {
            foreach (Transform _target in target)
            {
                Pathfinding.GraphNode _node = AstarPath.active.GetNearest(_hit.point, CustomPathNNConstraint.Default).node;

                _target.transform.position = (Vector3)_node.position;

                blockedNodes.Add(_node);
                Debug.Log(blockedNodes.Contains(_node));

                CustomPathNNConstraint.Default.SetBlockedNodes(blockedNodes);
                seeker.StartPath(transform.position, _target.transform.position, OnPathComplete);
            }
        }
    }

the console prints true, as expected.

but when i use the above code you provided it doesn’t seem to recognize the node in the parameter of the Suitable function, i’m not sure if i’ve done something wrong but i hope i now have provided all the right information :sweat_smile:

i am trying to use this for an rts style project and i’m using nodes as movement points so units are always positioned correctly(thats why i get the nearest node and set the target transform to its center)


#17

CustomPathNNConstraint.Default
Will call the constructor of CustomPathNNConstraint
So the one used in GetNearest and SetBlockedNodes is not the same.

You’ll want to create only one CustomPathNNConstraint and reuse it.


#18

Sorry, I don’t seem to understand and I’m frustrating myself. I will try and sort this out and reply when I have a better understanding of what i’m messing up


#19

so do you mean when i call
CustomPathNNConstraint.Default.SetBlockedNodes();
i should instead call
CustomPathNNConstraint.SetBlockedNodes():


#20

Try something like this:

public void SetPath () {
    RaycastHit _hit;

    if (Physics.Raycast (cam.ScreenPointToRay (Input.mousePosition), out _hit, Mathf.Infinity)) {

        CustomPathNNConstraint myConstraint = CustomPathNNConstraint.Default;

        foreach (Transform _target in target) {
            Pathfinding.GraphNode _node = AstarPath.active.GetNearest (_hit.point, myConstraint).node;

            _target.transform.position = (Vector3) _node.position;

            blockedNodes.Add (_node);
            Debug.Log (blockedNodes.Contains (_node));

            myConstraint.SetBlockedNodes (blockedNodes);
            seeker.StartPath (transform.position, _target.transform.position, OnPathComplete);
        }
    }
}

#21

i feel so silly :sweat_smile: i didn’t understand what i was doing wrong and it was right in front of me, thank you so much for your help and everything is working perfectly now :smiley: