First part of this series | Previous | Next | Index

So, I couldn’t resist, and uploaded my bot to the ladder. Predictably, it didn’t do very well, but it did won some games (Three of them, at the time of writing this). Some things I learned:

• I added 100 Zerglings to the build order. It seems like a lot, but I simply run out of build order items after a while, and the enemy just walked in my base. Also, since I didn’t make any overlords, I often ended up with a lot of unused money.
• Target prioritization is key, the a-move is really dumb sometimes. Bunker runbys are a thing, but if you run by a bunker just to attack a firebat, while still in range, that’s a questionable course of action. No big surprises here.
• For finding an enemy base, I don’t need to scout all the possible locations, just n-1 – if I don’t find the enemy there, there is only one place to go. This is somewhat specific to 4 Pool, but the concept itself is interesting.
• Scouting algorithm needs some checks if the position is actually reachable.

The last two points are kind of on hold, until the terrain analyzer is fully implemented in BWAPI4J. For the first point, I’ll make a StrategyPlanner class, which will adjust the build order. Eventually, I plan to place the learning logic there, too. 

For testing the StrategyPlanner, I just devised a logic that makes overlords, when I’m at max supply. But of course, the logic is not simple. Debugging my bot, I noticed that after reaching max supply, my available minerals are not getting over 50. Well, in hindsight, it’s obvious, I don’t do any kind of supply check before reserving resources.

There are multiple ways I can approach this. I don’t want to explicitly say I don’t want to reserve resources on full supply – the overlords are the best example, but also, I could envision a scenario when I know I will have the supply – for example, sending the army into battle, there will be losses, and I want to replace them as soon as humanly possible. (Well, botly, I guess)

So I just added a new parameter to PlannedItem, with a default false value. And enchanced our gööd öl’ Lööp with checking this.

private Boolean reserveOnFullSupply = false;
//Convenience method that is very convenient.
	public static boolean isAllSupplyUsed() {
		if (self.supplyTotal() <= supplyUsedActual ) {
			return true;
		}
		return false;
	}
//Lööp lögic
					if (pi.getReserveOnFullSupply() == false && isAllSupplyUsed()) {
						prereqsOk = false;
					}

I made a lot of things static. This bot is basically one entity, there won’t be multiple instances of it running controlling the same player, so if I’m not that object-oriented, it’s okay. I want to access a lot of methods/variables from other classes, and these mostly represent some game state, or the state of my plans.

Moving on, the StrategyPlanner is just very simple now.

    public void execute() {
        if (isAllSupplyUsed()
                && unitsInProduction.getOrDefault(UnitType.Zerg_Overlord, 0) == 0
                && supplyUsedActual <= 400) {
            PlannedItem overlord = new PlannedItem(PlannedItem.PlannedItemType.UNIT, UnitType.Zerg_Overlord, Main.supplyUsedActual, 1);
            overlord.setReserveOnFullSupply(true);
            plannedItems.add(overlord);
        }
    }

Looks good, let’s try it out.

Oh yes, morphing an overlord is not happening on the same frame, probably. I need a way to keep track if I already planned some overlords.

First I thought of just overriding the add/remove methods of the PriorityQueue, but in the end, I might need to check every fields of the added items, so might as well just check the queue itself. 

  if (isAllSupplyUsed()
                && unitsInProduction.getOrDefault(UnitType.Zerg_Overlord, 0) == 0
                && supplyUsedActual <= 400) {
            PlannedItem overlord = new PlannedItem(PlannedItem.PlannedItemType.UNIT, UnitType.Zerg_Overlord, Main.supplyUsedActual, 1);
            overlord.setReserveOnFullSupply(true);
            boolean isAny = plannedItems.stream().anyMatch(p -> p.getUnitType().equals(UnitType.Zerg_Overlord)
                    && p.plannedItemType.equals(PlannedItem.PlannedItemType.UNIT)
                    && p.getSupply().equals(overlord.getSupply()) && p.getImportance() == 1);
            if (!isAny) {
                plannedItems.add(overlord);
            }
        }

Getting convoluted. But tested out, and it seems to work – It will have to do for now.

With the pathfinding, I added one more check from BWEM to ZerglingManager.

  if (!Main.scoutTargets.contains(ti.getTile()) && ti.isWalkable()
                        && !Main.map.GetPath(unit.getPosition(), ti.getTile().toPosition()).isEmpty()) {
                            scoutingTarget = ti.getTile();
                            Main.scoutTargets.add(ti.getTile());
                            break;
                        }

Combat simulation is a very big topic. There are some existing combat simulators, which predict a battle’s outcome, the brilliantly named libraries:  C++ fap (Fast Approximation), and  Jabbo’s JFAP. There is also ASS from Bytekeeper. No, we are not juvenile at all.

Let’s just take one step back, and analyse the problems the lings have. 

• Anyone who played Brood War surely encountered a zergling pile-up. Basically, the units attack in a line, while.
• Attacking one by one, after being born, with no concept of squads, or any grouping whatsoever. I mean, I enjoy Bud Spencer&Terrence Hill movies, where the mooks attack one by one, but I’d like to be on the winning side on this.

Pathfinding is a very complex problem, again, even though we only have to do it in 2D. There are excellent articles about why and how BW pathfinding works, one by a developer working on it, and another one that is just good. 

BWEB has some pathfinding, but before I do that, I’d like to reinvent the wheel. Here is a quote from the second article:

“Each time it travels to a new square, it asks “is the next square along the path occupied?” If the answer is “no,” the unit keeps moving along the path. If the answer is “yes,” the unit waits a fraction of a second, and checks again. “

So every unit is only aware of it’s own location. But can one unit know it’s full path? If it does, then based on the unit’s speed, we can probably calculate which tile it will occupy on which frame. Then, we can use that for the second unit to calculate their path, and so on. I’m not sure this is the way to approach it, but experimenting can’t hurt. 

My first was just to draw a line where the unit will move, and use the GetPath() BWEB provides. It turns out, BWEB – rightfully – optimizes this out a little, so i get things like this:

Finding out which tiles (Positions, the smallest terrain unit) the unit occupies is actually not too hard. Finding out which tiles WILL the unit occupy is absolutely fucking terribly complicated, and it turns out, I can’t just, like, do that. Seriously, I probably should work with OpenBW about this, and dig around in C++ code, which I’m not ready for.

Bearing all that in mind, I’ll just outline my plans here, and implement them. It’s actually good sometimes to hash out ideas first, instead of coding like a madman. Just sometimes, please don’t throw rocks at me.

My basic algorithm would be the following: Let’s say I want to micro a bunch of biopuppers zerglings, and I’m less than satisified with the conga line approach of theirs. For individual pathfinding, ther are a lot of great algorithms already, like A*, or JPS.  I do that for one ling, then store the tiles occupied by it, along the (predicted) frame number, then exclude those from the next ling’s search. 

Another thing I would like to do are formations. The obvious one is the concave, since melee units are very dependent on surface area they can get, especially zerglings, who tend to die quick. I’d also experiment with loose grids for avoiding tank/mine hits. This is something a human can’t really do, but a bot has effectively infinite APM for it. 

Formations for flying units are presumably easier, since I don’t have any terrain constraints. The mutalisk deathball is a tried and true formation, but I’m not sure it’s necessary 100% of the time. And scourge could certainly benefit from the loose formation, as they tend to group up and die quickly to corsairs. 

A big topic is threat-aware pathfinding. A lot of bot games consist of units moving in and out of range of some enemy (usually a siege tank), and that’s detrimental to the unit’s longevity.

Some preparations can be done for this. I store enemy buildings, but not much about enemy units. 

Let’s make an EnemyUnitInfo class, which contains the “last known of” values of enemy units. This is necessary, since I can’t access the enemy Unit object when I don’t have vision of it. Let’s consider what fields I have to store:

• Hp/shields. This is obvious.
• Last known position.
• Weapons and armor level, and weapon range. Some units’ range changes with upgrades. 
• Unit type

From these info, I can make a map of threatened positions, which I want to avoid. I need to keep the air and ground threats separate. 

A good question is, when to update this? When enemy units are visible, I can just access their objects as needed, and don’t need to update everything every frame. On the other hand, I need to keep unseen units in mind when writing pathfinding/exploring logic. That has it’s own problems as well, since units can, well, move around and shit. So let’s just store the frame when I last saw the unit, and figure out, how to weigh that in later. 

Something like this:

public class EnemyUnitInfo {

    private UnitType type;
    private Weapon airWeapon;
    private Weapon groundWeapon;
    private int hp;
    private int shields;
    private int energy;
    private Position lastPosition;
    private int frameLastSeen;

I think this is enough for this post – it was a little more philosophical than usual, and again, I touched a lot of subjects. 

Thanks for reading! If you would like to be notified of updates on the blog, just subscribe with your e-mail in the box in the right column.