Author Topic: Pathfinding bug?  (Read 2701 times)

Gurok

  • Rottwheelers
  • When life hands you lemons, combine them with the mop
    • I can help with AGS tutoring
    • Best Innovation Award Winner 2016, for improving and extending the AGS scripting language
    • I can help with proof reading
    • I can help with scripting
    • Gurok worked on a game that won an AGS Award!
    •  
    • Gurok worked on a game that was nominated for an AGS Award!
Pathfinding bug?
« on: 21 May 2014, 11:25 »
I think I'm slowly going mad. I think I've found a bug, but I'm not sure if I'm missing something or maybe it's a known issue or something. Here are the steps:

1. Create a new Default Game
2. In the first room, use this as the background and the walkable areas mask:

3. Place a new label on the status line. Call it "lblStatus" and put this code in the global repeatedly_execute_always:
Code: [Select]
lblStatus.Text = String.Format("Player: (%d, %d)   Mouse: (%d, %d)", player.x, player.y, mouse.x, mouse.y);4. Start the game
5. Move the mouse to (158, 69) and click. Roger walks there (expected). Let him finish walking.
6. Move the mouse to (158, 183) and click. Nothing happens. In fact this seems to be true for (158, n) as far as I've tested.

Can anyone else replicate this and does anyone know what's going on here? I'm presuming it's a pathfinding bug, but I'm open to suggestions. I thought my paths were pretty safe (no areas < 3 pixels wide).

Khris

  • having to deal with what games are going through
    • Lifetime Achievement Award Winner
    • I can help with play testing
    • I can help with scripting
    • I can help with translating
    • Khris worked on a game that was nominated for an AGS Award!
Re: Pathfinding bug?
« Reply #1 on: 21 May 2014, 12:02 »
Yes, I can replicate this. Clicking just one pixel to the left or right of 158, 183 will work as usual.
Clicking on 158, 164 does nothing, clicking on 158, 163 and further up works normally.

Gurok

  • Rottwheelers
  • When life hands you lemons, combine them with the mop
    • I can help with AGS tutoring
    • Best Innovation Award Winner 2016, for improving and extending the AGS scripting language
    • I can help with proof reading
    • I can help with scripting
    • Gurok worked on a game that won an AGS Award!
    •  
    • Gurok worked on a game that was nominated for an AGS Award!
Re: Pathfinding bug?
« Reply #2 on: 21 May 2014, 12:56 »
Thanks Khris! Just knowing that someone else can replicate it is a big help. Your notes are pretty thorough. I've got the same results from my testing. Also, it's not tied to column 158 specifically. It just needs to be the same column that Roger walked to in the first place.

I'm still investigating. Appreciate any ideas.


Gurok

  • Rottwheelers
  • When life hands you lemons, combine them with the mop
    • I can help with AGS tutoring
    • Best Innovation Award Winner 2016, for improving and extending the AGS scripting language
    • I can help with proof reading
    • I can help with scripting
    • Gurok worked on a game that won an AGS Award!
    •  
    • Gurok worked on a game that was nominated for an AGS Award!
Re: Pathfinding bug?
« Reply #4 on: 21 May 2014, 14:43 »
Thank you Billbis. That was very informative. I did a quick text-based dump to see what was happening with the old pathfinding:





Now, I can only speculate right now as to why it stops at those points. Perhaps it runs out of directions to try, gets confused? I don't know. But this assumption in the code:

Code: [Select]
; // don't use new algo on arrow key presses
Is actually incorrect anyway.

1) Diagonal key presses won't give you a vertical or horizontal line to follow
2) Keyboard movement modules use WalkStraight anyway (which uses can_see_from, but not find_route)

I could be wrong, but it feels like this chunk of code should try find_route_dijkstra and then *only* if that fails revert to the old pathfinding routine.


EDIT: I tend to think it should be this:

Code: [Select]
  // Try the new pathfinder
  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;

Or at the very least, use is_straight to determine the order of old/new, not skip new entirely.
« Last Edit: 21 May 2014, 14:55 by Gurok »

Billbis

  • R, what else?
    • I can help with translating
Re: Pathfinding bug?
« Reply #5 on: 21 May 2014, 14:50 »
Quote from: Gurok
I could be wrong, but it feels like this chunk of code should try find_route_dijkstra and then *only* if that fails revert to the old pathfinding routine.
Agreed. It will require some testings to be 100% sure, but that is definitely an option.

Another solution that have been proposed was to recode a new pathfinder based on plygons, but obviously that's way more work than changing a boolean in the source code. ;)
« Last Edit: 21 May 2014, 15:32 by Billbis »

Re: Pathfinding bug?
« Reply #6 on: 21 May 2014, 14:56 »
A link to my WIKI on this is in this thread:

Click me.

The problem is not the width of the walkable area, but rather does that area line up with the grid such that a stair-step path can be clearly made.   The docs that say "make it more than 3 pixels wide" are misleading.  Just by looking at your walkable area, I'll bet that if you pad the narrow spots just a little bit to allow a clear 3x3 stair-step to fit it'll solve your problem. I don't have time to run it through the debug version that I made that draws the paths at the moment.

« Last Edit: 21 May 2014, 15:34 by TheBitPriest »

Re: Pathfinding bug?
« Reply #7 on: 21 May 2014, 16:08 »
Really, the easiest and quickest fix, with the least amount of side-effects, is to change the editor. 

If someone could either add a "grid paint" feature (or just always lock the painting walkable areas to the grid) it would fix the problem.

Adding a grid paint would probably be better, since there are times when you might want a 1-pixel through a narrow gap, and it's not that it doesn't work.  It's just prone to (seemingly mysterious) failures.

Try this one.






Gurok

  • Rottwheelers
  • When life hands you lemons, combine them with the mop
    • I can help with AGS tutoring
    • Best Innovation Award Winner 2016, for improving and extending the AGS scripting language
    • I can help with proof reading
    • I can help with scripting
    • Gurok worked on a game that won an AGS Award!
    •  
    • Gurok worked on a game that was nominated for an AGS Award!
Re: Pathfinding bug?
« Reply #8 on: 22 May 2014, 01:33 »
Try this one.



The same bug is present with that walkable area mask, TheBitPriest. After reading through that Pathfinding Granularity thread, I now suspect there's some part of my walkable area mask causing the old pathfinder to double back and/or halt due to depth. Even if clamping the path to a 3x3 grid did work for this case, I think it would be a really clunky approach.

I applied a patch to my local copy of AGS that does not use the old pathfinder over Dijkstra's algorithm when navigating straight lines and the problem went away. Similar to what I outlined a few posts above. I'm going to recommend this as a patch when CrimsonWizard gets back. The whole straight line assumption seems bogus to me.

Some more thoughts...

One possible reason for the "don't use new algo on arrow key presses" comment might be that the old pathfinding algorithm was determined to be faster for horizontal and vertical lines. Even if this is the case, that's no reason to discard the Dijkstra pathfinding entirely in these cases. We could use is_straight to determine which of the two algorithms is tested first.

I think it's more likely that this is old code though. As I said previously, WalkStraight makes reference to can_see_from, but not find_route. The keyboard modules I've seen use WalkStraight, so this find_route code isn't even called "on arrow key presses". And it's a bad assumption anyway because it doesn't cover diagonal arrow keys.
« Last Edit: 22 May 2014, 02:44 by Gurok »

Re: Pathfinding bug?
« Reply #9 on: 22 May 2014, 15:38 »
You removed the old search and the problem went away?  Do you mean you could still navigate to the point you were selecting?  I am really tempted to roll back my engine code and check that out.  If you're getting to the second search and the image is a 3x3 grid, then the first search must be hitting its limit.  Increasing the limits them can make pathfinding more successful, but it runs to the risk of introducing a more significant lag on slower machines.  I removed them on my machine.

The old search is just plain broken.  There are cases where it should work, but it fails by doubling back on itself.   Based on the text dumps that you uploaded, it looks like that's what happened.  My assumption was that the some of the quirky behavior of this old search became expected.  Otherwise, why keep it at all?  Why not use Dijkstra twice?   In fact, I tried that, and it works like a champ.  It's not an optimal solution though.

My main focus in getting into the pathfinding was to produce non-technical documentation in order to help users working with the current engine.   
After doing that, I replaced the entire thing with an A* based strategy.  It's about 3/4 finished.  I had wanted to make an interface to allow the designers (AGS users) to control the resolution of the search.  However, after CW announced his departure and the forum started talking about refactoring, I stopped working on that code altogether and went back to my other commitments.

Unless your project has the luxury of using its own version of the engine, if you need to get this room working, I would suggest shrinking the mask 33%, and then enlarging it to 320x200 using nearest neighbor.   If that still doesn't work, I'm at a loss... I'd have to throw it into the debugger.  I must have missed something about this system.  :-X


Gurok

  • Rottwheelers
  • When life hands you lemons, combine them with the mop
    • I can help with AGS tutoring
    • Best Innovation Award Winner 2016, for improving and extending the AGS scripting language
    • I can help with proof reading
    • I can help with scripting
    • Gurok worked on a game that won an AGS Award!
    •  
    • Gurok worked on a game that was nominated for an AGS Award!
Re: Pathfinding bug?
« Reply #10 on: 23 May 2014, 01:46 »
You removed the old search and the problem went away?  Do you mean you could still navigate to the point you were selecting?

More specifically, this is what I did:
https://github.com/gurok/ags/commit/d2635fa0116ea488dfa1c92171960b5911065e75

To clarify, I did not remove the old pathfinder completely. I just made it a second tier algorithm in the horz/vert case. With this in place, I could navigate the vertical paths outlined in my test case perfectly.

The old logic was:
if the line is not straight then
  try dijkstra and return on success
end if
try old pathfinder

The new logic is:
try dijkstra and return on success
try old pathfinder

I am really tempted to roll back my engine code and check that out.  If you're getting to the second search and the image is a 3x3 grid, then the first search must be hitting its limit.  Increasing the limits them can make pathfinding more successful, but it runs to the risk of introducing a more significant lag on slower machines.  I removed them on my machine.

The old search is just plain broken.

I think I may have poorly communicated what I actually did. See my outline of the logic changes above.

Agreed though! The old search is broken.

There are cases where it should work, but it fails by doubling back on itself.   Based on the text dumps that you uploaded, it looks like that's what happened.  My assumption was that the some of the quirky behavior of this old search became expected.  Otherwise, why keep it at all?  Why not use Dijkstra twice?   In fact, I tried that, and it works like a champ.  It's not an optimal solution though.

This is what I couldn't fathom. The reasoning for the use of the old search "don't use new algo on key presses" doesn't make any sense. That theory about the old search behaviour becoming expected sounds like a possibility. It would certainly explain why Dijjkstra was ruled out entirely for those cases. Perhaps this means I should hide the changes in the commit above behind a game version check, i.e. If game version is >= 3.3.1, ignore is_straight.

My main focus in getting into the pathfinding was to produce non-technical documentation in order to help users working with the current engine.

After doing that, I replaced the entire thing with an A* based strategy.  It's about 3/4 finished.  I had wanted to make an interface to allow the designers (AGS users) to control the resolution of the search.  However, after CW announced his departure and the forum started talking about refactoring, I stopped working on that code altogether and went back to my other commitments.

This is a better long term strategy, but I'd still like to patch the engine for now to at least *try* Dijkstra in these purely horz/vert cases. It does fix the problem for me. The 3x3 gridding you did to my walkable mask did not. I think the pathfinder is doubling back, like you suggested.

Regarding a future A* implementation, I think the interface could be as simple as a few values in a new Pathfinding section under General Settings, e.g.:
Pathfinder Grid Size (default = 3)
Pathfinder Timeout (default = 100ms?)
Use New Pathfinder (default = true)

Unless your project has the luxury of using its own version of the engine, if you need to get this room working, I would suggest shrinking the mask 33%, and then enlarging it to 320x200 using nearest neighbor.   If that still doesn't work, I'm at a loss... I'd have to throw it into the debugger.  I must have missed something about this system.  :-X

Yeah, I do build my own version of the engine. I thought I would make a pull request because it's listed in the bugtracker. I think your analysis is right. You might have missed a corner case or two that causes the old pathfinder to double back, as your 3x3 suggestion didn't seem to do anything. But nobody could really know what's expected with that old pathfinder!
« Last Edit: 23 May 2014, 02:07 by Gurok »

Crimson Wizard

  • Local Moderator
    • Best Innovation Award Winner 2013, for spearheading the AGS 3.3.0 project
    • Lifetime Achievement Award Winner
    • Crimson Wizard worked on a game that won an AGS Award!
    •  
    • Crimson Wizard worked on a game that was nominated for an AGS Award!
Re: Pathfinding bug?
« Reply #11 on: 23 Jun 2014, 11:33 »
I think we may take this fix for the time being, but I am interested in finding out whether old algorithm really works better (e.g. faster) for straight lines, and whether it is really needed at all.

Secondly, does this need a game version check? May there be a case when a game really needs this erroneous behavior (do I miss anything here)?