之字形填充算法？

Question

如何制作一种算法来锯齿形填充任意大小的网格，如下图所示？

这是我的算法，但它不起作用。（改为从左下角到右上角）：

x1 = 0;
y1 = grid_h-1;
var a = 0;
put(x1,y1);

while(!((x1 = grid_w-1) and (y1 = 0))) { //If it isn't at the top right corner
    if a = 2 {
        x1 += 1;
        put(x1,y1);
        while(x1 != grid_w-1) { //While x1 isn't at the right
            //Go diagonally down
            x1 += 1;
            y1 += 1;
            put(x1,y1);
        }
        y1 -= 1;
        put(x1,y1);
        while(y1 != 0) { //While y1 isn't at the top
            //Go diagonally up
            x1 -= 1;
            y1 -= 1;
            put(x1,y1);
        }
    } else if a = 1 {
        while(x1 != grid_w-1) { //While x1 isn't at the right
            //Go diagonally down
            x1 += 1;
            y1 += 1;
            put(x1,y1);
        }
        y1 -= 1;
        put(x1,y1);
        while(y1 != 0) { //While y1 isn't at the top
            //Go diagonally up
            x1 -= 1;
            y1 -= 1;
            put(x1,y1);
        }
        x1 += 1;
        put(x1,y1);
    } else {
        y1 -= 1;
        if (y1 = 0) { a = 1; } //At top?
        put(x1,y1);
        while(y1 != grid_h-1) { //While y1 isn't at the bottom
            //Go diagonally down
            x1 += 1;
            y1 += 1;
            put(x1,y1);
        }

        x1 += 1;
        put(x1,y1);
        while(x1 != 0) { //While x1 isn't at the left
            //Go diagonally up
            x1 -= 1;
            y1 -= 1;
            put(x1,y1);
            if (y1 = 0) { a = 2; } //At top?
        }
    }
}

有更简单的方法吗？

Answer 1

这是滥用 if-statements.

的解决方案

x1 = 0;
y1 = 0;
put(x1,y1);

var a = 0;
while(!((x1 = grid_w-1) and (y1 = grid_h-1))) {
    switch(a) { //Down, Right-Up, Right, Left-Down
        case 0: y1++; break;
        case 1: x1++;y1--; break;
        case 2: x1++; break;
        case 3: x1--;y1++; break;
    }
    put(x1,y1);
    if (a = 2) { //If moved right.
        if (x1 = grid_w-1) or (y1 = 0) { //If at the right or top edge. Go left-down.
            a = 3
        } else if (y1 = grid_h-1) { //At bottom edge. Go right-up.
            a = 1
        }
    } else if (y1 = 0) { ///At top edge.
        if (x1 = grid_w-1) { //If at the right corner. Go down.
            a = 0;
        } else { //Go right.
            a = 2;
        }
    } else if (a = 3) { ///If moved left-down.
        if (y1 = grid_h-1) { //At bottom n edge. Go right.
            a = 2
        } else if (x1 = 0) { //At left edge and not bottom. Go down.
            a = 0
        }
    } else if (a = 0) { //If moved down.
        if (x1 = 0) { //If at the left corner. Go right-up.
            a = 1
        } else if (x1 = grid_w-1) { //If at the right corner. Go left-down.
            a = 3
        } else { //Go right
            a = 2
        }
    } else if (a = 1) { //If right-up.
        if (x1 = grid_w-1) {  //If at the right corner.
            if (a = 2) { //If moved right. Go left-down.
                a = 3
            } else { //Go down.
                a = 0
            }
        }
    }
}

如果其中一个尺寸为 1，则效果不佳。

Answer 2

这里的关键观察是，当左上角的 Manhattan distance 方块为奇数时，您向东北方向前进，否则向西南方向前进。

当然，你必须考虑撞到其中一个边缘。例如，当您向西南走并碰到底部或南边时，您会向东移动；当您击中左边缘或西边缘时，您将向南移动。可以抓三种情况（南边、西边、乱跑），也可以在出界时移动修正位置。

点击广告后，您的新职位应该会让您转向另一条路。也就是说，每次校正涉及奇数个步骤。（这里的步数是您正常到达的地点和最终到达的地点之间的曼哈顿距离。）

如果您的之字形算法工作正常，您将最终访问每个单元格一次。那就是让 h × w 移动，其中 h 和 w 是高度和宽度。您可以将其用作终止标准，而不是检查您是否在最后一个方格中。

这是此解决方案的示例代码。额外的布尔参数 down 指定第一步是向下还是向左。

function zigzag(width, height, down) {
    var x = 0;
    var y = 0;
    var n = width * height;

    if (down === undefined) down = false;

    while (n--) {
        var even = ((x + y) % 2 == 0);

        put(x, y);

        if (even == down) {             // walk southwest
            x--;
            y++;

            if (y == height) {
                y--; x += 2;
            }
            if (x < 0) x = 0;
        } else {                        // walk northeast
            x++;
            y--;

            if (x == width) {
                x--; y += 2;
            }
            if (y < 0) y = 0;
        }
    }

    return res;
}

Answer 3

基本上我们可以使用状态图和递归来解决这个问题。

permitted_directions = {
"start":["down", "side"], 
"down":["north_east", "south_west"], 
"north_east":["north_east", "side","down"], 
"side":["north_east", "south_west"], 
"south_west":["south_west","down", "side"]
}

def is_possible(x, y, pos):
    if pos == "down":
        if x+1 < row and y >=0 and y < col:
            return (True, x+1, y)
    if pos == "side":
        if x >= 0 and x < row and y+1 >=0 and y+1 < col:
            return (True, x, y+1)
    if pos == "north_east":
        if x-1 >= 0 and x-1 < row and y+1 >= 0 and y+1 < col:
            return (True, x-1, y+1)
    if pos == "south_west":
        if x+1 >= 0 and x+1 < row and y-1 >= 0 and y-1 < col:
            return (True, x+1, y-1)
    return (False, 0, 0)

def fill_the_grid(grid, x, y, position, prev):
    grid[x][y] = prev
    prev = (x, y)
    for pos in permitted_directions[position]:
        possible, p, q = is_possible(x, y, pos)
        if possible:
            return fill_the_grid(grid, p, q, pos, prev)
    return grid

之字形填充算法？

Zig-zag fill algorithm?

algorithm

fill

game-maker