First part of this series | Previous | Next | Index

I’m continuing with the actual thing I’d like to use, which is a map of threatened WalkPositions. I need a method for “all WalkPositions in range of a unit”.

A unit has a top, left, right, and a bottom position for it’s bounding rectangle. For first step, I’ll just add the range of the weapon to the unit’s coordinates, and get the WalkPositions from that bigger rectangle.

So far so good, but that’s not exactly what I want. There are 9 distinct parts of this rectangle, divided by the corners of the unit’s bounds.

Disregarding the vibrant colors, and glorious misalignment on the picture, it helps us to understand the problem. All areas are clearly identifiable by their coordinates relative to the unit’s bounds.

Areas 2,4,6, and 8 are within range, and we don’t need to perform distance calculations there. For 1,3,7, and 9 we need to compare different corners of the WalkPosition to the unit’s bounds.

For 5, one would assume, that occupied WalkPositions are always in range. This is – according to my knowledge – only false for deployed siege tanks. We will have to take minimum ranges into account later anyway.

So, as the picture suggests, there are still a lot of pixel-to-pixel distance comparisons to be made. This is a point I identified as something that slows the game down considerably.

So, with that in mind, I added a method to the Cartography class. I used the square distance calculation to speed up the comparisons.

   public static Set<WalkPosition> getWalkPositionsInRange(Unit unit, int radiusInPixels) {
        //Make a large rectangle of walkpositions
        int left = unit.getLeft() - radiusInPixels;
        int top = unit.getTop() - radiusInPixels;
        int right = unit.getRight() + radiusInPixels;
        int bottom = unit.getBottom() + radiusInPixels;

        int leftWpPos = left / 8;
        int rightWpPos = right / 8;
        int topWpPos = top / 8;
        int bottomWpPos = bottom / 8;

        int offset = unit.getRight() % 8;
        if (offset > 0) {
            rightWpPos++;
        }
        offset = unit.getBottom() % 8;
        if (offset > 0) {
            bottomWpPos++;
        }

        int radiusSq = radiusInPixels * radiusInPixels;

        System.out.println("left:" + left + " leftwp:" + leftWpPos);
        HashSet<WalkPosition> wps = new HashSet<>();
        for (int i = leftWpPos; i <= rightWpPos; i++) {
            for (int j = topWpPos; j <= bottomWpPos; j++) {
                if (i < unit.getLeft() / 8) {
                    if (j < unit.getTop() / 8) {
                        //Top left corner - compare to WP's bottom right
                        if (positionToPositionDistanceSq(unit.getLeft(), unit.getTop(), i * 8 + 8, j * 8 + 8) <= radiusSq) {
                            wps.add(new WalkPosition(i, j));
                        }
                    } else if (j > unit.getBottom() / 8) {
                        //Bottom left corner
                        if (positionToPositionDistanceSq(unit.getLeft(), unit.getBottom(), i * 8 + 8, j * 8) <= radiusSq) {
                            wps.add(new WalkPosition(i, j));
                        }
                    } else {
                        wps.add(new WalkPosition(i, j));
                    }

                } else if (i > unit.getRight() / 8) {
                    if (j < unit.getTop() / 8) {
                        //Top right corner
                        if (positionToPositionDistanceSq(unit.getRight(), unit.getTop(), i * 8, j * 8 + 8) <= radiusSq) {
                            wps.add(new WalkPosition(i, j));
                        }
                    } else if (j > unit.getBottom() / 8) {
                        //Bottom right corner
                        if (positionToPositionDistanceSq(unit.getRight(), unit.getBottom(), i * 8, j * 8) <= radiusSq) {
                            wps.add(new WalkPosition(i, j));
                        }
                    } else {
                        wps.add(new WalkPosition(i, j));
                    }

                } else {
                    wps.add(new WalkPosition(i, j));
                }
            }
        }
        return wps;
    }

//Helper method
    public static int positionToPositionDistanceSq(int x1, int y1, int x2, int y2) {
        int distX = x1-x2;
        int distY = y1-y2;
        int distsq = distX*distX + distY*distY;
        return distsq;
    }

Of course this required some trial and error to get right – like finding out about the offset, and such. As you can see, I compare different corners of the would-be created WalkPositions.

But in the end, I prevailed, and there is the result:

I tested it manually, and it seems alright. As a side note, I tried out my square distance method, and measured the performance with VisualVM. I compared it to the built-in getDistance() method. The benchmark was getting points in a 100 pixel radius. With some tinkering, I managed to get it quite fast.

Now back to the actual threat map. I don’t actually want to draw the threatened positions, of course. Also, I thought about this, and there are a few considerations

• CPU time is precious, I want to do as few calculations as possible. Meanwhile, storage and memory is plentiful, so I can cache a lot of stuff.
• The things I want to store: The position, the ground/air weapons it is threatened by, and the owners of these weapons.

So some optimizations for how to store the map.

public class ThreatPosition {

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

//The actual map
	public static HashMap<WalkPosition, ThreatPosition> threatMap = new HashMap<>();

So, first I tried caching all the positions, but I ran into the problem that I still need to remove positions that are no longer threatened – so I have to iterate through the quite large collection. This is not the way forward. So, let’s try it another way – starting with an empty map, and re-adding the threatened positions. This will only work properly for visible units, obviosly, but that’s a problem for later.

For benchmarking, I ran the method 400 times every frame. This was too slow. The absolute limit is 85 ms per frame, as per the SSCAIT guidelines.

This happened almost every time. Oops. Re-examining my code, I figured out that I used Sets, because I don’t want duplicates – but the code already makes sure that there are different positions (If it works correctly), and I’ll check the map anyway, so I don’t need a Set for this. My use case is mostly adding elements, and iterating through them, so an ArrayList seemed like a better fit. See this article for details.

I tried it out, and while I got some performance improvements, still when the unit count approached maximum, I got some long bois frames, and FPS drops. After sacrificing a goat to the Computer Science gods, I came upon a revelation. Since I reset the threatmap, and then add new elements, the array behind an ArrayList gets resized a lot, thus degrading performance. But worry not – I can use a LinkedList, which does not have this problem.

This was close to optimal, but there were still frames that took too long. I talked about this on Discord, and upon the suggestion of Yegers, and a certain rotten fish eater who shall remain unnamed, I tried out TreeSet with a custom comparator (For WalkPositions). This turned out to be the fastest solution. So the final method looks like this.

TreeSet<WalkPosition> airwps = new TreeSet<>();
	TreeSet<WalkPosition> groundwps = new TreeSet<>();
	public void maintainThreatMap() {
		threatMap = new HashMap<>();
		for (Unit unit : enemyUnits) {
			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 = threatMap.getOrDefault(wp, new ThreatPosition());
				if (unit.exists()) { //Unit can be killed in the meantime
					threatPosition.getGroundThreats().putIfAbsent(unit.getID(), unit.getGroundWeapon());
				}
					threatMap.putIfAbsent(wp, threatPosition);
			}

			for (WalkPosition wp : airwps) {
				ThreatPosition threatPosition = threatMap.getOrDefault(wp, new ThreatPosition());
				if (unit.exists()) { //Unit can be killed in the meantime
					threatPosition.getAirThreats().putIfAbsent(unit.getID(), unit.getAirWeapon());
				}
				threatMap.putIfAbsent(wp, threatPosition);
			}
		}
	}

For the TreeSet, I also added a custom comparator. Code is not important, as I don’t actually care about the ordering, and I only plan to use it here.

Finally, running the maintainThreatMap() every frame didn’t cause a major FPS drop (worst case scenario was around 35 FPS), and more importantly, too long frames. And I don’t actually need to check this every frame, but just doing it every n frames is the last step I wanted to do.

Another optimization I can do relatively easily is just not checking enemies that are too far away. Let’s say I have a magic number, for starters, the double of the longest range of all weapons. I keep track of the most left, right, top, bottom positions of my forces. This isn’t particularly hard to do, as I loop through my units when counting them, might as well keep track of a few more numbers. When updating the threat map, I simply don’t check the enemy unit’s threatened area if it’s too far away. (The idea is proposed by McRave, I just stole it). This probably saves some calculations most of the time.

//This to the countAllUnits() method
forcesLeft = Integer.MAX_VALUE;
		forcesTop = Integer.MAX_VALUE;
		forcesRight = -1;
		forcesBottom = -1;
//(...)
if (unit.getLeft() < forcesLeft) {
				forcesLeft = unit.getLeft();
			}
			if (unit.getRight() > forcesRight) {
				forcesRight = unit.getRight();
			}
			if (unit.getTop() < forcesTop) {
				forcesTop = unit.getTop();
			}
			if (unit.getBottom() > forcesBottom) {
				forcesBottom = unit.getBottom();
			}
//Our magic number

//And a simple method 
public boolean isUnitInThreatCheckRange_(Unit unit) {
		if (unit.getLeft()+THREAT_CHECK_RANGE < forcesLeft
				|| unit.getRight()-THREAT_CHECK_RANGE > forcesRight
				|| unit.getTop() + THREAT_CHECK_RANGE < forcesTop
				|| unit.getBottom() - THREAT_CHECK_RANGE > forcesBottom) {
			return false;
		}
		return true;
	}

Now, this is essentially a rectangle, so if I have units in all corners of the map, I don’t gain anything, and an especially bad use case is when I got units in a U shape – but I’d wager, most of the time it’s beneficial, and when it’s not, the overhead is negligible.

Implementing all this took longer than I expected – but now that I have threats, I can begin to do some threat-aware pathing.

But wait, this only deals with currently visible units. Now, a good example why is this not a good idea would be siege tanks on the high ground.

I think this is enough for this post – I’ll cover the rest in the next one.