Miklix

Generator Labirinta Lov i Ubijanje

Objavljeno: 16. veljače 2025. u 21:01:12 UTC

Generator labirinta koji koristi algoritam Hunt and Kill za stvaranje savršenog labirinta. Ovaj je algoritam sličan Recursive Backtrackeru, ali nastoji generirati labirinte s nešto kraćim, vijugavim hodnicima.

Ova je stranica strojno prevedena s engleskog kako bi bila dostupna što većem broju ljudi. Nažalost, strojno prevođenje još nije usavršena tehnologija pa se mogu pojaviti pogreške. Ako želite, izvornu englesku verziju možete pogledati ovdje:

Hunt and Kill Maze Generator

Algoritam Hunt and Kill zapravo je modificirana verzija Recursive Backtrackera. Modifikacija se sastoji od sustavnog skeniranja (ili "lova") za novom ćelijom od koje se nastavlja kada ne može ići dalje, za razliku od pravog rekurzivnog pretraživanja, koje će se uvijek vratiti na prethodnu ćeliju na stogu.

Zbog toga se ovaj algoritam može lako prilagoditi za generiranje labirinta s različitim izgledom i osjećajem, samo češćim odabirom ulaska u način "lova" ili prema određenim pravilima. Ovdje implementirana verzija ulazi samo u "lov" način kada ne može ići dalje od trenutne ćelije.

Savršen labirint je labirint u kojem postoji točno jedan put od bilo koje točke u labirintu do bilo koje druge točke. To znači da se ne možete vrtjeti u krug, ali ćete često naići na slijepe ulice, zbog čega ćete se morati okrenuti i vratiti.

Ovdje generirane karte labirinta uključuju zadanu verziju bez ikakvih početnih i završnih pozicija, tako da ih možete sami odlučiti: postojat će rješenje od bilo koje točke u labirintu do bilo koje druge točke. Ako želite inspiraciju, možete omogućiti predloženu početnu i ciljnu poziciju - pa čak i vidjeti rješenje između ta dva.


Generirajte novi labirint








O algoritmu lov i ubij

Algoritam Hunt and Kill jednostavna je, ali učinkovita metoda za stvaranje labirinta. Donekle je sličan pretrazi u dubinu (tj. algoritmu Recursive Backtracker), osim kada ne može ići dalje od trenutne pozicije, sustavno skenira (ili "lovi") labirint kako bi pronašao novu ćeliju iz koje bi mogao nastaviti. Algoritam se sastoji od dvije glavne faze: hodanja i lova.

Kako algoritam lov i ubij radi za Maze Generation

Korak 1: Počnite od nasumične ćelije

  • Pronađite slučajnu ćeliju u mreži i označite je kao posjećenu.

Korak 2: Faza hodanja (nasumično hodanje)

  • Odaberite nasumično neposjećenog susjeda.
  • Pomaknite se do tog susjeda, označite ga kao posjećenog i iscrtajte put između prethodne i nove ćelije.
  • Ponavljajte sve dok ne ostanu neposjećeni susjedi.

Korak 3: Faza traženja (povratak putem skeniranja)

  • Skenirajte mrežu red po red (ili stupac po stupac).
  • Pronađite prvu neposjećenu ćeliju koja ima barem jednog posjećenog susjeda.
  • Povežite tu ćeliju s posjećenim susjedom kako biste nastavili fazu hodanja.
  • Ponavljajte dok se ne posjete sve ćelije.

Podijeli na BlueskyPodijelite na FacebookuPodijelite na LinkedInuPodijelite na TumblrPodijeli na XPodijelite na LinkedInuPrikvači na Pinterest

Mikkel Bang Christensen

O autoru

Mikkel Bang Christensen
Mikkel je kreator i vlasnik miklix.com. Ima više od 20 godina iskustva kao profesionalni računalni programer/razvijač softvera i trenutno je zaposlen na puno radno vrijeme za veliku europsku IT korporaciju. Kada ne piše blog, svoje slobodno vrijeme provodi na široku lepezu interesa, hobija i aktivnosti, što se u određenoj mjeri može odraziti na različite teme obrađene na ovoj web stranici.