First part of this series | Previous | Next | Index

Let’s continue with implementing the stuff from the last part. The main problem space I’d like to work on is scouting, and finding the enemy base. When I was writing my thesis, I took inspiration from from an excellent article, how to handle map exploring. I think it’s still a good baseline, so let’s implement it. TL:DR; We should have a heatmap, with TilePositions, which are aged regularly, visible tiles’ age set to 0. The scout is going to the tile with the highest importance first.

First, let’s pick a good data structure for storing our tiles, because it’s gonna be a FUCKHUEG quite large collection. Generally, we want to get the element(s) with the highest importance when scouting, and when updating (aging) the heat map, traversing as fast as we can. We can make the cost of getting the most important tile to close to O(1) by pre-ordering the collection. And sorting in general can be done in O(n log n). We also have a fixed size (Map size does not change during play). With all these considerations, I chose the TreeSet structure to represent our heatmap. We also need a custom comparator to sort the set. 

Or rather, TreeSet would be great if it would reorder it’s elements on modification – oops. Either I go with an ArrayList, and just call sort on it – that’s O(n) + O(n log n), or use a priority queue again – which is n*O(log n) for inserting, and O(1) for retrieving. Hmm, let’s go with that. The Computer Science Wizard is always watching. (Also, I found out about TreeSet after testing, so that’s some time wasted. Oh well.)

I also found out that PriorityQueue isn’t working the way I wanted either, so let’s just stick with ArrayList, and sort it. 

//Info we want to store about a tile
public class TileInfo {

    private TilePosition tile;
    private int importance;

    private boolean isWalkable;
//(...)
//The comparator
public class TileInfoComparator implements Comparator<TileInfo> {

    @Override
    public int compare(TileInfo x, TileInfo y) {
        return x.getImportance() < y.getImportance() ? 1 : -1;
    }
//Add this to onStart()
		scoutHeatMap = new  ArrayList<TileInfo>();
		//Build heatmap 
		for (int i=0; i<bw.getBWMap().mapWidth(); i++) {
			for (int j = 0; j < bw.getBWMap().mapHeight(); j++) {
				TileInfo ti;
				TilePosition tp = new TilePosition(i,j);
				ti = new TileInfo(tp, bw.isWalkable(tp.toWalkPosition()));
			}
		}
//And a very basic aging method
	public void ageHeatMap() {
		for (TileInfo ti : scoutHeatMap) {
			int i = ti.getImportance();
			if (bw.isExplored(ti.getTile())) {
				ti.setImportance(0);
			} else {
				ti.setImportance(ti.getImportance()+1);
			}
		}
	}

Let’s just debug the importance values of our map:

Sounds about right! Let’s improve this. I’d like to give different weights to the starting base locations, and expansions. For this, I have to have the concept of regions, or some kind of grouping for the tiles. I’m pretty sure that for the first few minutes, no enemy units will be in my base.

Let’s set the weight of the base locations to 3, expansions to 2, and any other positions  to 1. At the time I’m writing this, the pure BWEM JNI implementation is not finished in BWAPI4J, so some features have to wait. But we do have the Map.StartingLocations() method, which returns a few tiles. For the time being, we have to work with these. I added categories to the TileInfo class. 

//The little stuff we can use from BWAPI
	if (map.StartingLocations().contains(tp)) {
					ti = new TileInfo(tp, bw.isWalkable(tp.toWalkPosition()), TileInfo.TileType.BASELOCATION);
				} else {
					ti = new TileInfo(tp, bw.isWalkable(tp.toWalkPosition()), TileInfo.TileType.NORMAL);
				}
//Aging should weigh this accordingly
		weight = 3;
				} else if (ti.getTileType() == TileInfo.TileType.NATURAL) {
					weight = 2;
				} else if (ti.getTileType() == TileInfo.TileType.NORMAL) {
					weight = 1;
				}
				ti.setImportance(ti.getImportance()+weight);

Okay, now to the actual scouting orders. If I just select the highest priority tile, and assign that to the scout, that’s fine – but there are multiple tiles with the same priority. As long as there is one scout, that’s also acceptable. But my plan is to send one ling to each possible location, then as soon as they found a base, they demolish it kekeke.

Let’s approach this from the scout’s perspective. The scout shouldn’t pick a location if someone is already on the way. Also, if for some other reason, the tile becomes visible, the scout should pick another tile. There will be always more tiles, than scouts, so let’s just keep track of the target tiles. A HashSet is ideal for this, there shouldn’t be duplicates, and we don’t care about the order of the elements. We should add an element when we assing a scouting target, and remove it, if it becomes visible, or the scouting unit dies. 

Picking the target should be done in the unit’s manager. As of yet, no unit has a manager (A state of affairs I dearly miss in my professional life), so let’s add them. Keep in mind, that Zerglings have a weird unit transition, where one is morphed, and one is newly created – so onUnitMorph(), and onUnitCreate() both needs to be handled.

//Targets -that's in the Main class
public static HashSet<TilePosition> scoutTargets = new HashSet<>();
//UnitManager
public class UnitManager {

    protected TilePosition scoutingTarget;
    protected Unit unit;

    public UnitManager(Unit unit) {
        this.unit=unit;
    }

    public void execute() {

    }

    public void dieded() {
        if (scoutingTarget != null) {
            Main.scoutTargets.remove(scoutingTarget);
        }
    }
//ZerglingManager
 public enum Role{ SCOUT, FIGHT}

    private Role role;

    public ZerglingManager(Unit unit) {
        super(unit);
    }

    @Override
    public void execute() {
        if (this.role == Role.SCOUT) {
            if (scoutingTarget != null && Main.bw.isVisible(scoutingTarget)) {
                scoutingTarget = null;
            }

            if (unit.isIdle()) {
                while (scoutingTarget == null) {
                    for (TileInfo ti : Main.scoutHeatMap) {

                        if (!Main.scoutTargets.contains(ti.getTile()) && ti.isWalkable()) {
                            scoutingTarget = ti.getTile();
                            Main.scoutTargets.add(ti.getTile());
                            break;
                        }
                    }
                }
                //The actual scouting part
                unit.move(scoutingTarget.toPosition());
            }
        }
    }

Okay, let’s try it out. First, I forgot to add the ZerglingManager in the onUnitMorph(), so half of the lings were just laying on the biorug, but the others were drawing a nice… something on the minimap.

Codez.

if (unit.getType() == UnitType.Zerg_Zergling) {
				ZerglingManager zm = new ZerglingManager(unit);
				zm.setRole(ZerglingManager.Role.SCOUT);
				unitManagerMap.put(unit.getID(), zm);
			}

After that:

But if I let them run (Run free, you silly puppers), they will scout the same base over and over again. I did not consider if the base is explored already – but this is basically a matter of adjusting the weights of the heatmap. Sounds like something a neural network would be ideal for. But let’s not do that yet. 

Also, I accomplished my goal, which was finding the enemy base. My ling finally found the Barracks!

I mentioned keeping an enemy building memory before. So when a unit is spotted, I check it’s id, if it’s not present, I create a new info object, if it is, I update the fields of it, if necessary – mostly the position, but Zerg buildings can morph, so occasionally, the type too.

Some convoluted-looking logic below. The reason for the structure is that I will probably extend this in the future.  I created an EnemyBuildingInfo class with the unit’s type and position. I can’t just store the Unit object, because I can’t access it when I don’t have vision of the unit itself. So EnemyBuildingInfo represents “last known values of”). 

public void onUnitShow(Unit unit) {
		if (unit.getPlayer() == self) {

		} else {
			//Enemy
			if (!unit.getType().isNeutral()) {
				if (unit.getType().isBuilding()) {
					if (enemyBuildingMemory.containsKey(unit.getID())) {
						if (!enemyBuildingMemory.get(unit.getID()).equals(unit.getTilePosition())) {
							enemyBuildingMemory.get(unit.getID()).setTilePosition(unit.getTilePosition());
						}
					} else {
						enemyBuildingMemory.put((Integer) unit.getID(), new EnemyBuildingInfo(unit.getType(), unit.getTilePosition()));
					}
				}
			}
		}
//onUnitDestroy
//Same way, if not mine, and not neutral, then:
	if (!unit.getType().isNeutral()) {
				if (unit.getType().isBuilding()) {
					enemyBuildingMemory.remove(unit.getID());
				}
			}

Now, some quick logic for attacking the buildings: When the enemy building memory is not empty, all the lings should switch to attack mode, and just attack the first building’s position on the list. The position, because if they encounter enemy units, they should prioritize them – basically I’m using the game’s attack-move command. If the building is destroyed, they get a new target, as the list’s first element is a new one. 

I won’t write down this logic, because it’s very simple to figure out, and also, this is for just testing. But let’s just run it once. 

Woohoo! The jumpy doggos won!  (Well, against stock AI, but still)

Next time, maybe I’ll improve some pathing. Thanks for reading!

ps.: I uploaded the bot to the sscait ladder. So far, it has won a grand total of two games. I also managed to crash the ladder at first, so that’s an improvement.