I'm using a 2d array to represent the grid of cells. When a cell on an edge or in a corner checks it's neighbors that would be out of bounds, it treats them as permanently dead.

function getCell(row, column) {
  if(row === -1 || row === cellMatrix.length || column === -1 || column === cellMatrix[0].length)
  {
    return 0;
  }
  else return cellMatrixCopy[row][column];
}

I'd just like to get rid of behavior like gliders halting and turning into blocks when they reach the edge of the grid. How would you "get rid" of the edges of the array?

You can checkout the full implementation here. Thanks in advance.

I'm using a 2d array to represent the grid of cells. When a cell on an edge or in a corner checks it's neighbors that would be out of bounds, it treats them as permanently dead.

function getCell(row, column) {
  if(row === -1 || row === cellMatrix.length || column === -1 || column === cellMatrix[0].length)
  {
    return 0;
  }
  else return cellMatrixCopy[row][column];
}

I'd just like to get rid of behavior like gliders halting and turning into blocks when they reach the edge of the grid. How would you "get rid" of the edges of the array?

You can checkout the full implementation here. Thanks in advance.

• javascript
• algorithm
• multidimensional-array

Share Improve this question Follow asked Sep 1, 2013 at 23:52 user1707505user1707505 4

• 1 either you make it 'infinite' or wrap the opposite edges (thus being a torus) – Mitch Wheat Commented Sep 1, 2013 at 23:54
• 1 @MitchWheat I might be off on this one but I'm gonna say that it is impossible to fake being infinite(or be infinite) without needing infinite memory – aaronman Commented Sep 2, 2013 at 0:07
• If you want to fake an infinite 2d plane using a finite matrix, there are 3 ways .. 1st is to use a matrix as a window reading from a huge map that can be stored in file, 2nd is to consider that the player is always in the middle & the matrix is what changes\slides. 3rd is to consider what is beyond the borders an infinite mirrors of the same matrix (this can be achieved using modular arithmetic). – Khaled.K Commented Sep 2, 2013 at 5:27
• @aaronman Only if you let it run for an infinite amount of time. – Barmar Commented Mar 27 at 17:32

Add a ment  | 

4 Answers 4

Sorted by: Reset to default 3

How to fake an “infinite” 2d plane?

To create an infinite dimension game board use a sparse matrix representation where the row and column indicies are arbitrary-precision integers. Roughly as follows:

map<pair<BigInt,BigInt>, Cell> matrix;

Cell& get_cell(BigInt x, BigInt y)
{
    return matrix[make_pair[x,y]];
}

The game of life is impossible to fake being infinite. Say the structure you create tries to expand past the current bounds, what is to stop it from expanding infinitely. Like MitchWheat said you could wrap the edges which is your best bet (for the more natural looking behavior), but since it's turing plete you can't fake it being infinite in every situation without having infinite memory.

Since the game of life is turing plete that means if a something "goes off the edge" it is impossible to tell if it will e back for a general case (related to the halting problem), meaning any heuristic you use to decide when something goes off the edge will have a degree of inaccuracy, if this is acceptable then you should consider that approach to, though IMO simulating the game of life incorrectly kinda defeats the purpose.

Another way to go would be to purposely simulate a larger area than you show so objects appear to go off the edge

This question is also here with some good answers.

The simplest modification to your simulation (and not mentioned on the other question) would be to triple the area's length and width, but only show what you currently show. The only catch would be if something went off-screen, hit the wall, and then came back. You could try playing around with the game rules at the boundary to make it more likely for a cell to die (so that a glider could get a little further in before being a block that could mess things up). Maybe that a live cell with three neighbors would die if it were within two steps of the side.

One of the other answers (and our answer) can be summarized as keeping track of the live nodes, not the entire screen. Then you would be able to do cool stuff like zoom and pan as if it were Google Maps.

Here is a JavaScript implementation that maintains a set of cells that are alive by their stringified coordinates. If a cell is not in the set, it is not alive.

The coordinates are BigInt so that only memory is a limit.

The demo below will start with a glider. When the grid has focus you can use the arrow keys to move the display over the "infinite" Conway world and possibly follow the glider on its eternal journey:

class ConwayGame {
    constructor(initialMap) {
        this.alive = new Set();
        initialMap.forEach((line, y) => 
            line[Symbol.iterator]().forEach((ch, x) => 
                ch === "#" && this.alive.add(`${x}_${y}`)
            )
        );
    }
    
    isAlive(x, y) {
        return this.alive.has(`${x}_${y}`);
    }
    
    next() {
        // Get a set of neighboring empty cells, and decide which live cells will die
        const dead = new Map();
        const kill = new Set();
        for (const key of this.alive) {
            const [x, y] = key.split("_").map(BigInt);
            let count = 0;
            for (let i = -1n; i < 2n; i++) {
                for (let j = -1n; j < 2n; j++) {
                    if (!i && !j) continue;
                    const key2 = `${x+i}_${y+j}`;
                    if (this.alive.has(key2)) {
                        count++;
                    } else {
                        dead.set(key2, (dead.get(key2) ?? 0) + 1);
                    }
                }
            }
            if (count < 2 || count > 3) kill.add(key);
        }
        // Kill the cells that are marked for it:
        for (const key of kill) {
            this.alive.delete(key);
        }
        // Decide which new cells will be born
        for (const [key, count] of dead) {
            if (count === 3) this.alive.add(key);
        }
    }
}

const conway = new ConwayGame(["..#",
                               "#.#",
                               ".##"]);

// I/O handling
const rowCount = 16;
const colCount = 50;
const offset = [0n, 0n];
const div = document.querySelector("#msg");
const table = document.querySelector("table");
table.innerHTML = ("<tr>" + "<td></td>".repeat(colCount) + "</tr>").repeat(rowCount);

function display() {
    const [dx, dy] = offset;
    for (let y = 0, worldX = offset[0]; y < rowCount; y++, worldX++) {
        for (let x = 0, worldY = offset[1]; x < colCount; x++, worldY++) {
            table.rows[y].cells[x].style.backgroundColor = 
                conway.isAlive(worldX, worldY) ? "black" 
              : ((worldX / 5n) + (worldY / 5n)) % 2n ? "pink" 
              : "";
        }
    }
    div.textContent = offset.join();
}

setInterval(() => {
    conway.next();
    display();
}, 100);

document.addEventListener("keydown", function (e) {
    const key = ["ArrowRight", "ArrowLeft", "ArrowDown", "ArrowUp"].indexOf(e.key); 
    if (key < 0) return;
    offset[0] += BigInt((key === 2) - (key === 3));
    offset[1] += BigInt((key === 0) - (key === 1));
    display();
    e.preventDefault();
    return false;
});

#msg { position: absolute }
table { border-collapse: collapse }
td { border: 1px solid gray; min-width: 8px; height: 8px; }

<div id="msg"></div>
<table></table>