Terrain Analysis

https://github.com/bwapi/bwapi
Heinermann
Posts: 362
Joined: Thu Apr 26, 2007 12:42 am

Postby Heinermann » Mon Dec 22, 2008 11:12 pm

Well once those errors are worked out, we can add it to BWAPI and start with basic army management.
krasi0
Posts: 254
Joined: Thu Dec 18, 2008 12:42 pm

Postby krasi0 » Sat Dec 27, 2008 9:12 pm

lowerlogic, your approach looks very promising. As Heinermann has pointed out, we can use it in army management.
One particular place it may be useful is in BW::Position AI::getEnemyMain() method defined in BWAI/Source/BWAI/AI.cpp on line 1003.
It should return the position(with coordinates of where the base of an enemy is).
We may extend it to accept player ID as a parameter or just return the first *SCOUTED* main building position of all enemies.

Except for the fight command I've included in my last commit, I am planning to add a "scout" command as well, which is going to send an scv around any unrevealed starting positions.
User avatar
lowerlogic
Posts: 92
Joined: Sat Jun 21, 2008 11:50 pm

Postby lowerlogic » Mon Dec 29, 2008 12:01 am

Hi again. I've obtained some decent results with the latest iteration of the choke point algorithm. I fixed the bugs it had before and I've fixed the 3-way choke point problem by introducing a new type of object that I've unimaginatively decided to call intersections (and an algorithm for detecting them). Intersections always link to at least 3 choke points (possibly more), however, unlike regions, intersections are not necessarily located in relatively large open spaces.

I don't consider the algorithm to be "complete" yet however I think the latest results could already be quite useful for the BW AI. I think the remaining work for the choke point algorithm will be somewhat subjective and will have to be based on what is most useful for the AIs that will be using this data.

I've attached two zip files this time, the latest source code and also a set of xml files containing the base location data and region/intersection/choke point data for each of the 39 tournament map files.

I made a little program that accepts as input these xml files and images of the starcraft maps and renders the graph on the map, so its easy to quickly review the results on all the maps. So here are visualizations of the xml files on about half the maps. Blue dots are the centers of regions, red dots are the centers of choke points, and green dots are the centers of intersections. White edges are between regions and choke points, and cyan edges are between intersections and choke points:

First a really simple map that doesn't require intersections:
Andromeda
For these next few map intersections come in handy when expressing some parts of the map. For Athena 2 the 2 intersections on the right could probably be merged together:
Athena 2
Baekmagoji 1.2
Finally Blue Storm expressed in a way that makes sense (giving the raw walkablility data):
BlueStorm 1.2
Here is the first example showing that graph simplification may be useful. The region and 2 intersections in the middle of the map could all be merged together without any real loss of information:
Byzantium 2
Chupung-Ryeung 1.1
Colosseum 2
Hunters seems pretty good for the most part:
Hunters_KeSPA 1.1
Here it may look like an intersection is directly connected to a region, however that is just because the intersection connects to a choke point that is right below it, and that choke point connects to a region.
Longinus
In lost temple there are a few unnecessary regions, but I think some pruning could easily remove most of the useless ones.
Lost Temple
Here we have another example of unnecessary complexity in the center of the map, however this time the most "correct" way to simplify it is somewhat subjective:
Medusa 1.1
Monty Hall_SE 2.1
Peaks of Beakdu
Again some unnecessary complication in the middle of the map:
Python 1.3
This example is interesting because one of the expansion locations appears to be located in an intersection:
Rush Hour 3
I'm quite happy with how Tiamat turned out, the graph has perfect symmetry just like it should:
Tiamat
Here we have another example of an intersection being located directly above a choke point, which is actually quite common when two choke points "merge" into a third before opening out into a region:
Yellow

Stuff I plan to work on next (in no particular order):
-Make a graph simplification algorithm based on openness and relative lengths of edges to find a way to intelligently merge intersections and regions when doing so results in practically no loss of information.
-Update region detection algorithm to require that regions have to have a minimum maximum openness (should prune off useless regions that are currently found)
-Associate minerals and vespene geysers to base locations (useful to determine which base locations are mineral only)
-Determine which base locations are island expansions
-Associate every base location to a region or intersection
-Associate every walkable tile in the simplified walk map to a region, choke point, and/or intersection.
-Dig up old polygon extraction algorithm and use it to find the polygonal boundary of each region (useful to determine which region a unit is in (or closest to if it is an air unit)
-Find both "ends" of every choke point.
krasi0
Posts: 254
Joined: Thu Dec 18, 2008 12:42 pm

Postby krasi0 » Sat Jan 03, 2009 10:18 pm

Nice! Keep up the good work!
User avatar
lowerlogic
Posts: 92
Joined: Sat Jun 21, 2008 11:50 pm

Postby lowerlogic » Sat Jan 10, 2009 10:28 pm

Thanks.

The next semester of college is starting Monday and I don't think I'll have time to work on the algorithm during the semester. I have thought of several approaches for merging nearby regions/intersections and walling off choke points (which is a necessary intermediate step in generating a simple polygon for each region and intersection), however I haven't figured out a method that will always work for all maps yet. I did however complete 2 things on my to-do list:
-Associate minerals and vespene geysers to base locations (useful to determine which base locations are mineral only)
-Determine which base locations are island expansions

I have attached a new set of xml files for the ICCup maps with the output. For example the 12-o-clock position on Andromeda is listed as:

Code: Select all

<base_location x="62" y="5" mineral_only="false" island="true" />


Like before the x and y pair indicates where to put the top left corner of the CC, and the meaning of the attributes mineral_only and island should be self-explanatory.

While new graph files are also included in the attached zip, some of the graphs have severe structural problems (such as choke points linked to only one region), so I recommend you use the graph files included in my previous post until I get the simplification process sorted out.

Return to “BWAPI (wrappers in other languages / questions and announcements related to BWAPI itself)”

Who is online

Users browsing this forum: No registered users and 1 guest