Як кодувати свій власний процедурний генератор карт підземель за допомогою алгоритму випадкової прогулянки

Оскільки технологія розвивається, а вміст гри стає більш алгоритмічним, неважко уявити створення реальної симуляції з унікальним досвідом для кожного гравця.

Технологічний прорив, терпіння та вдосконалені навички приведуть нас туди, але першим кроком є ​​розуміння процесуального змісту вмісту .

Хоча існує багато готових рішень для створення карт, цей посібник навчить вас створювати власний двовимірний генератор карт підземель з нуля за допомогою JavaScript.

Існує багато типів двовимірних карт, і всі вони мають такі характеристики:

1. Доступні та важкодоступні зони (тунелі та стіни).

2. Підключений маршрут, яким гравець може рухатися.

Алгоритм у цьому посібнику походить від алгоритму випадкової прогулянки, одного з найпростіших рішень для створення карт.

Після створення сітчастої карти стін цей алгоритм починається із випадкового місця на карті. Він продовжує робити тунелі та робити випадкові повороти, щоб закінчити бажану кількість тунелів.

Щоб побачити демонстраційну версію, відкрийте проект CodePen нижче, клацніть на карті, щоб створити нову карту, і змініть такі значення:

  1. Розміри: ширина та висота карти.
  2. MaxTunnels: найбільша кількість поворотів, яку може зробити алгоритм при складанні карти.
  3. MaxLength: найбільшу довжину кожного тунелю, який вибере алгоритм перед тим, як робити горизонтальний або вертикальний поворот.

Примітка: чим більший maxTurn порівняно з розмірами, тим щільнішою буде карта. Чим більше maxLength у порівнянні з розмірами, тим більше буде виглядати "тунель-у".

Далі, давайте пройдемося по алгоритму генерації карт, щоб побачити, як це:

  1. Складає двовимірну карту стін
  2. Вибирає випадкову початкову точку на карті
  3. Поки кількість тунелів не дорівнює нулю
  4. Вибирає випадкову довжину з максимально дозволеної довжини
  5. Вибирає випадковий напрямок для повороту (вправо, вліво, вгору, вниз)
  6. Малює тунель у цьому напрямку, уникаючи країв карти
  7. Зменшує кількість тунелів і повторює цикл while
  8. Повертає карту зі змінами

Цей цикл триває до тих пір, поки кількість тунелів не дорівнює нулю.

Алгоритм у коді

Оскільки карта складається з тунельних та настінних комірок, ми могли б описати її як нулі та одиниці у двовимірному масиві, як показано нижче:

map = [[1,1,1,1,0], [1,0,0,0,0], [1,0,1,1,1], [1,0,0,0,1], [1,1,1,0,1]]

Оскільки кожна комірка знаходиться у двовимірному масиві, ми можемо отримати доступ до її значення, знаючи її рядок і стовпець, наприклад map [рядок] [стовпець].

Перед написанням алгоритму вам потрібна допоміжна функція, яка приймає символ і розмір як аргументи і повертає двовимірний масив.

createArray(num, dimensions) { var array = []; for (var i = 0; i < dimensions; i++) { array.push([]); for (var j = 0; j < dimensions; j++) { array[i].push(num); } } return array; } 

Для реалізації алгоритму випадкової прогулянки встановіть розміри карти (ширину та висоту), maxTunnelsзмінну та maxLengthзмінну.

createMap(){ let dimensions = 5, maxTunnels = 3, maxLength = 3; 

Далі створіть двовимірний масив, використовуючи заздалегідь визначену допоміжну функцію (двовимірний масив із них).

let map = createArray(1, dimensions);

Встановіть випадковий стовпець і випадковий рядок, щоб створити випадкову точку відліку для першого тунелю.

let currentRow = Math.floor(Math.random() * dimensions), currentColumn = Math.floor(Math.random() * dimensions);

Щоб уникнути складності діагональних поворотів, алгоритму потрібно вказати горизонтальний та вертикальний напрямки. Кожна комірка розміщена у двовимірному масиві, і її можна ідентифікувати за допомогою рядка та стовпця. Через це напрямки можна визначити як віднімання та / або додавання до номерів стовпців та рядків.

Наприклад, щоб перейти до комірки навколо комірки [2] [2], ви можете виконати такі операції:

  • щоб піднятися вгору , відніміть 1 з його рядка [1] [2]
  • щоб спуститися вниз , додайте 1 до його рядка [3] [2]
  • щоб рухатися праворуч , додайте 1 до його стовпця [2] [3]
  • щоб піти ліворуч , відніміть 1 із його стовпця [2] [1]

Наступна карта ілюструє ці операції:

Тепер встановіть для directionsзмінної наступні значення, з яких буде вибирати алгоритм перед створенням кожного тунелю:

let directions = [[-1, 0], [1, 0], [0, -1], [0, 1]];

Нарешті, ініціюйте randomDirectionзмінна, щоб зберегти випадкове значення з масиву напрямків, і встановіть для lastDirectionзмінної порожній масив, який буде містити старшийrandomDirectionзначення.

Примітка:lastDirection масив порожній на перший цикл , тому що це не старше randomDirectionзначення.

let lastDirection = [], randomDirection;

Далі переконайтеся, що maxTunnelне дорівнює нулю, і розміри та maxLengthзначення отримані. Продовжуйте знаходити випадкові напрямки, поки не знайдете той, який не є зворотним або ідентичним lastDirection. Цей цикл do while допомагає запобігти перезапису нещодавно намальованого тунелю або малюванню двох тунелів спиною до спини.

Наприклад, якщо ваше значення lastTurn- [0, 1], цикл do while заважає функції рухатися вперед, доки randomDirectionне встановлено значення, яке не [0, 1] або протилежне [0, -1].

do { randomDirection = directions[Math.floor(Math.random() * directions.length)]; } while ((randomDirection[0] === -lastDirection[0] && randomDirection[1] === -lastDirection[1]) || (randomDirection[0] === lastDirection[0] && randomDirection[1] === lastDirection[1])); 

У циклі do while є дві основні умови, які поділяються на || (АБО) знак. Перша частина умови також складається з двох умов. Перший з них перевіряє , є чи randomDirection«першим елементом є зворотним по відношенню до lastDirection" и першого елемента. Другий перевіряє, чи є randomDirectionдругий предмет зворотним до lastTurnдругого елемента.

Для ілюстрації, якщо значення lastDirectionдорівнює [0,1] і randomDirectionдорівнює [0, -1], перша частина умови перевіряє, чи randomDirection[0] === - lastDirection[0]), що дорівнює 0 === - 0, і це правда.

Потім перевіряється, чи ( randomDirection[1] === - lastDirection[1]), що дорівнює (-1 === -1), а також відповідає дійсності. Оскільки обидві умови є істинними, алгоритм повертається назад, щоб знайти іншу randomDirection.

Друга частина умови перевіряє, чи перше та друге значення обох масивів однакові.

Вибравши а, randomDirectionщо задовольняє умовам, встановіть змінну, щоб довільно вибрати довжину maxLength. Встановіть для tunnelLengthзмінної значення нуля для сервера як ітератора.

let randomLength = Math.ceil(Math.random() * maxLength), tunnelLength = 0;

Зробіть тунель, повернувши значення клітинок від одиниці до нуля, тоді як tunnelLengthзначення менше ніж randomLength. Якщо в межах циклу тунель потрапляє по краях карти, цикл повинен розірватися.

while (tunnelLength < randomLength) { if(((currentRow === 0) && (randomDirection[0] === -1))|| ((currentColumn === 0) && (randomDirection[1] === -1))|| ((currentRow === dimensions — 1) && (randomDirection[0] ===1))|| ((currentColumn === dimensions — 1) && (randomDirection[1] === 1))) { break; }

В іншому випадку встановіть поточну комірку карти на нуль, використовуючи, currentRowі currentColumn.додайте значення в randomDirectionмасиві, встановивши currentRowі currentColumnде вони повинні бути в майбутній ітерації циклу. Тепер збільште tunnelLengthітератор.

else{ map[currentRow][currentColumn] = 0; currentRow += randomDirection[0]; currentColumn += randomDirection[1]; tunnelLength++; } } 

Після того, як петля зробить тунель або зламається, натиснувши край карти, перевірте, чи довжиною тунель є хоча б один блок. Якщо так, то встановіть lastDirectionна randomDirectionі декремент maxTunnelsі повернутися , щоб зробити ще один тунель з іншого randomDirection.

if (tunnelLength) { lastDirection = randomDirection; maxTunnels--; } 

Цей оператор IF запобігає циклу for, який потрапив у край карти і не створив тунель принаймні з однієї комірки для зменшення maxTunnelта зміни lastDirection. Коли це трапляється, алгоритм шукає інший randomDirectionдля продовження.

When it finishes drawing tunnels and maxTunnels is zero, return the resulting map with all its turns and tunnels.

} return map; };

You can see the complete algorithm in the following snippet:

Congratulations for reading through this tutorial. You are now well-equipped to make your own map generator or improve upon this version. Check out the project on CodePen and on GitHub as a react application.

Thanks for reading! If you liked this story, don't forget to share it on social media.

Special thanks to Tom  for co-writing this article.