archive by month
Skip to content

how far zerg creep spreads

I took a preliminary look at how far creep spreads from a hatchery. Here’s a picture from my first experiment.

distances of creep spread

The numbers on each tile are the distance from the hatchery, determined by hatchery->getDistance() and scaled to tiles instead of pixels. Tiles for which BWAPI::Broodwar->hasCreep() is true get orange numbers. Boxed tiles are unwalkable according to Steamhammer’s walkability map: A 32x32 tile is walkable if all its constituent 8x8 walk tiles are walkable, taking into account terrain and fixed neutral units only.

Creep spreads in an oval pattern, similarly to power from a protoss pylon. Of course creep spreads bit by bit, unlike the instantaneous power from a pylon, but at the start of the game the initial hatchery has its full spread of creep, so in that case we can ignore the spreading process.

After trying this on a variety of maps, including some irregular Blizzard maps, I found that the initial hatchery’s creep, though its outline seems a little odd, takes on a tile-for-tile identical outline on all maps. I’ll test further, but it looks as though I can predict the creep for the initial hatchery without much trouble: Hardcode one pattern of creep spread, match it to the hatchery location, clip it at the edges of the map, and trim away the minerals, geyser, and any terrain features that don’t allow creep. So far I haven’t tried a map where this method would give a wrong answer.

If it continues to look good, then an upcoming 1.4.x version of Steamhammer will be a little faster to find the bases of zerg opponents. Early game scouting units will definitively identify the occupied base when they see creep, and definitively identify an empty base when they don’t see creep that should be there.

Later versions will also have the ability to infer the existence of a zerg base by seeing creep later in the game. It’s strange to see bots pass in sight of creep and not realize what it means—“must keep looking, where is that last enemy base?” That feature will be a little more complicated. We don’t want to infer the existence of a base which was just destroyed, or get confused because outlying creep colonies of one base extend the creep as far as another base.

Next: Other near-term plans for Steamhammer.

Trackbacks

No Trackbacks

Comments

Jay Scott on :

Another feature I’ll have to implement eventually is replacing destroyed pylons so protoss can restore the function of unpowered buildings. I have 3 ideas: 1. Remember the pylon locations and put them back in the same place. Simple, but risks repowering buildings which are also destroyed. 2. Use a method similar to the creep spread method to figure out from scratch where to place pylons to repower buildings. This would happen only after the placement planner is written. 3. Look up whatever Skynet or some other protoss bot does, and do the same. It might be different.

jtolmar on :

In case it's handy for #2, OpenBW has the pylon range as psi_field_mask in bwgame.h. This is one quarter of the range.

Arrak on :

I lean towards memory method for replacement due to precise walling being important in PvZ. You can always check the power field before placement.

jtolmar on :

I really enjoy these writeups on deeper details of the game's mechanics. If you want another one, I've been trying to figure out: certain units move a different number of pixels based on their animation frame (from iscript.bin). The patterns for zerglings and dragoons are so lopsided that it would be worth stopping entirely for a frame if it would reset the pattern. I've tried stopping every N frames, but the unit's speeds end up being something completely off-pattern. How is the game preventing this? Is it possible to somehow reset the unit's animation counter without stopping it?

Ankmairdor on :

I've not seen any sign in the code that movement is affected by animation frames. Rather, nearly everywhere I've seen the animation is treated as fire-and-forget, with new animations simply replacing the old. The movement code is likely the most complicated code in the game, so I could have missed it. Also the numbered flags for movement really don't help the readability of the code. Speed inconsistencies can come from many sources. Depending on the movement type of the unit, turning affects speed in different ways. Slight changes in direction are handled differently than major changes in direction, which can cause unit to stop and turn in place. Pathfinding can be a nightmare even in simple open space. While issuing more commands can result in better performance than fewer commands, generally units pause for a frame when receiving commands so too many commands is definitely worse.

jtolmar on :

There are two movement systems. Hovering/flying units use flingy, and other units use iscript (technically both are involved either way; it's pretty convoluted). iscript uses iscript.bin, which is some sort of scripting language for setting units display frames, per-frame movement speed values, determining when damage is applied, and so on. If you dig through ancient modding tool sites, you can find icecc, which decompiles iscript. The zergling walk animation consists of move N pixels, wait a frame, display an animation frame, and so on with different movements and sprites. The sequence of movements is 2 8 9 5 6 7 2. If you use BWAPI's method to get a current unit's speed, you'll find that a zergling follows that pattern if you order it to move once or spam movement commands. Trying to stop every couple frames to shorten the animation gives weird numbers I couldn't make sense of. All of these experiments were before OpenBW came out, but, as you noticed, the relevant code is very convoluted. (The other interesting unit is the dragoon, which goes 4 6 8 8 2 2 6 6. Reavers are even more lopsided but it's all at the end of the cycle.)

Arrak on :

Some units cannot fully stop, like the zerg guardian, but instead decelerate, which I once tried writing deceleration code for. So perhaps they are entering deceleration animations when you stop.

Ankmairdor on :

Both units described are not floating units, so they go from stop to full speed and full speed to stop in a single frame. The script for WalkingToIdle for both units basically starts displaying the idle images of the unit.

Ankmairdor on :

Thanks for the info, I got icecc and took a look. It took a while to track stuff down because it's a lot like solving a Sudoku puzzle. iscript.bin is essentially a machine language, and decompiles to about an assembly language. I've looked further and found a number of things that will cause problems. The order system does not directly effect the unit sprite script for movement, instead the tail end of the pathfinding system executes the appropriate script. It issues the Walking script when a unit is starting movement and WalkingToIdle when stopping movement. Issuing a stop command simply changes the order and places the last waypoint at the current position so pathfinding concludes that it has reached the end of the movement. The script's program_counter(index of next script command) for Walking only resets when the type of script changes, which is part of why reissuing move commands actually has near no adverse effect during a movement. Again, the script runs last, which sets the next speed and runs until it hits a Wait; therefore, the speed of the first frame of movement being applied will always be zero for units with speeds set by iscript(sidenote: iscript unit speeds reset to zero when used). This means there is single frame delay in applying the script speeds. But the first frame of unit movement is actually the second script speed because the script runs twice: once when the pathfinding starts the Walking script and once during the standard unit sprite update. The speed of a unit is updated twice any frame with starting or stopping movement, but only once any frame between. This means that a zergling's actual speeds when starting are 0 8 9 5 6 7 2 2, and it repeats starting at the 8. Next is the problem of the sources of the variable number of zero movement frames until the unit starts moving(I usually get 5-7). Latency frames are generally consistent in localhost games(I have 2). Orders are updated at the end of the unit updates so we end up with one init-order frame. There is one frame of zero speed movement. When the user issues most orders the game sets #2 of the user_action_flags, which leads to UM_UIOrderDelay for 0-2 frames when an iscript unit starts a path. There is still some a bit of frame variability that I haven't tracked down, but I hit the limit of my interest on that.(1 frame unexplained for those that counted, as well as the crazy cases of only 3 or 4 zero movement frames) As far as weird speed values with N frame movement orders, I have assumed it to be combination of variable zero movement frames as well as a repeated speed-update during movement likely as a result of the interrupting command. In summary, iscript units are best optimized by smartly choosing paths where they can stay moving, sometimes even if that means pacing a bit. Stopping to turn can be a couple frames better than a full stop, so long as you aren't facing backwards to the direction you want to go and the next speed values when you want to leave aren't 2 2. Full stop to hold a position isn't bad so long as you are facing the right direction. The worst is repeated short movements of start and stop.

Jay Scott on :

Wow, the details are awesomely complicated. I’ll keep this discussion in mind when I finally get around to working on movement. But there are always more questions. What happens when a unit collides, when it hits terrain or another unit? Reducing these slowdowns is a big part of smooth movement.

jtolmar on :

Thanks for digging into this! The double frame updates were a big missing piece of the puzzle for me (do you think it's possible to trigger a double update without the unit actually stopping?). I tried to cancel animations using short movements (variants on ordering a zergling to move 35 pixels every 6 frames, so it should be stopping naturally just as it gets a new order) but it looks like there's always either the animation continues normally or there's a many frame delay. The only remaining idea I have is to try issuing an attack command, but I don't have a good test setup for that yet.

Ankmairdor on :

The only kind of stopping that won't tank zergling speed is a single frame of the zero speed from a hard turn, which doesn't effect animation(though technically zero speed is not a stop in game logic). This might be useful if optimizing turns, but not the current task. When the zergling stops there is a mandatory zero movement period of 2-4 frames. I tried with queued moves and 3 frame moves issued on the first frame of movement; both gave reliable results matching the limit as expected from the code, and were better than the move every N frames method. There does not seem to be other ways of triggering a double update without creating a zergling-building, zergling-bullet, or zergling-thingy(technical term. units, bullets, thingies) hybrid. The attack order is mostly equivalent to move in range of target, stop, attack, and repeat. The attack-move order is mostly equivalent to move to position and auto-attack stuff along the way. The patrol order is mostly equivalent to attack-move between positions. There is no difference in a movement started by move or attack orders. Thus none of these orders change movement in any relevant way. I'll be looking into unit collisions; despite how messy it looks I think digging into iscript movement has given me a good start.

Add Comment

E-Mail addresses will not be displayed and will only be used for E-Mail notifications.

To prevent automated Bots from commentspamming, please enter the string you see in the image below in the appropriate input box. Your comment will only be submitted if the strings match. Please ensure that your browser supports and accepts cookies, or your comment cannot be verified correctly.
CAPTCHA

Form options

Submitted comments will be subject to moderation before being displayed.