1
\$\begingroup\$

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

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Lets Assume I go with a path search algorithm. How would I determine the grid of nodes? At present I simply have the whole level on top of a Plane, and snap the transform of the towers to world co-ordinates divisible by 5. \$\endgroup\$ – DeathSabre Apr 8 '15 at 12:38
0
\$\begingroup\$

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.

\$\endgroup\$
  • 1
    \$\begingroup\$ It depends on your design . What u want from ur game. Ether option would work. Your method would hold the players hand. While mine would punish the player for being careless. Both need the same solutio. Which so far looks like the only solution will be to implant a pathfinding algorithm.. Which seems like a waste to me, since navemesh must be running one already? \$\endgroup\$ – DeathSabre Apr 9 '15 at 11:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.