Experiencing strange recursion behavior with setTimeout

Question

I wrote a simple 3d flood-filling algorithm to draw a diamond shape into an array (that array is pseudo multi dimensional as described in this post). The actual method looks like this:

/**
 * Draws a 3d diamond shape into an array using a flood fill algorithm.
 *
 * @param data The array to "draw" the diamond shape in. Must be of length 100 * 100 * 100 and all values must be 0.
 * @param pos Tupel of x, y, z position to be the center of the diamond.
 */
 export function flood3dDiamondShape(data: Uint8Array, pos: [number, number, number], distance = 0): void {
    if (distance > 10) {
        return;
    }

    const [x, y, z] = pos;
    const index = (x) + (z * 100) + (y * 100 * 100);
    if (data[index] > 0) {
        return;
    }

    data[index] = 1;

    flood3dDiamondShape(data, [x + 1, y, z], distance + 1);
    flood3dDiamondShape(data, [x - 1, y, z], distance + 1);
    flood3dDiamondShape(data, [x, y + 1, z], distance + 1);
    flood3dDiamondShape(data, [x, y - 1, z], distance + 1);
    flood3dDiamondShape(data, [x, y, z + 1], distance + 1);
    flood3dDiamondShape(data, [x, y, z - 1], distance + 1);
}

However, this doesn't result in the expected result but draws a strangely shaped "blob" into the array (refer to image 2). I tried to debug that behavior by wrapping the six calls to flood3dDiamondShape(...) into a setTimeout callback. It looks like this:

setTimeout(() => {
    flood3dDiamondShape(data, [x + 1, y, z], distance + 1);
    flood3dDiamondShape(data, [x - 1, y, z], distance + 1);
    flood3dDiamondShape(data, [x, y + 1, z], distance + 1);
    flood3dDiamondShape(data, [x, y - 1, z], distance + 1);
    flood3dDiamondShape(data, [x, y, z + 1], distance + 1);
    flood3dDiamondShape(data, [x, y, z - 1], distance + 1);
}, 1);

This still works but now the strange "blob" isn't there anymore. It now is the expected diamond shape as you may see in image 3.

Note that using the second method I of course waited for the algorithm to finish before actually drawing the shape.

The question now actually is: Why am I experiencing this behavior? I would like to get the diamond shape 3 but without using setTimeout.

Minimum working example: I created a 2d version in html to show the algorithm. Please refer to: https://pastebin.com/raw/MvyJzR5x. How it looks: 4

Minimum working example in 2d

How it is supposed to look (with setTimeout)

How it actually looks (without setTimeout)

Good call. This would make answering this question easier indeed. I created a page with the algorithm in 2d. The source may be found here: https://pastebin.com/raw/MvyJzR5x — Paul, May 29 '22 at 19:57

Paul · Answer 1 · 2022-05-30T21:22:51.470

I somewhat solved it. The problem was with the distance field. The algorithm will walk through the array like a snake and will eventually come to a stop because the distance got too big. As the already visited fields will now check for painted fields to the top/bottom, left/right their may already be paint by the first "snake" and no more is painted. This results in an unwanted shape. This image shows how the algorithm goes down and then back up again and therefore eventually cuts itself of

Now this isn't really a solution but it explains the problem. I thought about replacing the base case distance > 10 with something like manhattenDistance(x, y, originalX, originalY). I am not able to come up with another solution.

By the way: The setTimeout solved the issue because the order in which the pixels are worked off is essentially reversed. This prevents the algorithm from becoming stuck. This could also be implemented with a list that keeps an order of when to work off which pixel.

EDIT:

I now found a way to keep the original distance field. I initially introduced it to ensure that the shape "bleeds" around already existing shapes in the data array. Using the manhattenDistance the shape would ignore boundaries. The result now looks like this:. The updated algorithm (in 2d like the provided example) now looks like this:

function floodFill(data, x, y, distance) {
    if (distance <= 0) {
        return;
    }

    const index = (x) + (y * 100);
    if (data[index] >= distance) {
        return;
    }
    data[index] = distance;

    floodFill(data, x, y + 1, distance - 1);
    floodFill(data, x, y - 1, distance - 1);
    floodFill(data, x + 1, y, distance - 1);
    floodFill(data, x - 1, y, distance - 1);
}

As you may see it was just a matter of flipping the base case of comparing the already painted color to the color that is to be painted.

Experiencing strange recursion behavior with setTimeout

1 Answers1