4

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.

  • 1
    either you make it 'infinite' or wrap the opposite edges (thus becoming a torus) – Mitch Wheat Sep 01 '13 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 Sep 02 '13 at 00: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 Sep 02 '13 at 05:27

3 Answers3

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]];
}
Andrew Tomazos
  • 66,139
  • 40
  • 186
  • 319
  • 1
    is this c++, the question is tagged js – aaronman Sep 02 '13 at 00:24
  • Oh sorry, don't know JS that well - I'm here from algorithm tag. Whats the arbitrary precision integer in JS? I might be able to translate. – Andrew Tomazos Sep 02 '13 at 00:25
  • JS sucks, I doubt there is one :( – aaronman Sep 02 '13 at 00:26
  • @VoronoiPotato good link but can't believe this answer got accepted, it has little to no content and is written in C++, WTF – aaronman Sep 03 '13 at 16:48
  • @aaronman: The OP question is essentially what data strucutre to use to represent an arbitrarily-expandng game board ("faking being infinite", "getting rid of the edges"). Your post below doesn't really answer that question, and is arguably incorrect as it claims it to be impossible. – Andrew Tomazos Sep 03 '13 at 17:36
  • Yeah basically the reason why this one got the answer is he was looking to a pragmatic "good enough" solution rather than a theory expose. It's not really an answer true, but knowing about arbitrary precision integers is the key he needed to get where he wanted to be. – VoronoiPotato Sep 03 '13 at 17:51
  • @user1131467 sorry but I only claimed it's impossible from a theoretical standpoint, and if you read my answer I proposed 2 ways both IMO better than your way because they don't involve letting the game allocate too much memory (definitely not something you want in JS). I'm 90% sure the only reason the OP accepted your answer is that you chose to down-vote it for opinionated reasons – aaronman Sep 03 '13 at 18:24
  • @aaronman: From a theoretical standpoint your answer is also wrong. You can run the game with the data structure I specify for as many turns as you like on a Turing Machine, and it will give accurate results. Using a Torus will not give accurate results. Using a "larger area" matrix will also not give accurate results, because it can also reach the edge there. – Andrew Tomazos Sep 04 '13 at 06:22
  • @aaronman I accepted this answer because it showed an implementation that was fundamentally different from my own and exhibited the behavior that I wanted to know about. Using a torus, as you suggested, is an interesting way to overcome the edge problem that I hadn't considered, but it still leaves me with a "finite" plane. As for the answer being in C++, the concept came across clearly enough that I at least know the direction to take if I want to improve my implementation. Best regards. –  Sep 04 '13 at 14:22
  • Addendum: Forgot to mention @MitchWheat first suggested the torus. –  Sep 04 '13 at 15:05
  • I forgot the "I". The mistake was on my part. –  Sep 04 '13 at 15:51
0

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 complete you can't fake it being infinite in every situation without having infinite memory.

Since the game of life is turing complete that means if a something "goes off the edge" it is impossible to tell if it will come 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

aaronman
  • 18,343
  • 7
  • 63
  • 78
  • 2
    If you agree that you can represent an "infinite integer" by an arbitrary-precision integer, then see my answer. Of course it is impossible to hold arbitrarily-large data in a finite capacity of memory, but you can write a program that can handle an arbitrarily-large amount of data in an sufficiently large amount of memory. – Andrew Tomazos Sep 02 '13 at 00:30
  • 1
    @user1131467 I think it's dangerous to let the game of life have as much space as it wants, because there is no way to predict what it will do for a general case, I hope ur not the downvoter – aaronman Sep 02 '13 at 00:32
  • 3
    By "no way to predict", you mean it will exhaust available memory. Yes, of course that is possible. There is a difference between your program failing with an out-of-memory error, and placing arbitrary limits on your program. – Andrew Tomazos Sep 02 '13 at 00:35
  • @user1131467 If you read my answer I conceded that if you allowed the simulation to expand that is one way to go, but the fact is you have to place a limit on at some point, I just felt that a question about simulating the game of life deserved a theoretical type answer – aaronman Sep 02 '13 at 00:37
  • 1
    @user1131467 anyway regardless of our disagreements I don't think I said anything incorrect, so if the down-vote was you I'd appreciate if you took it away – aaronman Sep 02 '13 at 00:56
0

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 becoming 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.

Community
  • 1
  • 1
Teepeemm
  • 4,331
  • 5
  • 35
  • 58