Anti-wall Algorithm

I been trying to think of ways to detect walling without the use of runners. The only one I actually thought of was to detect a building creation and use +/- offsets on its coords and somehow link them all together...

Any help?

An invisible runner?

Well, maybe this , convert it to a grid of 128x128 squares. Find a way to detect whether one of these squares has a building's portion in it. And another way to detect the newly-occupied squares when a building is built.

Now, for every square occupied by the building, check if there is a path of contiguous occupied squares that reaches "one of the sides of the road" , and then check if there is a path that reaches the other side. If both sides can be reached using only contiguous occupied paths, then the player has tried to make a wall.

To detect these paths use DFS or BFS (maybe recursion limit will force you to use BFS)

I need the check to be instant so...

I'm assuming DFS = Depth-first search and BFS = Simplex Algorithm? (Google ftl, Wiki ftw)

DFS/BFS will not take more steps than the number of occupied grid squares (EDIT: That are connected to the building being built)


Breadth-First-Search

The only way I can think of to detect is through GroupEnums. That correct or is there a better way?

http://www.wc3c.net/showthread.php?t...ighlight=awall

Essentially you drop rects behind runners and catch them re-entering them. Also you catch attack events, runners not moving, and runners with no order.

The runner method is ideal because it matches warcraft. If I had control over pathing, I would write a scanline algorithm over a sparse representation of warcraft space:
* Create an array of lists of sorted intervals of buildings in a row with one array row per warcraft grid row.
* Each time a building is built, find the appropriate interval and append the building or create a new interval.
* To check connectivity, look at the first row where you normally inject monsters. Create a list of intervals of regions between buildings (probably continuous at your first row) where monsters can get to
* Loop forward: Go to the next row by simultaneously iterating over the building list and interval list, and creating a new interval list split up, truncated and joined by the buildings.

It's not enough to know that the pathable area has been partitioned, because that still allows juggling.

For example you could create a long maze with two exits which are close together in space, but far apart in walking distance. When a runner gets close to an exit you sell the other one, then close the nearby one. The runner will hit the roadblock, pause for a moment, then (usually) turn around and head for the other exit. At no point was the runner ever locked in, but you've effectively trapped it anyways.

There's nothing wrong with hiding the builder or disabling constructuion for a set period of time.

If you're not allowing construction during the rounds then, yes, you can just ensure the start and end points are connected.

Wouldn't the algorithm be more basic if you just detected nearby towers after construction and checked for chains and if they reach the edges?

Sure, if you could somehow make sure that they were different "edges" (constant regions, perhaps?).