Come attraversare un labirinto in modo programmatico quando sei in un vicolo cieco

Question

Muoversi in avanti nel labirinto è abbastanza semplice, ma non riesco a capire come tornare indietro nel labirinto per provare un nuovo percorso una volta raggiunto un vicolo cieco senza tornare indietro troppo lontano?

Answer 1

Utilizzo fare marcia indietro mantenendo una pila di precedenti decisioni di direzione.

Answer 2

L'algoritmo più semplice (da implementare) sarebbe quello di conservare semplicemente una serie di luoghi in cui sei stato e il percorso che hai seguito da ciascuno, a meno che il backtracking non ti fornisca tali informazioni.

Per tornare indietro, rimuovi le vecchie posizioni dallo stack e controlla altre uscite da quella posizione finché non trovi una vecchia posizione con un'uscita non testata.

Testando costantemente le uscite nello stesso ordine ogni volta, se sai che il ritorno verso una posizione avviene dal basso (ad es.l'ultima volta che eri nella vecchia posizione in cui sei sceso), quindi scegli semplicemente la direzione successiva giù.

Non sono del tutto sicuro di cosa intendi con andando troppo indietro tuttavia, suppongo che vorresti tornare al luogo precedente in cui hai percorsi non testati, non è quello che vuoi?

Tieni presente che, a meno che non provi a tenere traccia del percorso dal punto di partenza alla posizione corrente ed eviti quei quadrati quando provi a trovare nuovi percorsi, potresti finire per andare in cerchio, il che alla fine renderebbe la pila troppo grande.

Un semplice metodo ricorsivo che segna il percorso da seguire e non entra mai nelle aree contrassegnate può farlo facilmente.

Inoltre, se il tuo cosa che si muove attraverso il labirinto è leggermente più intelligente che semplicemente essere in grado di muoversi e colpire (fermarsi) i muri, in quanto può vedere dal suo punto attuale in tutte le direzioni, ho altri algoritmi che potrebbero aiutare.

Answer 3

Eric Lippert ha scritto una serie di articoli sulla creazione di un file Implementazione C# di A*, che potrebbe essere più efficiente.