Geek asks and answers

Distance A * manhattan

I searched for the algorithm / pseudo-code A * I and followed it. I used the Manhattan distance for h (n). (f (n) = g (n) + h (n)) And this is the result,

This always happens when there are no walls blocking the path, but when I put a lot of walls, it seems that it takes the shortest path. Is this the shortest way? I mean, why doesn't this look like this below?

This one is also A * Manhattan, and they are the same size (19x19). This is from http://qiao.github.com/PathFinding.js/visual/

+5
source share
3 answers

. , , . , , A *.

: , (.. ) "" (.. ) . , -, , , :)

+5

- . . -, , , , , , .

0

(/) ( manhattan/A *) . / , , . A - /. :

: --------- > S + N ( )

Second / Midline / s: Locked Point ----------> S + N (before another locked point) is repeated again (new line / segment) until the line of sight is set to the target.

Last line: locked point -------------> Target

Connect all the lines and you have a much shorter shortest path. You can do it again, but vice versa, to add another precision so that the line of sight starts from the target before the start.

0
source

More articles:


All Articles