Miklix

Caça i mata generador de laberints

Publicat: 6 de març del 2025, a les 11:17:37 UTC

Generador de laberints amb l'algoritme Hunt and Kill per crear un laberint perfecte. Aquest algorisme és similar al Backtracker recursiu, però tendeix a generar laberints amb passadissos una mica menys llargs i sinuosos.

Aquesta pàgina es va traduir automàticament de l'anglès per tal de fer-la accessible al màxim de persones possible. Malauradament, la traducció automàtica encara no és una tecnologia perfeccionada, de manera que es poden produir errors. Si ho prefereixes, pots veure la versió original en anglès aquí:

Hunt and Kill Maze Generator

L'algoritme Hunt and Kill és realment una versió modificada del Recursive Backtracker. La modificació consisteix a escanejar (o "caçar") sistemàticament una nova cel·la per continuar des de quan no pot anar més enllà, en oposició a una veritable cerca recursiva, que sempre tornarà a la cel·la anterior de la pila.

Per això, aquest algorisme es pot adaptar fàcilment per generar laberints amb un aspecte i una sensació diferent, només escollint entrar en el mode "caça" més sovint o segons unes regles específiques. La versió implementada aquí només entra en mode "caça" quan no pot anar més lluny de la cel·la actual.

Un laberint perfecte és un laberint en el qual hi ha exactament un camí des de qualsevol punt del laberint fins a qualsevol altre punt. Això vol dir que no pots acabar donant voltes, però sovint et trobaràs amb carrerons sense sortida, obligant-te a donar la volta i tornar enrere.

Els mapes de laberint generats aquí inclouen una versió predeterminada sense cap posició d'inici i d'arribada, de manera que les podeu decidir vosaltres mateixos: hi haurà una solució des de qualsevol punt del laberint fins a qualsevol altre punt. Si voleu inspiració, podeu activar una posició d'inici i d'arribada suggerida, i fins i tot veure la solució entre les dues.


Genera un laberint nou








Sobre l'algoritme Hunt and Kill

L'algoritme Hunt and Kill és un mètode senzill però eficaç per generar laberints. És una mica semblant a una cerca en profunditat (és a dir, l'algoritme Recursive Backtracker), excepte que quan no pot anar més lluny de la posició actual, escaneja (o "caça") sistemàticament el laberint per trobar una nova cel·la per procedir. L'algorisme consta de dues fases principals: caminar i caçar.

Com funciona l'algoritme Hunt and Kill per a Maze Generation

Pas 1: comença en una cel·la aleatòria

  • Trobeu una cel·la aleatòria a la quadrícula i marqueu-la com a visitada.

Pas 2: Fase de caminada (caminada aleatòria)

  • Trieu un veí no visitat a l'atzar.
  • Desplaceu-vos a aquest veí, marqueu-lo com a visitat i traieu un camí entre la cel·la anterior i la nova.
  • Repetiu-ho fins que no quedi cap veïnat no visitat.

Pas 3: fase de caça (retrocés mitjançant l'escaneig)

  • Escaneja la quadrícula fila per fila (o columna per columna).
  • Trobeu la primera cel·la no visitada que tingui almenys un veí visitat.
  • Connecteu aquesta cel·la a un veí visitat per reprendre la fase de caminada.
  • Repetiu fins que s'hagin visitat totes les cel·les.

Comparteix a BlueskyComparteix a FacebookComparteix a LinkedInComparteix a TumblrComparteix a XComparteix a LinkedInPin a Pinterest

Mikkel Bang Christensen

Sobre l'autor

Mikkel Bang Christensen
Mikkel és el creador i propietari de miklix.com. Té més de 20 anys d'experiència com a programador/desenvolupador de programari informàtic professional i actualment treballa a temps complet per a una gran corporació informàtica europea. Quan no fa blocs, dedica el seu temps lliure a una gran varietat d'interessos, aficions i activitats, que fins a cert punt es poden reflectir en la varietat de temes tractats en aquest lloc web.