Справка по алгоритму: Создание игрового поля, но нужно знать, когда квадрат заблокирован

Question

Я построил игровую доску, состоящую из сетки, которая затем случайным образом назначается сетке "Стены" в ячейку. Как только ячейки построены, как я могу проверить, заблокирована ли определенная ячейка, чтобы я не поместил туда игрока?

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

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

Как это обычно обрабатывается? Я использую python, если это имеет значение для любых примеров кода.

Спасибо!

Answer 1

Вы в основном хотите алгоритм заливки.
http://en.wikipedia.org/wiki/Floodfill

edit
Я думаю, что я неправильно понял ваши определения 'locked' и 'escape'.Если у вас ограничено игровое поле, каждая клетка там заперта в каком-то пространстве.Если я вас правильно понимаю, вы просто хотите, чтобы это пространство было достаточно большим.Ну, вы легко вычисляете его площадь с помощью алгоритма заливки.

Answer 2

Я не совсем уверен, как может выглядеть ваша игровая доска, но если у вас есть что-то вроде этого:

+----------------------+
|      +-----+         |
|      | c   |         |
|      |     |         |
|      +-----+         |
|                      |
|                      |
|                      |
+----------------------+

И вы хотите избежать размещения символа на c, потому что он «окружен стеной», хотя он не совсем окружен стенами, вы можете легко реализовать алгоритм Левая или правая рука - только вместо того, чтобы пытаться выбраться из лабиринта, вы проверяете, возвращаетесь ли вы к той же координате.

Answer 3

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

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

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

Answer 4

Может быть этот предыдущий пост - это то, что вы ищете.В этом посте я ответил, как подсчитать количество различных областей точек на сетке, на которой можно разместить точки.Ваша проблема похожа, за исключением того, что вместо «точек» у вас есть стены.Алгоритм, приведенный в этом посте, даст вам версию вашей сетки G, где

G[x1][y1] == G[x2][y2]

только в том случае, если игрок может перейти из (x1, y1) в (x2, y2), т.е.Если есть четкий путь без стен от этой первой точки ко второй точке.

Это то, что вы ищете?Вам нужны дополнительные сведения или вы хотите, чтобы я адаптировал этот код к вашей конкретной проблеме?