adventuregamestudio/ags — pull request #160 by gurok (2014-05-22 09:45:21+00:00)
Title: Bugtracker pathfinding straight 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 removes the straight line check and 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, but I'm open to suggestions.

Let me know if this seems wrong. I can make a more conservative version, i.e. use is_straight to determine the order in which algorithms are applied. It's also possible for me to put this behind a game version check if needed.