- Joined
- Jul 12, 2009
- Messages
- 321
In a maze-style TD, I'm hoping to have a predictive anti-block. In other words, instead of just canceling construction of a tower if it blocks (which I already have working), I'd like to make it impossible to even start building in any place which would block. This could be accomplished by changing terrain pathing in those places, whatever. That's not important.
The map structure is an N by M grid with arbitrary walkable/buildable squares. Towers are 1x1 and there is only 1 exit but an arbitrary number of spawn locations.
The trick is finding the critical places. What I'm wondering is if there's a smarter way to determine what positions would block than testing every position by brute force. I can do that, but it's pretty intensive and lags for a second, and I don't like it. Is there a way to somehow find which squares are crucial to connecting each spawn to the exit?
For example, if the map is like this:
...I want to find these squares:
...without having to try blocking every blank square and then seeing if the path is clear.
Any suggestions?
The map structure is an N by M grid with arbitrary walkable/buildable squares. Towers are 1x1 and there is only 1 exit but an arbitrary number of spawn locations.
The trick is finding the critical places. What I'm wondering is if there's a smarter way to determine what positions would block than testing every position by brute force. I can do that, but it's pretty intensive and lags for a second, and I don't like it. Is there a way to somehow find which squares are crucial to connecting each spawn to the exit?
For example, if the map is like this:
Code:
XXXXX
X O X
X X
XX X
X XX
XO X
XXXXX
...I want to find these squares:
Code:
XXXXX
X O X
X X
XXB X
X BXX
XO X
XXXXX
Any suggestions?