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

For scripts to aid with computation or simulation in cellular automata.
Post Reply
User avatar
IAmRasputin
Posts: 4
Joined: February 2nd, 2020, 1:18 pm

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

Post by IAmRasputin » February 2nd, 2020, 2:25 pm

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
Attachments
unknown.png
unknown.png (302.92 KiB) Viewed 420 times
unknown (2).png
unknown (2).png (521.67 KiB) Viewed 420 times
unknown (1).png
unknown (1).png (220.87 KiB) Viewed 420 times

Ian07
Posts: 488
Joined: September 22nd, 2018, 8:48 am

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

Post by Ian07 » February 2nd, 2020, 2:57 pm

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.

User avatar
IAmRasputin
Posts: 4
Joined: February 2nd, 2020, 1:18 pm

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

Post by IAmRasputin » February 2nd, 2020, 3:05 pm

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
Posts: 488
Joined: September 22nd, 2018, 8:48 am

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

Post by Ian07 » February 2nd, 2020, 3:13 pm

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.

User avatar
dvgrn
Moderator
Posts: 6310
Joined: May 17th, 2009, 11:00 pm
Location: Madison, WI
Contact:

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

Post by dvgrn » February 2nd, 2020, 3:17 pm

IAmRasputin wrote:
February 2nd, 2020, 3:05 pm
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.)

User avatar
Moosey
Posts: 3069
Joined: January 27th, 2019, 5:54 pm
Location: A house, or perhaps the OCA board. Or [click to not expand]
Contact:

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

Post by Moosey » February 3rd, 2020, 9:40 am

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
I am a prolific creator of many rather pathetic googological functions

My CA rules can be found here

Also, the tree game
Bill Watterson once wrote: "How do soldiers killing each other solve the world's problems?"

User avatar
blah
Posts: 248
Joined: April 9th, 2016, 7:22 pm

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

Post by blah » February 5th, 2020, 2:13 pm

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
Ian07 wrote:
February 2nd, 2020, 3:13 pm
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?
succ

User avatar
IAmRasputin
Posts: 4
Joined: February 2nd, 2020, 1:18 pm

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

Post by IAmRasputin » February 7th, 2020, 7:22 am

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
Attachments
solved.png
solved.png (22.86 KiB) Viewed 227 times

User avatar
blah
Posts: 248
Joined: April 9th, 2016, 7:22 pm

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

Post by blah » February 8th, 2020, 6:28 am

IAmRasputin wrote:
February 7th, 2020, 7:22 am
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.
succ

User avatar
IAmRasputin
Posts: 4
Joined: February 2nd, 2020, 1:18 pm

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

Post by IAmRasputin » February 8th, 2020, 12:45 pm

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

Post Reply