Creating a Starcraft AI – Part 8: Making a threat map

First part of this series | Previous | Next | Index

I decided to go forward with working on the threat map.

HashSet<Unit> enemyUnits = new HashSet<>(); //Currently visible enemy units
HashMap<Integer, EnemyUnitInfo> enemyUnitInfo = new HashMap<>(); //"Last seen" info 

BWAPI has the onUnitHide(), and onUnitShow() methods for basically exactly this. So on show i’ll add the unit to the currently visible ones, and on hide I’ll remove them from there and store their last known state. 

//To onUnitShow
if (!unit.getType().isNeutral()) {
				if (unit.getType().isBuilding()) {
//(...)
} else {
					enemyUnits.add(unit);
				}
//To onUnitHide
enemyUnits.remove(unit);
			if (!unit.getType().isBuilding()) {
				if (enemyUnitMemory.containsKey(unit.getID())) {
					enemyUnitMemory.get(unit.getID()).update(unit.getType(), unit.getAirWeapon(),
							unit.getGroundWeapon(), unit.getHitPoints(),
							unit.getShields(), unit.getEnergy(), unit.getPosition(), frameCount);
				}
				enemyUnitMemory.put(unit.getID(),
						new EnemyUnitInfo(unit.getType(), unit.getAirWeapon(),
								unit.getGroundWeapon(), unit.getHitPoints(),
								unit.getShields(), unit.getEnergy(), unit.getPosition(), frameCount));
			}
		}

You can guess what the update method does. So far so good. So much codez. 

Képtalálat a következőre: „it's beautiful cat”
Yes, I’m still using lolcats in 2018.

The immediate usage of this will be in my threat map. How to design one?

Well, we can just consider the ranges of the units’ weapons, and have an “overlay” over the map with the threatened areas. Or two, since we would like to handle air and ground threats separately. For mere mortals, this could be good enough, but I like overdoing things. 

How about we don’t just store the positions, but the potential damage that can be received there? Some quality sketches below, courtesy of Microsoft Paint. Consider Mr. Hydralisk.

His name is Gary.

He can spit hurting juice to a certain range. More, if he’s upgraded.

Fig. 2: Spitting the moist zerg juice

So we add the affected tiles to the threat map. But let’s say, I want to do a runby. Gary is on hold position, because he is lazy. I must absolutely pass the affected area to scout something behind him. If I do it with a drone, it will probably die, because it’s a useless fucking hovercrab it’s weak. An overlord, however, can easily survive the Garyturret. So what if we store the expected damage with the tile positions?

Obviously, for every tile, not just, like, ten. Also, you can’t really tell, so I’m making sure you know that I used comic sans.

This can be used to calculate runbys too. But this damage only occurs in every n frames, which we know. I have two options here. 

  • Add another variable to the threat map, which tracks when the unit last attacked, and disables the threatened fields until the weapon cooldown passes. 
  • When a unit wants to pass through threatened areas, calculate how much time it would take to travel, and how much damage will it receive. So I can add “If (willBeDed) {dontGoThere}” type logic.

In both cases, I’d want to store at least some info about the unit that’s threatening. 

At first glance, the second option seems more convincing – somewhat less stuff to store, and I just calculate stuff on demand. But keep in mind that in most cases, there are multiple units fighting. I want to calculate “how many units will get there to fight” kind of things.

Also, I definitely need to consider the damage type. I’m not sure I should handle splash damage here (I definitely want to handle that eventually)

With the cooldown, a great concern is that there is no onUnitAttack() method. We can, however, have the Unit.isAttacking(), and Unit.getGroundWeapon.cooldown() methods. So check enemy units, if it’s attacking, then adjust the threat map with the cooldowns. We can sneak in some optimizations (We know the cooldowns, we will check on the unit when it has reached 0).

Oh, also, with units that are mobile, the longer we didn’t see them, the bigger the chance that they are no longer a threat in some area. This has many dimensions, some units are less likely / slower to move (Siege tanks, for example). “Forgetting” threats, and handling threatened areas by unseen units need careful consideration – I saw countless matches when units wander in and out of tank range, because probably some timer reached zero. 

I have no idea if storing and keeping track of all this is feasible. Only one way to find out.

//Something like this.
public class ThreatPosition {

    private int x,y;
    private Integer threatenedById;
    private boolean air;
    private boolean ground;
    private Weapon weapon;
    private Integer nextThreatFrame;

    @Override
    public boolean equals(Object obj) {
        ThreatPosition anotherPos = (ThreatPosition) obj;
        return this.x == anotherPos.getX() && this.y == anotherPos.getY();
    }

The equals() override is necessary, because the collections’ contains() method uses it to compare values, and i don’t want to store the same position multiple times. If I detect a threat, I store the position, with the info needed. If it’s already present, then I just update it (This check will occur when threat areas overlap) 

For start, I will remove and re-add the objects every frame. Let’s see if that’s feasible. 

Képtalálat a következőre: „one eternity later”

In short: It’s not bya long shot. Especially if you confuse Positions with WalkPositions, and calculate a threat for almost every pixel every time. Oh well. The game came to a screeching halt when I tried this out, mostly because I used sqrt to calculate distances. Several hundreds of thousands per frame, that can get expensive. I omit the code here, as it’s not important, and also, not particularly hard to write.

Okay, good news, there is definitely a lot to improve here. First of all, let’s use WalkPositions, which are 8×8 pixel sized tiles.

I also did a rethinking of the ThreatPositions. Since I mostly just want to know the weapon that is threatening me, I’ll just store those. I might extend that with the unit IDs in the future.

    private Integer x,y;
    private HashMap<Integer, Weapon> groundThreats = new HashMap<>();
    private HashMap<Integer, Weapon> airThreats = new HashMap<>();

So, let’s fill the map with positions. The bw.getBWMap.mapWidth() and height() functions are returning the sizes in TilePositions, which are 32×32 pixel large units. So we have to multiply that by 4, because math.

	public void setupThreatMap() {
		int widthWP = bw.getBWMap().mapWidth() * 4;
		int heightWP = bw.getBWMap().mapHeight()  *4 ;
		for (int w=0; w<widthWP;w++) {
			for (int h=0; h<heightWP;h++) {
				threatMap.add(new ThreatPosition(w*8, h*8));
			}
		}
	}

I wanted to debug this, so I tried to draw the grid. After debugging, rewriting, and checking for one-off errors, I had to find out the hard way, that there is a hard limit in BWAPI for drawing things. It is around 39378. Remember this number, it was measured in blood. 

Never forget

So, we shall presume for now, that even though we can’t draw it out in it’s full, majestic size, it will work, and contain the positions for a threat map. 

Then, let’s go forward with the update logic. What I need to find out, is if I see an enemy unit, which WalkPositions are in range of it’s weapons. Weapon ranges are measured in pixels, so we need to keep that in mind. So great, we just use some coordinate geometry to get positions in a radius, right?

Well, it would be, if units would occupy only one position, which they don’t. We actually have to do a radius around a box. Our wonderful and purple hero has a solution for this. It’s in Scala, so we have to adapt it a little.

There are two ways I can approach this.

  • First convert the unit’s occupied positions into WalkPositions, and then measure their weapon range from that rectangle.
  • Measure walkpositions from pixel rectangles.

I started working on the first version, but since unit sizes are not divisible by 8 in every case, this will be inaccurate. Regardless, a method to get walk positions occupied by a unit will be useful.

I created a Cartography class, because I like fancy names, also, map fuckery functions of the spatial calculation variety will deserve their own logical unit.

   public static List<WalkPosition> getOccupiedWalkPositionsOfUnit(Unit unit) {
        unit.getPosition();
        int leftPixelPos = unit.getPosition().getX() - unit.getType().dimensionLeft();
        int topPixelPos = unit.getPosition().getY() - unit.getType().dimensionUp();
        int rightPixelPos = unit.getPosition().getX() + unit.getType().dimensionRight();
        int bottomPixelPos = unit.getPosition().getY() + unit.getType().dimensionLeft();

        int offset = 0;
        int leftWpPos = leftPixelPos / 8;

        int rightWpPos = rightPixelPos / 8 + offset;
        int topwpPos = topPixelPos / 8;
        int bottomwpPos = bottomPixelPos / 8 + offset;

        List<WalkPosition> wps = new ArrayList<>();
        for (int i = leftWpPos; i <= rightWpPos; i++) {
            for (int j = topwpPos; j<=bottomwpPos; j++) {
                wps.add(new WalkPosition(i,j));
            }
        }
        return wps;
    }

As you can see, I’m not sure I need an offset – tests will have to be concluded.

I tested this out by drawing a 8*8 box for every occupied tile – it seems to be doing what I want.

HAHAHA WELCOME TO CRAB PRISON YOU FUCKS

The orange rectangle is the unit’s pixel position. So far, this seems okay. The next thing I need is the walkpositions within a unit’s radius. This one is a little more tricky.

When trying out the pixel-radius thing, I noticed that the sqrt calls were very slow, and I can’t make them fast enough. There are a lot of distance checks, which are essentially sqrt(x*x + y*y) > distance.

But by utilizing the power of elementary school mathematics, one can observe that this is the same as comparing x*x+y*y to distance squared, which we can do very fast.

    public static Set<Position> getPositionsInRadius(Position point, int radius) {
        int x = point.getX();
        int y = point.getY();
        HashSet<Position> positionsInRadius = new HashSet<Position>();
        for  (int i = x-radius; i<=x+radius; i++) {
            int distX = Math.abs(x-i);
            for (int j = y-radius; j<=y+radius ; j++) {
                int distY = Math.abs(y-j);
                int distsq = distX*distX + distY*distY;
                int radiussq = radius* radius;
                if (distsq <=radiussq) {
                    Position check = new Position(i,j);
                    positionsInRadius.add(check);
                };
            }
        }
        return positionsInRadius;
    }

On the other hand, if we want to work with ThreatPositions, this is far too much objects to handle. For experimenting, I tried it out, and it was fine up until the enemy had three marines. So yeah.. limited usefulness.

Kapcsolódó kép

With that, I’ll conclude today’s lesson this part – I’ll continue work on this problem. Thanks for reading!

Leave a Reply