Вычисление значений массива 2X2 в соответствии со строкой кривой Дракона параллельно - OpenCL

Question

Что такое кривая дракона? Дракон начинает с простой аксиомы: FX, Затем это раскрывается в более длинную строку с использованием следующих правил:

X -> X+YF+
Y-> -FX-Y

Это приводит к такому поведению / рисованию

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

FX
FX+YF+
FX+YF++-FX-YF+
FX+YF++-FX-YF++-FX+YF+--FX-YF+
FX+YF++-FX-YF++-FX+YF+--FX-YF++-FX+YF++-FX-YF+--FX+YF+--FX-YF+
^^^^^^ ^^^^^^^ ^^^^^^^ ^^^^^^^ ^^^^^^^ ^^^^^^^ ^^^^^^^ ^^^^^^^
  A*      B       A       B       A       B       A       B

A & B Шаблон легко вычисляется параллельно на OpenCL как одномерная задача. Но когда у вас есть расширенная строка, скажем, FX+YF++-FX-YF++-FX+YF+--FX-YF++-FX+YF++-FX-YF+--FX+YF+--FX-YF+ (4 дополнения) вы хотели бы создать реальный чертеж кривой дракона. Это делается путем заполнения массива 2X2 значениями координат X,Y с использованием следующих правил:

for c in expandedString:
  if c == "F":
        turtles.forward(10)
  elif c == "-":
        turtles.left(90)
  elif c == "+":
        turtles.right(90)

Определения функций вправо, влево и вперед:

def forward(n):
     global angle
     global x
     global y

     if n != 0:
        draw()

        if angle == 0:
            y -= 1

        elif angle == 90:
            x += 1        
        elif angle == 180:
            y += 1        
        elif angle == 270:
            x -= 1       
        else:
            print "angle:"
            print angle
            sys.exit("Invalid angle!")

        forward(n - 1)

def left(a):
    global angle
    angle = ((angle - a) + 360) % 360


def right(a):
    global angle
    angle = ((angle + a) + 360) % 360

canvas = numpy.zeros(shape=(50000, 50000)).astype('uint8')
def draw():   
        canvas[x, y] = 255

Примечание: эти правила в Python.

Canvas - это массив 2X2 и функция forward заполняет его значениями 255, используя функцию draw в соответствии с глобальным углом, который изменяется при чтении строки слева направо. Встречая - а также + приводит к повороту вправо или влево, вызывая left или же right функционировать соответственно и сталкиваясь F приводит к заполнению десяти слотов массива canvas 2X2 значениями 255. Любой другой незаполненный слот содержит значение 0.

Пока что я определил, что мы заполняем массив только когда встречаем F. Это происходит каждые четыре шага раскрытой строки -> FX+YF++-FX-YF++-FX+YF+--FX-YF++-FX+YF++-FX-YF+--FX+YF+--FX-YF+, Вычисление углов, при которых F встречается также имеет шаблон. Каждый нечетный F(который начинается с первого F как 0, встречается, когда глобальный угол равен 180 градусам или 0 градусам, а X остается постоянным, а Y повышается или понижается согласно правилам (см. выше). Каждый четный F встречается под любым углом 270 или 90, и X идет вверх или вниз, пока Y остается постоянным. Тем не менее, прогнозирование точного значения как 180/0 для even Fs или 90/270 для odd Fs пока не возможно Кроме того, предсказание, при каких значениях координат X и Y холста мы встретим F, является загадкой. Это, вероятно, связано с первой проблемой.

Я думаю, что где-то есть решение, и оно мне нужно:). Или какие-либо идеи энтузиастов OpenCL, как я мог бы подойти к этой проблеме неправильно вообще. Я точно знаю, что это двумерная проблема, но если ее можно распараллелить на OpenCL - загадка. Последовательная его обработка довольно проста, но мне нужен параллельный подход (не обязательно 100% парелл).