Labirinturi - nu este doar o clasă independentă de jocuri, dar, de asemenea, baza pentru crearea de locații în alte genuri de jocuri: de exemplu, sisteme de peșteri, care, la rândul lor, pot fi folosite într-o clasă foarte largă de jocuri-brodilok etc. Cu toate acestea, în cazul în care jucătorul va trebui să constant „examineze“ aceeași locație, se poate ajunge în curând plictisi cu ea, ci pentru că înainte de dezvoltatorii de jocuri există o chestiune de o generație labirint de procedură, și anume, la fiecare joc la următoarea trecere a avut loc pe teritoriul regenereze.
Labirinturi, vom construi pe un teren dreptunghiular de celulare (+ unul dintre articolele pe generarea de spațiu tridimensional), astfel încât toate dintre ele pot fi împărțite în două grupe: labirinturi cu pereți subțiri „“ și „groase“. În primul rând - cei ale căror pereți sunt situate la limitele de celule, acestea din urmă - sunt acelea în care unele dintre celulele însele sunt de netrecut, și anume pereți. Ele se disting, de exemplu, o metodă de stocare a datelor pe o hartă.
Există, de asemenea, soluții gata făcute pentru generarea de labirinturi: Obligarea Generator. care este utilizat în DOOM, DOOM II și Heretic, și colab.
Eller algoritm
Pe tema generării de labirinturi, în cazul în care pereții sunt situate la limitele de celule Habré au o bună traducere a articolului «Eller Algoritmul lui» (adică Eller, nu Euler - «Eller lui», mai degrabă decât «Euler») cu privire la modul de a crea perfectă labirint (f) - astfel că există o cale, și numai unul între oricare două dintre celulele sale.
Ideea generală a algoritmului este de a genera non-interlaced, în care între fiecare două celule rând în anumite condiții (pentru a evita bucle și celule inaccesibile) apare un perete aleatoriu. În cele din urmă toate celulele vor fi „un set“, ceea ce ar însemna că există între oricare două celule de drum.
Magazin de carte de labirint poate fi, de exemplu, în matrice bidimensionale: pereți verticale și orizontale, respectiv.
Cum se păstrează labirinturi cu perete „gros“?
Răspunsul la întrebarea de carduri de stocare astfel de labirinturi este evidentă: într-o matrice bidimensională a boolean, în cazul în care, de exemplu, 1 - este celula de netrecut (perete), 0 - gratuit.
Algoritmul naiv
Desigur, există două aspecte: dacă camera nu se vor suprapune, și cum să construiască tranzițiile între ele? Răspunsul la prima întrebare depinde de cerințele dumneavoastră pentru labirint, dacă nu doriți să fi traversat camera, a scrie o funcție care verifică o pereche de camere de la intersecție, și apariția camera alăturată, un card de verificare.
Labirintul în tabelul
În algoritmul descris mai sus, există un dezavantaj evident: verifica dacă camerele sunt traversate, avem o funcție separată. Se pune întrebarea dacă este de a face o acțiune prea mult posibil. Se pare, și algoritmul poate- este descris mai jos.
Ideea este că domeniul inițial este împărțit în celule dreptunghiulare „mari“ (adică, nici celule elementare ale terenului de joc, și dreptunghiuri, constând din câteva celule), formând astfel de masă. Mai mult, în fiecare dintre aceste celule apare aleator dimensiune camera aleatoare, nu și dimensiunile celulei superioare - astfel posibilitatea de a se intersecteze spațiu dispare. Apoi, camerele holurile combinate, de exemplu, în aceeași manieră ca cea descrisă în paragraful anterior.
Detalii acest algoritm de generare descris în articolul «grid pe Dungeon Generator».
copaci BSP
BSP - este prescurtarea de binar Space Partiționarea - diviziunea binară a spațiului. Acest algoritm evită, de asemenea, trecerea camerelor încă în procesul de a le pune pe hartă, după cum De asemenea, pre-împarte o porțiune a câmpului de joc - „frunze“, care generează apoi în interiorul camerei. Această zonă diviziune ideologic mai dificilă, deoarece toți împărtășesc. decât algoritmul precedent, dar, de asemenea, vă permite să creați un spațiu mai interesant locație de configurare.
labirinturi Generation folosind automat celular
Fiecare programator a scris cel puțin o dată, „Life“ - un automat celular inventat de matematicianul Conway. Deci, de ce să nu utilizați o idee similară pentru a genera un labirint? Esența algoritmului propus este de a pune în aplicare doar două etape: în primul rând, întregul câmp este umplut cu pereți aleatoare - adică pentru fiecare celulă determinată în mod aleatoriu dacă este liber sau impracticabil - și apoi actualizează în mod repetat starea cardului în conformitate cu termenii și condițiile similare condițiilor de naștere / moarte „Viața.“
Sursa de - articol pagina «genera niveluri aleatoare Cave Folosind Cellular automatelor» - puteți experimenta cu un demo interactiv, stabilirea unor valori diferite pentru a genera: numărul de iterații de renovare, valorile limită pentru moartea / celulă de viață etc. - și a vedea rezultatul. Ibid descrie capcanele de punere în aplicare.
Generarea de spațiu tridimensional
Ce urmează?
Pe tema acestui articol, există o mare varietate de materiale, care pot fi găsite pe Internet, așa că, dacă doriți să se îngropa în problema generării de labirinturi, poti sa te uiti aici mai întâi. și numai atunci, desigur, că e aici.
Vă mulțumesc pentru atenție!