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) work.
Reference image:
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 three solutions can be found and tested by downloading [my git project][3]. 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:
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.
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:
Errors from A3: jumps and inconsistent move ambiguities, only one diagonal behaves the way I want.
