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:
(http://i.imgur.com/PcBe4wx.gif)
3. Place a new label on the status line. Call it "lblStatus" and put this code in the global repeatedly_execute_always:
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).
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.
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.
Hi Gurok,
to learn more about it, you can read these :
http://www.adventuregamestudio.co.uk/forums/index.php?topic=48529.0 (http://www.adventuregamestudio.co.uk/forums/index.php?topic=48529.0)
http://www.adventuregamestudio.co.uk/forums/index.php?topic=49076.msg636472655#msg636472655 (http://www.adventuregamestudio.co.uk/forums/index.php?topic=49076.msg636472655#msg636472655)
http://www.adventuregamestudio.co.uk/forums/index.php?issue=418.0 (http://www.adventuregamestudio.co.uk/forums/index.php?issue=418.0)
Thank you Billbis. That was very informative. I did a quick text-based dump to see what was happening with the old pathfinding:
(http://i.imgur.com/FeL0XCx.gif)
(http://i.imgur.com/O8DDpQ3.gif)
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:
; // 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:
// 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.
Quote from: GurokI 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 (http://www.adventuregamestudio.co.uk/forums/index.php?topic=49076.msg636472721#msg636472721) was to recode a new pathfinder based on plygons, but obviously that's way more work than changing a boolean in the source code. ;)
A link to my WIKI on this is in this thread:
Click me. (http://www.adventuregamestudio.co.uk/forums/index.php?topic=49646.0)
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.
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.
(http://i.imgur.com/ZFQz8wF.png)
Quote from: TheBitPriest on Wed 21/05/2014 16:08:24
Try this one.
(http://i.imgur.com/ZFQz8wF.png)
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.
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
Quote from: TheBitPriest on Thu 22/05/2014 15:38:35
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
Quote from: TheBitPriest on Thu 22/05/2014 15:38:35
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.
Quote from: TheBitPriest on Thu 22/05/2014 15:38:35
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.
Quote from: TheBitPriest on Thu 22/05/2014 15:38:35
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)
Quote from: TheBitPriest on Thu 22/05/2014 15:38:35
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!
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)?