adventuregamestudio/ags — pull request #212 by gurok (2014-11-16 00:44:15+00:00)
Title: 340 fixed pathfinding

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:

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.)

This commit makes the Dijkstra pathfinder the preferred pathfinder,
defaulting only to the old pathfinder when Dijkstra (rarely) fails. Keyboard
movement is handled with can_see_from (basically a best-first search) and
has no real relevance to the pathfinder.

This is a revision of a previous commit that erroneously removed the
pathfinding code altogether. It would seem that our Dijkstra algorithm isn't a
fully correct implementation (which should cover the test area in < 5000
iterations) and might need to be revisited in future. My recommendation would
be to implement A* in a future release. For now, this fixes the original bug
and gives people the pathfinding they expect (retaining backwards
compatibility).

One more thing, I tested this against:
- My simple test case (above)
- Ben Jordan 3