Strange spaceship that is supposed to be impossible and infinite cell spread

[IAmRasputin]

So, recently I wrote the "Game of Life" using Lua and LOVE2D engine for visualization. The first thing I have noticed is that in 90% of outcomes the cells continued to spread infinitely. Then, the only spotted spaceship was the one in red circle on the image below. I followed the rules of the automata and yet the result is still confusing me. Does anyone have an idea of what can be wrong (or maybe it's just me still struggling with lua)?

Here's the code for the "rules" part for those who can read it:

Code: Select all

function live()
  fieldB = field

  for i=1, 398 do
    for j=1, 198 do
      num = 0
      if field[i-1][j-1] == 1 then num = num + 1 end 
      if field[i][j-1] == 1 then num = num + 1 end 
      if field[i+1][j-1] == 1 then num = num + 1 end 
      if field[i-1][j] == 1 then num = num + 1 end 
        if num >= 4 then goto done end 
      if field[i+1][j] == 1 then num = num + 1 end 
      if field[i-1][j+1] == 1 then num = num + 1 end 
      if field[i][j+1] == 1 then num = num + 1 end 
      if field[i+1][j+1] == 1 then num = num + 1 end 

      ::done::

      if (num ~= 3 and fieldB[i][j] == 0) then fieldB[i][j] = 0
      elseif ((num ~= 2 and num ~= 3) and fieldB[i][j] == 1) then fieldB[i][j] = 0
      elseif ((num == 2 or num == 3) and field[i][j]) == 1 then fieldB[i][j] = 1
      elseif (num == 3 and fieldB[i][j] == 0) then fieldB[i][j] = 1
      else fieldB[i][j] = 0
      end
    end
  end
return fieldB
end

[Ian07]

I'm pretty sure this is because you've accidentally created an implementation of what's sometimes known as NaiveLife (as it's a common mistake made by many people coding CGoL for the first time): you're probably updating the cells as you go along, rather than updating them all at the same time after all of their next states have been evaluated and stored.

[IAmRasputin]

I thought about that. The thing is that I'm using two arrays. The first one contains the old cell position and is used to calculate the next position of each cell, and the second one stores their newly calculated position. In the end the 'old' array is equated to the 'new' array. So they basically are all updated at the same time(

[Ian07]

Ah, I might have run into this same issue when trying to make CGoL in JavaScript a while ago. I'm not sure why, but it seems that changing the entire array by saying "currentArray = nextArray;" doesn't actually work: rather you have to change each cell individually using another nested loop. (i.e. "currentArray[i][j] = nextArray[i][j];") Again, why this happens is beyond me, but hopefully the solution does work.

[dvgrn]

I thought about that. The thing is that I'm using two arrays. The first one contains the old cell position and is used to calculate the next position of each cell, and the second one stores their newly calculated position. In the end the 'old' array is equated to the 'new' array. So they basically are all updated at the same time.

Yeah, I was also going to accuse you of implementing NaiveLife -- but NaiveLife doesn't look much like your screenshots.

However, check your code in this section:

Code: Select all

      if (num ~= 3 and fieldB[i][j] == 0) then fieldB[i][j] = 0
      elseif ((num ~= 2 and num ~= 3) and fieldB[i][j] == 1) then fieldB[i][j] = 0
      elseif ((num == 2 or num == 3) and field[i][j]) == 1 then fieldB[i][j] = 1
      elseif (num == 3 and fieldB[i][j] == 0) then fieldB[i][j] = 1
      else fieldB[i][j] = 0

The third line's first array reference is correctly field[​i][j], but lines 1, 2, and 4 say fieldB instead of field. So you've invented a new CA rule that probably nobody has ever done before in the history of Conway's Life. Could call it something like "ThreeFourthsNaiveLife", maybe.

(Short summary: sometimes you're accidentally reading from your new array instead of from your old one.)

[Moosey]

From your screenshots, it is easy to tell that you have not implemented GoL-- there is a mess in the middle which is definitely not characteristic of GoL

Still, it does look like a somewhat interesting OCA rule

[blah]

It's writing to the same array it's reading from. dvgrn's point is also correct; some instances of fieldB should be field.

One solution is to copy all the contents of field into fieldB and then return fieldB. That makes no sense, though, when you could just alternate between the two arrays, which is obviously faster than redundantly copying the entire field every step.

Here's a modified version of your code that works. You can run it in a command-line and press enter to advance the displayed generation, and type 'quit' to exit:

Code: Select all

function live(field, new_field)
  --Simulate one generation of B3/S23 on field, writing the result to new_field.
  for i=1, 64 do
    for j=1, 64 do
      num = 0
      if field[i-1][j-1] == 1 then num = num + 1 end 
      if field[i][j-1] == 1 then num = num + 1 end 
      if field[i+1][j-1] == 1 then num = num + 1 end 
      if field[i-1][j] == 1 then num = num + 1 end 
        if num >= 4 then goto done end 
      if field[i+1][j] == 1 then num = num + 1 end 
      if field[i-1][j+1] == 1 then num = num + 1 end 
      if field[i][j+1] == 1 then num = num + 1 end 
      if field[i+1][j+1] == 1 then num = num + 1 end 

      ::done::

      if (num ~= 3 and field[i][j] == 0) then new_field[i][j] = 0
      elseif ((num ~= 2 and num ~= 3) and field[i][j] == 1) then new_field[i][j] = 0
      elseif ((num == 2 or num == 3) and field[i][j]) == 1 then new_field[i][j] = 1
      elseif (num == 3 and field[i][j] == 0) then new_field[i][j] = 1
      else new_field[i][j] = 0
      end
    end
  end
end

fieldA = {}
fieldB = {}
for i=0, 65 do
  fieldA[i]={}
  fieldB[i]={}
  for j=0, 65 do
    if i==0 or i==65 or j==0 or j==65 then --ensure cells outside grid are dead
      fieldA[i][j]=0
    else
      fieldA[i][j] = math.random(2)-1
    end
    fieldB[i][j]=0
  end
end
while io.read()~="quit" do
  for i=1, 64 do
    for j=1, 64 do
      io.write(fieldA[i][j]);
    end
  print("")
  end
  live(fieldA, fieldB)
  swap = fieldA
  fieldA = fieldB
  fieldB = swap
end

Ah, I might have run into this same issue when trying to make CGoL in JavaScript a while ago. I'm not sure why, but it seems that changing the entire array by saying "currentArray = nextArray;" doesn't actually work: rather you have to change each cell individually using another nested loop. (i.e. "currentArray[ i][j] = nextArray[ i][j];") Again, why this happens is beyond me, but hopefully the solution does work.

I remember having the same experience trying to implement cellular automata in JavaScript. I was similarly baffled and incredulous as to why it didn't copy the contents of the array, and now that I know more about computers, I'm baffled and incredulous at the implication that it should work any other way.

Processors do not deal in large volumes of data, they deal in registers, no larger than 64 bits. The fundamental operations and types of a language will often reflect this. The assignment operator, to me as a more low-level programmer, seems like it should take O(1) under all circumstances, and copying a large space of memory involves many operations, presumably a function call to memcpy(). As such, the intuition of a low-level programmer tells them that copying an entire memory space requires a loop, and since arrays are pointers, setting an array to another array means setting a pointer to another pointer. Thus the low-level programmer finds this behaviour not just reasonable, but obvious.

Does that make sense?

EDIT 2020-12-01: It turns out my swapping code is slightly overcomplicated. You can just do "fieldA, fieldB = fieldB, fieldA" to swap the arrays.

[IAmRasputin]

Thank you! It works perfectly now. It seems that the main problem was that the second array was assigned all values of the first one in the constructor function so I never had a clear field to assign new cell values to

[blah]

It seems that the main problem was that the second array was assigned all values of the first one in the constructor function so I never had a clear field to assign new cell values to

I'm not sure you understand why your original program didn't work. Your phrasing here implies you still think fieldB and field in your function were actually different arrays, but that fieldB had been 'assigned all values of' field, which is not the case; fieldB=field does not create a new array.

And you also seem to think the field being written to has to be 'clear', which I assume means all 0s? That's not true, given that you're overwriting all its contents (other than the edges), and not reading from it.

[IAmRasputin]

My bad in explaining stuff. I meant that I was firstly creating array "A" and filling it with cells and then assigning "B" values of "A". Guess it's better for me to just show the constructor code:

Code: Select all

function test0:new()
  math.randomseed(os.time())

  iterations = 0

  field = {}
  fieldBCKP = {}

  w = 479
  h = 199

  for i=0, w do
    field[i] = {}
    fieldBCKP[i] = {}
    for j=0, h do
      field[i][j] = 0
      fieldBCKP[i][j] = 0
    end
  end

  for i=1, w - 1 do
    for j=1, h - 1 do
      a = math.random()
      if a >= 0.93 then field[i][j] = 1
      else field[i][j] = 0 end
      a = 0
    end
  end

  fieldBCKP = field --this line is the cause of all confusion

end

[yay]

Ah, I might have run into this same issue when trying to make CGoL in JavaScript a while ago. I'm not sure why, but it seems that changing the entire array by saying "currentArray = nextArray;" doesn't actually work: rather you have to change each cell individually using another nested loop. (i.e. "currentArray[j] = nextArray[j];") Again, why this happens is beyond me, but hopefully the solution does work.

I believe this is due to arrays being passed by reference, which makes it so that assigning an array to a variable causes it to store a reference instead of a new copy of the array. Example:

Code: Select all

// this is javascript
const arr = ["item1", "item2"]
console.log("arr is: " + arr)
const newArr = arr
console.log("newArr is: " + newArr)
console.log("modifying newArr")
newArr[1] = "a modified item"
console.log("newArr is now: " + newArr)
console.log("arr is now: " + arr)