A* Pathfinding Project

Find out what's blocking the path and move to it


#1

Hi!

I’m making a tower defense type of game and decided to switch to A* because of the better grid-like movement that suits my game better. So obviously, I’m using the grid graph.
Now, this is where it gets a bit tricky. I want to be able to build my towers on the enemy path and they have to adapt around it. But what if the enemy path gets completely blocked? Right now, depending on the circumstances, it sometimes walks to a point along the path and sometimes it just gives up and walks to a certain point and falls through the map???
What I want is to reliably find a path to the closest object that is blocking the complete path. With Unity’s navmesh system that was fairly simple due to the pathStatus property which told me if the path was only partial (blocked). It then navigated to the closest path it could find anyways.

So the question is; how can I find the closest thing that is blocking the path and navigate to it? I’m using the free version 4.2.8 if that affects anything.

Thanks


#2

Hey,

There are actually a few utilities that could help you out here, take a look at https://arongranberg.com/astar/docs/turnbased.php

You could make a custom NNConstraint and use that to find the closest building. https://arongranberg.com/astar/docs/class_pathfinding_1_1_n_n_constraint.php

Hope that helps


#3

Hi!

I’m having a bit of trouble putting this together. My current setup consists of having the DyanmicGridObstacle component on my towers. Is this wrong and should I use the BlockManager only instead? I kinda see how I can make the blocking with the BlockManager but not how I can make them go to the nearest blocking tower. I can’t figure out how to use the constraints.


#4

To use the NNConstraint you don’t need to switch them to the BlockManager.

I’m writing this on mobile so excuse me for the formatting.

Here is an example of how you can make a custom NNConstraint

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

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

			if (buildingNodes != null && buildingNodes.Contains(node)) return true;

			return false;
		}
	}

This will return the closest node that contains a building. Though knowing what building will need some extra code, perhaps a dictionary with nodes referencing the building.

Honestly this is sort over over complicating everything.

Let’s take a different approach:
Let us first check if the path to the end is possible, we can use https://arongranberg.com/astar/docs/pathutilities.html#IsPathPossible3

If there is no path available find the closest building and destroy it.

GraphNode node1 = AstarPath.active.GetNearest(point1, NNConstraint.Default).node;
GraphNode node2 = AstarPath.active.GetNearest(point2, NNConstraint.Default).node;

if (! PathUtilities.IsPathPossible(node1, node2)) {
   destination = GetClosestBuildingPos() ;
} 

This isn’t the best solution, since there is no guarantee that destroying the building will result in an opening for the agents to reach the original desired destination.
Alternatively we could target the last building placed when a path was still available. But also this the player could miss use.

I don’t have an exact answer for you. I might investigate a better solution in some free time.

Hope this helps for now!