Adventure Game Studio | Forums

AGS Development => Engine Development => Topic started by: Billbis on 27 Jun 2013, 21:29

Title: Bug in AGS pathfinder.
Post by: Billbis on 27 Jun 2013, 21:29
I (and other: Kitai (;u=12595) and valoulef ( have discovered a strange bug in AGS pathfinder (or, at least I think so). It is reproducible, but I have not so well define when it can occurs.
It happens mainly when a "pure horizontal" movement is ordered while the walkable area do not allow a single straight line passage. It may happen in pure vertical movement to, but that I am not sure.

I have made a small example project in which the bug is obvious : Download here, 1.8Mo (
Its just the default template with an example room.
Spoiler: ShowHide

(sorry about image scale)
The archive contain an AGS project (and its compiled file). Just interact with the gray area to trigger this script :
Code: Adventure Game Studio
  1. function hHotspot1_Interact()
  2. {
  3.   player.Say("First movement.");
  4.   player.Walk(699, 551, eBlock, eWalkableAreas);
  5.   player.Say("Second (buggy) movement.");
  6.   player.Walk(67, 551, eBlock, eWalkableAreas);
  7. }
Briefly, when player is in A and walk to B, character follow the yellow line, which doesn't seem to be the shortest pace.  :P
(Walkable area is the withe zone).

This bug is reproducible in AGS 3.2.1 and AGS 3.3.0 beta 4.
It does not depend on game resolution (tried in 1024x768 and 800x600).
It does not depend on blocking style.
It does depend on the shape of the walkable area.
It can be trigger with mouse click (and not script), but you'll have to be very accurate.
It is exacerbated when using this (still in development and not so well design) module ( that try to enforce walk on only 8 directions (verticals, horizontals and isometric diagonals).

Not sure if that helps, but it seems somehow dependent of 3x3 gird AGS uses for pathfinding :
Code: Adventure Game Studio
  1. //Bug not present
  2. player.Walk(699, 551, eBlock, eWalkableAreas);
  3. player.Walk(67, 549, eBlock, eWalkableAreas);
  4. //Bug present
  5. player.Walk(699, 551, eBlock, eWalkableAreas);
  6. player.Walk(67, 550, eBlock, eWalkableAreas);
  7. //Bug present
  8. player.Walk(699, 551, eBlock, eWalkableAreas);
  9. player.Walk(67, 551, eBlock, eWalkableAreas);
  10. //Bug not present
  11. player.Walk(699, 551, eBlock, eWalkableAreas);
  12. player.Walk(67, 552, eBlock, eWalkableAreas);
  13. //Bug present
  14. player.Walk(699, 552, eBlock, eWalkableAreas);
  15. player.Walk(67, 552, eBlock, eWalkableAreas);

My wife think that it can be due to taking the wrong limit of ArcTan(delta(x)/delta(y)) when delat(y) is near 0, but  :-, it can be many other things and I am by far not competent to have a look in Engine source code.
Title: Re: Bug in AGS pathfinder.
Post by: Billbis on 18 Jul 2013, 09:27
I started looking at AGS engine source code. Please note that I am in no way a programmer, and that I am a complete noob in C++.
If I understand correctly, the pathfinding thing is code in ags/Engine/ac/route_finder.cpp ( from GitHub. On the function __find_route (lines 568 - 616) there is these lines:
Code: Adventure Game Studio
  1.   if (is_straight)
  2.     ; // don't use new algo on arrow key presses
  3.   else if (find_route_dijkstra(srcx, srcy, tox[0], toy[0])) {
  4.     return 1;
  5.   }
  7.   // if the new pathfinder failed, try the old one
  8.   pathbackstage = 0;
  9.   memset(&beenhere[0][0], 0, wallscreen->GetWidth() * wallscreen->GetHeight() * BEENHERE_SIZE);
  10.   if (try_this_square(srcx, srcy, tox[0], toy[0]) == 0)
  11.     return 0;
  13.   return 1;

Which means that on straight line movements, Dijkstra is not called but the "old pathfinder". So basically I suspect that if there is any bug, it may be in the "old pathfinder" and not in Dijkstra implementation.
I tried to understand the "old parthfinder", but I failed miserably.  :embarrassed:
Any ideas ?
Title: Re: Bug in AGS pathfinder.
Post by: Crimson Wizard on 29 Aug 2014, 01:10
Billbis, can you confirm that this is fixed in AGS 3.3.1 alpha 2 (
Title: Re: Bug in AGS pathfinder.
Post by: Billbis on 29 Aug 2014, 10:11
Oh yes, sorry. I meant to test it some times ago, then I got lazy and never done it. I've just tet it now, and it work's like a charm, thank you all (and specially Gurok, I think). Bug is corrected. :)