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

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

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

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

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
Posts: 4
Joined: February 2nd, 2020, 1:18 pm

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

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

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
Moderator
Posts: 6310
Joined: May 17th, 2009, 11:00 pm
Contact:

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

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.

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

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?"

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

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

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

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

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

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 (22.86 KiB) Viewed 227 times

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

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

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

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

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

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