Hogyan kell kódolni saját eljárási börtöntérkép-generátorát a Random Walk algoritmus segítségével

Amint a technológia fejlődik és a játék tartalma algoritmikusabban generálódik, nem nehéz elképzelni egy életszerű szimuláció létrehozását, amely minden játékos számára egyedi élményeket nyújt.

A technológiai áttörések, a türelem és a kifinomult készségek eljutnak oda, de az első lépés az eljárási tartalom létrehozásának megértése .

Habár a térképkészítéshez sok out-of-the-box megoldás létezik, ez az oktatóanyag megtanít arra, hogy saját maga készítsen kétdimenziós börtöntérkép-generátort a semmiből a JavaScript használatával.

Sok kétdimenziós térképtípus létezik, és mindegyikük a következő jellemzőkkel rendelkezik:

1. Hozzáférhető és megközelíthetetlen területek (alagutak és falak).

2. Csatlakoztatott útvonalon a játékos navigálhat.

Az oktatóanyag algoritmusa a Random Walk algoritmusból származik, amely a térképkészítés egyik legegyszerűbb megoldása.

A falak rácsszerű térképének elkészítése után ez az algoritmus a térkép véletlenszerű helyéről indul. Folyamatosan alagutakat készít és véletlenszerű kanyarokat hajt végre a kívánt számú alagút teljesítéséhez.

A bemutató megtekintéséhez nyissa meg az alábbi CodePen projektet, kattintson a térképre egy új térkép létrehozásához, és változtassa meg a következő értékeket:

  1. Méretek: a térkép szélessége és magassága.
  2. MaxTunnels: a legtöbb fordulat, amelyet az algoritmus elvégezhet a térkép elkészítése során.
  3. MaxLength: az alagutak legnagyobb hosszát választja ki az algoritmus, mielőtt vízszintes vagy függőleges fordulatot hajtana végre.

Megjegyzés: minél nagyobb a maxTurn a méretekhez képest, annál sűrűbb lesz a térkép. Minél nagyobb a maxLength a méretekhez képest, annál inkább „alagút-y” fog kinézni.

Ezután menjünk át a térképgeneráló algoritmuson, hogy lássuk, hogyan:

  1. Kétdimenziós térképet készít a falakról
  2. Véletlenszerű kiindulási pontot választ a térképen
  3. Míg az alagutak száma nem nulla
  4. Véletlen hosszúságot választ a maximálisan megengedett hosszúság közül
  5. Véletlenszerű irányt választ, amely felé fordul (jobbra, balra, felfelé, lefelé)
  6. Alagutat rajzol abba az irányba, elkerülve a térkép széleit
  7. Csökkenti az alagutak számát, és megismétli a while ciklust
  8. Visszaadja a térképet a változtatásokkal

Ez a kör addig folytatódik, amíg az alagutak száma nulla.

Az algoritmus a kódban

Mivel a térkép alagút- és falcellákból áll, nullaként és egyekként írhatjuk le egy kétdimenziós tömbben, például:

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]]

Mivel minden cella kétdimenziós tömbben van, az értékét úgy tudjuk elérni, hogy ismerjük a sorát és az oszlopát, például a térkép [sor] [oszlop].

Az algoritmus megírása előtt szükséged van egy segítő függvényre, amely egy karaktert és dimenziót vesz fel argumentumként, és kétdimenziós tömböt ad vissza.

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; } 

A Véletlen séta algoritmus megvalósításához állítsa be a térkép méreteit (szélesség és magasság), a maxTunnelsváltozót és a maxLengthváltozót.

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

Ezután készítsen kétdimenziós tömböt az előre definiált segítő függvény segítségével (ezek kétdimenziós tömbje).

let map = createArray(1, dimensions);

Állítson be egy véletlenszerű oszlopot és egy véletlenszerű sort, hogy véletlenszerű kiindulási pontot hozzon létre az első alagút számára.

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

Az átlós fordulatok bonyolultságának elkerülése érdekében az algoritmusnak meg kell határoznia a vízszintes és a függőleges irányt. Minden sejt kétdimenziós tömbben ül, és sorával és oszlopával azonosítható. Emiatt az irányok meghatározhatók az oszlopok és sorok számának kivonásaként és / vagy kiegészítéseként.

Például a cella [2] [2] körüli cellához lépéshez a következő műveleteket hajthatja végre:

  • menni fel , 1 kivonása a sor [1] [2]
  • a lefelé lépéshez adjon 1-et a sorához [3] [2]
  • menni jobbra , adjunk hozzá 1 annak oszlopon [2] [3]
  • hogy menjen balra , 1 kivonása az oszlopban [2] [1]

A következő térkép szemlélteti ezeket a műveleteket:

Most állítsa be a directionsváltozót a következő értékekre, amelyek közül az algoritmus választani fog minden alagút létrehozása előtt:

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

Végül kezdeményezzen randomDirectionváltozó, hogy véletlenszerű értéket tartson az iránytáblából, és állítsa a lastDirectionváltozót egy üres tömbre, amely megtartja a régebbitrandomDirectionérték.

Megjegyzés: a lastDirectiontömb üres az első cikluson, mert nincs régebbi randomDirectionérték.

let lastDirection = [], randomDirection;

Ezután ellenőrizze, hogy maxTunnelnem nulla-e, és maxLengthmegkapta-e a dimenziókat és értékeket. Folytassa a véletlenszerű irányok keresését, amíg nem talál olyan irányt, amely nem fordított vagy azonos lastDirection. Ez a hurok segít megakadályozni a nemrégiben megrajzolt alagút felülírását vagy két alagút össze-vissza rajzolását.

Például, ha a lastTurnértéke [0, 1], akkor a do while ciklus megakadályozza a függvény továbblépését, amíg randomDirectionegy nem [0, 1] vagy ezzel ellentétes [0, -1] értékre állítunk.

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])); 

A do while ciklusban két fő feltétel van, amelyeket elválaszt egy || (VAGY) jel. A feltétel első része szintén két feltételből áll. Az első ellenőrzi, hogy a randomDirection„s első elem a fordítottja a lastDirection” s első elem. A második ellenőrzi, hogy a randomDirection'második tétel fordítottja-e a lastTurn' második tételnek.

Annak szemléltetésére, hogy ha a lastDirection[0,1] és randomDirection[0, -1], a feltétel első része ellenőrzi, hogy randomDirection[0] === - lastDirection[0]), ami 0 === - 0, és igaz.

Then, it checks if (randomDirection[1] === — lastDirection[1]) which equates to (-1 === -1) and is also true. Since both conditions are true, the algorithm goes back to find another randomDirection.

The second part of the condition checks if the first and second values of both arrays are the same.

After choosing a randomDirection that satisfies the conditions, set a variable to randomly choose a length from maxLength. Set tunnelLength variable to zero to server as an iterator.

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

Make a tunnel by turning the value of cells from one to zero while the tunnelLength is smaller than randomLength. If within the loop the tunnel hits the edges of the map, the loop should break.

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; }

Else set the current cell of the map to zero using currentRow and currentColumn. Add the values in the randomDirection array by setting currentRow and currentColumn where they need to be in the upcoming iteration of the loop. Now, increment the tunnelLength iterator.

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

After the loop makes a tunnel or breaks by hitting an edge of the map, check if the tunnel is at least one block long. If so, set the lastDirection to the randomDirection and decrement maxTunnels and go back to make another tunnel with another randomDirection.

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

This IF statement prevents the for loop that hit the edge of the map and did not make a tunnel of at least one cell to decrement the maxTunnel and change the lastDirection. When that happens, the algorithm goes to find another randomDirection to continue.

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.