Регулярные выражения - это компактный способ выразить синтаксис ограниченного (и все еще бесконечного) набора языков. С помощью регулярных выражений вам не нужно указывать, где искать следующий символ, поскольку известно, что вы работаете со строкой и перебираете ее символы, принимая их за символы языка ... но в 3D вы будете нужно сказать, в какую сторону идти.
Вы можете думать об этом как о машине 3D Тьюринга, то есть о машине Тьюринга, которая имеет внутреннее состояние и может считывать символы с трехмерной «ленты», так как мы проверяем только, давайте проигнорируем запись на ленту. Затем эта машина Тьюринга пройдет трехмерную «ленту» или трехмерную сетку вокселей и прочитает воксели как символы, после считывания каждого символа внутреннее состояние машины Тьюринга изменится в соответствии с определенными законами. Как только выполнение закончится, окончательное состояние машины скажет вам, было ли это совпадение или нет. Теперь эти законы в архитектуре фон Ньюмана представляют собой интерпретацию данных с ленты как инструкции, но мы хотим использовать гарвардскую архитектуру, то есть инструкции отделены от данных. Теперь вы хотите описать эти инструкции для машины Тьюринга. [Вы можете думать об этом как о черепахе с логотипом, но в 3D].
Следуя духу регулярных выражений, мы бы предпочли язык, который напоминает реальную структуру. Если мы сделаем его основанным на тексте, это будет описательный язык (поскольку императивный не лучше, чем ваш любимый полный по Тьюрингу), он должен будет сказать, например (на английском языке):
There is a voxel type A and then moving (x1, y1, z1) from that there is a voxel of type B or C and then moving (x2, y2, z3) from that there is a voxel type D
Это описание того, что ищет машина Тьюринга, с алгоритмом обратного отслеживания, который проверяет все потенциальные совпадения, и будет работать так, как ожидалось.
Обратите внимание, что я не знаю множество возможных значений вокселей. То есть я не знаю алфавита. Итак, я только что сказал тип A, тип B, тип C и тип D в качестве примеров, один из которых может быть представлением без вокселя, а другие могут быть цветами или чем-то, что вы используете. Вокселей может быть столько, сколько нужно. Если тип вокселя сложный, его описание должно быть вставлено туда.
Я думал о практическом использовании такого рода языка, и одна проблема, которая возникает очень быстро, это ротации, я должен решить, что три вокселя типа A по оси X считаются одинаковыми, как три вокселя типа A над Z ось, тем лучше дать возможность описать это на языке.
Теперь очень похоже на описание пути, если воксели - это узлы, я создал язык для описания 2D-путей как часть частного проекта (чтобы сохранить их в базе данных, перейдите к рисунку ...), это очень просто, он резервирует символ для каждого направления и использует число для шагов, например: «2d5l1u». Сделайте то же самое для 3D и добавьте способ группировки и сопоставления. Чтобы решить проблему вращения, необходимо расширить направление, чтобы позволить дизъюнкциям выразить альтернативные конфигурации для совпадения. Это станет более понятным на примере того, как это может работать, о котором я думал (я не работал с формальным синтаксисом в EBNF или аналогичном):
Соответствие линии трех вокселей типа A по оси X:
(A1X){3}
Здесь я вставляю сопоставление «A» с движением «1X», использую скобки «(» и «)» для группировки и фигурные скобки «{» и «}» для количественного определения. Это раскатывает к этому:
A1XA1XA1X
Последний «1X» не влияет на результат, поэтому он также может быть:
A1XA1XA
И здесь четко сказано: сопоставьте воксел типа A, переместите 1 над X и сопоставьте с вокселем типа A, переместите 1 над X и сопоставьте воксель типа A.
Соответствует линии из трех вокселей типа A по оси X или по оси Z:
(A1X){3}|(A1Z){3}
Альтернатива:
(A1[X|Z]){3}
Здесь я использую скобки «[» и «]» для создания «класса», расположение которого говорит о направлении и включает только возможную ось, не путайте с:
[(A1X)|(A1Z)]{3}
Это будет соответствовать трем вокселям типа A, но они могут быть не на одной оси, они должны быть только смежными и иметь общую ось X или Z с соседом.
Соответствует набору 3x3Вокселы набирают a над плоскостью X, Y:
(((A1X){3})1Y){3}
Это соответствует линии по оси X и перемещается на 1 по оси Y, чтобы соответствовать другой, и так далее.Это подразумевает, что после группировки повторения «([(A1X)] {16})» мы возвращаемся туда, откуда началось выполнение следующего хода «1Y».Чтобы развернуть это было бы:
(A1XA1XA1X)1Y(A1XA1XA1X)1Y(A1XA1XA1X)1Y
Посмотрите оставшиеся круглые скобки, это означает, что нужно вернуться туда, где началось совпадение.Таким образом, программа проверит, что находится внутри группы, и когда это будет сделано, она вернется туда, где она была до входа в группу, и продолжит выполнение после нее.
Соответствует паре вокселей типа A, разделенных вокселем.игнорируемого типа (по любой оси):
A1(X|Y|Z).1(X|Y|Z)A1(X|Y|Z)
Под влиянием регулярных выражений мы используем точку "."для представления любого типа вокселя.
Я до сих пор не решаю, лучше ли использовать отрицательные значения, чем использовать другие буквы для другой оси, также я считаю, что число 1 может быть необязательным.Также другие части синтаксиса регулярных выражений, такие как «+», «*» и «?»должен быть хоть и осторожнее.Может быть хорошо применять «{» и «}» для любого количественного определения до тех пор, пока не будет доказано, что двусмысленности нет.
Как вы, возможно, заметили, не будет проблемой добавить другое направление движения или совсем другоеось, так что этот порт очень хорошо сказать, четыре измерения, как в:
(A1[X|Y|Z|W]){3}
Также может быть хорошо использовать точку "."для представления любого направления:
(A1.){3}
Существует проблема с принятием любого направления, когда оно не указано, и заключается в том, что этот язык определен для определения того, что является направлением, и отличает их от типов вокселей на основе расположения внутривыражения.Таким образом, "(A1B1) {3}" не будет отображаться на "(A1.B1.) {3}", поскольку в качестве направления движения будет использоваться буква "B", возможно, можно определить значение по конечному числу вконец, но я не знаю, будет ли это однозначно.
Наконец, это будет соответствовать любому действительному фрагменту тетриса в плоскости X, Y, изготовленному из вокселей типа A:
(A1[X|Y]){4}
Если мы предположим, что мир только двумерен и что мы позволяем игнорировать номер один, он сводится к следующему:
(A.){4}
И я доволен этим.Тем не менее, вам следует рассмотреть более сложную, менее компактную и более читаемую нотацию для сложных структур.
И это моя теория обобщения регулярных выражений на два, три или более измерений.
РЕДАКТИРОВАТЬ:
Если тип вокселя сложный или вызывает неоднозначность, я предлагаю написать его с угловыми скобками «<» и «>», так что, например, вы можете использовать шестнадцатеричное значение необработанногоданные вокселя:
(<0088FF>.){4}