First part of this series | Previous | Next | Index

In the last part I implemented a threat map for visible units. For unseen units, the problem is actually a little bit different. My intention is that I should store the threatened positions within range of the last known location of the enemy unit. Things that are different this time:

• The time of the recording matters. The more time passed since I recorded the threatened positions, the more likely that they are no longer there. After enough time, I should reset this. Finding the “enough time” is not trivial, though.
• If I see the unit anywhere else, I should immediately clear up the previous threatened positions.
• I should record the threatened areas regardless of the unit’s position.

With all that, I decided to have a different collection for storing these positions, since the triggers for manipulating it are different.

With these in mind, I added a HashMap to the ThreatPosition class. The key is the unit’s ID, the value is the frame when the threat recording happened. The difficulty here is that one position can be threatened by multiple units. I don’t want to change the ThreatPosition class, and I don’t want to iterate through it too many times either.

//Doesn't matter if it was air or ground threat.
  private HashMap<Integer, Integer> threatTime = new HashMap<>();
//Renamed stuff for clarity in the main class
	public static HashMap<WalkPosition, ThreatPosition> activeThreatMap = new HashMap<>();
	public static HashMap<WalkPosition, ThreatPosition> threatMemoryMap = new HashMap<>();

So what’s the quickest way to keep track of the threatened positions in the threaMemoryMap? The answer is, of course, another map. Let’s just store the sets of walkpositions by unit IDs, and if I need to remove them, I can get them in O(1) time.

So, the codez.

		public void addToThreatMemory(Unit unit) {
		if (unit.getGroundWeapon() != null && !(unit.getGroundWeapon().type() == WeaponType.None)) {
			int hrange = unitStatCalculator.weaponMaxRange(unit.getType().groundWeapon());
			groundwps = Cartography.getWalkPositionsInRange(unit, hrange);
		}

		if (unit.getAirWeapon() != null && !(unit.getAirWeapon().type() == WeaponType.None)) {
			int hrange = unitStatCalculator.weaponMaxRange(unit.getType().airWeapon());
			airwps = Cartography.getWalkPositionsInRange(unit, hrange);
		}

		for (WalkPosition wp : groundwps) {
			ThreatPosition threatPosition = threatMemoryMap.getOrDefault(wp, new ThreatPosition());
			threatPosition.getGroundThreats().putIfAbsent(unit.getID(), unit.getGroundWeapon());
			threatPosition.getThreatTime().put(unit.getID(), frameCount);
			threatMemoryMap.putIfAbsent(wp, threatPosition);

		}

		for (WalkPosition wp : airwps) {
			ThreatPosition threatPosition = threatMemoryMap.getOrDefault(wp, new ThreatPosition());
			threatPosition.getAirThreats().putIfAbsent(unit.getID(), unit.getAirWeapon());
			threatPosition.getThreatTime().putIfAbsent(unit.getID(), frameCount);
			threatMemoryMap.putIfAbsent(wp, threatPosition);
		}

		TreeSet<WalkPosition> allWps = groundwps;
		allWps.addAll(airwps);
		threatenedWPsByIDs.put(unit.getID(), allWps);
	}
	//On unit show
	public void removeFromThreatMemory(Unit unit) {
		for (WalkPosition wp : threatenedWPsByIDs.get(unit.getID())) {
			threatMemoryMap.get(wp).getGroundThreats().remove(unit.getID());
			threatMemoryMap.get(wp).getAirThreats().remove(unit.getID());
			threatMemoryMap.get(wp).getThreatTime().remove(unit.getID());
		}
	}
//onUnitShow
	public void removeFromThreatMemory(Unit unit) {
		if (threatenedWPsByIDs.containsKey(unit.getID())) {
			for (WalkPosition wp : threatenedWPsByIDs.get(unit.getID())) {
				if (threatMemoryMap.containsKey(wp)) {
					ThreatPosition tp = threatMemoryMap.get(wp);
					tp.getGroundThreats().remove(unit.getID());
					tp.getAirThreats().remove(unit.getID());
					tp.getThreatTime().remove(unit.getID());

					if (tp.getGroundThreats().isEmpty() && tp.getAirThreats().isEmpty()) {
						threatMemoryMap.remove(wp);
					}
				}
			}
			threatenedWPsByIDs.remove(unit.getID());
		}
	}

A bit convoluted, but gets the job done. Ah, also, one must be careful to only use this with enemy units (These kinds of derps always come out as a suprise). So, this is in a somewhat usable state now.

One problem that’s immediately obvious, is that I only update the threat memory with onOnitShow/Hide(). A unit can hide for a long time, and it’s threats will remain in the memory. Upon seeing the position where the unit was, we can safely concluded it has moved on, started a family and settled down and we should remove it’s positions. For this, we need to the position the threatener (is that a word?) occupied, and check it periodically.

For that, what else could we have than another map? Oh how I love thee!

First step is to store the position of the threats. BWAPI has a getBwMap().isVisible() method for checking visibility, so we can loop through that. Unit.getPosition() returns roughly the center of the unit – i think this is good enough for me. If that tile is visible, then I should just remove the fields from the threat memory – the unit is either destroyed, or somewhere else, and if I see it, that will be handled.

It’s relatively simple for now.

// the map - add on onUnitHide
public HashMap<Position, Integer> threatUnitPositions = new HashMap<>();
//add to OnFrame
	public void checkThreatMemoryPositions() {
		for (Position p :threatUnitPositions.keySet()) {
			if (bw.getBWMap().isVisible(p.getX(), p.getY())) {
				System.out.println("Position visible");
				removeFromThreatMemory(threatUnitPositions.get(p));
			}
		}
	}

Let’s test a little. Drawing the tiles in memory:

You can’t really tell from the picture, but it works. Now I think the issue of threat maps are finally done, and we can, you know, actually do something with it. Also, I should re-think my method names sometime, and maybe restructure them.

The most obvious thing we can do is just not walk into those areas. For scouting, that might be a great addition. Not picking any of those as a destination is an obvious upgrade, but this presents a very foreseeable problem.

Yeah, we still run through them. That might be what we want in a lot of cases – often we will have no other choice. Also, I plan to have something to calculate the damage taken if running through (For calculating runbys and the like). For now, I want to have a logic to completely avoid them.

The waffle matrix will have all shapes and forms. If it’s a convex form, I just calculate a triangle around it, so instead of one movement command, I give it two. Or am I?

Theoretically, yes… but this represents a quite large detour. I have to approximate this better with some kind of polygon. I can, of course, just “hug” the edges, but that’s the most amount of calculations. Also, while I work with WalkPositions, unit’s ranges are pixel-precision, and if I’m too close, I’ll probably get a shot/spit/blue ball of pain. One other thing is that there is a theoretical limit of commands that I can queue up for a unit, so I’d like to be wary of that.

Looking at the picture, the obvious solution for this path is a “half-hexagon”. That’s 3 move commands to reach my destination. Computing this have to be relatively fast, too.

The very first thing I need is to verify if the straight line between origin and destination intersects any threatened positions. This is a well known problem, with known solutions. Yet again, we have to use math to achieve our goals – these are dark times.

I digged around a lot, and the thing with the least amount of operations would be generating (the coordinates of) the WalkPositions between the two points in a rectangle, then checking if the line between the two points. This will be done by checking each side of the WalkPosition, essentially just comparing line segments. I will write the technical details on the next post, this is enough thinking for today – programming coordinate geometry is where I draw the line.