JavaScript Maze Risolutore Algoritmo

Question

HTML

<div id="labirinth"> 
    <form style="text-align:center" name="forma1" autocomplete="on"> 
     <table style="margin:0 auto;"> 
      <tr> 
       <td style="float:right;">Height:</td> 
       <td><input type="text" id="height" name="height" autofocus="autofocus" maxlength="2" size="6" /></td> 
      </tr> 
      <tr> 
       <td style="float:right;">Width:</td> 
       <td><input type="text" id="width" name="width" maxlength="2" size="6" /></td> 
      </tr> 
     </table> 
    </form> 
    <input type="button" alt="submit" onClick="datas();" value="New" style="margin-top:10px;" /> 
</div> 
<pre id="out"></pre> 

JavaScript

function datas() { 

    var height = parseInt(document.getElementById("height").value); 
    var width = parseInt(document.getElementById("width").value); 

    document.getElementById('out').innerHTML = display(maze(height,width)); 
} 

function maze(x,y) { 
    var n=x*y-1; 
    if (n<0) {alert("Bad numbers!");return;} 
    var horiz=[]; 
     for (var j= 0; j<x+1; j++) horiz[j]= []; 
    var verti=[]; 
     for (var j= 0; j<y+1; j++) verti[j]= []; 

    var here= [Math.floor(Math.random()*x), Math.floor(Math.random()*y)]; 
    var path= [here]; 
    var unvisited= []; 
    for (var j= 0; j<x+2; j++) { 
     unvisited[j]= []; 
     for (var k= 0; k<y+1; k++) 
      unvisited[j].push(j>0 && j<x+1 && k>0 && (j != here[0]+1 || k != here[1]+1)); 
    } 
    while (0<n) { 
     var potential= [[here[0]+1, here[1]], [here[0],here[1]+1], 
      [here[0]-1, here[1]], [here[0],here[1]-1]]; 
     var neighbors= []; 
     for (var j= 0; j < 4; j++) 
      if (unvisited[potential[j][0]+1][potential[j][1]+1]) 
       neighbors.push(potential[j]); 
     if (neighbors.length) { 
      n= n-1; 
      next= neighbors[Math.floor(Math.random()*neighbors.length)]; 
      unvisited[next[0]+1][next[1]+1]= false; 
      if (next[0] == here[0]) 
       horiz[next[0]][(next[1]+here[1]-1)/2]= true; 
      else 
       verti[(next[0]+here[0]-1)/2][next[1]]= true; 
      path.push(here= next); 
     } else 
      here= path.pop(); 
    } 
    return ({x: x, y: y, horiz: horiz, verti: verti}); 
} 

function display(m) { 
    var text= []; 
    for (var j= 0; j<m.x*2+1; j++) { 
     var line= []; 
     if (0 == j%2) 
      for (var k=0; k<m.y*4+1; k++) 
       if (0 == k%4) 
        line[k]= 'X'; 
       else 
        if (j>0 && m.verti[j/2-1][Math.floor(k/4)]) 
         line[k]= ' '; 
        else 
         line[k]= 'X'; 
     else 
      for (var k=0; k<m.y*4+1; k++) 
       if (0 == k%4) 
        if (k>0 && m.horiz[(j-1)/2][k/4-1]) 
         line[k]= ' '; 
        else 
         line[k]= 'X'; 
       else 
        line[k]= ' '; 
     if (0 == j) line[1]=line[3]=' ',line[2]= '1'; 
     if (m.x*2-1 == j) line[4*m.y]= '2'; 
     text.push(line.join('')+'\r\n'); 

    } 
    return text.join(''); 
} 

Sto cercando di creare completamente funzionante generatore labirinto in JavaScript senza l'utilizzo di celle di una tabella HTML. Ora ho problemi con il risolutore di creazione per questo labirinto.

Domanda: Quale algoritmo di risoluzione del labirinto devo utilizzare per il mio codice? Con cosa dovrei iniziare? Non ho bisogno dell'algoritmo intero - ho solo bisogno di un consiglio se sia possibile avere un labiruatore in questo generatore di labirinti.

JSbin - http://jsbin.com/uwoyon/1

Answer 1

La mia raccomandazione per un risolutore che dovrebbe funzionare per i labirinti si sta generando sarebbe l'algoritmo di Dijkstra. Mentre non sono sicuro di come i parametri horiz e verti definiscano la struttura del labirinto, l'algoritmo di Dijkstra funzionerebbe nella tua situazione partendo dalla cella accanto a "1" e costruendo da lì.

Il modo in cui opera è etichettare ciascuna cella con il numero di celle tra esso e la cella iniziale. Per un 3x3 labirinto prima cella sarebbe:

x 1 xxxxxxxxx 
x 1   x 
x xxxxxxxxx 
x   x 
x xxxxxxxxx 
x   2 
xxxxxxxxxxxxx 

lavoro da un controllo di cella etichettata se v'è una cella adiacente vuota (non bloccata da un muro), incrementare il valore della cella di 1. Ripetere questo processo per tutte le celle vuote:

x 1 xxxxxxxxx 
x 1 2 3 x 
x xxxxxxxxx 
x 2 3 4 x 
x xxxxxxxxx 
x 3 4 5 2 
xxxxxxxxxxxxx 

Ora ritroso dalla cella adiacente all'estremità '2'. Questo mostra che la soluzione ha un percorso di 5 fasi, quindi inizia da 5, trova il 4 adiacente, poi il 3, ecc. Torna a 1.

Nota: Raccomando una soluzione ricorsiva usando le code per etichettare le celle :

1- Label prima cella con un '1' e posizionarlo nella coda.

2- Prendere la cella dalla coda: - Controllare se un vicino legale (quelli che non sono bloccati da un muro) non è etichettato. - Se una cella adiacente non è etichettata, etichettarla con la cella corrente + 1. - Aggiungi cella adiacente alla coda. - Ripetizione per tutti e 4 i potenziali vicini

3- Ripetere i passaggi 1 e 2 finché non ci sono più celle non etichettate.

EDIT: Ecco il fiddle per un risolutore utilizzando quello che ho suggerito, che non riguarda il generatore labirinto nella questione in modo meno che chiesto, non voglio entrare nei dettagli su come funziona (è un po ' ruvido, ma la sua implementazione dovrebbe essere abbastanza facile da seguire).

Answer 2

Se è un labirinto perfetto (solo un percorso tra due celle qualsiasi), è sufficiente un follower ricorsivo. Inizia con la prima cella e controlla tutte le celle circostanti in un determinato ordine, in genere in senso orario o antiorario. Se la cella può essere inserita, inseriscila. Se è la fine, hai finito. In caso contrario, recurse. Quando hai controllato tutti e 3 altri percorsi e nessuno è la fine, torna semplicemente.Quando raggiungi la fine, lo stack di chiamate ha la soluzione :) Quello che faccio in genere è "false" per "Non ho trovato la soluzione qui" o "true" per "questa è la soluzione".

Si può vedere come posso risolvere nei miei algoritmi labirinto su github:

https://github.com/mdchaney/jsmaze

Se si guarda jsmaze2.html il "find_depth" la funzione è in realtà un risolutore.

jsmaze4.html è molto più complesso ma in realtà costruisce la soluzione mentre costruisce labirinti con l'algoritmo ricorsivo. Lo fa tenendo traccia di quale muro è stato abbattuto quando una cella è "entrata" durante la costruzione. Dato che ci sono altri algoritmi, ho incluso anche "find_depth" che imposta la parete di ingresso per qualsiasi labirinto.

Questo è sufficiente per iniziare.

Answer 3

Il modo non ricorsivo risolverebbe il labirinto per te. Con la ricorsione (algo backtracking), puoi cavalcare la fortuna.

fare riferimento a questo documento: - http://cs.stanford.edu/people/eroberts/courses/cs106b/chapters/07-backtracking-algorithms.pdf

Se questa domanda sarebbe aperto fino a fine settimana. Vorrei pubblicare una risposta codificata.

Grazie