Intelligently predict TD blocking?

[Weep]

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:

XXXXX
X O X
X   X
XX  X
X  XX
XO  X
XXXXX

...I want to find these squares:

XXXXX
X O X
X   X
XXB X
X BXX
XO  X
XXXXX

...without having to try blocking every blank square and then seeing if the path is clear.

Any suggestions?

 

[Magtheridon96]

Well, I'm not exactly sure of how it could be possible using code (Efficiently that is)

Regions are probably your best answer

They're clearly faster than a bunch of code mumbo jumbo x)


EDIT: To explain further, when a unit is issued a build order, you'd reject it if:

- GetOrderPointX() < GetRectMaxX(somerect) and GetOrderPointX() > GetRectMinX(somerect)
- GetOrderPointY() < GetRectMaxY(somerect) and GetOrderPointY() > GetRectMinY(somerect)


Since all your towers have the same collision, this will be pretty easy

 

[Weep]

Thanks for the thought, but I'm looking to do this dynamically, as towers get placed - using regions like that only really works for the initial layout of the map.

 

[Weep]

Bump.

 

[Nestharus]

Loop through 64x64 tiles (open spaces). When a unit is built, mark the space it is built on as occupied. As you loop through, only go to unoccupied spaces (3 leaf tree).

So, you go on to your first tile. If it is empty, then you go into its leaves (down first*). Order them down, left, right. If the down is full, then go either left or right. If left is full, go right. If you run into a dead end, you back track until you find a path that hasn't been tread yet (as you go through the nodes, mark them). If the find node is 0, then the path is blocked (you ended up backtracking to where you were). If it isn't 0, then you reached the goal (regardless of where the may be).

Newer algorithms mark a path with a difficulty to tread across rather than just an occupied flag. For example, if a path was super muddy and another one was plain and flat, AI would know to take the plain and flat one. You could also add in how long each path is and then see which one is the best possible path to take.

When a unit is placed, it occupies 1 or 4 squares (32x32 squares), so mark all 4 of them as occupied. Once they are marked, then traverse down the lane to see if you can make it through. You can use a 2D array for this or a hashtable.

Here is another method-

X X X X X X X X X X
X _ _ _ X X _ X _ X
X _ X _ _ X _ _ _ X
X S X X _ _ _ X _ X
X _ X _ _ X _ _ _ X
X _ _ _ X X _ X _ X
X _ X _ _ X _ X _ X
X _ X X _ _ _ X _ X
X _ _ 0 _ X _ _ _ X
X X X X X X X X X X

First, create a list of coordinates, which we will use as a queue. The queue will be initialized with one coordinate, the end coordinate. Each coordinate will also have a counter variable attached (the purpose of this will soon become evident). Thus, the queue starts off as ((3,8,0)).

Then, go through every element in the queue, including elements added to the end over the course of the algorithm, and to each element, do the following:
Create a list of the four adjacent cells, with a counter variable of the current element's counter variable + 1 (in our example, the four cells are ((2,8,1),(3,7,1),(4,8,1),(3,9,1)))
Check all cells in each list for the following two conditions:
If the cell is a wall, remove it from the list
If there is an element in the main list with the same coordinate and an equal or lower counter, remove it from the list
Add all remaining cells in the list to the end of the main list
Go to the next item in the list

Thus, after turn 1, the list of elements is this: ((3,8,0),(2,8,1),(4,8,1))
After 2 turns: ((3,8,0),(2,8,1),(4,8,1),(1,8,2),(4,7,2))
After 3 turns: (...(1,7,3),(4,6,3),(5,7,3))
After 4 turns: (...(1,6,4),(3,6,4),(6,7,4))
After 5 turns: (...(1,5,5),(3,5,5),(6,6,5),(6,8,5))
After 6 turns: (...(1,4,6),(2,5,6),(3,4,6),(6,5,6),(7,8,6))
After 7 turns: ((1,3,7)) - problem solved, end this stage of the algorithm - note that if you have multiple units chasing the same target (as in many games - the finish to start approach of the algorithm is intended to make this easier), you can continue until the entire map is taken up, all units are reached or a set counter limit is reached

Now, map the counters onto the map, getting this:
X X X X X X X X X X
X _ _ _ X X _ X _ X
X _ X _ _ X _ _ _ X
X S X X _ _ _ X _ X
X 6 X 6 _ X _ _ _ X
X 5 6 5 X X 6 X _ X
X 4 X 4 3 X 5 X _ X
X 3 X X 2 3 4 X _ X
X 2 1 0 1 X 5 6 _ X
X X X X X X X X X X

This is that method in more detail- http://www.policyalmanac.org/games/aStarTutorial.htm

And wikipedia article complete with pseudocode http://en.wikipedia.org/wiki/A*_search_algorithm


edit
My method tries to find any path to the goal, even if that path may be bad. Since you don't care about the length of the path, you don't have to take the extra steps to find the shortest path =).

Also, the last tower placed is the tower that blocked the path if you are checking the path every time a tower is placed.


If you wanted it to be super, super, super dynamic at the cost of a huge overhead, you'd use a group enum + get collision size script at every single little square to see if there are units occupying it :\.

Also, you should be able to pass in a square size. For example, if your unit fits into a 32x32 square, you want to check 32x32 squares. If it fits into a 128x128, you want to check 128x128 squares.

 

[Weep]

Thanks for all that, but if I'm not misinterpreting what that method does, it just checks whether the path is currently blocked? I'd still have to run it for every available square one by one to see if building there would cause a block, right?

 

[Nestharus]

No, you wouldn't... look at the initial algorithm more closely.

You would just run it until you reached the goal, whatever path that may be. You could make a function.

bool isPathBlocked(real startX, real startY, real endX, real endY) {
    //path down
    return lastNode == 0;
}