Walkability and Collision Detection

https://github.com/bwapi/bwapi
chippydip
Posts: 3
Joined: Fri Mar 26, 2010 4:50 pm

Walkability and Collision Detection

Postby chippydip » Fri Mar 26, 2010 5:21 pm

I was wondering if anybody happened to know how the game uses the walkability data and unit size to determine where units can actually walk.

My best guess at this point is that it uses the UnitType::dimensionLeft/Up/Right/Down fields to create a bounding box or bounding circle and then won't let a unit's bounding shape overlap unwalkable terrain.

So, for example, a marine looks like it's 16 pixels wide and 19 pixels tall. Does that mean they should be able to just barely squeeze through a vertical passageway that's 2 walk tiles wide, but need 3 walk tiles to be able to fit through a horizontal passage?

Does anyone know if it uses bounding rects or circles or some other shape? (Matters for diagonal movement, and possibly being able to partially enter an area that is too small to full walk through).

Is there any reason I shouldn't trust the values in the UnitType class for creating bounding shapes?

I realize that I could probably fudge it and err on the side of caution when doing things like pathfinding. However, this may cause problems if I tried to block off a choke point with units (leaving spaces between them that were too big) or even buildings (tile unbuildable, but still walkable by at least some units) so the more I can learn about how the game actually handles this the better.
krasi0
Posts: 254
Joined: Thu Dec 18, 2008 12:42 pm

Postby krasi0 » Fri Mar 26, 2010 9:30 pm

Your questions seem to be very clever and in the right place but I doubt anyone could answer them completely. I guess the best option you have is the trial and error approach. I would be happy if you post the results afterwards as they might be of great interest to anyone developing a serious bot AI.
chippydip
Posts: 3
Joined: Fri Mar 26, 2010 4:50 pm

Postby chippydip » Mon Mar 29, 2010 5:35 pm

Well, I decided to do some testing.

TLDR version:

Unit bounding boxes seem to be (Left+Right+1)x(Up+Down+1) and diagonal movement only seems possible when all squares that the bounding box moves through are walkable.

Setup:

I created a bot to draw a dot on every walk tile (green for walkable, red for not) and draw lines around the unwalkable parts of the map. I also added a "/size" command to report the (Left+Right)x(Up+Down) size of the currently selected unit.

Then I created a map with a bunch of doodads on it to find some that I could create specific sized chokepoints with (by viewing their unwalkable squares with my bot). Then I put some specific ones together to create horizontal and vertical chokepoints of 1-5 walk tiles and spawned in a set of all the ground units to test with.

Results:

The 31x31 units (most of the bigger ones) can fit through a 4 walk tile chokepoint in either direction. The 15x15 zergling can fit through a 2 walk tile chokepoint in either direction. Most of the "mid-sized" units can fit through a 3 walk tile chokepoint in either direction.

Marines are 16px wide (according to the Left+Right formula) but I could NOT get them to fit through a 2 walk tile passage in the north-south direction. This leads me to believe that dimensions are actually (Left+Right+1)x(Up+Down+1) where the pixel the unit is currently on (unit->getPosition()) counts for the +1 in both directions.

I didn't test diagonal movement very extensively since its much more difficult to find good doodads to use for different choke widths. A 15x15 zergling could fit through a 1.5 tile diagonal space, but only because it was able to zig-zag in order to always be in a 2x2 walkable area. A 22x22 unit wasn't able to move through a 2.5 diagonal space, which would have been enough for a rounded bounding shape (2.5*8*1.4 = 28).

Now, I still haven't figured out how to use this info in a pathfinder to efficiently figure out if a marine can get from A to B when a siege tank can't, but hopeful this is helpful to some other people. ;-)
krasi0
Posts: 254
Joined: Thu Dec 18, 2008 12:42 pm

Postby krasi0 » Mon Mar 29, 2010 7:57 pm

Hey, this really is useful. For example to developers like me trying to implement a good terran choke wall algorithm. :)
Thanks!
jorgen
Posts: 1
Joined: Fri Sep 10, 2010 8:07 am

Postby jorgen » Fri Sep 10, 2010 8:10 am

There could be other answer: bounding box for marine is the -square- 19x19 (no need for +1's)

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 0 guests