After some discussion on a previous thread, I have straightened out some ideas about my problem: A bottleneck in a strategy game is a place where few units can pass through. Thus, it's a key strategic point that can be easily defended. An area surrounded by bottlenecks makes a good base position. Thus, I want my AI to identify bottlenecks. I have already developed an algorithm which runs in linear time (in the number of tiles on the map), which reads the passable/nonpassable status of each tile and cuts the map into sectors. Because of the way it is built, the edges between sectors are then good candidates for choke points. The image below shows a typical result (black: walls, colors: one sector each, red lines: connectivity): Are there any algorithms which, unlike mine, will evaluate the "bottleneckyness" of a given tile on the map? Are there other known algorithms to cut a map into sectors faster than linear-time (assuming that one can fill a sector with known edges in negligible time), with sector edges being good candidates for bottlenecks ?

I'd do this, somewhat similar to what another user said in the other thread:

For each node, do a pathfind to ALL the other nodes.
Each time a node is used in a path, increase its "Visited" variable.

Then check which nodes have the highest visited variables, meaning they are more prone to be a bottleneck since more paths go through this area.
Solve the problem: Edit the area around this node, or add more nodes there etc.

/rb

Nice image! [smile]

Sorry if this doesn't help much - it's a bit of a brain dump.

Why do you need linear time for this? Can't you precalculate various statistics based on your maps? Even if your maps are mutable, can't you localize your algorithms to reduce their processing overheads?

Re. bottleneck detection:

1. Take the (red) arcs in your map and adjust them so that they only pass through non-blocked squares (some of your current arcs pass through blocked terrain).
2. For each arc, increase the width of the arc until it touches a blocked square on both sides, or the width is greater than some 'obviously open area' value. (Another approach would be to try to pass a large circle along the arc and shrink it whenever it touches a blocked square)
3. If arc width < 'bottleneck width', then arc represents a bottleneck - add one to each connected node's bottleneck count.

Game Programming Gems 3 section 3.4: "Terrain Analysis in an RTS - The Hidden Giant" might also be useful.

Hope this helps.
Cheers,
Jones.

I think a maximum flow solver might be what you are looking for. Use the sectors as you have them now, assign a capacity to every edge, place some sources and sinks and solve the maximum flow problem. Then you look for edges that are fully utilized, these are chokepoints.

This approach is conceptually close to what you are looking for and quite flexible as you can tweak it at 3 "places":
selecting your sources,
selecting your sinks,
assigning capacities

Quote: Original post by Trap
I think a maximum flow solver might be what you are looking for. Use the sectors as you have them now, assign a capacity to every edge, place some sources and sinks and solve the maximum flow problem. Then you look for edges that are fully utilized, these are chokepoints.

It is a good idea, but there is an algorithmic subtlety.

In the maximum flow solution, some edges are necessarily fully utilized because they are choke points, others turn out fully utilized only because the solver chooses to saturate them instead of splitting the flow more evenly with other possible paths.
If this happens, spurious choke points will result.

Example: a 5 node graph with maximum flow between A and E.
Edges and capacities:
A B 3
A C 3
B C 3
B D 4
C D 4
D E 4
The maximum flow is obviously 4, as constrained by edge DE.
So DE is a choke point; it should be the only one in the map, and a symmetrical solution could be flow 2 through AB, AC, BD, CD and 0 through BC.
But solvers could saturate AB or AC with a flow of 3 and 1 on the other; or even create three spurious choke points at AB, BC, CD or AC, BC, BD with a flow of 3 and 1 on edges from A, 3 on BC and 4 and 0 on the edges to D.

I believe you could solve this by reducing the graph to a set of cliques. Then the edges between cliques would correspond to chokepoints. If there is no clique graph for your starting graph (because it is too higly connected) then remove the node with highest connectivity (and all edges touching it) and recompute. You can find information on building clique trees in any decent graph theory text book.

Cheers,

Timkin

Quote: Original post by ToohrVyk
A bottleneck in a strategy game is a place where few units can pass through. Thus, it's a key strategic point that can be easily defended. An area surrounded by bottlenecks makes a good base position. Thus, I want my AI to identify bottlenecks.

I came to the same conclusion some time ago myself. (Only I wanted to use for steering.)

My algorithm is fairly complicated, but for the bottleneck stage it's a bit as follows:
1. for each free-grid, calculate distance and direction to the nearest wall-grid
2. for each free-grid, if a neighbour grid's wall-direction is "fairly" opposite than current grid's one, and the wall-distance is less than some treshhold, the grid is considered a bottleneck grid

(Step 2 is quite tricky, since I had to relax the contraint of "opposition" a little on a local scale, to strict it later on a global scale (in "gather stage"). Similar technique I used in edge detection algorithm a few years back.)

I guess it wouldn't work in real time, though.

Here's a sample output for your map:

Quote: Original post by ToohrVyk
Are there any algorithms which, unlike mine, will evaluate the "bottleneckyness" of a given tile on the map? Are there other known algorithms to cut a map into sectors faster than linear-time (assuming that one can fill a sector with known edges in negligible time), with sector edges being good candidates for bottlenecks ?

Why in linear time? For real-time terrain modifications?

ajones: I already have the size of the border between two sectors (represented by the width of the edges in the graph) and can use this as bottlenecks. What I'm looking for is mainly another way to compute the border and edges. Thank you for your book suggestion, though.

Trap & Lorenzo: I'm looking for local bottlenecks. Global bottlenecks are generally rare and not really defendable positions (since in general there are several ways to reach every single point). A local bottleneck might not guard the only way through, but it's a good place to place a cannon or tower.

Timkin: thank you, this is an approach I had not thought of. However, I was looking more for ways to create the graph of sectors from the original map (I don't think this approach would work directly when applied to a tilemap).

Quote: Original post by deffer
Why in linear time? For real-time terrain modifications?

Real-time is one of the objectives (although with a lower resolution), but also to handle randomly generated maps (as opposed to predesigned maps for which compile time is available).

Your approach looks really good, though!

Quote: Original post by ToohrVyk
Real-time is one of the objectives (although with a lower resolution), but also to handle randomly generated maps (as opposed to predesigned maps for which compile time is available).

Random maps? Then what about processing in load-time?
It would take only a few seconds. All the professional games do that all the time.

Quote: Original post by ToohrVyk
Timkin: thank you, this is an approach I had not thought of. However, I was looking more for ways to create the graph of sectors from the original map (I don't think this approach would work directly when applied to a tilemap).

Each tile is represented by a vertex in a graph representation of your map, with connections between tiles depicted by edges in the graph. It's a 1-1 translation that is easily invoked in code.