Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

I'm trying to implement a Line Draw or Line of Sight algorithm for my hex boardgame. Upon reading several different solutions from most common places like the Hex Bible none of the algorithms adapted to my grid config (even-q as stated in Hex Bible).

Reference image:

reference

What I want is an algorithm that given hex A and hex B returns all hexes that would be crossed by a line going from the center of A to the center of B, and in case of diagonal going right through a division it selects both sides of it. As in A(0,1) and B(2,1) => {[0,1][1,1][1,0][2,1]} for horizontal and A(1,0) B(0,2) => {[1,0][0,1][1,1][0,2]} for diagonal. An in-game example: character in A(0,1) shoots arrow towards B(6,1) the arrow will check for collision in Step 1: [1,1][1,0], Step 2: [2,1], Step 3: [3,1][3,0], Step 4: [4,1], Step5: [5,1][5,0], Step 6: [6,1]

After a sleepless night I have come up with 3 different solutions: two adapted and one of my own. None of them gives perfect results because the math is flawed, so I would like some help.

All 3 solutions can be found and tested by downloading my git project. The class is found at com.wartricks.tools.MapTools.java

Algorithm 1 as per hex bible:

public Array<Pair> getLOSCells(int x, int y, int x0, int y0) {
    final Array<Pair> highlights = new Array<Pair>();
    // PROBLEM! my offset system has 0,0 on the bottom left and is flat-top
    // coord2Offset gives valid results, but they don't translate well
    // for example my 0,1 should be 0,1,-1 but gets 0,-1,1 instead
    // this causes problems with rounding that make the line break
    final int[] cubeCoordsOrigin = MapTools.coordOffset2Cube(x, y);
    final int[] cubeCoordsDestination = MapTools.coordOffset2Cube(x0, y0);
    final int dx = cubeCoordsOrigin[0] - cubeCoordsDestination[0];
    final int dy = cubeCoordsOrigin[1] - cubeCoordsDestination[1];
    final int dz = cubeCoordsOrigin[2] - cubeCoordsDestination[2];
    float distance = Math.max(Math.abs(dx - dy), Math.abs(dy - dz));
    distance = Math.max(distance, Math.abs(dz - dx));
    if (distance > 0) {
        int[] previousCoord = new int[3];
        for (float i = 0; i <= distance; i++) {
            final float currentX = (cubeCoordsOrigin[0] * (i / distance))
                    + (cubeCoordsDestination[0] * (1 - (i / distance)));
            final float currentY = (cubeCoordsOrigin[1] * (i / distance))
                    + (cubeCoordsDestination[1] * (1 - (i / distance)));
            final float currentZ = (cubeCoordsOrigin[2] * (i / distance))
                    + (cubeCoordsDestination[2] * (1 - (i / distance)));
            final int[] currentCoord = roundCubeCoord(currentX, currentY, currentZ);
            if (!currentCoord.equals(previousCoord)) {
                final int[] offsetCoord = MapTools.coordCube2Offset(currentCoord[0],
                        currentCoord[1], currentCoord[2]);
                highlights.add(new Pair(offsetCoord[0], offsetCoord[1]));
                previousCoord = currentCoord;
            }
        }
    }
    return highlights;
}

public static int[] coordOffset2Cube(int x, int y) {
    final int[] coord = new int[3];
    coord[0] = x;
    coord[2] = y - ((x + (x % 2)) / 2);
    coord[1] = -x - coord[2];
    return coord;
}

public static int[] coordCube2Offset(int x, int y, int z) {
    final int[] coord = new int[2];
    coord[0] = x;
    coord[1] = (z + ((x + (x % 2)) / 2));
    return coord;
}

public static int[] roundCubeCoord(double x, double y, double z) {
    float rx = Math.round(x);
    float ry = Math.round(y);
    float rz = Math.round(z);
    final int s = (int)(rx + ry + rz);
    if (s != 0) {
        final float x_err = (float)Math.abs(rx - x);
        final float y_err = (float)Math.abs(ry - y);
        final float z_err = (float)Math.abs(rz - z);
        if ((x_err > y_err) && (x_err > z_err)) {
            rx -= s;
        } else if (y_err > z_err) {
            ry -= s;
        } else {
            rz -= s;
        }
    }
    return new int[] {
            (int)rx, (int)ry, (int)rz
    };
}

this one is a mess, it doesn't behave as expected at all

errors 1

Algorithm B as per Bresenham's Line Draw:

public Array<Pair> getLOSCellsPlanB(int y1, int x1, int y2, int x2) {
    // Works with errors, probably due to being swapped with x and y
    // !!!Designed for even-r pointy-tops
    final Array<Pair> highlights = new Array<Pair>();
    int i; // loop counter
    int ystep, xstep; // the step on y and x axis
    int error; // the error accumulated during the increment
    int errorprev; // *vision the previous value of the error variable
    int y = y1, x = x1; // the line points
    int ddy, ddx; // compulsory variables: the double values of dy and dx
    int dx = x2 - x1;
    int dy = y2 - y1;
    highlights.add(new Pair(y1, x1)); // first point
    // NB the last point can't be here, because of its previous point (which has to be verified)
    if (dy < 0) {
        ystep = -1;
        dy = -dy;
    } else {
        ystep = 1;
    }
    if (dx < 0) {
        xstep = -1;
        dx = -dx;
    } else {
        xstep = 1;
    }
    ddy = 2 * dy; // work with double values for full precision
    ddx = 2 * dx;
    if (ddx >= ddy) { // first octant (0 <= slope <= 1)
        // compulsory initialization (even for errorprev, needed when dx==dy)
        errorprev = error = dx; // start in the middle of the square
        for (i = 0; i < dx; i++) { // do not use the first point (already done)
            x += xstep;
            error += ddy;
            if (error > ddx) { // increment y if AFTER the middle ( > )
                y += ystep;
                error -= ddx;
                // three cases (octant == right->right-top for directions below):
                if ((error + errorprev) < ddx) {
                    highlights.add(new Pair(y - ystep, x));
                } else if ((error + errorprev) > ddx) {
                    highlights.add(new Pair(y, x - xstep));
                } else { // corner: bottom and left squares also
                    highlights.add(new Pair(y - ystep, x));
                    highlights.add(new Pair(y, x - xstep));
                }
            }
            highlights.add(new Pair(y, x));
            errorprev = error;
        }
    } else { // the same as above
        errorprev = error = dy;
        for (i = 0; i < dy; i++) {
            y += ystep;
            error += ddx;
            if (error > ddy) {
                x += xstep;
                error -= ddy;
                if ((error + errorprev) < ddy) {
                    highlights.add(new Pair(y, x - xstep));
                } else if ((error + errorprev) > ddy) {
                    highlights.add(new Pair(y - ystep, x));
                } else {
                    highlights.add(new Pair(y, x - xstep));
                    highlights.add(new Pair(y - ystep, x));
                }
            }
            highlights.add(new Pair(y, x));
            errorprev = error;
        }
    }
    // assert ((y == y2) && (x == x2)); // the last point (y2,x2) has to be the same with the
    // last point of the algorithm
    return highlights;
}

the problem with 2 is that it adds extra squares where it shouldn't because it's calculating for pointy-top hexes

errors 2

Algorithm 3 as I like it. It uses some magic numbers because of some offsets in the render system.

public Array<Pair> getLOSCellsPlanC(int x1, int y1, int x2, int y2) {
    final Array<Pair> highlights = new Array<Pair>();
    final int dx = x2 - x1;
    final int dy = y2 - y1;
    final FloatPair origin = this.world2window(x1, y1);
    final FloatPair destination = this.world2window(x2, y2);
    final float dpx = destination.x - origin.x;
    final float dpy = destination.y - origin.y;
    final float distance = 2 * Math.max(Math.abs(dx), Math.abs(dy));
    if (distance > 0) {
        for (int i = 0; i <= distance; i++) {
            final float currentX = ((origin.x + ((dpx * i) / distance)));
            final float currentY = ((origin.y + ((dpy * i) / distance)));
            float posx = ((currentX) / gameMap.colSize);
            float posy = (((currentY) - ((gameMap.rowSize * (posx % 2)) / 2)) / gameMap.rowSize);
            final Pair targetHex = new Pair((int)posx, (int)posy);
            highlights.add(targetHex);
        }
    }
    return highlights;
}

results from A3

Algorithm 3

errors from a3: jumps and inconsistent move ambiguities, only 1 diagonal behaves the way I want.

Errors 3

share|improve this question

1 Answer 1

up vote 3 down vote accepted

In algorithm 1, you're using “even-q” but you should use “odd-q” instead. Your grid is flipped upside down relative to the one on my page, so you want to shift every odd column up instead of every even column down. Change + (x % 2) in coordOffset2Cube and coordCube2Offset to use - (x % 2) instead.

Also, on diagonals, the line drawing algorithm will not hit both sides of the line. It only picks one side. This Stackoverflow question shows the problem on square grids. You can modify hex-rounding to return both sides when x_err, y_err, z_err have a tie (I haven't tried this). Or you can at each step add offsets in various directions and then round, so that if there's a tie, the offsets will end up finding multiple hexes (I've tried this and it seems to work, but I haven't written it up yet).

share|improve this answer
    
The problem has been solved thanks to this tips, and I already made my own "rounding" changes. Feel free to check commit 0f0a366 for changes and the final result. –  MLProgrammer-CiM Jun 9 '13 at 15:14

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.