метод для специализированного поиска пути?

Question

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

       B       
       X       
       X       
       X       
      XX       
     XX        
    XX         
  AXX          

Я действительно хочу что-то похожее на это:

       B       
       X       
       XXXX    
          X    
          X    
          X    
          X    
  AXXXXXXXX    

Эти пути должны удовлетворять нескольким свойствам:

1. Я должен быть в состоянии указать область, внутри которой они ограничены,
2. Я должен иметь возможность параметризовать, насколько они ветрены и длинны,
3. Строки не должны выглядеть так, как будто они начинались на одном пути и заканчивались на другом. Например, первый приведенный выше пример выглядит так, как если бы он начинался с А и заканчивался на В, потому что он в основном неоднократно менял направления, пока не выровнялся с В, а затем просто пошел прямо туда.

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

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

Answer 1

Прежде чем вы сможете понять, как создавать пути, вы должны найти более точный способ указать, что вы хотите. Один из способов сделать это - назначить каждому пути оценку, а затем искать пути с высокими показателями. Вот несколько вопросов для рассмотрения:

1. Вы предпочитаете длинные прямые трассы коротким? Как вы будете количественно определять это предпочтение? (Чтобы алгоритм поиска сходился, будет проще, если ваша функция подсчета будет нелинейной.)

2. Если вы не хотите идти прямо к месту назначения, вы можете вознаграждать шаги, которые находятся за пределами основной линии. Например, на пути от A до B рассмотрите каждую точку, затем сделайте три шага и вычислите направление между точками. Теперь возьмите косинус разности этого направления и направления от А до Б. Отрицайте его. Шаги на линии подсчитывают -1 против вас, шаги перпендикулярно нейтральны, а шаги вдали от линии считают +1 для вас.

Вот несколько хороших следующих шагов:

• Подумайте о еще нескольких идеях подсчета очков.
• Нарисуйте десяток дорожек от руки и ранжируйте их по тому, насколько они вам нравятся.
• Для каждого пути создайте пару небольших вариаций вручную.
• Запустите функцию подсчета очков на всех путях. Продолжайте играть, пока не получите функцию оценки, которая нравится то, что вам нравится.

Тогда вы будете готовы подумать об алгоритмах поиска.

Answer 2

Я бы сказал, что поиск пути - это неправильный термин: обычно он включает в себя поиск правильного маршрута от А до В, и ваша проблема не в том, чтобы найти этот маршрут, а в создании маршрутов, соответствующих вашим целям. Вы сознательно создаете неоптимальные пути, и их качество будет трудно определить количественно. Поэтому я не думаю, что алгоритм поиска с какой-либо эвристикой был бы лучшим решением проблемы. Если у вас есть один обязательный критерий (рабочий путь) и несколько нечетких, неопределенных критериев (естественный и извилистый), лучше всего начать с удовлетворения обязательных требований и попытаться изменить его в соответствии с другими требованиями. Таким образом, у вас всегда есть что-то, что работает.

Я предлагаю, учитывая, что вы, кажется, предпочитаете горизонтальные и вертикальные траектории, поворачивающиеся под прямым углом, начинать с прямой двухсегментной траектории от А до Б. так же легко это сделать самостоятельно). Затем возьмите случайную точку вдоль одного из двух сегментов и одну из двух конечных точек для этого сегмента и переместите этот участок линии параллельно себе на некоторое случайное расстояние. Затем добавьте 2 дополнительных отрезка, чтобы соединить новую позицию линии со старыми точками соединения. Ваш второй пример показывает одну итерацию этого алгоритма: если A равно (0,0), а B равно (5, 7), то вы случайно выбрали 2-й отрезок (вертикальный), конечную точку в (0,5 ) и среднюю точку в (5,5), и передвиньте эту секцию вправо на 3 единицы, прежде чем снова присоединиться к ней.

Answer 3

Вот идея ---

Начните с А и сделайте движение в случайном направлении - влево, вверх или вниз. После каждого хода бросайте случайное число, чтобы увидеть, повернете ли вы. Допустим, 75% времени вы продолжаете путешествовать в одном и том же направлении, а 25% времени вы поворачиваете. Когда вы поворачиваете, всегда поворачивайте в направлении, которое ведет ближе к B. Это будет означать, что если вы двигаетесь влево или вправо, вам придется повернуть вверх, а если вы двигаетесь вверх, сделайте выбор вправо / влево в зависимости от того, как далеко вы находитесь в данный момент справа или слева от цели. Кроме того, если вы попали в одну из границ мира, включите!

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