Джулия / Сотовые автоматы: эффективный способ получить окрестности - PullRequest
Новая
       36

Джулия / Сотовые автоматы: эффективный способ получить окрестности

3 голосов
/ 26 сентября 2019

Я бы хотел внедрить сотовый автомат (СА) в Джулию.Размеры должны быть перенесены, это означает: левый сосед самой левой ячейки является самой правой ячейкой и т. Д.

Один важный вопрос: как заставить соседей одной ячейки вычислять ее состояние в следующем поколении?Поскольку измерения должны быть обернуты, а Джулия не допускает отрицательных индексов (как в Python), у меня была такая идея:

Рассматривается 1D CA, одно поколение - это одномерный массив:

0 0 1 0 0

Что если мы создадим двумерный массив, в котором первая строка смещена вправо, а третья смещена влево, например: 

0 0 0 1 0
0 0 1 0 0
0 1 0 0 0

Теперь в первом столбце содержатся состоянияпервой ячейки и ее соседей и т. д.

я думаю, что это легко можно обобщить для двух и более измерений.

Первый вопрос : считаете ли вы, что это хорошоидея, или это неправильный трек?

РЕДАКТИРОВАТЬ: Ответ на первый вопрос был нет, второй вопрос и пример кода отброшены.

Второй вопрос : Еслиподход в целом нормальный, пожалуйста, взгляните на следующий эскиз:

РЕДАКТИРОВАТЬ: Другой подход, здесь урезанная версия 1D CA, используя mod1 () для получения индексов окрестности,как предложил Богумил Каминский.

для любой ячейки: - массив всех индексов - массив B всех состояний окрестности - состояния C, преобразованные в одно целое число - поиск D следующего состояния 

function digits2int(digits, base=10)
   int = 0
   for digit in digits
      int = int * base + digit
   end
   return int
end

gen = [0,0,0,0,0,1,0,0,0,0,0]
rule = [0,1,1,1,1,0,0,0]

function nextgen(gen, rule)
  values = [mod1.(x .+ [-1,0,1], size(gen)) for x in 1:length(gen)] # A
  values = [gen[value] for value in values]                         # B
  values = [digits2int(value, 2) for value in values]               # C
  values = [rule[value+1] for value in values]                      # D
  return values
end

for _ in 1:100
  global gen
  println(gen)
  gen = nextgen(gen, rule)
end

Следующим шагом должно быть его расширениев двух измерениях, попробую сейчас ...

Ответы [ 2 ]

2 голосов
/ 26 сентября 2019

Обычно я использую функцию mod1 для индексирования с переносом.

В этом подходе, независимо от того, какой будет размерность вашего массива a, тогда, когда вы хотите перейти из позиции x delta dx достаточно написать mod1(x+dx, size(a, 1)), если x является первым измерением массива.

Вот простой пример случайного обхода двумерного тора, подсчитывающего числоколичество посещений данной ячейки (здесь я дополнительно использую широковещательную передачу для обработки всех измерений в одном выражении): 

function randomwalk()
    a = zeros(Int, 8, 8)
    pos = (1,1)
    for _ in 1:10^6
        # Von Neumann neighborhood
        dpos = rand(((1,0), (-1,0), (0,1), (0,-1)))
        pos = mod1.(pos .+ dpos, size(a))
        a[pos...] += 1
    end
    a
end
2 голосов
/ 26 сентября 2019

Обычно, если у СА есть ячейки, которые зависят только от соседних ячеек, проще просто «обернуть» вектор, добавив последний элемент спереди и первый элемент сзади, выполнив симуляцию,и затем "разверните", снова убрав первый и последний элементы, чтобы получить длину результата, равную длине начального массива.Для одномерного случая: 

const lines = 10
const start = ".........#........."
const rules = [90, 30, 14]

rule2poss(rule) = [rule & (1 << (i - 1)) != 0 for i in 1:8]

cells2bools(cells) = [cells[i] == '#' for i in 1:length(cells)]

bools2cells(bset) = prod([bset[i] ? "#" : "." for i in 1:length(bset)])

function transform(bset, ruleposs)
    newbset = map(x->ruleposs[x],
        [bset[i + 1] * 4 + bset[i] * 2 + bset[i - 1] + 1
        for i in 2:length(bset)-1])
    vcat(newbset[end], newbset, newbset[1])
end

const startset = cells2bools(start)

for rul in rules
    println("\nUsing Rule $rul:")
    bset = vcat(startset[end], startset, startset[1]) # wrap ends
    rp = rule2poss(rul)
    for _ in 1:lines
        println(bools2cells(bset[2:end-1]))  # unwrap ends
        bset = transform(bset, rp)
    end
end

Если для моделирования любой ячейки используются только смежные ячейки, это правильно.

Если вы расширите это до 2Dматрица, вы также «оберните» первую и последнюю строки, а также первый и последний столбцы и так далее.

...