Caça i mata generador de laberints

L'algoritme Hunt and Kill és en realitat 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 ja no pot anar més enllà, a diferència d'una veritable cerca recursiva, que sempre tornarà a la cel·la anterior de la pila.

Per això, aquest algoritme es pot adaptar fàcilment per generar laberints amb diferents aspectes i sensacions, simplement triant entrar en mode "caça" més sovint o segons 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.

Sobre l'algoritme de caça i mort

L'algoritme Hunt and Kill és un mètode senzill però eficaç per generar laberints. És una mica similar 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 des de la qual procedir. L'algoritme consta de dues fases principals: caminar i caçar.

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

Pas 1: Comenceu en una cel·la aleatòria

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

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

• Trieu un veí a l'atzar que no es visiti.
• Mou-te a aquesta cel·la veïna, marca-la com a visitada i crea un camí entre la cel·la anterior i la nova.
• Repetiu-ho fins que no quedin veïns sense visitar.

Pas 3: Fase de caça (retrocés mitjançant escaneig)

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

Lectures addicionals

Si t'ha agradat aquesta publicació, també et poden agradar aquests suggeriments:

• Generador de laberints d'algoritmes d'Eller
• Generador de laberints d'algoritmes d'arbres en creixement
• Generador de laberints d'algoritmes de Wilson