Как создать график из лабиринта - PullRequest
Новая
       29

Как создать график из лабиринта

0 голосов
/ 24 апреля 2019

Я хотел реализовать некоторые графы и связующее дерево, которые я выучил в классе на этой неделе, поэтому я создал алгоритм генерации лабиринта на основе алгоритма Прима.Сейчас я пытаюсь создать алгоритм для эффективного решения лабиринтов.До сих пор я сделал заливку, которая в конечном итоге решает лабиринт, но очень неэффективна.Сейчас я пытаюсь найти способ преобразовать лабиринт в граф, чтобы использовать алгоритм Дейкстры или DFS, но я в тупике.Лабиринт хранится в двоичном массиве, где 1 - стена, а 0 - открытое пространство.Лабиринт всегда начинается с единственного 0 в первой строке и заканчивается единственным нулем в последней строке.Лабиринт хранится, как показано ниже. 

static int maze2[][] = {{1, 1, 1, 1, 1, 0, 1, 1, 1, 1},
                        {1, 1, 1, 0, 0, 0, 0, 0, 0, 1},
                        {1, 0, 0, 0, 1, 0, 1, 0, 0, 1},
                        {1, 0, 0, 1, 1, 0, 1, 1, 0, 1},
                        {1, 1, 0, 0, 1, 0, 1, 1, 0, 1},
                        {1, 0, 0, 1, 1, 0, 1, 0, 0, 1},
                        {1, 1, 0, 0, 1, 0, 1, 0, 1, 1},
                        {1, 0, 0, 1, 1, 0, 1, 0, 0, 1},
                        {1, 1, 0, 0, 1, 0, 1, 0, 1, 1},
                        {1, 1, 1, 1, 1, 0, 1, 1, 1, 1}};

1 Ответ

0 голосов
/ 25 апреля 2019

Вы не конвертируете лабиринт в график.Вы просто думаете об этом как о графике.

Когда вы пишете свой алгоритм (BFS, DFS и т. Д.), Вам нужно только:

  • Способчтобы идентифицировать узел - пары (строка, столбец) работают нормально, или вы можете использовать одну целую строку * WIDTH + столбец.
  • Способ найти соседние узлы - просто проверьте соседние ячейки в матрице.
...