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 https://i.sstatic.net/rG7N5.png

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'. https://i.sstatic.net/Gk2Wa.png

However, there are instances where the algorithm abruptly stops like on this particular map: https://i.sstatic.net/oQOYL.png

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

Enhance the <div> with interactive content through dynamic updates on click within the same element

Instructions on how to dynamically update a form field based on the input in another field using conditional statements

Updating the Ajax Url dynamically while scrolling

Retrieve the data from Mysql database, transform the information inside the link into XML format, and display the final output

The function Document.getElementsByName() behaves differently in Internet Explorer, returning an object, compared to Chrome where it returns

Using JavaScript to trigger actions via links or buttons inside a table will only function properly in the first row

Is there a way to verify the presence of a complete object by using a specific key in JavaScript

Turn off choices by utilizing data type attribute values within select2 version 4

Comparing Embedded and Linked JS/CSS

Substitute a single occurrence of the dollar sign with an HTML tag

Querying MongoDB findAndModify: <<< locate and modify an object within an array in a document

Received a Vue prop as a variable name, rather than the actual string value it represents

Is there a way to tally ng-required errors specifically for sets of radio buttons?

What could be the reason for my Bootstrap popover malfunctioning?

What causes the DOM to be updated upon each opening of the browser extension for Chrome?

Looking for assistance in resolving the error message: 'state' is not defined no-undef

Ways to add items to an array adjacent to items sharing a common property value

Performing mathematical operations in JavaScript, rounding to the nearest .05 increment with precision up to two

Steps for dynamically changing the class of a dropdown when an option is selected:

Creating a simulation in THREE.js that incorporates MeshBasicMaterial, with the added feature of being able to