Algorithm for converting a 2D voxel map into a line may encounter occasional difficulty in progressing

Question

Algorithm for converting a 2D voxel map into a line may encounter occasional difficulty in progressing

For my game, I am dealing with a 2D voxel map stored as a 2D array where 1 represents ground and 0 represents sky.

In the map, areas marked as 1 (ground) are represented by green boxes

The algorithm initiates at the leftmost ground voxel touching the sky (marked red in the picture).

It scans the 8 neighboring positions to identify if any of them are ground voxels that also touch sky voxels. These points are added to the groundline.

The algorithm works efficiently even when navigating through 'caves'.

However, there are instances where the algorithm abruptly stops like on this particular map:

After around 10 iterations, it fails to continue creating the line.

Below is the code along with explanatory comments:

voxelToLine() {
let voxels = this.voxels.length, //this.voxels is the 2d array
    lineGround = [],
    checkedVoxels = [],
    nowChecking,
    toCheck = [],
    otherPaths = [],
    done = false;

for (let y = 1; y < voxels - 1; y++) //sets first coordinate for line
    if (this.voxels[0][y] && (!this.voxels[0][y - 1] || !this.voxels[1][y] || !this.voxels[0][y + 1])) {
        lineGround[0] = [0, y / voxels];
        nowChecking = [1, y]; //search starts from this point
    }

let looped = 0;
while (!done) { //continues search until right side is located or gets stuck (max 10*voxelmap width loops)
    toCheck = nowChecking.neighbours(8, (n) => n[0] > 0 && n[0] < voxels - 1); //gets 8 neighbour points around the current point
    let foundNew = false;
    for (let i = 0; i < toCheck.length; i++) {
        let x = toCheck[i][0],
            y = toCheck[i][1],
            index = y * voxels + x;
        if (!checkedVoxels.includes(index)) {
            if (this.voxels[x][y] && (!this.voxels[x][y - 1] || !this.voxels[x + 1][y] || !this.voxels[x - 1][y] || !this.voxels[x][y + 1])) {
                checkedVoxels.push(index);
                if (foundNew) {
                    otherPaths.push([x, y]);
                } else {
                    lineGround.push([x / voxels, y / voxels]);
                    nowChecking = [x, y];
                    foundNew = true;
                }
                if (x >= voxels) done = true;
            }
        } else if (i == toCheck.length - 1 && !foundNew) {
            if (otherPaths.length > 0) {
                nowChecking = otherPaths.pop();
                foundNew = true;
            }
        }
    }

    if (!foundNew || looped++ > voxels * 10) {
        console.log('loops: ', looped);
        break;
    }
}

if (lineGround[0][0] !== 0) lineGround.splice(0, 0, [0, lineGround[0][1]]);
if (lineGround[lineGround.length - 1][0] !== 1) lineGround.push([1, lineGround[lineGround.length - 1][1]);

return lineGround;
}

You can test it here: game. Clicking removes some voxels within a radius and recalculates the line.

I am facing a challenge as to why the line discontinues in certain scenarios. All code is available here, with the relevant file being js/Level.js.

javascript arrays algorithm line

Answer 1

Answer №1

Upon exploring your website, I noticed several other issues aside from the one you mentioned. While trying to comprehend your code's logic, I found myself getting lost in the complexities. Consequently, I took the liberty of rewriting a significant portion of your code. The crux of my modification revolves around keeping track of the direction (slope) traveled along the ground, allowing for the accurate scanning of neighboring cells.

To elaborate further on this concept, envision each neighbor being sequentially numbered from 0 to 7:

+---+---+---+
| 7 | 0 | 1 |
+---+---+---+
| 6 | * | 2 |
+---+---+---+
| 5 | 4 | 3 |
+---+---+---+

In this scenario, the cell marked with * denotes the most recent instance of locating solid ground. Consider an example where the preceding discovery was at position 6; subsequently, the search among neighbors should commence at positions 7, 0, 1, 2, and so forth up until 5. The initial solid ground encountered during this pursuit represents the next addition to the ground level.

For another illustration: if the latest finding occurred at position 4, indicating an upward trajectory, the subsequent scan should begin from 5, continuing through 6, 7, 0, 1, 2, and concluding at 3.

The primary objective is to identify the first solid neighbor (ground) and include it as the subsequent component of the ground line. This method ensures meticulous tracking along every curve, including traversals through "caves," either ascending or descending, leftward or rightward.

Naturally, outliers may still arise, especially when commencing from isolated locations such as islands. However, addressing those specific cases was beyond the scope of my current endeavor.

The proposed approach has been integrated into the revised iteration of your method as provided below:

voxelToLine() {
    let voxels = this.voxels.length, x, y, i;
    // Neighbor coordinates listed clockwise    
    const neighbor = [ [0,-1], [1,-1], [1,0], [1,1], [0,1], [-1,1], [-1,0], [-1,-1] ];

    for (y = 0; y < voxels; y++) // Sets initial coordinate for the line.
        if (this.voxels[0][y]) break; // Ground found, cease downward search
    let lineGround = [[0, y / voxels]];
    let [curX, curY] = [0, y]; // Initiate search here
    let direction = 0; // Ascending

    let looped = 0;
    do {// Iterates until right side is identified or maximum loops reached
        for (i = 0; i < 8; i++) {// Inspects each neighbor, starting from `direction`
            [x, y] = [curX + neighbor[direction][0], curY + neighbor[direction][1]];
            // Upon encountering solid ground, designate as the subsequent line entry
            if (x>=0 && x<voxels && y>=0 && y<voxels && this.voxels[x][y]) break;
            direction = (direction + 1) % 8; // Clockwise rotation to access next neighbor
        }
        if (i === 8) break; // In case no valid neighbor is found
        lineGround.push([x / voxels, y / voxels]);
        // Prepare for next iteration
        [curX, curY] = [x, y];
        direction = (direction + 5) % 8;
    } while (looped++ <= voxels*10 && curX < voxels - 1);

    // Ensure existence of x=0 and x=1 entries; add them if absent
    if (lineGround[0][0] !== 0) lineGround.splice(0, 0, [0, lineGround[0][1]]);
    if (lineGround[lineGround.length - 1][0] !== 1) 
        lineGround.push([1, lineGround[lineGround.length - 1][1]]);
    return lineGround;
}

Answer 2

Upon exploring your website, I noticed several other issues aside from the one you mentioned. While trying to comprehend your code's logic, I found myself getting lost in the complexities. Consequently, I took the liberty of rewriting a significant portion of your code. The crux of my modification revolves around keeping track of the direction (slope) traveled along the ground, allowing for the accurate scanning of neighboring cells.

To elaborate further on this concept, envision each neighbor being sequentially numbered from 0 to 7:

+---+---+---+
| 7 | 0 | 1 |
+---+---+---+
| 6 | * | 2 |
+---+---+---+
| 5 | 4 | 3 |
+---+---+---+

In this scenario, the cell marked with * denotes the most recent instance of locating solid ground. Consider an example where the preceding discovery was at position 6; subsequently, the search among neighbors should commence at positions 7, 0, 1, 2, and so forth up until 5. The initial solid ground encountered during this pursuit represents the next addition to the ground level.

For another illustration: if the latest finding occurred at position 4, indicating an upward trajectory, the subsequent scan should begin from 5, continuing through 6, 7, 0, 1, 2, and concluding at 3.

The primary objective is to identify the first solid neighbor (ground) and include it as the subsequent component of the ground line. This method ensures meticulous tracking along every curve, including traversals through "caves," either ascending or descending, leftward or rightward.

Naturally, outliers may still arise, especially when commencing from isolated locations such as islands. However, addressing those specific cases was beyond the scope of my current endeavor.

The proposed approach has been integrated into the revised iteration of your method as provided below:

voxelToLine() {
    let voxels = this.voxels.length, x, y, i;
    // Neighbor coordinates listed clockwise    
    const neighbor = [ [0,-1], [1,-1], [1,0], [1,1], [0,1], [-1,1], [-1,0], [-1,-1] ];

    for (y = 0; y < voxels; y++) // Sets initial coordinate for the line.
        if (this.voxels[0][y]) break; // Ground found, cease downward search
    let lineGround = [[0, y / voxels]];
    let [curX, curY] = [0, y]; // Initiate search here
    let direction = 0; // Ascending

    let looped = 0;
    do {// Iterates until right side is identified or maximum loops reached
        for (i = 0; i < 8; i++) {// Inspects each neighbor, starting from `direction`
            [x, y] = [curX + neighbor[direction][0], curY + neighbor[direction][1]];
            // Upon encountering solid ground, designate as the subsequent line entry
            if (x>=0 && x<voxels && y>=0 && y<voxels && this.voxels[x][y]) break;
            direction = (direction + 1) % 8; // Clockwise rotation to access next neighbor
        }
        if (i === 8) break; // In case no valid neighbor is found
        lineGround.push([x / voxels, y / voxels]);
        // Prepare for next iteration
        [curX, curY] = [x, y];
        direction = (direction + 5) % 8;
    } while (looped++ <= voxels*10 && curX < voxels - 1);

    // Ensure existence of x=0 and x=1 entries; add them if absent
    if (lineGround[0][0] !== 0) lineGround.splice(0, 0, [0, lineGround[0][1]]);
    if (lineGround[lineGround.length - 1][0] !== 1) 
        lineGround.push([1, lineGround[lineGround.length - 1][1]]);
    return lineGround;
}

Answer 3

Answer №2

It appears as though the voxel directly below the last genuine ground voxel is being skipped over because it has already been marked as "checked" and added to the checkedVoxels array.

Curiously, this skipping behavior would result in your ground path never making a 90-degree turn (as evidenced by the absence of such a voxel pattern in your example picture).

Answer 4

It appears as though the voxel directly below the last genuine ground voxel is being skipped over because it has already been marked as "checked" and added to the checkedVoxels array.

Curiously, this skipping behavior would result in your ground path never making a 90-degree turn (as evidenced by the absence of such a voxel pattern in your example picture).

Algorithm for converting a 2D voxel map into a line may encounter occasional difficulty in progressing

Answer №1

Answer №2

Similar questions

Incorporate a local asciinema file into an HTML document

Discover the color value within an array that begins with the "#" symbol

Is there a way to invoke a php function in javascript with the help of Ajax?

Accessing table cell value when clicked using JavaScript or jQuery

Design a CreateJS/EaselJS website, comprised of multiple web pages, that is not focused on gaming

I am encountering an issue with my Javascript file not running due to a bigint error

Scrolling text box utilizing Jquery

Tips on changing the name of a property within an object using JavaScript

Tips on invoking a method from a JavaScript object within an AJAX request

Modify the NAME attribute when clicked using Jquery

Is there a way to make the primary button on the previous page function correctly again, just like it did before it was clicked?

What is the best way to retrieve a lengthy HTML page string parameter from a Java request?

Experience seamless one-to-many broadcasting with WebRTC/Kurento, featuring server-side recording capabilities

Conceal a div until reaching the end of the webpage by scrolling

Isolating an array from an object?

Difficulty Establishing a Connection with SQL Server Using TypeORM

How can the value be accessed when using getElementById in Angular for <mat-select> elements that do not have a value attribute?

Ways to determine if a new set of input values duplicates previous rows in an array

Using JQuery to reverse the action of hiding an image

Calculating the hour difference between two time stamps (HH:MM:SS a) using moment.js