RTS: identifying choke points

ToohrVyk · 2006-08-19T02:02:31

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 ?