Caça i mata generador de laberints

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.

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.