Perché il percorso A * a volte va in linea retta e talvolta in diagonale? (Java)

Question

Sono in procinto di sviluppare un semplice gioco di simulazione basato su una griglia 2d, e ho una ricerca di percorso completamente funzionale.

Ho utilizzato la risposta trovata nella domanda precedente come base per l'implementazione del percorso A *. (Pathfinding 2D Java game?).

Per mostrarti veramente quello che sto chiedendo, ho bisogno di mostrarti questa schermata che ho catturato. Stavo solo mettendo alla prova per vedere come la persona si muoverebbe in una posizione e viceversa, e questo è stato il risultato ...

http://www.screenjelly.com/watch/Bd7d7pObyFo

Diversa scelta del percorso a seconda della direzione, un risultato inaspettato. Qualche idea?

Answer 1

Se stai cercando una soluzione semplice, posso suggerire un po 'di randomizzazione?

Ciò che intendo è questo: nell'esempio di codice cokeandcode, esiste il nested-for-loops che genera gli "stati successivi" (per utilizzare il termine AI). Mi riferisco al punto in cui circola sul quadrato 3x3 attorno allo stato "corrente", aggiungendo nuove posizioni sulla pila da considerare.

Una correzione relativamente semplice dovrebbe (dovrebbe :)) essere isolare quel codice un po 'e farlo, ad esempio, generare un elenco di nodi collegato prima del resto della fase di elaborazione. Quindi Containers.Shuffle (o è Generics.Shuffle?) Quell'elenco collegato e continua l'elaborazione lì. Fondamentalmente, dire una routine, "createNaiveNeighbors (node)" che restituisce una LinkedList = {(node.x-1, node.y), (node.x, node.y-1) ...} (per favore perdonare il pidgin Java, sto cercando (e sempre fallendo) di essere breve

Una volta creato l'elenco collegato, tuttavia, dovresti essere in grado di fare un "for (Node n: myNewLinkedList)" invece di il

for (int x=-1;x<2;x++) { 

    for (int y=-1;y<2;y++) { 

e continuare a utilizzare lo stesso codice esatto corpo!

cosa questo avrebbe fatto, idealmente, è una sorta di percorsi "scuotere" l'ordine dei nodi considerati, e creare più vicino al la diagonale, ma senza dover cambiare l'euristica. I percorsi saranno comunque i più efficienti, ma di solito più vicino alla diagonale.

Lo svantaggio è, ovviamente, se si passa da A a B più volte, può essere preso un percorso diverso. Se ciò è inaccettabile, potrebbe essere necessario prendere in considerazione una modifica più drastica.

Spero che questo aiuti! -Agor

Answer 2

Entrambi i percorsi hanno la stessa lunghezza, quindi l'algoritmo sta svolgendo il proprio lavoro in modo ottimale - sta trovando un percorso più breve. Tuttavia, l'algoritmo A * non specifica QUANTO il percorso più breve che prenderà. Le implementazioni normalmente prendono il "primo" percorso più breve. Senza vedere il tuo, è impossibile sapere esattamente perché, ma se vuoi ottenere gli stessi risultati ogni volta dovrai aggiungere regole di priorità di qualche tipo (in modo che il percorso desiderato venga visualizzato per primo nella ricerca).

Answer 3

Il motivo è il percorso che si desidera venga eseguito dall'algoritmo.
Non conosco l'euristico utilizzato dal tuo A *, ma nel primo caso deve prima andare alla fine del tunnel e poi pianificare la strada dalla fine del tunnel al bersaglio.

Nel secondo caso, le mosse più semplici verso i bersagli si abbassano fino a colpire il muro e poi pianifica la strada dal muro al bersaglio.

La maggior parte A * So che lavoro con una linea di vista euristica o un Manhattan Distance nel caso di un mondo a blocchi. Questa euristica ti dà la via più breve, ma in caso di ostacoli che costringono ad andare in una direzione diversa dalla linea di vista, le vie dipendono dal tuo punto di partenza.
L'algoritmo andrà alla linea di vista il più a lungo possibile.

Answer 4

Se ho visto bene, la sfera si sta muovendo prima a destra in una linea straigt, perché non può arrivare direttamente verso l'obiettivo (il percorso è bloccato). Quindi, va dritto verso l'obiettivo. Sembra solo diagonale.

Answer 5

La ricerca appare prima nella direzione "in basso"? Questo potrebbe spiegare l'algoritmo. Prova a cambiarlo per cercare "su" prima e scommetto che vedresti il ​​comportamento opposto.

Answer 6

La risposta più probabile è che andare dritto verso il sud lo faccia per primo al suo obiettivo; andando nella direzione opposta, questa non è una scelta, quindi ottimizza il sub-percorso a tratti con il risultato che alternando le mosse su/attraverso sono viste come migliori.

Se vuoi che la diagonale torni indietro, dovrai identificare alcuni punti di interesse lungo il percorso (ad esempio la foce del tunnel) e tenerne conto nella tua euristica. In alternativa, puoi tenerne conto nell'algoritmo rielaborando qualsiasi sottotracciato che passa attraverso un punto di interesse.

Nel corso della giornata erano soliti eseguire un'analisi statica precompilata di mappe e posizionare marcatori di percorso nei punti di strozzatura. A seconda di quale sia il tuo obiettivo finale, potrebbe essere una buona idea anche qui.

Se sei veramente interessato a sapere cosa sta succedendo, ti suggerisco di eseguire i passaggi della ricerca A *. Data la tua domanda, potrebbe essere molto illuminante per te.

Answer 7

Il motivo per cui è in realtà piuttosto semplice: il percorso cercherà sempre di avere l'euristica più bassa possibile perché ricerca in modo avido. Avvicinarsi all'obiettivo è un percorso ottimale.

Se si consentiva il movimento diagonale, ciò non accadrebbe.

Answer 8

In ogni caso preferisce il percorso che lo porta più vicino al suo nodo obiettivo prima, che è ciò per cui è progettato A *.

Answer 9

A seconda dell'implementazione del tuo astar vedrai risultati diversi con la stessa euristica, come molte persone hanno menzionato. Ciò è dovuto ai legami, quando due o più traiettorie legano il modo in cui ordini il tuo set aperto determinerà il modo in cui apparirà il percorso finale. Otterrai sempre il percorso ottimale se disponi di un'euristica ammissibile, ma i nodi visitati aumenteranno con il numero di legami che hai (rispetto a un euristico che produce meno vincoli).

Se non pensi che visitare più nodi sia un problema, ti suggerirei di usare la proposta di randomizzazione (che è la tua risposta corrente). Se ritieni che la ricerca di più nodi sia un problema e desideri ottimizzare, suggerirei di utilizzare una sorta di tie-breaker. Sembra che tu stia usando la distanza di manhattan, se usi la distanza euclidea quando due nodi si legano come tiebreaker otterrai percorsi più dritti verso l'obiettivo e visiterai meno nodi. Questo è naturalmente senza alcuna trappola o blocco di linea di mira verso la meta.

Per evitare di visitare i nodi con elementi di blocco nel percorso della linea di vista, suggerirei di trovare un'euristica che tenga conto di questi elementi di blocco. Naturalmente una nuova euristica non dovrebbe fare più lavoro di una normale ricerca di una stella.

Suggerirei di guardare a my question in quanto potrebbe produrre alcune idee e soluzioni a questo problema.