Java: Как проверить, возможен ли сгенерированный уровень?

Question

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

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

Есть ли у кого-нибудь мысли о повторяющейся части, чтобы поддерживать ее быстро, или лучший способ достичь этого?

Вот изображение сгенерированной карты: # заблокированы комнаты. http://postimg.org/image/8oo88jxgb/

Answer 1

Вы можете использовать Dijkstra's algorithm или какой-либо другой pathfinding algorithm, чтобы проверить, есть ли путь от входа в комнату, чтобы каждый объект, а затем отбросить недопустимые номера. Это, вероятно, будет немного медленным, хотя, особенно если комнаты становятся больше или вы добавляете больше объектов.

Лучшим вариантом было бы гарантировать по конструкции, что каждая часть комнаты может быть достигнута. Этого можно достичь, используя Binary Space Partioning (BSP). Его можно использовать для создания случайных подземелий, гарантируя, что все комнаты подключены. Дополнительную информацию вы можете получить в this tutorial.

Существует много материала о процедурно созданных подземельях. Вы можете проверить еще один интересный tutorial here.

Answer 2

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

Donald Knuth (1974 Turing Award Lecture, Communications of the ACM 17 (12), (December 1974), pp. 667–673)

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

Answer 3

Сделайте массив A со строкой для каждой комнаты и столбом для каждой комнаты.

Поместите 1 в каждое положение i, j (строка, столбец), если две комнаты соединены.

Эта матрица (A) - это числовое представление графика, который является вашей игрой, узлы графика - это комнаты, а края - это двери.

Теперь возьмите вектор с длиной, соответствующей количеству комнат, которые у вас есть, и заполните ее нулями, за исключением одного в позиции, соответствующей комнате, в которой вы начинаете. Этот вектор (P) - это количество вы можете добраться до данной комнаты после 0 переходов.Чтобы проверить, можно ли попасть в данную комнату (n), переходы просто умножают P A^n и ищите ненулевое значение в позиции в векторе, который представляет данную комнату.

это обобщение математики хорошо описано здесь https://en.wikipedia.org/wiki/Markov_chain

Answer 4

Вы могли бы представить свой совет, как график проведения значения координат в качестве ключа и набор координат в качестве значений, представляющих каждый координаты neighbors..example Map<Coordinate, HashSet<Coordinate> = new Hashmap<Coordinate, HashSet<Coordinate>();. Затем заполнить график с каждым значением координаты в качестве ключа с соответствующими соседями в качестве их значений. Всякий раз, когда появляется заблокированная комната, просто удалите эту координату из каждого из соседних координат, окружающих ее.

Итак, если у вас есть координата (5,5) в качестве заблокированной комнаты, вы должны удалить (5,5) из соседнего набора (4,5) s, (5,4) s соседнего набора, (6,5) s соседний набор и (5,6) s соседний набор. Это в основном не позволит вам пройти этот путь больше.

Для заполнения граф можно использовать две петли:

for(int r = 0; r <= 10; r++){ 
     for(int c = 0; c <= 10; c++){ 
      HashSet<Coordinate> neighbors = new HashSet<Coordinate>(); 
       if(r > 0){ 
        neighbors.add(new Coordinate(r - 1, c)); 
       } 
       if(r < 8){ 
        neighbors.add(new Coordinate(r + 1, c)); 
       } 
       if(c > 0){ 
        neighbors.add(new Coordinate(r, c - 1)); 
       } 
       if(c < 8){ 
        neighbors.add(new Coordinate(r, c + 1)); 
       } 
      graph.put((new Coordinate(r,c)), neighbors); 
     } 
    } 

Я надеюсь, что это то, что вы просили.