Zig-zag fill algorithm?

Question

How do I make an algorithm to zig-zag fill a grid at any size as shown in the image below?

Here is my algorithm which doesn't work. (Starting bottom left to top right corner instead):

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

Any simpler way to do this?

Answer 1

The key observation here is that you go northeast when the Manhattan distance to the top left square is odd and southwest otherwise.

Of course, you must consider hitting one of the edges. For example, when you walk southwest and hit the bottom or south edge, you move east instead; when you hit the left or west edge, you move south. You can either catch the three cases (south edge, west edge, unrestrained movement) or you can move and correct your position when you have walked out of bounds.

After hitting an adge, your new position should leave you moving the other way. That is, each correction involves an odd number of steps. (Steps here is the Manhattan distance between the point you'd have gone to normally and the point you ended up in.)

If your zigzagging algorithm works correctly, you will end up visiting each cell once. That is you make h × w moves, where h and w are the height and width. You can use this as termination criterion instead of checking whether you are in the last square.

Here's example code for this solution. The additional boolean parameter down specifies whether the first step is down or left.

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