Sarebbe accettabile per inserire un limite intorno alla mia zona pathfinding?

Question

Attualmente sto usando l'algoritmo A * pathfinding per calcolare un percorso su una griglia infinita (utilizzando un UnboundedGrid nel Gridworld, caso di studio AP CS, se questo aiuta a chiunque). Tutto funziona meravigliosamente, salvo i casi in cui non esistono percorso valido perché il nodo finale è completamente circondato da pareti. Come previsto, l'algoritmo continua la ricerca all'infinito, senza mai trovare il nodo finale.

Una possibile soluzione a questo problema sarebbe quella di inserire invisibile (come in, l'utente non li vede ma l'algoritmo fa) pareti intorno l'intera area pathfinding, assicurandosi che il nodo di partenza, nodo terminale, e tutti i nodi parete sono tra queste mura, con 2-3 spazi imbottitura o così. Qualcosa di simile:

_________________________________
|                               |
|              S  |             |
|            _____|   _____     |
|                     | E |     |
|                     |___|     |
|_______________________________|

... l'idea è che alla fine tutti saranno aggiunti i nodi al closedlist, l'openlist diventerà vuoto, ea quel punto saprò che non esiste alcun percorso valido.

Questo sembra una soluzione ragionevole al problema? Ci sono dei modi in cui questo potrebbe potenzialmente andare male? Ho capito che un'altra soluzione è simultaneamente pathfind all'indietro dalla fine, ma sembra che potrebbe essere potenzialmente costoso, in particolare nei casi in cui il nodo finale non è così strettamente racchiuso.

Answer 1

Non si sa esattamente dove si trova il nodo finale? Se lo fai, basta controllare se è circondato prima di fare il vostro algoritmo.

Answer 2

Si veda anche il mio commento alla tua domanda. Dopo aver digitato mi si avvicinò con quello che potrebbe essere una bella soluzione. Questo è per un caso in cui non si conosce il nodo finale e può fare niente con la posizione vostro di end-nodo come suggerito sopra.

Si potrebbe anche qualcosa sulla falsariga di: "Ho trovato una scatola chiusa nel mio campo e nessun percorso dopo x tempo così con y% propability posso dire non v'è alcun percorso, e aggiornare il y% ad aumentare nel tempo, ma senza mai raggiungere il 100%.

Potrebbe essere una bella soluzione, che si trova nel mezzo della delimitazione della zona di ricerca e non fare nulla.

Answer 3

Ho avuto un problema simile e questo è quello che ho fatto:

1. Esegui algoritmo per n iterazioni, a partire da una ricerca per B.
2. Esegui algoritmo per n iterazioni, a partire da B alla ricerca di un.

Se uno dei due run determina che uno o l'altro si trova in una zona completamente isolata (nessun nodo più aperti), la ricerca fallisce. In caso contrario, la ricerca viene effettuata come di consueto.

Il trucco è, naturalmente, a venire con un buon valore per n . Ho fatto più passaggi con l'aumentare della n e memorizzati nella cache i risultati (il mio grafico cambiamento non ha ancora un sacco).

Answer 4

si utilizza un * così si dovrebbe essere in grado di pesare i nodi del terreno con un costo. Mettere un costo follemente alto sui nodi parete. Deve essere maggiore del costo totale di ogni possibile percorso. Se il costo fine del percorso è maggiore di quella dei costi di confine, allora si doveva passare un muro per trovare un percorso, quindi è valido. L'A * Percorsi algoritmo intorno nodi ad alto costo, in modo che non sarà percorso attraverso un muro a meno che non deve.