(This is an ongoing series. I’m referring to things I did in the previous installment. If you’re new to this, I recommend starting at the first episode. This part is somewhat enjoyable without doing that, though.)

First part of this series | Previous | Next | Index

After recovering from the bamboozle, I decided to work on some other areas of the pathfinding. There is still optimizations to be made, but they are just more of the same. I won’t be documenting that, because it’s boring at this point, and quite frankly, I’m getting tunnel vision about this problem. So for the time being, I’ll table it.

Let’s revisit the backlog. I made this excellent, production quality representation of a problem, which has truly stood the test of time:

So the problem is, we have a path in WalkPositions, which are usually smaller in size than our units. WalkPositions are 8×8 pixels in size. For example, a Zergling’s size is 16×16 px. Here is a list of all the unit sizes.

I also brainstormed a little before how to solve this. Basically, unit movement is done center-to-center, so if I issue a command, then the unit will position it’s center to the center of the tile.

The issue is further complicated by the fact that units are squares. I don’t mean that they are the cool kids who are groovy and tubular, but rather the space they occupy can be rectangle-shaped. And you got weird unit sizes like 21×23 for Hydralisks.

Fortunately, the Unit.getPosition() returns the center of the unit-rectangle. Not so fortunately, we have to keep in mind the unit’s facing. With long boiz units with larger sides, you may think that we could encounter the issue that just turning places the unit in the range of something. That is not the case, the unit’s dimensions stay the same, no matter it’s facing. One less issue to deal with.

For the first step, by getting the center, I can determine the edges and corners of the unit’s bounding rectangle. There is only two cases I need to handle, diagonal, and straight movement, the logic is the same. I’ll tackle straight position adjustment first.

I looked in the API a little, and there is actually an easier way to get a bounding rectangle for a unit. There is a getBottom(), getTop(), getLeft(), and getRight() methods, which are returning the unit’s bounds in that directions (x and y coordinates). Using these, finding out the corners is trivial. We might not actually need this.

        Position topLeft = new Position(unit.getLeft(), unit.getTop());
        Position topRight = new Position(unit.getRight(), unit.getTop());
        Position bottomLeft = new Position(unit.getLeft(), unit.getBottom());
        Position bottomRight = new Position(unit.getRight(), unit.getBottom());

Keep in mind that this is Position, not WalkPosition, so the resolution is one pixel here. The plan here is to find an answer to the question “Is there a one-unit wide path between these two WalkPositions”? The first thing to do is to check if the default movement is sufficient. Since we know that movement is center-to-center, we need to superimpose the unit rectangle into the target position, then draw lines between the corresponding corners. Like so:

And we don’t even need all 4 corner-to-corner lines, only 2 of them. As for which ones, that depends on the relative direction of the two rectangles.

There is a small issue, or rather, concern. In Brood War, there is no such thing as diagonal movement. A unit might appear to do so, but it’s always horizontal or vertical. The unit’s actual bounds can leave the borders denoted by the outer black lines by some pixels – probably. At the moment, I can’t confirm whether that will happen or not. But I do not care actually. My threat maps’ precision is WalkPosition, and I made it to be on the safe side, so if a unit’s range is even one pixel into a WalkPosition, that tile is considered threatened. And if despite that if a unit still gets damaged, well, shit happens, and I will cross that bridge when I come to it. And also, with the path given by JPS, I only do this with diagonally-adjacent WalkPositions anyway.

Onto the first sub-problem – where will be the unit’s bounds, if I place it’s center into the WalkPosition’s center? Now, you might remember that a WalkPosition’s dimensions are 8×8 pixels, where is the center of that?

After a little looking around, I realized that I’ve been working on wrong assumptions. The Unit class does not accept a WalkPosition as an argument – movement of a unit is indeed center-to-center, but I can only specify a Position object. This is good, and bad news, and more of the good this time. The WalkPosition class has a toPosition() method, which looks like this:

  public Position toPosition() {
    final int x = getX() * WalkPosition.SIZE_IN_PIXELS;
    final int y = getY() * WalkPosition.SIZE_IN_PIXELS;
    return new Position(x, y);
  }

Which returns the top-left corner of the WalkPosition – we can work with this just as well. In fact, I have just formed a new plan – let’s align the unit’s center into the four corners of the WalkPosition, and if any of them is a clear way forward, choose that. This will probably give us some false negatives, but not enough to care. The goal here is to have an algorithm that is right in the majority of the cases, not 100% – we can’t afford that, performance-wise.

Of course, the checking of positions should be done with primitives/arrays – most likely it wouldn’t be a bottleneck with objects, but any performance gain is welcome at this point. I feel like I’m repeating the arrays-performance thing a lot. I perhaps should have a mascot for this.

Now, for superimposing the unit on a corner (That sounds like management slang used by pimps), I need to know where the unit’s boundaries will be. And since unit sizes are sometimes even numbers, I don’t know the exact center of them, I might be one pixel off. Which doesn’t seem like a big deal anyway, but meh, might as well do it. It’s very simple:

        int unitX = unit.getPosition().getX();
        int unitY = unit.getPosition().getY();
        int leftOffset = unitX - unit.getLeft();
        int rightOffset = unit.getRight() - unitX;
        int topOffset = unit.getTop() - unitY;
        int bottomOffset = unitY - unit.getBottom();

With those, I can find the new corners. Now, for the drawing lines part – I previously encountered that problem back when all the madness started.

I already have the the getWalkPositionsOnLine() method, and that is something that perfectly fits my use case. The legends are true, reusable code exists! The broad plan for the algorithm is the following:

        Position topLeft = new Position(unit.getLeft(), unit.getTop());
        Position topRight = new Position(unit.getRight(), unit.getTop());
        Position bottomLeft = new Position(unit.getLeft(), unit.getBottom());
        Position bottomRight = new Position(unit.getRight(), unit.getBottom());

        int unitX = unit.getPosition().getX();
        int unitY = unit.getPosition().getY();
        int leftOffset = unitX - unit.getLeft();
        int rightOffset = unit.getRight() - unitX;
        int topOffset = unit.getTop() - unitY;
        int bottomOffset = unitY - unit.getBottom();

        //Top left corner of the target position
        int targetX = target.toPosition().getX();
        int targetY = target.toPosition().getY();

        Position newTopLeft = new Position(targetX-leftOffset, targetY-topOffset);
        Position newTopRight = new Position(targetX+rightOffset, targetY-topOffset);
        Position newBottomLeft = new Position(targetX-leftOffset, targetY + bottomOffset);
        Position newBottomRight = new Position(targetX+rightOffset, targetY + bottomOffset);

        Set<WalkPosition> occupiedPositions = new HashSet<>();
        occupiedPositions.addAll(getWalkPositionsOnLine(topLeft, newTopLeft));
        occupiedPositions.addAll(getWalkPositionsOnLine(topRight, newTopRight));
        occupiedPositions.addAll(getWalkPositionsOnLine(bottomLeft, newBottomLeft));
        occupiedPositions.addAll(getWalkPositionsOnLine(bottomRight, newBottomRight));
        for (WalkPosition wp :occupiedPositions) {
            if (isUnderThreat(true, wp, true, true)) {
                //Exclude
            } else {
                return; //Some useful thing
            }
        }

This, but for each new corner. I didn’t finish it, because well, it’s not terribly optimized, it uses objects and shit, almost if like the language would be oriented around those, or something. So instead of objects…

*courtesy of Dan

Yes, arrays. Maybe. Mostly primitives. Maybe Performance Bob should have a friend called Patrick Primitive (although I’m sure that name is taken by the lead singer of some Irish punk band). Anyway, here is the glorious, full, and exhausting to read code.

    public boolean canUnitPass(Unit unit, WalkPosition target, boolean ground, boolean useActiveThreatMap, boolean useThreatMemory) {
        
        int unitX = unit.getPosition().getX();
        int unitY = unit.getPosition().getY();
        int leftOffset = unitX - unit.getLeft();
        int rightOffset = unit.getRight() - unitX;
        int topOffset = unit.getTop() - unitY;
        int bottomOffset = unitY - unit.getBottom();

        int targetX = target.toPosition().getX();
        int targetY = target.toPosition().getY();

        int newTop =  targetX-leftOffset;
        int newLeft = targetY-topOffset;
        int newBottom = targetY + bottomOffset; 
        int newRight = targetX+rightOffset;
        
        if (isRectangleLinesUnthreatened(unit, newLeft, newRight, newTop, newBottom, ground, useActiveThreatMap, useThreatMemory)) {
            return true;
        } else { //Transform coordinates to top right of target position
            newLeft = newLeft+8;
            newRight = newRight+8;
        }
        if (isRectangleLinesUnthreatened(unit, newLeft, newRight, newTop, newBottom, ground, useActiveThreatMap, useThreatMemory)) {
            return true;
        } else { //Transform coordinates to bottom right of target position
            newTop = newTop+8;
            newBottom = newBottom+8;
        }
        if (isRectangleLinesUnthreatened(unit, newLeft, newRight, newTop, newBottom, ground, useActiveThreatMap, useThreatMemory)) {
            return true;
        } else { //Transform coordinates to bottom left of target position
            newLeft = newLeft-8;
            newRight = newRight-8;
        }
        if (isRectangleLinesUnthreatened(unit, newLeft, newRight, newTop, newBottom, ground, useActiveThreatMap, useThreatMemory)) {
            return true;
        }        
        
        return false;

    }
    
    public static boolean isRectangleLinesUnthreatened(Unit unit, int newLeft, int newRight, int newTop, int newBottom, boolean ground,  boolean useActiveThreatMap, boolean useThreatMemory) {
        if (!isLineUnderThreat(unit.getLeft(), unit.getTop(), newLeft, newTop, ground, useActiveThreatMap, useThreatMemory)
                && !isLineUnderThreat(unit.getRight(), unit.getTop(), newRight, newTop, ground, useActiveThreatMap, useThreatMemory)
                && !isLineUnderThreat(unit.getLeft(), unit.getBottom(), newLeft, newBottom, ground, useActiveThreatMap, useThreatMemory)
                && !isLineUnderThreat(unit.getRight(), unit.getBottom(), newRight, newBottom, ground, useActiveThreatMap, useThreatMemory)) {
            return true;
        }
        return false;
        
    }

    public static boolean isLineUnderThreat(int p1X, int p1Y, int p2X, int p2Y, boolean ground, boolean useActiveThreatMap, boolean useThreatMemory) {
        //Get the "big rectangle"
        int left = Math.min(p1X, p2X);
        int top = Math.min(p1Y, p2Y);
        int right = Math.max(p1X, p2X);
        int bottom = Math.max(p1Y, p2Y);

        int leftWpPos = left / 8;
        int rightWpPos = right / 8;
        int topwpPos = top / 8;
        int bottomwpPos = bottom / 8;

        for (int i = leftWpPos; i <= rightWpPos; i++) {
            for (int j = topwpPos; j <= bottomwpPos; j++) {
                if (doIntersect(i * 8, j * 8, i * 8 + 8, j * 8, p1X, p1Y, p2X, p2Y)   //top
                        || doIntersect(i * 8, j * 8, i * 8, j * 8 + 8, p1X, p1Y, p2X, p2Y)   //left
                        || doIntersect(i * 8 + 8, j * 8, i * 8 + 8, j * 8 + 8, p1X, p1Y, p2X, p2Y)   //bottom
                        || doIntersect(i * 8 + 8, j * 8, i * 8 + 8, j * 8 + 8, p1X, p1Y, p2X, p2Y)   //right
                ) {
                    if ( isCoordsUnderThreat(ground, i, j, useActiveThreatMap, useThreatMemory) {
                        return true;
                    }

                }
            }
        }
        return false;
    }

Will this work? If you are not new to the blog, the answer may not surprise you. I dunno lol. I will find out, and debug this eyesore in the next episode.

Thank you very much for reading! If you liked this article, you can subscribe to my mailing list (in the box on the right), follow me on Twitter, or Facebook, or check the RSS feed on the top right.

Also, I’d like to share an affiliate link with you – I’m not directly sponsored by Hired.com, but I found their services useful. They are basically a very good unified job search platform, where you apply once (with salary request, and conditions), then employers can make offers. It is hidden from your current employer, absolutely free to use and if you get hired, you even get a (not insignificant) cash bonus. I encourage you to check them out. Here is the link.