Page 1 of 1

### Euclidean CA (ECA)

Posted: November 20th, 2018, 5:43 pm
There is an interesting sort of CA that comes when one considers an infinite universe, where the cells have less and less of an effect as their Euclidean Distance becomes greater.

This script runs CA with the following rules:

-The 'heat' or neighbour count of a cell is the total sum of all reciprocals of quarted(^4) euclidean distances to other live cells.
-It chooses to birth or survive cells based on thresholds specified by the rule. For example, ECA:B(1,2)(3,4)/S(3,6) would birth if the heat was between 1 and 2 (including both of those), or 3 and 4, and survive if between 3 and 6.

Code: Select all

``````--This is a preliminary version. If sufficiently interesting behaviours show
--up, it would be nice to get a full simulating algorithm in better-written
--softawre like Golly. Speaking of Golly, make sure you have a version that
--supports Lua, so you can run this script. Stinky.

--TERMS TO KNOW:
--Heat - The number returned when the previous equation is ran on all of the
--       other cells in relation to the given cell (basically what count()
--       does)

local g = golly()
local gp = require "gplus"

local rulesB = {.01, 7}
local rulesS = {}

function count(x1, y1) --determine cell's heat
local pat
local total = 0
if g.getcell(x1, y1) == 1 then --ok i know it's ugly but it saves a lot of processing time than doing a conditional
g.setcell(x1, y1, 0)
pat = g.getcells(g.getrect())
g.setcell(x1, y1, 1)
else
pat = g.getcells(g.getrect())
end

for i = 1, #pat, 2 do
local x2 = pat[i]
local y2 = pat[i+1] --ugly
total = total+1 / ((x2-x1)^2+(y2-y1)^2)^2 --i know i said i was using fourth powers, however the square root and fourth power cancel out leaving just a stray ^2
end

end

function ring(r) --basically, it returns a 'outer moore birth ring' of the given size
local pat = g.getcells(g.getrect())
local x, y, w, h = table.unpack(r) --there a better way to do this?
g.select({x-1, y-1, w+2, h+2})
g.randfill(100)
g.select({x, y, w, h})
g.clear(0)
local nring = g.getcells(g.getrect())
g.putcells(pat)
g.clear(1)
g.select({})
return nring
end

function step()
--hoooo boy i hated writing this
--don't read it if you don't want to get lost
local pat = g.getcells(g.getrect())
if g.getpop() == "0" then
return
end
local rulesBclone = rulesB
table.sort(rulesBclone)
local minrulesB = rulesBclone[1] --math.min but with an array
local lx, ly, lw, lh = table.unpack(g.getrect())
while true do --this loop determines how far to check for births
local localmax = 0
local localring = ring({lx, ly, lw, lh})
for i = 1, #localring, 2 do
local localcount = count(localring[i], localring[i+1])
if localcount > localmax then
localmax = localcount
end
end
if localmax < minrulesB then
break
end
lx = lx - 1
ly = ly - 1
lw = lw + 2
lh = lh + 2
end
--gosh that took me months to make, now onto processing
g.select({lx, ly, lw, lh})
g.randfill(100)
g.putcells(pat, 0, 0, 1, 0, 0, 1, --[[ugh why]] "xor")
local area = g.getcells(g.getrect())
g.clear(0)
g.putcells(pat)
--NOW LET'S FINALLY PROCESS BIRTH, aka the reason that hellhole of lines above had to be done
local localcells = {}
for i = 1, #area, 2 do
local localcount = count(area[i], area[i+1])
for j = 1, #rulesB, 2 do
if localcount >= rulesB[j] and localcount <= rulesB[j+1] then
table.insert(localcells, area[i])
table.insert(localcells, area[i+1]) --can't think of a way to insert two at once
end
end
end
--and survival, the easy part
for i = 1, #pat, 2 do
local localcount = count(pat[i], pat[i+1])
for j = 1, #rulesS, 2 do
if localcount >= rulesS[j] and localcount <= rulesS[j+1] then
table.insert(localcells, pat[i])
table.insert(localcells, pat[i+1])
end
end
end
g.select(g.getrect())
g.clear(0)
g.putcells(localcells)
g.select({})
g.setgen(tonumber(g.getgen())+1)
end

while true do
step()
g.update()
step()``````
There are optimizations, but I will briefly explain some properties I have noticed.

Thresholds

A cell with maximum heat would be surrounded by infinitely many cells. This 'maximum heat' number is finite, but I do not yet know its value. A 511x511 block of cells yields the number 6.0267726589419..., but that's not even close to a good estimate. I have settled on using 7 when engineering day and night-esque rules.

Another threshold that isn't yet known is being able to expand outside its bounding box.

EDIT 11/30/2018: Thanks to Caenbe and Freywa for pointing out that the maximum heat is (2/3)*pi^2*C, where C = Catalan's constant. Wolfram says this is the value to 1000 digits:

Code: Select all

``6.0268120396919401235462601927282855839417908072537241239789823989168652037814250418764946630938418433906127747493598517914519884043536868495100966503449541972750061912676710610851774101700255398481455670182612361266898875483352921070069449008114281527829434299322822560251114200149117706817994764236876636117413174159952976496849741988010861076557834927010493267788390209735731100040920526016251643211225971568622986661712279082923986446238998997768676990659832983376483731474723643953842741351597605714161337207790707042631552431695921352276400390580604568489239229700788071861541187775637812405539300590870406433494222017883382946074250172136911832633689703956037954481037629038480262769680362849773653130682557719791223453092147760706480221366950515486440933396727770173048557378012773452636411632552957204199179226582314343628445920394854336019550159007480469325289524410543403938235788421982263661511011524075413030449483389003139678799601958658704861812673964630612466034108439517982559502176303...``
[/i]

Lonely patterns

Ah, yes, a big problem. I had to choose between either having patterns that can only exist alone on a grid, or having patterns behave way differently when alone. Yes, there are patterns that, due to having maximized or minimized heat within a range, can only exist alone. You could engineer this for any pattern, really. For example, here is a glider (quite vast in its rule range) that can exist only by itself in this rule:

Code: Select all

``````#C rule = ECA:B(1.15,1.5625)/S(1.6,3)
x = 2, y = 3, rule = B/S012345678
bo\$2o\$bo!
``````

Code: Select all

``````#C rule = ECA:B(1.15,1.5625)/S(1.6,3)
x = 9, y = 3, rule = B/S012345678
bo\$2o6bo\$bo!
``````
The speed of light

This one may bother calcyman and Apple Bottom and the like. The speed of light in this rule is infinite, so it is way more comfortable to use one cell per generation. To demonstrate it is infinite, a single cell in the rule ECA:B(.01,7)/S (I've nicknamed this family of quite redundant rules 'Target', this would be 'Target.01') turns into this monstrosity in 5 generations:

Code: Select all

``````#C rule = ECA:B(.01,7)/S
x = 57, y = 57, rule = B/S012345678
23b11o\$19b19o\$17b23o\$15b27o\$13b31o\$12b33o\$10b37o\$9b15o9b15o\$8b13o15b
13o\$7b12o19b12o\$6b11o23b11o\$6b10o25b10o\$5b9o29b9o\$4b9o31b9o\$4b8o12b9o
12b8o\$3b9o10b13o10b9o\$3b8o9b17o9b8o\$2b8o9b19o9b8o\$2b8o8b21o8b8o\$b8o8b
23o8b8o\$b8o7b10o5b10o7b8o\$b7o8b8o9b8o8b7o\$b7o7b8o11b8o7b7o\$8o7b7o13b7o
7b8o\$7o7b7o15b7o7b7o\$7o7b7o6b3o6b7o7b7o\$7o7b6o6b5o6b6o7b7o\$7o7b6o5b7o
5b6o7b7o\$7o7b6o5b3ob3o5b6o7b7o\$7o7b6o5b7o5b6o7b7o\$7o7b6o6b5o6b6o7b7o\$
7o7b7o6b3o6b7o7b7o\$7o7b7o15b7o7b7o\$8o7b7o13b7o7b8o\$b7o7b8o11b8o7b7o\$b
7o8b8o9b8o8b7o\$b8o7b10o5b10o7b8o\$b8o8b23o8b8o\$2b8o8b21o8b8o\$2b8o9b19o
9b8o\$3b8o9b17o9b8o\$3b9o10b13o10b9o\$4b8o12b9o12b8o\$4b9o31b9o\$5b9o29b9o\$
6b10o25b10o\$6b11o23b11o\$7b12o19b12o\$8b13o15b13o\$9b15o9b15o\$10b37o\$12b
33o\$13b31o\$15b27o\$17b23o\$19b19o\$23b11o!
``````
Rules & Other miscellany
This rulespace is infinitely big. To start, here's a rule with a rhomblicator and the aforementioned T-glider:

Code: Select all

``````#C rule = B(1.15,1.2)(1.3,1.4)(1.5,1.6)/S(1.603,2.5)(3,4)
x = 2, y = 13, rule = B/S012345678
bo\$2o\$bo8\$o\$2o\$bo!
``````
I guess I'll post more rules later once I've done more research.

### Re: Euclidean CA (ECA)

Posted: November 20th, 2018, 6:01 pm
I noticed my script has a glitch when running the rule

Code: Select all

``````local rulesB = {.085, .105, .135, .143, 2, 2.15}
local rulesS = {1, 1.02, 2, 2.5}``````
A domino becomes asymmetric in 3 generations.

### Re: Euclidean CA (ECA)

Posted: November 20th, 2018, 7:40 pm
danny wrote:I noticed my script has a glitch when running the rule

Code: Select all

``````local rulesB = {.085, .105, .135, .143, 2, 2.15}
local rulesS = {1, 1.02, 2, 2.5}``````
A domino becomes asymmetric in 3 generations.
Probably because floating-point addition is non-associative.

### Re: Euclidean CA (ECA)

Posted: November 20th, 2018, 7:57 pm
calcyman wrote:Probably because floating-point addition is non-associative.
Aarrgghh. How do I fix this?

### Re: Euclidean CA (ECA)

Posted: November 20th, 2018, 8:27 pm
danny wrote:
calcyman wrote:Probably because floating-point addition is non-associative.
Aarrgghh. How do I fix this?
When you compute the 'total', you need to sort the cells by distance before summing.

I don't know the Lua equivalent of this, but in pseudocode it would be:
• Create an empty list.
• Iterate over the other cells, appending the values 1/((x2-x1)^2+(y2-y1)^2)^2 to the list.
• Sort the list into ascending order.
• Traverse the list in order, accumulating a running total.

### Re: Euclidean CA (ECA)

Posted: November 22nd, 2018, 4:32 pm
The script does not work.

### Re: Euclidean CA (ECA)

Posted: November 22nd, 2018, 10:10 pm
fluffykitty wrote:The script does not work.
Just replace "step()" on the last line with "end".

Edit:
calcyman wrote:
danny wrote:
calcyman wrote:Probably because floating-point addition is non-associative.
Aarrgghh. How do I fix this?
When you compute the 'total', you need to sort the cells by distance before summing.

I don't know the Lua equivalent of this, but in pseudocode it would be:
• Create an empty list.
• Iterate over the other cells, appending the values 1/((x2-x1)^2+(y2-y1)^2)^2 to the list.
• Sort the list into ascending order.
• Traverse the list in order, accumulating a running total.
Unfortunately, in this very particular case, sorting the list in ascending order and then calculating the sum gives the less precise result (which is < 0.85) whereas calculating the list in descending order and then calculating the sum gives the expected result ( == 0.85). It's not too surprising that floating point summations and comparisons can't be relied on here, but it still is annoying. In Python, using math.fsum() gives the expected result for both sort orders, but that probably can't be relied on. It's also possible to use something like math.isclose() as part of the comparison, but it seems to me that for this application there are bound to be cases where the exact count of a particular cell actually is really close to a birth or survival threshold and comparing with isclose() may actually give the wrong result for a particular tolerance value.

I suspect there are two options here:
• Use a summing algorithm (such as calcyman's) which gives the same result for all cells whose count should be equal, but accept that sometimes it will be wrong, or
• Use a more precise summing algorithm (such as Python's fsum) which probably gives the expected result more often (and consistently), but will be much slower.
For lua, there is this implementation of fsum. The performance hit is significant for a population of 100, and above 1000 cells it's rather horrible.

### Re: Euclidean CA (ECA)

Posted: November 27th, 2018, 5:43 am
Here's a version of the Euclidean CA script which uses the FastFloatSum implementation I linked to in the previous post. I've made a few other changes in an attempt to improve performance for larger patterns, particularly where there are distantly separated parts of the current pattern. Performance for populations > 200 starts to really suffer.

Code: Select all

``````-- EuclideanCA.lua, v0.2
-- This is a preliminary version. If sufficiently interesting behaviours show
-- up, it would be nice to get a full simulating algorithm in better-written
-- software like Golly. Speaking of Golly, make sure you have a version that
-- supports Lua, so you can run this script.

-- TERMS TO KNOW:
-- Weight:  The contribution of an On cell to the heat of another cell given
--          by the reciprocal of its euclidean distance to the fourth power
-- Heat:    The heat of each cell is calculated by summing the weights
--          of all live cells relative to the current cell

-- Author: Dani, Nov 2018
-- Contributors: Arie Paap

local g = golly()
local gp = require "gplus"

-- Birth and survival ranges
--local rulesB = {.01, 7}
--local rulesS = {}
local rulesB = {.085, .105, .135, .143, 2, 2.15}
local rulesS = {1, 1.02, 2, 2.5}

--[[
Accurate floating point summation. Like Python's fsum.
This version collect partial sums in reverse order, with each entry (except last) used up all 53 bits.
Author: Albert Chan
See http://lua-users.org/wiki/FloatSumFast
--]]
local function fsum(v)
local p, abs = {1}, math.abs    -- p[1] == #p
local p, i = p, 2
for j = 2, p[1] do
local y = p[j]
if abs(x) > abs(y) then x, y = y, x end
local hi = x + y
local lo = x - (hi - y)
x = hi
if lo ~= 0 then p[i] = x; x = lo; i = i + 1 end
end
if x ~= x then p[1] = 2 return end  -- Inf or NaN
p[1] = i
p[i] = x
end
local function ftotal(clear)
if clear then p[1] = 1 end  -- clear all partials
repeat
local n, overlap = p[1], false
local prev = {table.unpack(p, 1, n)}
if n <= 3 then return p[2] end
for i = 1, n do
if p[i] ~= prev[i] then overlap = true; break end
end
until not overlap
local x, lo, err = table.unpack(p, 2, 4)
if (lo < 0) == (err < 0) then
lo = lo * 2             -- |lo| = 1/2 ULP
local hi = x + lo       -- -> x off 1 ULP
if lo == hi - x then x = hi end
end
return x
end
for i = 1, #v do fadd(v[i]) end
return ftotal()
end

-- Table to store cell heat as they are calculated.
local cellcounts = {}
local function getcount(x, y, pat)
g.doevent("") -- Allow Esc to abort
local key = x..' '..y
local c = cellcounts[key]
if not c then
local patweights = {}
for i = 2, #pat, 2 do
local w = 1.0/((pat[i-1]-x)^2 + (pat[i]-y)^2)^2
if w == math.huge then w = 0.0 end
patweights[i//2] = w
end
c = fsum(patweights)
cellcounts[key] = c
end
return c
end
local function clearcounts()
cellcounts = {}
end

-- Expand the current pattern by including all cells within a given distance of any On cell
-- Uses an LtL rule with disc neighbourhood, all Birth and no Survival
-- Returns a cell list containing the additional cells
local neighbourcounts = {8, 20, 36, 68, 96, 136, 176, 224, 292, 348}
local currpat = g.getcells(g.getrect())
g.run(1)
local nring = g.getcells(g.getrect())
g.putcells(currpat)
return nring
end

-- Evolve the current pattern one step in the given ECA rule
local function step()
if g.getpop() == "0" then
return
end
local pat = g.getcells(g.getrect())
local gen = tonumber(g.getgen())
local rule = g.getrule()
local algo = g.getalgo()
local minrulesB = math.min(table.unpack(rulesB))
clearcounts() -- clear the cache of cell heats

-- Determine how far out from the current pattern to test for birth
expand(2) -- Assume a ring of at least size 2 is required
while true do
local localmax = 0
local localring = expand(2)
for i = 1, #localring, 2 do
local localcount = getcount(localring[i], localring[i+1], pat)
if localcount > localmax then
localmax = localcount
if localmax >= minrulesB then break end -- Need to expand the ring further
end
end
if localmax < minrulesB then break end
end
-- All cells which need to be checked for birth or survival are now On
-- Remove the cells from this current pattern to get the list of cells to test for birth
g.putcells(pat, 0, 0, 1, 0, 0, 1, "xor")
local area = g.getcells(g.getrect())

-- Process birth
local localcells = {}
for i = 1, #area, 2 do
local localcount = getcount(area[i], area[i+1], pat)
for j = 1, #rulesB, 2 do
if localcount >= rulesB[j] and localcount <= rulesB[j+1] then
localcells[#localcells+1] = area[i]
localcells[#localcells+1] = area[i+1]
end
end
end

-- Process survival
for i = 1, #pat, 2 do
local localcount = getcount(pat[i], pat[i+1], pat)
for j = 1, #rulesS, 2 do
if localcount >= rulesS[j] and localcount <= rulesS[j+1] then
localcells[#localcells+1] = pat[i]
localcells[#localcells+1] = pat[i+1]
end
end
end

-- Update the pattern
g.select(g.getrect())
g.clear(0)
g.setalgo(algo)
g.setrule(rule)
g.putcells(localcells)
g.select({})
g.setgen(gen+1)
end

g.show("Press 'q' to quit.")

while true do
step()
g.update()
local event = g.getevent()
if #event > 0 then
if event:find("^key") then
local _, key, mods = gp.split(event)
if key == "q" then break end
else
g.doevent(event)
end
end
end

g.show("")
``````
Edit: I forgot to mention that a large part of the performance degradation of the Fast Float Sum implementation for large populations was due to the usage of var args. I modified the function to accept an array instead, and this improved the situation, but there's no getting away from the O(N^2) characteristic inherent in the Euclidean CA definition.

### Re: Euclidean CA (ECA)

Posted: November 30th, 2018, 1:04 am
danny wrote: A cell with maximum heat would be surrounded by infinitely many cells. This 'maximum heat' number is finite, but I do not yet know its value. A 511x511 block of cells yields the number 6.0267726589419..., but that's not even close to a good estimate. I have settled on using 7 when engineering day and night-esque rules.
That's actually pretty close to the actual value of (2/3)*pi^2*G, where G is Catalan's constant.
Proof coming. Maybe soon, maybe not. EDIT: Here is my derivation, in case anyone is interested: viewtopic.php?f=12&p=66047#p66047

### Re: Euclidean CA (ECA)

Posted: November 30th, 2018, 2:51 am
Caenbe wrote:
danny wrote: A cell with maximum heat would be surrounded by infinitely many cells. This 'maximum heat' number is finite, but I do not yet know its value. A 511x511 block of cells yields the number 6.0267726589419..., but that's not even close to a good estimate. I have settled on using 7 when engineering day and night-esque rules.
That's actually pretty close to the actual value of (2/3)*pi^2*G, where G is Catalan's constant.
Proof coming. Maybe soon, maybe not.
The maximum heat is indeed 2/3 * pi^2 * G = 4 * G * zeta(2) = 6.0268120… It is equivalent to 4 * (q + s), where q is the sum of −4th-power distances to (1, 0), (2, 0), (3, 0)… (= zeta(4)) and s is the sum of −4th-power distances to all other cells with both coordinates positive (= G * zeta(2) − zeta(4), as derived e.g. here).

### Re: Euclidean CA (ECA)

Posted: November 30th, 2018, 3:26 am
Thank you! I've added that to the main post with credit.

I will experiment with ECA later on today. Hopefully I will find interesting rulespaces... I may try and write a soup searching program muchlike nbsearch.

### Re: Euclidean CA (ECA)

Posted: November 30th, 2018, 7:01 am
danny wrote:Another threshold that isn't yet known is being able to expand outside its bounding box.
Given that we have computed the maximum heat, this is easily worked out. Take a large rectangle of ON cells in a universe of OFF cells and consider the heat experienced by a cell adjacent to this rectangle in the middle of one side (i.e. the yellow cell below):

Code: Select all

``````x = 115, y = 89, rule = 345/2/4
57.C\$115A\$115A\$115A\$115A\$115A\$115A\$115A\$115A\$115A\$115A\$115A\$115A\$115A
\$115A\$115A\$115A\$115A\$115A\$115A\$115A\$115A\$115A\$115A\$115A\$115A\$115A\$
115A\$115A\$115A\$115A\$115A\$115A\$115A\$115A\$115A\$115A\$115A\$115A\$115A\$115A
\$115A\$115A\$115A\$115A\$115A\$115A\$115A\$115A\$115A\$115A\$115A\$115A\$115A\$
115A\$115A\$115A\$115A\$115A\$115A\$115A\$115A\$115A\$115A\$115A\$115A\$115A\$115A
\$115A\$115A\$115A\$115A\$115A\$115A\$115A\$115A\$115A\$115A\$115A\$115A\$115A\$
115A\$115A\$115A\$115A\$115A\$115A\$115A\$115A!``````
Now expand the rectangle in three directions, the excluded direction being the direction the marked cell lies in. In the limit you get a half-plane of ON cells, and the heat experienced by any OFF cell adjacent to the ON half-plane is L / 2 − zeta(4) = 1.931082… where L is the maximum heat we worked out earlier. The derivation of this number is simply the sum of the parts in the following diagram:

Code: Select all

``````x = 115, y = 89, rule = 345/2/4
57.C\$57AB57A\$57AB57A\$57AB57A\$57AB57A\$57AB57A\$57AB57A\$57AB57A\$57AB57A\$
57AB57A\$57AB57A\$57AB57A\$57AB57A\$57AB57A\$7A3.2A.2A.3A.2A3.2A.6A.2A.3A.
4A.2A.7AB7A3.2A.2A.3A.2A3.2A.6A.2A.3A.4A.2A.7A\$6A.3A.A.A.A.A.2A.3A.2A
.5A.A.A.A.4A2.3A.6AB6A.3A.A.A.A.A.2A.3A.2A.5A.A.A.A.4A2.3A.6A\$6A.6A3.
2A.6A.2A.6A3.2A.3A.A.3A.6AB6A.6A3.2A.6A.2A.6A3.2A.3A.A.3A.6A\$6A.A2.3A
.4A.3A3.3A.A3.2A.4A.2A.2A.3A.6AB6A.A2.3A.4A.3A3.3A.A3.2A.4A.2A.2A.3A.
6A\$6A.3A.3A2.2A.2A.6A.7A2.2A.2A5.2A.6AB6A.3A.3A2.2A.2A.6A.7A2.2A.2A5.
2A.6A\$6A.3A.4A.2A.2A.6A.8A.2A.5A.3A.6AB6A.3A.4A.2A.2A.6A.8A.2A.5A.3A.
6A\$7A3.4A.4A.A5.A.8A.4A.4A.2A.7AB7A3.4A.4A.A5.A.8A.4A.4A.2A.7A\$57AB
57A\$57AB57A\$57AB57A\$115A\$49AB2AB3AB4AB2AB50A\$49ABABABAB4A2B3AB49A\$50A
3B2AB3ABAB3AB49A\$50AB4AB2AB2AB3AB49A\$51A2B2AB2A5B2AB49A\$52AB2AB5AB3AB
49A\$51AB4AB4AB2AB50A\$115A\$57AB57A\$57AB57A\$57AB57A\$57AB57A\$57AB57A\$57A
B57A\$57AB57A\$57AB57A\$57AB57A\$57AB57A\$57AB57A\$57AB57A\$57AB57A\$57AB57A\$
57AB57A\$57AB57A\$57AB57A\$57AB57A\$57AB57A\$57AB57A\$57AB57A\$57AB57A\$57AB
57A\$57AB57A\$57AB57A\$57AB57A\$57AB57A\$57AB57A\$57AB57A\$57AB57A\$57AB57A\$
57AB57A\$57AB57A\$57AB57A\$57AB57A\$57AB57A\$57AB57A\$57AB57A\$57AB57A\$57AB
57A\$57AB57A\$57AB57A\$57AB57A\$57AB57A\$57AB57A\$57AB57A\$57AB57A\$57AB57A\$
57AB57A\$57AB57A\$57AB57A\$57AB57A\$57AB57A\$57AB57A\$57AB57A\$57AB57A!``````
Thus we have that if there is no birth on heat below 1.931082… the pattern cannot expand beyond its bounding box.

Another observation that may help speed up implementations is that the Moore neighbourhood of a cell already contributes 5 out of the possible 6.027 heat that a cell may experience. Interval arithmetic may be useful to decide early whether a cell is born or survives – sum the heat of cells in the Moore neighbourhood to get H, then only proceed to add the heat of more live cells if the interval [H, H + 1.027) contains a boundary point between birth and non-birth or survival and non-survival.

The following patterns were found in B(1.15,1.2)(1.3,1.4)(1.5,1.6)/S(1.603,2.5)(3,4). Here are p2 c spaceships:

Code: Select all

``````x = 17, y = 8, rule = B3/S23
2b2o11b2o\$2bo12bo\$obo10bobo\$2bo12bo\$3bo12bo\$b2o11b2o2\$14bo!``````

Code: Select all

``````x = 30, y = 5, rule = B3/S23
2bo\$29bo\$30o\$o\$25bobo!``````
2×N rectangles (N > 2) also just stretch longer and longer:

Code: Select all

``````x = 4, y = 2, rule = B3/S23
4o\$4o!``````
p2 oscillators:

Code: Select all

``````x = 11, y = 3, rule = B3/S23
b2o\$o8b2o\$o8bo!``````
This fuse produces Ts going backwards, at least until the asymmetry at the front of the ship interferes with the production:

Code: Select all

``````x = 78, y = 5, rule = B3/S23
bo\$2bo74bo\$obob74o\$2bo\$bo73bo!``````
p1 c spaceship:

Code: Select all

``````x = 9, y = 3, rule = B3/S23
obo3bobo\$2bo3bo\$2b2ob2o!``````

### Re: Euclidean CA (ECA)

Posted: November 30th, 2018, 7:39 am
Freywa wrote:Another observation that may help speed up implementations is that the Moore neighbourhood of a cell already contributes 5 out of the possible 6.027 heat that a cell may experience. Interval arithmetic may be useful to decide early whether a cell is born or survives – sum the heat of cells in the Moore neighbourhood to get H, then only proceed to add the heat of more live cells if the interval [H, H + 1.027) contains a boundary point between birth and non-birth or survival and non-survival.
That seems to me like a very good suggestion. I don't know when, but I'll certainly have a go at implementing some variation of that idea if nobody else does.

### Re: Euclidean CA (ECA)

Posted: November 30th, 2018, 9:44 am
I tried to match Conway's Life as closely as possible in ECA:

Code: Select all

``````local rulesB = {0.75, 0.95, 1.5, 1.7, 2.25, 2.45, 3, 3.2}
local rulesS = {0.5, 0.75, 0.75, 0.95, 1.25, 1.45, 1.5, 1.7, 2.25, 2.45, 3, 3.2}``````
The intervals are all possible heats corresponding to the birth and survival configurations of Life, with a 0.2 interval of error.

Instead, I get that the pre-block is a period-2 oscillator, tlife's T shows up (and the glider turns into a T) and this period-2 oscillator exists:

Code: Select all

``````x = 5, y = 4, rule = B3/S23
2bo\$bob2o\$o\$3o!``````
For these intervals

Code: Select all

``````local rulesB = {0.75, 0.95, 1.5, 1.7, 2.25, 2.5, 3, 3.3}
local rulesS = {0.5, 0.95, 1.25, 1.7, 2.25, 2.5, 3, 3.3}``````
there's a c/10 diagonal spaceship:

Code: Select all

``````x = 3, y = 3, rule = B3/S23
2o\$2o\$3o!``````
For these more simplified intervals

Code: Select all

``````local rulesB = {0.75, 0.95, 1.5, 1.7, 2.25, 2.5, 3, 3.3}
local rulesS = {0.5, 0.95, 1.25, 2.5, 3, 3.3}``````
there's a p16 oscillator and a c/3 orthogonal spaceship:

Code: Select all

``````x = 27, y = 5, rule = B3/S23
2bo21b2o\$bobo20bobo\$o3bo21bo\$bobo20bobo\$2bo21b2o!``````
and one glider cannot survive on its own, but two can together.

### Re: Euclidean CA (ECA)

Posted: November 30th, 2018, 10:17 am
wildmyron wrote:Edit: I forgot to mention that a large part of the performance degradation of the Fast Float Sum implementation for large populations was due to the usage of var args. I modified the function to accept an array instead, and this improved the situation, but there's no getting away from the O(N^2) characteristic inherent in the Euclidean CA definition.
For a k-by-k grid, you can get down to O(k^2 log(k)) operations using an FFT-based convolution -- which is better when the pattern is dense than the O(k^4) approach of calculating each cell individually.

Freywa's idea is great -- and I think might be even better for this case when you just want to detect whether the total lies in an interval rather than calculating it exactly.

Indeed, you can implement that by creating a Golly rule which decides whether a cell becomes on, off, or 'insufficient information', and then only process the 'insufficient information' cells.