search

wheybags / freeablo

[ARCHIVED] Modern reimplementation of the Diablo 1 game engine
GNU General Public License v3.0
2.16k stars 195 forks source link

Fix mistake in heuristic #439

Closed akuskis closed 4 years ago

akuskis commented 5 years ago

Hi @wheybags , please review.

Fixed bug in heuristic.

Before:

. . ✔ . . 
. ✔ . . . 
✔ . . . . 
✔ . . . . 
. ✔ . . . 
. . ✔ . .

After:

. . ✔ . . 
. . ✔ . . 
. . ✔ . . 
. . ✔ . . 
. . ✔ . . 
. . ✔ . .
akuskis commented 5 years ago

Fix for #440

wheybags commented 4 years ago

Thanks for the fix!

AJenbo commented 4 years ago

Just some trivia, in the original game, if A and B were not aligned on either x or y the path would first move diagonally until they align. This appears to be down to the order the A* implementation looks at different directions on the grid:

-1,-1 = NW
-1, 1 = SW
 1,-1 = SE
 1, 1 = NW
-1, 0 = W
 0,-1 = N
 1, 0 = E
 0, 1 = S
 . . B . . 
 . . ^ . . 
 . . ^ . . 
 . . ^ . . 
 . . ^ . . 
 . . . A .