Bug in AGS pathfinder.

Started by Billbis, Thu 27/06/2013 21:29:01

Previous topic - Next topic

Billbis

Hello,
I (and other: Kitai 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
[close]
(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: AGS
function hHotspot1_Interact()
{
  player.Say("First movement.");
  player.Walk(699, 551, eBlock, eWalkableAreas);
  player.Say("Second (buggy) movement.");
  player.Walk(67, 551, eBlock, eWalkableAreas);
}

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: AGS

//Bug not present
player.Walk(699, 551, eBlock, eWalkableAreas);
player.Walk(67, 549, eBlock, eWalkableAreas);
//Bug present
player.Walk(699, 551, eBlock, eWalkableAreas);
player.Walk(67, 550, eBlock, eWalkableAreas);
//Bug present
player.Walk(699, 551, eBlock, eWalkableAreas);
player.Walk(67, 551, eBlock, eWalkableAreas);
//Bug not present
player.Walk(699, 551, eBlock, eWalkableAreas);
player.Walk(67, 552, eBlock, eWalkableAreas);
//Bug present
player.Walk(699, 552, eBlock, eWalkableAreas);
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.

Billbis

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: AGS
  if (is_straight)
    ; // don't use new algo on arrow key presses
  else if (find_route_dijkstra(srcx, srcy, tox[0], toy[0])) {
    return 1;
  }

  // if the new pathfinder failed, try the old one
  pathbackstage = 0;
  memset(&beenhere[0][0], 0, wallscreen->GetWidth() * wallscreen->GetHeight() * BEENHERE_SIZE);
  if (try_this_square(srcx, srcy, tox[0], toy[0]) == 0)
    return 0;

  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 ?

Crimson Wizard

Billbis, can you confirm that this is fixed in AGS 3.3.1 alpha 2?

Billbis

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


SMF spam blocked by CleanTalk