Алгоритм создания 2D паттернов PHP

Question

Я ищу алгоритм, который поможет мне строить 2D-модели на основе правил.Идея состоит в том, что я мог бы написать сценарий, используя заданный сайт параметров, и он возвращал бы случайную двумерную последовательность вплоть до заданной длины.

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

Например, предположим, что вы можете использовать A, B, C и D для создания шаблона.Правило состоит в том, что C и A никогда не могут быть рядом друг с другом, и что D всегда следует за C. Далее, скажем, я хочу шаблон размером 4x4.Результатом может быть следующее, в котором соблюдаются все правила.

A B C D
B B B B
C D B B
C D C D

Существуют ли какие-либо библиотеки, которые могут выполнять такие вычисления?Есть ли математические формулы, по которым я могу прочитать?

Answer 1

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

Он следует простому шаблону, и если он написан правильно, вы можете легко заменить набор правилв это.

Answer 2

Предположим, что ваши правила ограничены "тип X может иметь тип Y непосредственно слева / справа / сверху / снизу" у вас потенциально могут быть ситуации, когда генерация возможных шаблонов является вычислительно сложной.Взгляните на Wang Tiles (хорошим источником является книга Tilings and Patterns Грюнбаума и Шепарда), и вы увидите, что с помощью наборов правил состояний вы можете определять наборыВан Тайлз.Соответствующие наборы из них - Turing Complete.

Для небольших прямоугольников или ваших наборов правил это может представлять только академический интерес.Как уже упоминалось в другом месте, подход обратного отслеживания может быть подходящим для вашего набора правил - в этом случае вы можете рассмотреть возможность использования подходящих эвристик для порядка, в котором новые компоненты добавляются в вашу сетку.Опять же, в зависимости от ваших наборов правил, другие подходы могут работать.Например, если ваш набор правил допускает много решений, вы можете пройти долгий путь, случайным образом распределив множество элементов по сетке, прежде чем пытаться заполнить оставшиеся пробелы.

Answer 3

Определите ваши правила структуры данных;то есть, определите набор операций, которые правила могут инкапсулировать, и определите доступные перекрестные ссылки, которые могут быть выполнены.Как только вы это сделаете, у вас должно быть более четкое представление о том, какой тип алгоритмов использовать для применения этих правил к потенциальному набору результатов.