Euclidean CA (ECA)

For discussion of other cellular automata.
Post Reply
dani
Posts: 1222
Joined: October 27th, 2017, 3:43 pm

Euclidean CA (ECA)

Post by dani » 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

   return total
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
     g.exit("All cells are dead.")
     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.
Last edited by dani on November 30th, 2018, 3:25 am, edited 1 time in total.

dani
Posts: 1222
Joined: October 27th, 2017, 3:43 pm

Re: Euclidean CA (ECA)

Post by dani » 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.

User avatar
calcyman
Moderator
Posts: 2932
Joined: June 1st, 2009, 4:32 pm

Re: Euclidean CA (ECA)

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

dani
Posts: 1222
Joined: October 27th, 2017, 3:43 pm

Re: Euclidean CA (ECA)

Post by dani » November 20th, 2018, 7:57 pm

calcyman wrote:Probably because floating-point addition is non-associative.
Aarrgghh. How do I fix this?

User avatar
calcyman
Moderator
Posts: 2932
Joined: June 1st, 2009, 4:32 pm

Re: Euclidean CA (ECA)

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

fluffykitty
Posts: 1175
Joined: June 14th, 2014, 5:03 pm
Contact:

Re: Euclidean CA (ECA)

Post by fluffykitty » November 22nd, 2018, 4:32 pm

The script does not work.

wildmyron
Posts: 1542
Joined: August 9th, 2013, 12:45 am
Location: Western Australia

Re: Euclidean CA (ECA)

Post by wildmyron » 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.
The 5S project (Smallest Spaceships Supporting Specific Speeds) is now maintained by AforAmpere. The latest collection is hosted on GitHub and contains well over 1,000,000 spaceships.

Semi-active here - recovering from a severe case of LWTDS.

wildmyron
Posts: 1542
Joined: August 9th, 2013, 12:45 am
Location: Western Australia

Re: Euclidean CA (ECA)

Post by wildmyron » 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 function fadd(x)
        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)}
            fadd(0)                 -- remove partials overlap
            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 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 nring
end

-- Evolve the current pattern one step in the given ECA rule
local 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)
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.
The 5S project (Smallest Spaceships Supporting Specific Speeds) is now maintained by AforAmpere. The latest collection is hosted on GitHub and contains well over 1,000,000 spaceships.

Semi-active here - recovering from a severe case of LWTDS.

Caenbe
Posts: 52
Joined: September 20th, 2016, 4:24 pm
Location: USA

Re: Euclidean CA (ECA)

Post by Caenbe » 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
Last edited by Caenbe on November 30th, 2018, 6:26 pm, edited 1 time in total.
Music make you lose control
Music make you lose control
echo "print(10**10**5//~-10**1000//9801)" | python | aplay

User avatar
Freywa
Posts: 877
Joined: June 23rd, 2011, 3:20 am
Location: Singapore
Contact:

Re: Euclidean CA (ECA)

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

Code: Select all

x = 31, y = 5, rule = B2-a/S12
3bo23bo$2obo4bo13bo4bob2o$3bo4bo13bo4bo$2bo4bobo11bobo4bo$2bo25bo!

dani
Posts: 1222
Joined: October 27th, 2017, 3:43 pm

Re: Euclidean CA (ECA)

Post by dani » 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.

User avatar
Freywa
Posts: 877
Joined: June 23rd, 2011, 3:20 am
Location: Singapore
Contact:

Re: Euclidean CA (ECA)

Post by Freywa » 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!
which can be made double-ended:

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!
Princess of Science, Parcly Taxel

Code: Select all

x = 31, y = 5, rule = B2-a/S12
3bo23bo$2obo4bo13bo4bob2o$3bo4bo13bo4bo$2bo4bobo11bobo4bo$2bo25bo!

wildmyron
Posts: 1542
Joined: August 9th, 2013, 12:45 am
Location: Western Australia

Re: Euclidean CA (ECA)

Post by wildmyron » 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.
The 5S project (Smallest Spaceships Supporting Specific Speeds) is now maintained by AforAmpere. The latest collection is hosted on GitHub and contains well over 1,000,000 spaceships.

Semi-active here - recovering from a severe case of LWTDS.

User avatar
Freywa
Posts: 877
Joined: June 23rd, 2011, 3:20 am
Location: Singapore
Contact:

Re: Euclidean CA (ECA)

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

Code: Select all

x = 31, y = 5, rule = B2-a/S12
3bo23bo$2obo4bo13bo4bob2o$3bo4bo13bo4bo$2bo4bobo11bobo4bo$2bo25bo!

User avatar
calcyman
Moderator
Posts: 2932
Joined: June 1st, 2009, 4:32 pm

Re: Euclidean CA (ECA)

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

Post Reply