gurok/ags — pull request #19 by gurok (2014-06-03 20:56:11+00:00)
Title: Fixed pathfinding failure on horizontal/vertical lines

This fixes a bug that has been reported by several forum folks:
http://www.adventuregamestudio.co.uk/forums/index.php?topic=48529

Bug tracker here:
http://www.adventuregamestudio.co.uk/forums/index.php?issue=418.0

The pathfinding algorithm often fails to find a path when navigating in
a straight line from the player's current location. My thread above
contains a simple test case for replicating the problem:
http://www.adventuregamestudio.co.uk/forums/index.php?topic=50487

Whether or not it fails depends on the complexity of the walkable area
mask. If the walkable area mask is too complicated for the old
pathfinder, pathfinding fails.

The culprit is some code in __find_route that prevents AGS from using
the Dijkstra pathfinder when navigating along a vertical or horizontal
path. The consequences of using Dijkstra in these cases aren't clear,
but the current check for vertical and horizontal lines appears to make
a faulty assumption:

```
; // don't use new algo on arrow key presses
```

I think this is bogus because:

1) Keyboard movement modules bundled with AGS use WalkStraight.
WalkStraight calls can_see_from, but does not use the main find_route
function. (It's possible that this is an old comment. In the past, there
might have been some code that called find_route from WalkStraight.)

2) Diagonal key presses do not result in vertical or horizontal paths.
So even if this was relevant to key presses, it would not be relevant to
all directions.

This commit only does the straight line check for older versions. For
newer versions, it makes the __find_route always try Dijkstra first and
try the old pathfinder only if Dijkstra fails. I think this is the right
way to fix the problem.