The building gap and unit size numbers at liquipedia let us predict which units can get through which horizontal and vertical building gaps. They do not give us any such detailed information about corner gaps between 2 adjacent buildings. The game logic must be calculating these corner gaps somehow, so I looked at the available numbers and the observed behavior of units in-game to try to figure it out. This is what I found.
I will refer to these liquipedia pages by number:
[1] List_of_Unit_and_Building_Sizes
Note 1: This post does not involve terrain edges, only buildings in open areas. It also does not involve glitching, just simple move commands.
Note 2: I do not claim that this is what the game logic is ACTUALLY doing, only that:
The formula is simple, and
It fits with the data I've tested so far
Deriving a formula with a zealot
Consider the four possible barracks and supply depot corner gaps. Only one of them is too small for a zealot to pass, when the depot is NE of the barracks. At this point, refer to [1] for gap and unit sizes:
zealot size: 23 wide, 19 high
barracks gap T,L,B,R: 8, 16, 15, 7
depot gap T,L,B,R: 10, 10, 5, 9
We know that horizontal and vertical gaps are calculated by simply adding the two gap sizes corresponding to the adjoining sides of the two buildings. For two buildings whose corners are touching, imagine that BOTH of the horizontal and vertical gaps between them are in effect. From here on, I'll use Hgap and Vgap for brevity.
barracks-NE-depot: Hgap(right of barracks, left of depot) is (7 10) = 17, Vgap(top of barracks, bottom of depot) is (8 5) = 13.
barracks-SE-depot: Hgap(right of barracks, left of depot) is (7 10) = 17, Vgap(bottom of barracks, top of depot) is (15 10) = 25.
barracks-SW-depot: Hgap(left of barracks, right of depot) is (16 9) = 25, Vgap(bottom of barracks, top of depot) is (15 10) = 25.
barracks-NW-depot: Hgap(left of barracks, right of depot) is (16 9) = 25, Vgap(top of barracks, bottom of depot) is (8 5) = 13.
Bit of a Numberwang, but with these numbers and the zealot's size, it should be possible to find a formula that matches the zealot's observed behavior. After some failures, I tried taking half of each gap and adding them:
corner gap = (Hgap / 2) (Vgap / 2)
But that's just another way to average the two values:
corner gap = (Hgap Vgap) / 2
So the averaged Hgap and Vgap sizes for the four barracks cases are:
barracks-NE-depot: (17 13) / 2 = 15
barracks-SE-depot: (17 25) / 2 = 21
barracks-SW-depot: (25 25) / 2 = 25
barracks-NW-depot: (25 13) / 2 = 19
Four potential corner gap sizes. The NE corner, with size 15, is the only one that a zealot(23 x 19) is too big to walk through. This seems to say that if we take the height, or more likely the smaller of a unit's height and width, we can know that it will fit through a corner gap if the unit size is less than or equal to the corner gap size.
Cgap = AVG(adjacent Hgap, adjacent Vgap)
Unit passes = MIN(unit height, unit width) <= Cgap
Testing the formula with a zergling
The graphic at the bottom of [2] shows some interesting zergling paths around depots. As before, the horizontal and vertical gaps can be compared to zergling size in the usual way to verify the simple cases. Let's plug the numbers into this formula for corner gaps.
zergling size: 16 x 16
depot gap T,L,B,R: 10, 10, 5, 9
When two buildings of the same type share a corner, all four corners have the same gap size. Also, there are only two configurations to calculate, as the other two are identical. And now that I've typed it out, I guess you can just calculate any one corner gap.
NW,SE: Hgap(10 9) = 19, Vgap(10 5) = 15
SW,NE: Hgap(10 9) = 19, Vgap(10 5) = 15
Both: (19 15) / 2 = 17
All four depot corner gaps are size 17, and a zergling with size 16 x 16 fits through all of them.
In searching for prior work in this area, I found these interesting links:
https://www.codeofhonor.com/blog/the-starcraft-path-finding-hack
https://dke.maastrichtuniversity.nl/m.winands/documents/CIG2018_157.pdf
Regarding that last one, a vulture's size is 32 x 32, and a pylon's corner gap is 31.
All feedback welcome, especially if anyone can find a case that proves me wrong! Feel free to repost this anywhere you like. No credit necessary.
GLHF!
(Edited for formatting)
Edit a few days in: I was able to chat with some folks who’ve been at this much longer than I have, and I may have been overthinking it. While the above seems to yield the correct answer, so does simply saying “If the unit can pass through either of the two gaps that make up this corner, then the unit can pass through this corner.”
I very much hope that this bears out further testing, as it’s pretty much the simplest equation I can imagine.
Subreddit
Post Details
- Posted
- 3 years ago
- Reddit URL
- View post on reddit.com
- External URL
- reddit.com/r/broodwar/co...