First part of this series | Previous | Next | Index

The last time, I was thinking about getting the WalkPositions on a line between two points. For this, I first create a rectangle with all the WalkPositions in between. Since the top left point of the map is the (0,0) point, for my rectangle, the top left coordinate will be the smallest of the x,y coordinates, and the bottom right is the largest.

Previously, I already wrote a getOccupiedWalkPositionsOfRectangle() method. I can just use this, and use the output, but that would make, like three objects I don’t need, and that’s clearly a waste of CPU cycles, precious resources of our planet, and frankly, human life.

Therefore I evaluate the WalkPosition squares before creating the objects. The four sides are four lines (line segments, if I’m being precise), and I need to check if they intersect with the main line I’m drawing. Upon much trying and failing, I resorted to a known algorithm. Turns out this math thing is kind of figured out for a while, and derping around for hours and trying to find some solution is not the most predictable route.

I used primitives for extra speed gainz, but otherwise, the code is basically unchanged. Yeah, it’s ugly.

 public static boolean onSegment(int px, int py, int qx, int qy, int rx, int ry)
    {
        if (qx <= Math.max(px, rx) && qx >= Math.min(px, rx) &&
                qy <= Math.max(py, ry) && qy >= Math.min(py, ry))
            return true;

        return false;
    }


    public static int orientation(int qx, int qy, int px, int py, int rx, int ry)
    {
        int val = (qy - py) * (rx - qx) -
                (qx - px) * (ry - qy);

        if (val == 0) return 0;  // colinear

        return (val > 0)? 1: 2; // clock or counterclock wise
    }


    public static boolean doIntersect(int p1x, int p1y, int q1x, int q1y, int p2x, int p2y, int q2x, int q2y)
    {
        // Find the four orientations needed for general and
        // special cases
        int o1 = orientation(p1x, p1y, q1x, q1y, p2x, p2y);
        int o2 = orientation(p1x, p1y, q1x, q1y, q2x, q2y);
        int o3 = orientation(p2x, p2y, q2x, q2y, p1x, p1y);
        int o4 = orientation(p2x, p2y, q2x, q2y, q1x, q1y);

        // General case
        if (o1 != o2 && o3 != o4)
            return true;

        // Special Cases
        // p1, q1 and p2 are colinear and p2 lies on segment p1q1
        if (o1 == 0 && onSegment(p1x, p1y, p2x, p2y, q1x, q1y)) return true;

        // p1, q1 and q2 are colinear and q2 lies on segment p1q1
        if (o2 == 0 && onSegment(p1x, p1y, q2x, q2y, q1x, q1y)) return true;

        // p2, q2 and p1 are colinear and p1 lies on segment p2q2
        if (o3 == 0 && onSegment(p2x, p2y, p1x, p1y, q2x, q2y)) return true;

        // p2, q2 and q1 are colinear and q1 lies on segment p2q2
        if (o4 == 0 && onSegment(p2x, p2y, q1x, q1y, q2x, q2y)) return true;

        return false; // Doesn't fall in any of the above cases
    }

Okay, this has proven to be a more complicated problem than I thought. Let’s return to our original one, with the WalkPositions. If any side of the square intersects our line, then it is on the line, no further checks needed.

    public static Set<WalkPosition> getWalkPositionsOnLine(Position p1, Position p2) {
        //Get the "big rectangle"
        int left = Math.min(p1.getX(), p2.getX());
        int top = Math.min(p1.getY(), p2.getY());
        int right = Math.max(p1.getX(), p2.getX());
        int bottom = Math.max(p1.getY(), p2.getY());

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

        HashSet<WalkPosition> wps = new HashSet<>();
        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, p1.getX(), p1.getY(), p2.getX(), p2.getY())   //top
                ||  doIntersect(i*8, j*8, i*8, j*8+8, p1.getX(), p1.getY(), p2.getX(), p2.getY())   //left
                ||  doIntersect(i*8+8, j*8, i*8+8, j*8+8, p1.getX(), p1.getY(), p2.getX(), p2.getY())   //bottom
                ||  doIntersect(i*8+8, j*8, i*8+8, j*8+8, p1.getX(), p1.getY(), p2.getX(), p2.getY())   //right
                )  {
                  wps.add(new WalkPosition(i,j));
                }
            }
        }
        return wps;
    }

So let’s test it, and draw out the WalkPositions on the line.

Is that…? Could it be…? Is the math finally over?

I seriously forgot what was the thing I was trying to achieve here for a moment. Oh yeah, avoiding the hurty waffle.

I thought about it, and I will follow the honed approach of not researching just going blindly with my own idea method, after all, this time, it will be different.

The basic logic of the pathfinding is: If the path contains threatened areas, then I get some point on the line segment connecting the unit and the destination, then I start exploring in a rectangular fashion – check the 8 WalkPositions around the chosen one, if all of them are still threatened, check again with the distance of 2, etc. If I find one, that’s not threatened, then i restart the algorithm with this point, and the start, and the end. In the end, I get some collection / collections of WalkPositions. These will be likely not in the order I want the unit to visit them in, so I have do some sorting.

This is just crying to be a recursive algorithm of some sort.

Before jumping into it, however, there are a lot to consider.

• Picking the initial point to start the algorithm from. Halfway point seems like a good start, but there are a lot of edge cases where it will produce subpar results. Either the target, or origin point has it’s merits – or maybe just a random one. Threatened areas tend be large, convex lumps in most cases.
• What to do when encountering an unwalkable tile? This could be an area wall, or a small obstacle, which I can just go around.
• Sorting. I get some waypoints, but how to queue up the movement commands to them? The movement can be in any direction, so a coordinate-based sorting is out of the question – the planned route, and the line between the origin and target not necessarily have the same orientation/slope/direction, however you want to call it.
• Where should I place the recursion, exactly?

For the first iteration of the algorithm, I will do the following:

• Start from halfway point
• Stop the algorithm in that direction if I encounter an unwalkable tile.
• For the result, I always pick the closest WalkPosition to the previous one, starting with the unit’s origin. This can be probably improved upon later.

Let’s start with a method for getting all WalkPositions in a given radius. This is for the exact distance, so WalkPositions exactly n tiles away, and not including the ones closer. Also, this is grid-based, not on “real” distance. We must take care to not check positions that are not on the map – obviously we can’t go there, and also, some BWAPI methods will throw an error if we try – for example, isWalkable().

    public static Set<WalkPosition> getWalkPositionsInGridRadius(WalkPosition origin, int radius) {
        HashSet<WalkPosition> walkPositions = new HashSet<>();
        int left = origin.getX()-radius;
        int top = origin.getY()-radius;
        int right = origin.getX()+radius;
        int bottom = origin.getY()+radius;

        //Do not check positions that are not on the map
        if (left < 0) {left = 0;}
        if (top < 0) {top = 0;}
        if (bottom > Main.bw.getBWMap().mapHeight() /8) {bottom = Main.bw.getBWMap().mapHeight() /8;}
        if (right > Main.bw.getBWMap().mapWidth() /8) {bottom = Main.bw.getBWMap().mapWidth() /8;}

    int steps = radius*2+1;
    //Top row
        for (int i=0; i<steps;i++) {
        walkPositions.add(new WalkPosition(left+i, top));
    }
    //Bottom row
        for (int i=0; i<steps;i++) {
        walkPositions.add(new WalkPosition(left+i, bottom));
    }
    //Left column
        for (int i=1; i<steps-1;i++) {
        walkPositions.add(new  WalkPosition(left, top+i));
    }
    //Right column
        for (int i=1; i<steps-1;i++) {
        walkPositions.add(new  WalkPosition(right, top+i));
    }
        return walkPositions;
}

Pretty simple, just drawing some rectangles. Let’s test it out.

I intentionally left out the walkability and on map checks. The objects have to be created anyway to check them, so we don’t gain anything, and also, this is a functionality that might be used elsewhere, so better just decouple it (Using words like this makes me feel smart).

I would need an algorithm that takes three arguments: Start and end point, and if it’s a ground or air pathfinding – since it’s always one, I can use a boolean here. First, let’s implement finding the closest non-threatened point between the start and end points.

The getWalkPositionsOnLine() will return some WalkPositions, I can compare this to the threatmap(s). That actually brings us to another point: Should I use both threat maps? The answer is clearly “I dunno lol”, so I’ll just add that as a parameter.

In the next post, I will continue with the implementation. Thanks for reading!

If you liked this article, consider subscribing to the mailing list – you can find the form in the sidebar.