(Whew, this post contains a lot of code. Well, I did say comprehensive!). Special thanks for Ankmairdor for the tremendous amount of help he provided with this part! I quoted him a few times (almost) verbatim, and he deserves a lot of pizza.
Index for the Comprehensive Guide posts
First, a little bit of extension to the previous section (Unit attributes).
Mineral and gas price: The resource cost required to build, train, or morph the unit. The resources are deducted at the moment of creation, or queuing up, so a unit heading to build/morph something might fail to do so when arriving, and not having enough resources.
Build time: The amount of frames required to build, train, or morph the unit.
Unit movement types
Unit movement is measured in pixels per frame. If a unit changes direction, it will perform a turn. The turn rate of the unit is a non-visible variable, and it’s the amount of degrees a unit can turn per frame. Unit graphics only have 32 directionss, and he game itself has 256 angles and BWAPI returns this in radians) This is also called a turn radius, which is a a little bit misleading, since this is an angle, not a radius.
There are basically three types of unit movements.
Iscript units: The first one is what most units have, called iscript units after how it is referred in the code (There is an almost incomprehensible file called iscript.bin. It is characterized as “essentially a machine language, and decompiles to about an assembly language”). If these units need to turn, they do it in place, and during turning, their speed is 0.
These units have a repeating sequence of movement speeds per frame. For example, Zerglings have the sequence listed as 2 8 9 5 6 7 2 which in-game behaves as 0 8 9 5 6 7 2 2 , repeating after the 8. When iscript units completely stop moving, the next move starts the sequence from the start, though the next move has to wait at least 2 frames before it can begin.
Based on this behavior, Ankmairdor describes the most frame-effective movement in practice as:
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 (…). 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.
The actual method that calculates the unit speed is the following (that’s why there is a difference in the numbers above) – this averages the speeds while running the iscript for the unit’s movement for 32 frames:
void update_unit_speed(unit_t* u) {
if (u->flingy_movement_type == 2) {
image_t* image = u->sprite->main_image;
if (!image) error("null image");
auto* script = image->iscript_state.current_script;
auto& anims_pc = script->animation_pc;
int anim = iscript_anims::Walking;
if ((size_t)anim < anims_pc.size() && anims_pc[anim] != 0) {
auto ius = make_thingy_setter(iscript_unit, u);
iscript_state_t st;
st.current_script = script;
st.animation = anim;
st.program_counter = anims_pc[anim];
st.return_address = 0;
st.wait = 0;
fp8 total_distance_moved {};
for (int i = 0; i < 32; ++i) {
fp8 distance_moved {};
if (!iscript_execute(image, st, true, &distance_moved)) error("update_unit_speed: image destroyed");
// This get_modified_unit_acceleration is very out of place, and
// it makes the stored flingy_top_speed value wrong. But BroodWar does it.
// It's probably a bug, but the value might not be used for anything
// significant.
total_distance_moved += get_modified_unit_acceleration(u, distance_moved);
}
auto avg_distance_moved = total_distance_moved / 32;
u->flingy_top_speed = avg_distance_moved;
}
} else {
u->flingy_top_speed = get_modified_unit_speed(u, u->flingy_type->top_speed);
u->flingy_acceleration = get_modified_unit_acceleration(u, u->flingy_type->acceleration);
u->flingy_turn_rate = get_modified_unit_turn_rate(u, u->flingy_type->turn_rate);
}
}Hovering units: Workers, Archons, Dark Archons, and Vultures are hovering units. These units have an acceleration phase before reaching their top speed, and likewise, they must decelerate if they want to stop – this only applies for far enough targets, of course. Determining what is far enough is governed by their halt distance, detailed below. Hovering units don’t trigger Spider Mines.
Flying units: These behave much like hovering unit (with acceleration and deceleration), except they have a behavior called repulse, where they try to stay apart from each other.
void increment_repulse_field(unit_t* u) {
if (!u_can_move(u)) return;
if (ut_building(u)) return;
if (unit_is(u, UnitTypes::Protoss_Interceptor)) return;
if ((u->repulse_flags & 0xf0) == 0) {
unsigned int v = lcg_rand(37);
u->repulse_direction = direction_from_index(v & 0xff);
v = (v >> 8) & 0xf0;
if (v == 0) v = 0xf0;
u->repulse_flags = v;
}
u->repulse_flags &= ~7;
u->repulse_index = repulse_index(u->sprite->position);
auto& v = st.repulse_field.at(u->repulse_index);
if (v < 0xff) ++v;
}
void decrement_repulse_field(unit_t* u) {
if (!u_can_move(u)) return;
if (ut_building(u)) return;
if (unit_is(u, UnitTypes::Protoss_Interceptor)) return;
auto& v = st.repulse_field.at(u->repulse_index);
if (v > 0) --v;
}These units have a repulse index attribute, that determines how much they drift apart.
bool movement_UM_Flyer(unit_t* u, execute_movement_struct& ems) {
if (u->sprite->position != u->move_target.pos) {
xy move_target = restrict_unit_pos_to_bounds(u->move_target.pos, u->unit_type, map_bounds());
if (move_target != u->move_target.pos) {
set_flingy_move_target(u, move_target);
u_set_status_flag(u, unit_t::status_flag_immovable);
}
}
update_unit_movement_values(u, ems);
bool being_repulsed = apply_repulse_field(u, ems);
ems.position = restrict_unit_pos_to_bounds(ems.position, u->unit_type, map_bounds());
finish_unit_movement(u, ems);
if (u_can_move(u) && !ut_building(u)
&& u->unit_type->id !=UnitTypes::Protoss_Interceptor) {
size_t index = repulse_index(u->position);
if (index != u->repulse_index) {
decrement_repulse_field(u);
increment_repulse_field(u);
}
if (being_repulsed) {
if (std::max(std::abs(u->move_target.pos.x - u->position.x),
std::abs(u->move_target.pos.y - u->position.y)) < 24) {
u->move_target.pos = u->position;
u->next_movement_waypoint = u->position;
}
}
}
return false;
}
size_t repulse_index(xy pos) {
size_t ux = pos.x;
size_t uy = pos.y;
ux /= 48;
uy /= 48;
return uy * game_st.repulse_field_width + ux;
}This is mostly noticeable when units are not moving. A well-known trick to override repulse is to group Mutalisks with an Overlord in a control group. Then the movement logic overrides the repulse. To be more precise, the repulse grid is made up from 48×48 pixel tiles, and each tile stores the strength of the repulse field (0-255. Each unit adds 1 strength to the repulse field which they belong to – this is determined by their center. If the strength of the field is 0 or 1, there is no effect. Up to 4 units can overlap and not repulse each other, if their center is belonging to a different tile. The direction of the repulse is semi-random. If the unit is closer than 32 pixels to the edge of the map, it resets, and the unit is forced to repulse away from the edge of the map (it is also reset when the unit is not within a strong enough repulse grid). In other cases, if the unit is not at its move target, the direction of the repulse will change every 8 frames. It will be an angle offset between 32 and 64 (which are StarCraft angle values, it translates to 45-90 degrees) from the direction of movement.
If the unit is not moving, the repulse distance is 0.5 pixel, otherwise it’s repulse field strength/16 + 0.25 pixels. Furthermore, there is a random factor involved, adding a value between -7 and +7 to the repulse distance. This will have a negligible effect in practice.
Repulsion stops when there is only one unit per repulse frame. Also, if the unit is subject to repulse while moving, and enters withing a 49×49 pixel rectangle of its move target, then the unit’s move target will be set to the unit’s current position. This is the explanation why a pack of bunched up air units will stop a little bit earlier than the position they were told to move.
Acceleration and deceleration: Both hovering and flying units have an acceleration value which expresses the rate they can change their speed. The deceleration, and acceleration rates are the same. Flying and hovering units must perform a mandatory deceleration if they want to stop. Hovering units are also stopped by collisions. Flying buildings and High Templars are the exeption, they don’t have a halt distance.
Halt distance: Flying and hovering units have a halt distance, which is the minimum distance that the unit needs to travel before stopping (from their full speed). Note that in BWAPI, there is also a value dependent on the unit type called halt distance, which is not the same as the one here, which is only used when the unit moves at top speed. Here is the code segment dictating the halt distance in the game code (not BWAPI):
fp8 unit_halt_distance(const flingy_t* u) const {
ufp8 speed = u->next_speed.as_unsigned();
if (speed == ufp8::zero()) return 0_fp8;
if (u->flingy_movement_type != 0) return 0_fp8;
if (speed == u->flingy_type->top_speed.as_unsigned() && u->flingy_acceleration == u->flingy_type->acceleration) {
return u->flingy_type->halt_distance;
} else {
return (ufp8::multiply_divide(speed, speed, u->flingy_acceleration.as_unsigned()) / 2u).as_signed();
}
}Halt distance also plays a part in choosing if the unit accelerates or decelerates. For accelerating:
int d = xy_length(u->next_movement_waypoint - u->position);
bool accelerate = false;
if (u->current_velocity_direction == u->desired_velocity_direction) accelerate = true;
else if (d >= 32) accelerate = true;
else {
fp8 turn_rate = u->flingy_turn_rate;
fp8 diff = fp8::extend(u->desired_velocity_direction - u->current_velocity_direction).abs();
unsigned int val = fp8::divide_multiply(diff * 2 + turn_rate - 1_fp8, turn_rate, u->next_speed).integer_part();
if (val * 3 / 2 <= (unsigned int)d) accelerate = true;
}Basically, the default is to decelerate, if the unit’s next waypoint is 32 or more distance away, or the unit is facing the right direction, then it may accelerate.
if (accelerate) {
if (u->flingy_movement_type == 0) {
if (!u_movement_flag(u, 0x20) || u->next_movement_waypoint != u->move_target.pos) {
if (!u_movement_flag(u, 0x10) || u_movement_flag(u, 0x40)) {
fp8 remaining_d = xy_length(to_xy_fp8(u->next_movement_waypoint) - u-> exact_position);
if (unit_halt_distance(u) >= remaining_d) accelerate = false;
}
}
}
}If a unit would accelerate, but the unit’s halt distance is equal or greater than the distance to the next waypoint, then it decelerates.
Unit collisions
Air units can stack basically indefinitely, although there is the gentle drifting-away behaviour that keeps them separated. For ground units, the intention for them is to not stack, and they will have problems performing most tasks if they do. Workers heading to resources or resource depots, or gathering from resources ignore collisions. The reasoning behind this is described in detail in the unit movement section. Otherwise a check is performed whether units can collide. Collision is mostly relevant for pathfinding, which has its own section.
bool unit_can_collide_with(const unit_t* u, const unit_t* target) const {
if (target == u) return false;
if (~target->pathing_flags & 1) return false;
if (u_no_collide(target)) return false;
if (u_status_flag(target, unit_t::status_flag_400000)) {
if (unit_target_is_enemy(u, target)) return false;
}
if (u_gathering(u) && !u_grounded_building(target)) {
if (!u_gathering(target)) return false;
if (u->order_type->id == Orders::ReturnGas) return false;
if (target->order_type->id != Orders::WaitForGas) return false;
}
if (unit_is(u, UnitTypes::Zerg_Larva)) {
if (!u_grounded_building(target)) return false;
} else if (unit_is(target, UnitTypes::Zerg_Larva)) {
return false;
}
return true;
}Larvae can’t collide with anything that is not a grounded building.
bool pathfinder_unit_can_collide_with(const unit_t* u, const unit_t* target, const unit_t* consider_collision_with_unit, bool consider_collision_with_moving_units) const {
if (target != consider_collision_with_unit
&& !consider_collision_with_moving_units) {
if (!unit_is_at_move_target(target)) return false;}
if (unit_is(target, UnitTypes::Special_Upper_Level_Door)) return false;
if (unit_is(target, UnitTypes::Special_Right_Upper_Level_Door)) return false;
if (unit_is(target, UnitTypes::Special_Pit_Door)) return false;
if (unit_is(target, UnitTypes::Special_Right_Pit_Door)) return false;
return unit_can_collide_with(u, target);
}Walling
A very important quirk of Brood War is the ability to wall off. This just means blocking the path for enemy ground units, preferably while shooting at them. This article explains the basics. To quote:
All buildings in StarCraft have a span of at least 2×2 matrices areas (64×64 pixels). However, even though the buildings appear to fully occupy the area as you are choosing where to build them, the vast majority do not. They have gaps.
Players have learned through trial and error what works and what doesn’t – I will try to shed some more light on the matter. When placing buildings, they need to conform on the TilePosition grid. However, when considering unit movement, their actual pixel size is considered. Buildings tend to be centered on their tiles, but that’s not always the case. Consider this image:
The green mesh is the occupied TilePositions (32×32 pixel), while the red rectangle is the “actual” occupied position in pixels. This information is not readily available to players. BWAPI provides this, but walling is still not a trivial affair, even for bot authors.
Worker-specific mechanics
Resource gathering
A resource can be harvested by one unit at a time. Other harvesters will wait their turn. The actual harvesting for gas takes 37 frames, while harvesting minerals takes at least 75 frames, and in practice, it is usually 82 frames. However, before the resources can start being gathered or dropped off, there is a semi-random delay between 0-8 frames, which is further randomized every 150 frames. (more on that delay in the orders section) – in effect, mineral gathering usually takes more time than the stated value. This means that the worker will stop before the resource, and wait this amount before their order gets changed to actual gathering. You might have seen players frantically clicking on minerals, and swearing that improves gathering speed – they haven’t been entirely wrong, but the amount gained this way is minuscule. The relevant code segment:
if (u->order_process_timer) {
--u->order_process_timer;
return;
}
u->order_process_timer = 8;
switch (u->order_type->id) {
case Orders::MoveToGas:
order_MoveToGas(u);
break;
case Orders::WaitForGas:
order_WaitForGas(u);
break;
}There are also some queueing logic. Units always have a current order, and this can be WaitForGas/WaitForMinerals for waiting, and HarvestGas/MiningMinerals respectively. Every frame every unit will get its turn, and if the resource is free, the first unit with a waiting order will get to gather it. If it is occupied, the worker will add itself to the end of the waiting queue. When the current worker finishes, it will tell the first worker in the queue that its their turn. There is a few code segments describing the waiting for resources logic:
bool try_gather_resource(unit_t* u, unit_t* target) {
if (target->building.resource.is_being_gathered) return false;
target->building.resource.is_being_gathered = true;
u->worker.gather_target = target;
u->worker.is_gathering = true;
if (u->order_type->id == Orders::WaitForGas) {
queue_order_front(u, get_order_type(Orders::HarvestGas), {target->sprite->position, target});
} else {
queue_order_front(u, get_order_type(Orders::GatheringInterrupted), {});
queue_order_front(u, get_order_type(Orders::MiningMinerals), {target->sprite->position, target});
}
order_done(u);
return true;
}
//(...)
void wait_for_resource(unit_t* u, unit_t* target) {
u->order_process_timer = 0;
u->order_state = 2;
if (!try_gather_resource(u, target)) {
if (!u->worker.gather_target) {
u->worker.gather_target = target;
target->building.resource.gather_queue.push_front(*u);
}
queue_order_front(u, get_order_type(Orders::GatherWaitInterrupted), {});
}
}
//(...)
void gather_queue_next(unit_t* u, unit_t* resource) {
u->worker.is_gathering = false;
u->worker.gather_target = nullptr;
if (resource) {
resource->building.resource.is_being_gathered = false;
unit_t* next_unit = nullptr;
for (unit_t* queued_unit : reverse(ptr(resource->building.resource.gather_queue))) {
if (!unit_is_disabled(queued_unit)) {
if (queued_unit->order_type->id == Orders::WaitForGas || queued_unit->order_type->id == Orders::WaitForMinerals) {
next_unit = queued_unit;
break;
}
}
}
if (next_unit) {
next_unit->worker.gather_target = nullptr;
resource->building.resource.gather_queue.remove(*next_unit);
remove_one_order(next_unit, get_order_type(Orders::GatherWaitInterrupted));
try_gather_resource(next_unit, resource);
}
}
}In practice, it is quite hard for a human player to gain any meaningful extra efficiency in the long run. With bots, there are a few techniques to improve that – but that’s not in the scope of this section.
Repairing
Terran buildings and mechanical units can be repaired by SCVs. The unit must not be under stasis. Repair resource cost is calculated based upon the unit’s purchase price, and an internal variable called hp_construction_rate. This variable is calculated by the following formula:
u->hp_construction_rate = (u->unit_type->hitpoints - u->unit_type->hitpoints / 10 + fp8::from_raw(u->unit_type->build_time) - 1_fp8) / u->unit_type->build_time;This variable is also the amount of hit points repaired per frame. So for example, a supply depot has 500 HP, the build time is 600 frames, so (500-50+600) -1) / 600 ~= 1.74 is the hp_costruction_rate, which is roughly 42 HP repaired per second.
The repair cost calculated the following way:
auto calc_repair_costs = [&]() {
int target_mineral_cost = target->unit_type->mineral_cost;
int target_gas_cost = target->unit_type->gas_cost;
int lowest_cost = target_gas_cost == 0 ? target_mineral_cost : std::min(target_mineral_cost, target_gas_cost);
if (lowest_cost) {
auto target_max_hp = target->unit_type->hitpoints;
auto hp_construction_rate = target->hp_construction_rate;
if (st.cheat_operation_cwal) hp_construction_rate *= 16;
time_cost = target_max_hp.raw_value * 3 / (lowest_cost * hp_construction_rate.raw_value);
if (time_cost) {
if (lowest_cost == target_mineral_cost) {
mineral_cost = 1;
gas_cost = target_gas_cost / target_mineral_cost;
} else {
mineral_cost = target_mineral_cost / target_gas_cost;
gas_cost = 1;
}
} else {
if (target_mineral_cost) {
mineral_cost = target_mineral_cost * hp_construction_rate.raw_value / (target_max_hp.raw_value * 3);
if (mineral_cost == 0) mineral_cost = 1;
} else mineral_cost = 0;
if (target_gas_cost) {
gas_cost = target_gas_cost * hp_construction_rate.raw_value / (target_max_hp.raw_value * 3);
if (gas_cost == 0) gas_cost = 1;
} else gas_cost = 0;
time_cost = 1;
}The time_cost is – in a somewhat counter-intuitive way – the number of frames between substracting the resource cost. If the time_cost is not zero, then the repair cost is calculated the follwing way:
| Unit mineral price < gas price? | Gas repair cost | Mineral repair cost |
|---|---|---|
| Yes | Gas price/mineral price | 1 |
| No | 1 | Mineral price/gas price |
If the time_cost is zero, the calculation is the following. This is most likely to happen in custom games, with modified values.
| Unit mineral price > gas price? | Gas repair cost | Mineral repair cost |
|---|---|---|
| No | 0 | Max((Mineral price*hp_construction_rate) / (max hp*3), 1) |
| Yes | Max((Unit gas price*hp_construction_rate) / (max_hp*3), 1) | 0 |
Adding SCVs increases the rate of repair the same amount for each SCV added, and increases the total repair cost a generally negligible amount. Unless the player is spamming repair, which results in a repair cost per SCV per click and slower repairs.
And that’s where I finish this article. Thanks for reading this code-heavy, and sometimes confusing. episode! If you liked the article, consider subscribe to the mailing list for updates, or following me on my social media channels, which are Facebook and Twitter!