Deleting fewest Navmesh Obstacles when no valid path is found

Question

So I'm building a Tower Defence, with mazing (i.e. the player can place towers to make the mobs take a longer route to there destination.)

I'm using Unity's Navmesh system. Each Enemy unit has a Navmesh Agent component. And each Tower has a Navmesh Obstacle component.

The Path-finding is working Perfectly. However (as expected) when the play completely blocks off all routes to the Agent's Destination, the agent simply moves to the spot closest to the destination that it can get to and sits there.

What i need, is to detect when that happens... Some kindof NoValidRoute() or something, I haven't been able to dig anything up in the Unity documentation or from google Searches.

Once i have that, I need to determin which Navmesh Obstacles need to be destroyed to open the shortest route possible with the fewest number of Obstacles destroyed. (i.e. if a path can be opened with only 1 tower destroyed which tower would give me the shortest route.)

I'm finding a serious lack of any information on this subject.. as far as i can tell no one has even tried to do this, or asked for help doing something like this. (at least not with Unity's Nevmesh.) I think A* is a little(and by little i Mean LOTS) outside of my skill to implement at present.

Thanks In advance

Answer 1

Make the cost of moving through/destroying an obstacle an order of magnitude greater than the cost of the entire path. The exact amount is not important just that destroying a single obstacle is more expensive than taking the long way around through every tile of your map.

Then using the usual shortest path search methods (Dijkstra/A*) you will end up with the path that uses the least amount of obstacle destructions.

From the cost of the resulting path you can derive how many obstacles there need to be destroyed.

Answer 2

I feel like there is a conceptual error: Do you really want to destroy the 'cheapest' obstacle, or rather preventing the player from placing this last, full blocking, tower. If this is the case you should recreate a new route as soon as the player clicks to place a tower. As ratchet freak said you can assign a much higher cost to passing through towers and you will find out this way if there is still a valid route (no high cost). If there isn´t you just prevent the player from placing the tower.