A * manhattan distance

Question

Ho cercato l'algoritmo/pseudocodice di A * l'ho seguito e l'ho codificato. Ho usato la distanza di Manhattan per h (n). (F (n) = g (n) + h (n)) E questo è il risultato,

Questo avviene sempre quando non ci sono pareti che bloccano la strada, ma quando ho messo un sacco dei muri, sembra che stia prendendo la strada più breve. È questo il percorso più breve? Intendo perché non è come questo qui sotto?

Questo è anche A * Manhattan, e hanno le stesse dimensioni (19x19). Questo è da http://qiao.github.com/PathFinding.js/visual/

Answer 1

Entrambi i percorsi hanno la stessa distanza di manhattan. Pertanto, dipende dall'implementazione il percorso scelto. Per capire perché è stata scelta questa parte specifica, dovremmo esaminare il codice di questa specifica implementazione A *.

Suggerimento: ogni percorso da una sorgente a una cella di destinazione che utilizza solo Von Neumann neighborhood (ovvero, non cammina in diagonale) e non fa un passo nella direzione "sbagliata" (ovvero, non va mai avanti o a sinistra nell'esempio) ha la stessa distanza di manhattan. Quindi, se sei a New York, non importa quale incrocio si prende per raggiungere un certo posto a Manhattan :)

Answer 2

Con la distanza di manhattan il primo è un percorso più breve. Conta semplicemente il numero di passi orizzontali e verticali presi. Se vuoi qualcosa che somiglia più a un percorso più breve nella distanza euclidea, puoi provare a cambiare il tuo algoritmo in modo che quando ha la possibilità di spostarsi orizzontalmente o verticalmente in un punto, sceglie quello orizzontale se la distanza orizzontale è maggiore della verticale uno e viceversa.

Answer 3

È necessario lanciare una linea di vista (pitagorico/euclideo) dal punto di partenza a ogni punto (del risultato manhattan/A *) fino al termine. Se il lancio di una linea a un certo punto viene bloccato/nascosto dall'ostacolo, si usa il punto precedente lanciato e si inizia a lanciare un'altra linea da quel punto bloccato poi avanti fino alla fine. Un punto bloccato è quando un punto è nascosto dalla linea di vista del punto iniziale del segmento/linea. quindi è come:

Prima riga: Inizio ---------> S + N (punto prima bloccato)

Seconda/Medio Linea/s: Point bloccati ------ ----> S + N (prima di un altro punto bloccato) ripetere di nuovo (nuova linea/segmento) fino a quando non ha stabilito una linea di mira all'obiettivo.

ultima riga: Bloccato Point -------------> Goal

Collegare tutte le linee e hai un percorso più breve molto più breve. È possibile eseguire di nuovo, ma in senso inverso per aggiungere un'altra precisione in modo che la linea di vista inizierà dall'obiettivo fino all'inizio.