在“偶数”垂直平顶六角网格上划线

我正在尝试为我的hex棋盘游戏实现一个Line Draw或Line of Sightalgorithm。 在阅读几个不同的解决scheme,从最常见的地方,如hex的圣经,没有适应我的网格configuration的algorithm(even-q如在圣经中所述)。

参考图像:

参考

我想要的是一个给定的hexA和hexB的algorithm返回将从A的中心到B的中心的一条线所穿过的所有的hex,并且在对角线穿过一个分割线的情况下,它select它。 如在A(0,1)和B(2,1)=> {[0,1] [1,1] [1,0] [2,1]}中对于水平和A(1,0)B 0,2)=> {[1,0] [0,1] [1,1] [0,2]}为对角线。 游戏中的一个例子:A(0,1)中的角色射向箭头B(6,1),箭头将在步骤1中检查碰撞:[1,1] [1,0],步骤2:[2, 1],步骤3:[3,1] [3,0],步骤4:[4,1],步骤5:[5,1] [5,0],步骤6:[6,1]

经过一个不眠之夜,我想出了3个不同的解决scheme:两个适应和我自己的一个。 因为math是有缺陷的,所以他们都没有给出完美的结果,所以我想要一些帮助。

所有3个解决scheme都可以通过下载[我的git项目] [3]find并testing。 该类可以在com.wartricks.tools.MapTools.javafind

algorithm1根据六角星:

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 }; } 

这是一个混乱,它并不像预期的那样

错误1

algorithmB根据Bresenham线绘制:

 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; } 

2的问题是,它不应该添加额外的正方形,因为它是在计算尖顶的正方形

错误2

algorithm3,因为我喜欢它。 它使用一些神奇的数字,因为在渲染系统中有一些偏移量。

 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; } 

来自A3的结果

算法3

来自a3的错误:跳跃和不一致的移动歧义,只有一个对角线performance我想要的方式。

错误3

在algorithm1中,您使用的是“even-q”,但应该使用“odd-q”。 你的网格相对于我的页面翻转,所以你想把每一个奇数列,而不是每个偶数列向下。 将coordOffset2CubecoordCube2Offset + (x % 2) coordCube2Offset为使用- (x % 2)

另外,在对角线上,线条绘制algorithm不会碰到线条的两侧。 它只挑一边。 此Stackoverflow问题显示正方形网格上的问题。 你可以修改hex,当x_err,y_err,z_err有一个领带(我没有试过这个)时返回双方。 或者你可以在每一步添加偏移在各个方向,然后四舍五入,所以,如果有一个领带,抵消将最终find多个hexes(我已经尝试过,似乎工作,但我没有写出来然而)。