Region and Chokepoint detection: an interesting paper

[wraitii]

I've been trying for the past couple days to implement a convincing system to detect chokepoints in Marilyn, and failed. Searched the internet, and found this paper, which suggest a freely available API already exists, coded in C++, to deal with exactly such things.

Any chance this could get into 0 AD? Adaptability can be a concern, but given the input received, I think it shouldn't be too hard to adapt.

[quantumstate]

This looks pretty interesting. The algorithm seems to work very well with the starcraft maps. Hopefully this would translate to 0 AD maps well, though since 0 AD maps are typically more open I would expect there to be a larger rate of false positives. With some pruning this shouldn't be an issue though.

The library they provide looks pretty Starcraft focused, it looks fairly strongly bound to bwapi which is not great. It might be easier to start from the CGAL library since the operations performed on the Voronoi Diagram look relatively straightforward.

[wraitii]

I didn't look into the code, if they only rely on bwapi for the initial phase, it should be fairly updatable, but if there are more calls, indeed it could be "easier" to simply recreate everything. It could also be more suited to 0 A.D., which has you said has more open-ended maps.

I'm also unsure whether Starcraft has water... I've never played it, but this would require two different settings in the algorithm I guess.

I think it's the way to go for the AIs though, because chokepoints could really be useful, particularly for pathfinding and strategic defense.

(0 A.D. also has some "open-ended with chokepoints" type map, such as Oasis, where the behavior of the algorithm would have to be tested.

Edited March 11, 2012 by wraitii

[myconid]

IMHO, this sort of thing could be built into the pathfinder itself. And maybe the pathfinder could even go a step further than the paper.

The Voronoi partitioning could be combined with a summed area table, which would make it dead easy to approximate how crowded a square region is (including objects like trees, etc!) and avoid it... if that makes sense.

Edited June 26, 2012 by myconid

[wraitii]

It's probably the better way, but we have to wait for Philip to have finished the new pathfinder for that. The summed area table is a neat idea, though.