Home  •  LifeWiki  •  Forums  •  Download Golly

## Euclidean CA (ECA)

For discussion of other cellular automata.

### Euclidean CA (ECA)

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.

`--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   return totalendfunction 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 nringendfunction 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     g.exit("All cells are dead.")     return   end   local rulesBclone = rulesB   table.sort(rulesBclone)   local minrulesB = rulesBclone --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)endwhile 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:
`6.0268120396919401235462601927282855839417908072537241239789823989168652037814250418764946630938418433906127747493598517914519884043536868495100966503449541972750061912676710610851774101700255398481455670182612361266898875483352921070069449008114281527829434299322822560251114200149117706817994764236876636117413174159952976496849741988010861076557834927010493267788390209735731100040920526016251643211225971568622986661712279082923986446238998997768676990659832983376483731474723643953842741351597605714161337207790707042631552431695921352276400390580604568489239229700788071861541187775637812405539300590870406433494222017883382946074250172136911832633689703956037954481037629038480262769680362849773653130682557719791223453092147760706480221366950515486440933396727770173048557378012773452636411632552957204199179226582314343628445920394854336019550159007480469325289524410543403938235788421982263661511011524075413030449483389003139678799601958658704861812673964630612466034108439517982559502176303...`

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:
`#C rule = ECA:B(1.15,1.5625)/S(1.6,3)x = 2, y = 3, rule = B/S012345678bo\$2o\$bo!`

`#C rule = ECA:B(1.15,1.5625)/S(1.6,3)x = 9, y = 3, rule = B/S012345678bo\$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:
`#C rule = ECA:B(.01,7)/Sx = 57, y = 57, rule = B/S01234567823b11o\$19b19o\$17b23o\$15b27o\$13b31o\$12b33o\$10b37o\$9b15o9b15o\$8b13o15b13o\$7b12o19b12o\$6b11o23b11o\$6b10o25b10o\$5b9o29b9o\$4b9o31b9o\$4b8o12b9o12b8o\$3b9o10b13o10b9o\$3b8o9b17o9b8o\$2b8o9b19o9b8o\$2b8o8b21o8b8o\$b8o8b23o8b8o\$b8o7b10o5b10o7b8o\$b7o8b8o9b8o8b7o\$b7o7b8o11b8o7b7o\$8o7b7o13b7o7b8o\$7o7b7o15b7o7b7o\$7o7b7o6b3o6b7o7b7o\$7o7b6o6b5o6b6o7b7o\$7o7b6o5b7o5b6o7b7o\$7o7b6o5b3ob3o5b6o7b7o\$7o7b6o5b7o5b6o7b7o\$7o7b6o6b5o6b6o7b7o\$7o7b7o6b3o6b7o7b7o\$7o7b7o15b7o7b7o\$8o7b7o13b7o7b8o\$b7o7b8o11b8o7b7o\$b7o8b8o9b8o8b7o\$b8o7b10o5b10o7b8o\$b8o8b23o8b8o\$2b8o8b21o8b8o\$2b8o9b19o9b8o\$3b8o9b17o9b8o\$3b9o10b13o10b9o\$4b8o12b9o12b8o\$4b9o31b9o\$5b9o29b9o\$6b10o25b10o\$6b11o23b11o\$7b12o19b12o\$8b13o15b13o\$9b15o9b15o\$10b37o\$12b33o\$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:
`#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/S012345678bo\$2o\$bo8\$o\$2o\$bo!`

I guess I'll post more rules later once I've done more research.
Last edited by danny on November 30th, 2018, 3:25 am, edited 1 time in total.
she/they // Please stop using my full name. Refer to me as dani.

"I'm always on duty, even when I'm off duty." -Cody Kolodziejzyk, Ph.D. danny

Posts: 960
Joined: October 27th, 2017, 3:43 pm
Location: New Jersey, USA

### Re: Euclidean CA (ECA)

I noticed my script has a glitch when running the rule

`local rulesB = {.085, .105, .135, .143, 2, 2.15}local rulesS = {1, 1.02, 2, 2.5}`

A domino becomes asymmetric in 3 generations.
she/they // Please stop using my full name. Refer to me as dani.

"I'm always on duty, even when I'm off duty." -Cody Kolodziejzyk, Ph.D. danny

Posts: 960
Joined: October 27th, 2017, 3:43 pm
Location: New Jersey, USA

### Re: Euclidean CA (ECA)

danny wrote:I noticed my script has a glitch when running the rule

`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.
What do you do with ill crystallographers? Take them to the mono-clinic! calcyman

Posts: 2072
Joined: June 1st, 2009, 4:32 pm

### Re: Euclidean CA (ECA)

calcyman wrote:Probably because floating-point addition is non-associative.

Aarrgghh. How do I fix this?
she/they // Please stop using my full name. Refer to me as dani.

"I'm always on duty, even when I'm off duty." -Cody Kolodziejzyk, Ph.D. danny

Posts: 960
Joined: October 27th, 2017, 3:43 pm
Location: New Jersey, USA

### Re: Euclidean CA (ECA)

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.
What do you do with ill crystallographers? Take them to the mono-clinic! calcyman

Posts: 2072
Joined: June 1st, 2009, 4:32 pm

### Re: Euclidean CA (ECA)

The script does not work.
I like making rules
fluffykitty

Posts: 604
Joined: June 14th, 2014, 5:03 pm

### Re: Euclidean CA (ECA)

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.
The latest version of the 5S Project contains over 196,000 spaceships. Tabulated pages up to period 160 are available on the LifeWiki.
wildmyron

Posts: 1209
Joined: August 9th, 2013, 12:45 am

### Re: Euclidean CA (ECA)

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.
`-- 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 Paaplocal 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 ChanSee http://lua-users.org/wiki/FloatSumFast--]]local function fsum(v)    local p, abs = {1}, math.abs    -- p == #p    local function fadd(x)        local p, i = p, 2        for j = 2, p 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 = 2 return end  -- Inf or NaN        p = i        p[i] = x    end    local function ftotal(clear)        if clear then p = 1 end  -- clear all partials        repeat            local n, overlap = p, false            local prev = {table.unpack(p, 1, n)}            fadd(0)                 -- remove partials overlap            if n <= 3 then return p 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 cendlocal 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 cellslocal neighbourcounts = {8, 20, 36, 68, 96, 136, 176, 224, 292, 348}local function expand(radius)    local nc = neighbourcounts[radius]    local currpat = g.getcells(g.getrect())    g.setrule(string.format("R%u,C0,M1,S0..0,B1..%u,NC", radius, nc))    g.run(1)    local nring = g.getcells(g.getrect())    g.putcells(currpat)    return nringend-- Evolve the current pattern one step in the given ECA rulelocal function step()    if g.getpop() == "0" then        g.exit("All cells are dead.")        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)endg.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    endendg.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.
The latest version of the 5S Project contains over 196,000 spaceships. Tabulated pages up to period 160 are available on the LifeWiki.
wildmyron

Posts: 1209
Joined: August 9th, 2013, 12:45 am

### Re: Euclidean CA (ECA)

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
Last edited by Caenbe on November 30th, 2018, 6:26 pm, edited 1 time in total.
0.1485̅
Caenbe

Posts: 51
Joined: September 20th, 2016, 4:24 pm
Location: Nowhere Land, USA

### Re: Euclidean CA (ECA)

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).
Princess of Science, Parcly Taxel Freywa

Posts: 566
Joined: June 23rd, 2011, 3:20 am
Location: Singapore

### Re: Euclidean CA (ECA)

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.
she/they // Please stop using my full name. Refer to me as dani.

"I'm always on duty, even when I'm off duty." -Cody Kolodziejzyk, Ph.D. danny

Posts: 960
Joined: October 27th, 2017, 3:43 pm
Location: New Jersey, USA

### Re: Euclidean CA (ECA)

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):
`x = 115, y = 89, rule = 345/2/457.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:
`x = 115, y = 89, rule = 345/2/457.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\$57AB57A\$57AB57A\$57AB57A\$115A\$49AB2AB3AB4AB2AB50A\$49ABABABAB4A2B3AB49A\$50A3B2AB3ABAB3AB49A\$50AB4AB2AB2AB3AB49A\$51A2B2AB2A5B2AB49A\$52AB2AB5AB3AB49A\$51AB4AB4AB2AB50A\$115A\$57AB57A\$57AB57A\$57AB57A\$57AB57A\$57AB57A\$57AB57A\$57AB57A\$57AB57A\$57AB57A\$57AB57A\$57AB57A\$57AB57A\$57AB57A\$57AB57A\$57AB57A\$57AB57A\$57AB57A\$57AB57A\$57AB57A\$57AB57A\$57AB57A\$57AB57A\$57AB57A\$57AB57A\$57AB57A\$57AB57A\$57AB57A\$57AB57A\$57AB57A\$57AB57A\$57AB57A\$57AB57A\$57AB57A\$57AB57A\$57AB57A\$57AB57A\$57AB57A\$57AB57A\$57AB57A\$57AB57A\$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:
`x = 17, y = 8, rule = B3/S232b2o11b2o\$2bo12bo\$obo10bobo\$2bo12bo\$3bo12bo\$b2o11b2o2\$14bo!`

which can be made double-ended:
`x = 30, y = 5, rule = B3/S232bo\$29bo\$30o\$o\$25bobo!`

2×N rectangles (N > 2) also just stretch longer and longer:
`x = 4, y = 2, rule = B3/S234o\$4o!`

p2 oscillators:
`x = 11, y = 3, rule = B3/S23b2o\$o8b2o\$o8bo!`

This fuse produces Ts going backwards, at least until the asymmetry at the front of the ship interferes with the production:
`x = 78, y = 5, rule = B3/S23bo\$2bo74bo\$obob74o\$2bo\$bo73bo!`

p1 c spaceship:
`x = 9, y = 3, rule = B3/S23obo3bobo\$2bo3bo\$2b2ob2o!`
Princess of Science, Parcly Taxel Freywa

Posts: 566
Joined: June 23rd, 2011, 3:20 am
Location: Singapore

### Re: Euclidean CA (ECA)

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.
The latest version of the 5S Project contains over 196,000 spaceships. Tabulated pages up to period 160 are available on the LifeWiki.
wildmyron

Posts: 1209
Joined: August 9th, 2013, 12:45 am

### Re: Euclidean CA (ECA)

I tried to match Conway's Life as closely as possible in ECA:
`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:
`x = 5, y = 4, rule = B3/S232bo\$bob2o\$o\$3o!`

For these intervals
`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:
`x = 3, y = 3, rule = B3/S232o\$2o\$3o!`

For these more simplified intervals
`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:
`x = 27, y = 5, rule = B3/S232bo21b2o\$bobo20bobo\$o3bo21bo\$bobo20bobo\$2bo21b2o!`

and one glider cannot survive on its own, but two can together.
Princess of Science, Parcly Taxel Freywa

Posts: 566
Joined: June 23rd, 2011, 3:20 am
Location: Singapore

### Re: Euclidean CA (ECA)

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.
What do you do with ill crystallographers? Take them to the mono-clinic! calcyman

Posts: 2072
Joined: June 1st, 2009, 4:32 pm

Return to Other Cellular Automata

### Who is online

Users browsing this forum: testitemqlstudop and 4 guests