Tuesday, September 18, 2012

Choke Detection Tweaks

A statement I made earlier was incorrect: Skynet's algorithm does not find all regions first as BWTA does. Instead, it alternates, finding a region, then determining the limits of that region by closing it off with chokepoints. Thus the order of forming regions matters and will affect where the choke points are found. Skynet starts with the largest region and works its way down.

Two thresholds control the chokepoint detection process. The regionThreshold, originally set at 0.9, eliminates chokepoints that are too wide compared to the parent region. The tileThreshold controls how quickly the choke must widen out. It was originally 0.8, but changing it to 0.91 greatly improves accuracy over my map sample set.

 Orbital Relay is not shown since it remains identical.
 Python's top left resource area is now detected thanks to the bump to 0.91.

 Many changes in Tau Cross. The importance of the additional regions is that all resources are now partitioned into their own regions. I believe that this is important for strategic purposes.

Lost temple's center area is now cordoned off, which is the important part. It now looks similar to BWTA's output, but has extra regions. BWTA has an extra step in which it merges small regions together. I don't think it is necessary, since the AI should be able to deal with having extra regions. In any case, it is better to have too many divisions than too few.

No comments:

Post a Comment