(solved) Pathfinding granularity

[Radiant]

I've found that, on a room with thin walkable areas in a W shape, if the player character stands in the top left point and is given a Walk command to the top right point (typically by clicking the walk cursor there), the expected behavior would be to create a rather long and roundabout path, since there's no shortcut in the walkable areas.

However, if this path becomes too long, the pathfinding algorithm appears to give up, and just moves the character to somewhere in the middle; it requires multiple MoveCharacter calls in sequence to get him to his destination. This is understandable because lengthier pathfinding would cause the game to slow down; however is there some in-game way to tweak this, e.g. set the cutoff point higher in certain convoluted rooms?

[Andail]

I know virtually nothing about the these things, but I'm pretty sure this is hard-coded and impossible to tweak in the editor.

[selmiak]

*mumbles mysterious gibberish and summons a Crimson Wizard*

[Sephiroth]

If you don't mind having a pre-defined path when the distance is too far, then it can be quite easily done with 'basic' waypoints.
It would look like this:

Code: ags

//2d array containing x,y coordinates for all the waypoints
int WayPoints[20];

//2d array containing the coordinates of waypoints to use 
int CurrentWayPoints[20];

//simple math formula here
int GetDistance(x1, y1, x2, y2);

//get waypoints between pc position and destination/store them in CurrentWayPoints
void GetWayPoints();

//sort them with getdistance() or any algorithm
void SortWayPoints();


//on walkto action
if(GetDistance(player.X, player.Y, mouse.x, mouse.y) >= cutoff_point)
{
  int target_x = mouse.x;
  int target_y = mouse.y;
  GetWayPoints();
  SortWayPoints();
  int i = 0;
  while(i<20)
  {
    if(CurrentWayPoints[i] != -1 && CurrentWayPoints[i+1] != -1) //-1 means its not active
      player.Walk(CurrentWayPoints[i], CurrentWayPoints[i+1], eBlock, eWalkableAreas);
    i+=2;
  }
  player.Walk(target_x, target_y, eBlock, eWalkableAreas);
}

You would just have to define the waypoints coordinates and they will be used if you click past the cutoff point.
It would require some minor tweaks to make the walk actions non blocking. I can further implement this concept if you think it can be helpful.

[Radiant]

Thanks. Yes, it works to fix it in code; actually I'm more interested in knowing when it happens so that I can fix it in code

[TheBitPriest]

This has happened to me too!

Out of curiosity, I took a look at route_finder.cpp. It looks like there are several opportunities for the path-finding system to bail.

I made a test room with a large W and replicated your problem.  On a hunch, based on what I could see in the code above, I tired breaking up the W into multiple walkable areas.  FWIW, this fixes the problem. 

[Khris]

This is incredibly useful information, thanks for taking the time!

We should definitely add this to the manual, right...?

[Radiant]

I made a test room with a large W and replicated your problem.  On a hunch, based on what I could see in the code above, I tired breaking up the W into multiple walkable areas.  FWIW, this fixes the problem. 

Seriously? If instead of having one W of walkable-area-1, you have two V's of area 1 and 2, then it works? Wow.

[qptain Nemo]

We should definitely add this to the manual, right...?

Actually, yes. It's an actual limitation of the engine and users should be made aware of that as soon as possible as in any other such case.

[TheBitPriest]

grr...  I wanted to give you an exact answer, Radiant, but now I cannot reproduce the situation.  Earlier, I had used at least three walkable areas, but I may have been too sloppy with my test.

This time around, I was a little more methodical, making a big pink W background, tracing it with walkable areas, but no matter how I break them up, the player can only navigate one turn.  Either I was too sloppy with the first test (which I did not save... ), or I cannot seem to split the areas right. 

However, I did notice that even a slightly wider path fixed the problem.  I may have inadvertently made the path slightly wider in the first test.  I'm not really familiar enough with the engine code to be well-qualified to speak, and like I mentioned, without putting it in the debugger, I'm just guessing. 

For certain, AGS's pathfinding code struggles with at least two, long, acute, narrow turns.  One of those conditions above is causing it to bail.  An interesting problem!  I'm tempted to d/l the engine and try a few things or at least see which condition is failing.  I think I'd try increasing some of those #define'd values first.   Surely one of the folks on this board has looked at this before...

[TheBitPriest]

Last night I downloaded and compiled the engine in order to take a crack at this problem. 

First:  The number and width of your walkable areas do indeed have an impact on the success of the pathfinding algorithm.   If you simply have a large W with one walkable area, the pathfinding fails with return 0 below:

Code: c

    for (int n = 0; n < iteration; n++) {
      if (visited[n] == -1)
        continue;

      i = visited[n] % wallscreen->GetWidth();
      j = visited[n] / wallscreen->GetWidth();
      granularity = walk_area_granularity[wallscreen->GetScanLine(j)[i]];
      adjcount = 1;

//    char tempb[200]; sprintf(tempb, "checking: %d,%d\n",i,j); write_log(tempb);
      if (i >= granularity) {
        modifier = (destx < i) ? DIRECTION_BONUS : 0;
        CHECK_MIN(i - granularity, j)
      }

      if (j >= granularity) {
        modifier = (desty < j) ? DIRECTION_BONUS : 0;
        CHECK_MIN(i, j - granularity)
      }

      if (i < wallscreen->GetWidth() - granularity) {
        modifier = (destx > i) ? DIRECTION_BONUS : 0;
        CHECK_MIN(i + granularity, j)
      }

      if (j < wallscreen->GetHeight() - granularity) {
        modifier = (desty > j) ? DIRECTION_BONUS : 0;
        CHECK_MIN(i, j + granularity)
      }

      // If all the adjacent cells have been done, stop checking this one
      if (adjcount) {
        if (numreplace < 40) {
          visited[numreplace] = -1;
          replace[numreplace] = n;
          numreplace++;
        }
      }
    }

    if (numfound == 0) {
      free(visited);
      free(parent);
      return 0;
    }

I included this large section of code because the variable numfound is set within the macro CHECK_MIN.  I am out of time this morning, or else I would try to investigate this part of the problem further.   We might be able to fix it by tweaking the granularity of the algorithm, or by changing one of several hard coded constants sprinkled throughout this file.  I have not had time to figure out all of their purposes.

Second: If you create a large W and break it up into four (I only tested four) walkable areas, one for each branch of the W, the current engine will fail because of the length of the resulting path.  In my test, a full screen W with four walkable areas had to iterate 16836 times.  The engine is currently restricted by MAX_TRAIL_LENGTH which is set to 5000.   When I increased this to an arbitrarily large value, I could “count a second” (never a good thing on a computer!! ) while the engine iterated its 16k iterations.   The character did, however, successfully navigate the W.  Now, my machine is not the newest machine on the market. I have a 2.4 GHz Core 2 Duo P8600.  Perhaps, a larger cap of 20k or so would be tolerable on beefier machines.

As I mentioned before, I am out of time for today.   More (and wider) walkable areas might bring the value of iteration below the obnoxiously high value of 16836!!  Or the engine lords might decide to increase the value of  MAX_TRAIL_LENGTH...  with possible performance issues...  although they are in the hands of the room designer.  Maybe it could allow the path, but warn the programmer in the log? IMHO, I think letting the scripter hang himself would be preferable over just mysteriously failing to find a path.

There may be a better way to tweak the algorithm without a painful performance hit (or just replace this code).

I hope this information helps!!  We're all waiting for the latest Crystal Shard masterpiece! 

[Radiant]

Interesting, thanks. I would expect running time to increase exponentially as MAX_TRAIL_LENGTH goes up; it could probably be increased a bit on modern computers but tripling it would be pushing it. I'm not quite seeing how the above code makes a difference if I use differently-numbered walkable areas? Of course they're all at least 5 or 6 pixels wide (on 320x200 resolution) and it's currently more of a figure-eight than a W.

[TheBitPriest]

EDIT:  I've added a render update that lets me watch this work in realtime.  This has revealed some more information.  I'll update this post as I learn more.  The "fix" below is still accurate, but there are still a few mysteries to solve.

This was  my first time looking into anything in the engine.  I think it wasn't the number of sections but the max width of the widest section.  With the case I was using it was failing in is_route_possible.  The room below is different.

This has been fun learning a little more about how AGS works under the covers, and it help explain some mysterious behavior. 

In general, when you ask to move somewhere, the engine first determines the possibility of movement which at its root is done with Allergo's floodfill function.  Then the engine uses Dijkstra's path-finding algorithm to try and find a solution on a 3x3 grid.  If this fails, it reverts to a pixel-by-pixel recursive algorithm (optimized with a goto but the first and oldest limitation was to keep the game from blowing the stack! ).  Once you've begun this process, a path can (sometimes... notice the green spots inside the otherwise orange-filled area... for efficiency(? or a bug), a few pixels will be skipped) be drawn even through a 1 pixel gate.  The place where your character is standing will determine the success of the path.  It's not very predictable, but when you can see the result (as you can with my new debug code), you can solve the path-finding problems quickly.

Also, I have discovered that even with paths less than 3x3 the Dijkstra implementation can navigate them as long as the grid can successful be completed (i.e. 2x2 paths at right angles in the right places -- it will start were your character is standing)  The "make it wider than 3 advice" is just advice.    Good advice, to be sure.  But if you have the need, not only can you make rooms with 1 pixel paths, you can also make rather extensive paths at right angles in the right places.  Just as long as the algorithm can solve the path within its hard-coded limits.

What the Dijkstra search will not do is navigate diagonally unless the diagonal path allows the 3x3 grid to fit within the walkable area. So, it's more than just "over 3 pixels wide."  The grid must fit. 

Given the following mask (I've cropped it to the problem area -- just in case seeing this mask could be a spoiler for a certain Sierra-like game that we're all anticipating):



The room designer may be frustrated that you can navigate into the area below, but you cannot get back up.  The screen below includes my path-finding debug code that draws a dark green 3x3 square for every visited node by the Dijkstra search and an orange pixel for every node visited by the recursive search.  If successful, the former will produce a bright green path-back, the latter will be red.



Notice that in the image on the left, Captain Disater cannot get to the cyan walkable area at the top of the screen.  You might assume that this is because he is a cosmic-blunder, but no, it's because when the Dijkstra search hit the narrow bend, it failed, and AGS resorted to the brute force method.  It did not traverse the narrow opening.  Confusingly, on the right hand side of the screen, you can make it through this narrow bend if you start from the top.  This is because the brute force method can gain a line-of-sight within the iteration limit.  Notice the red line.  At this point, you may conclude that Captain Disaster is not just "a little slow on the uptake," but rather stubborn.  But this might describe Zero-Bit a little more accurately than the good captain...  CD's not stubborn, he just doesn't have enough patience to continue looking for a way to return to the cyan corridor. 

A good method for repairing such a screen is to take it into the image editor and turn on a 3x3 grid.  Find the places where the grid cannot draw a stair-stepped line, and fill those squares like this (the image on the right is zoomed):



Now, even Captain Disaster is intelligent enough to navigate this path without resorting to the brute force method.



(Yes, it's surprising that he can do anything right. )

In conclusion, the following walkable area, counter-intuitively to "best practice," with it's 1 and 2 pixel wide corridors, is indeed navigable by AGS.  (all of us have likely tried a screen like this and never gave it a second thought, but here's why it works -- remember the red line is the brute force search) 





Reminding us that while no one would call the captain a genius, when the going gets tough he can prevail...  or get lucky!

[Radiant]

Very interesting! I'll have to try that!

[TheBitPriest]

I have not spent as much time pouring through this engine as many of you have.  For this reason, I hesitate to give more details and offer an opinion as a solution as if I'm an expert. And a caveat:  I have a bad habit of missing details.  But... I think I have, more or less, completely mined the depths of the path-finding system.   

There's much going on in the path-finding system.  I don't know if I'm the only one, but when I first peaked into this code, I thought, "Holy hand grenade!   What's going on in here!?"   But once you've sorted through everything, it's less complex than it first looks.  It's just years of performance tweaks, legacy code, and maybe even some WIP improvements.   It's just a project with a lot of history.  It was very kind of CJ to let us get into his code and see what's going on.  We are indebted to his herculean effort.  Considering all the amazing games that have been made with AGS, maybe trying to get this system right is overkill.  Even so, it might be less frustrating for the folks who have hit dead ends while trying to get maps to work. 

But I digress... 

AGS currently performs an efficient search (let's call it Search A) on a sparse grid (making it even more efficient) and when that search fails, it performs a second less efficient search (Search B) on a dense grid (see post above).   What I've learned is that neither solution works 100% of the time.

If the designer makes a walkable area that is does not neatly fit into a 3x3 grid, Search A will usually (but not always, see post above) fail to find a solution to the path.  If the designer's path is too complex, even if it is wide enough, Search A can also fail because either the resulting path is too long, or the number of moves needed by the character to complete the path is too large (it is currently set to 40).

At the moment, the engine will then revert to the “old method,” Search B, that uses a per-pixel granularity.  However, due to an optimization, this method can also fail to find a solution to the path.  It is legitimately broken in that even with an infinite amount of time and memory, if it is going to fail, it will fail.  When I replaced it with a true, yet suboptimal, per-pixel search, it worked for every possible walkable area, but that begs the question:  Why bother doing a second less optimal search at all? 

If we ever care to fix this, I would propose the following changes to the path-finding system :

• Replace Search A with a form of A Star
• Expose the grid size to the designer as a variable in the game settings.   If the game needs a 1x1 grid, then let the designer choose this.  Choosing 3x3, 5x5, 10x10 (or more) might be helpful for some of the more diminutive platforms.
• Consider ditching Search B altogether, or replace it with a per-pixel form of Search A.
• Consider adding a “grid paint” mode to the walkable mask painter in the editor.
• Consider adding the path tracing code as a debug option.

A lesser, yet easier, solution is to keep Search A as is, and just remove the 3x3 grid.  For all but redonkulously large rooms I believe that in 2013 we're going to be okay cycle-wise.  I would feel even more confident if we implemented #1 above.  But allowing the designer the option of tweaking the grid would be both efficient and flexible.  If we were to implent #4 in the editor, all problems would be solved tomorrow, but we would give up the occasionally needed (is it really needed?) per-pixel granularity.

For fun, after changing the engine to do a 1x1 search with Search A and increasing the limit on the number of movements available, I set up the following test room.   The little green square can successfully navigate this 1 pixel wide maze in AGS.  In case you're wondering, the red dot is the inner most point (the "solution").   

[Scarab]

Interesting read. When drawing the three pixel grid, does it have to be perfectly aligned with the room edges?


That is to say, if the image on the right were offset by one pixel in the x or y direction, how would that affect the algorithm?

[Snarky]

A lesser, yet easier, solution is to keep Search A as is, and just remove the 3x3 grid.  For all but redonkulously large rooms I believe that in 2013 we're going to be okay cycle-wise.

The pathfinding is already noticeably slow in the current implementation (if a character is walking and you click to change where they're going, e.g. to keep them moving forward in a scrolling room, they freeze for a moment as the game runs the pathfinding). If it were nine times as slow, I don't think it would be acceptable.

I haven't studied the game implementation or the A* algorithm, but the current performance is poor enough that I should think optimizations ought to be possible.

Really, walkable areas should be defined with polygons, not bit masks, and then the whole problem would pretty much go away.

[TheBitPriest]

A lesser, yet easier, solution is to keep Search A as is, and just remove the 3x3 grid.  For all but redonkulously large rooms I believe that in 2013 we're going to be okay cycle-wise.

The pathfinding is already noticeably slow in the current implementation (if a character is walking and you click to change where they're going, e.g. to keep them moving forward in a scrolling room, they freeze for a moment as the game runs the pathfinding). If it were nine times as slow, I don't think it would be acceptable.
away.

I haven't studied the game implementation or the A* algorithm, but the current performance is poor enough that I should think optimizations ought to be possible.

Nod.  That's what I meant by lesser but easier.  I didn't see a huge difference on my machine in the test rooms, but that's a poor test.  I'm sure that you could devise a room that would bring it to its knees. 

But remember, in the current design, we are sometimes doing two searches, and many other operations on the entire set in preparation for pathfinding, including a floodfill to test for walkability.  I think we can squeeze some cycles out of that.  I have tried a few things, but I have not had enough free time to really code anything too sophisticated.  I would like to keep working on this a bit though... at least it's less mysterious now.  I'll gather some better profiling information so that I'm not just taking big o guesses.

What about the idea of just exposing the granularity?  If it's too slow on your intended target, you can experiment with a larger grid (even 10x10 or 20x20).  I even thought, very briefly, about the idea of letting the user set the granularity for each walkable area, but my brain was hurting a little too much while thinking about the  combinations and bug possibilities.  Per room would be less risky.  Do you think either would be too much of a mess?  Combining this with a change to the painter in the editor should make it foolproof.  We could even experiment with automatically scaling down the mask (forcing it to the grid) on import, virtually keeping the artists' resource development pipeline intact. 

FWIW, there is code that tries to adjust the granularity based on the size of the walkable areas (I just glossed over this as an attempt at an optimization up above).  I'm pretty sure that this is what made the first tests at the beginning of this thread work.  However, after tracing through this part of the code, I'm fairly confident that this does not create enough of a difference on the final outcome to be worthwhile.  But since really getting into the system, I have not really investigated this part of the code by making some test cases.  Besides, there are hard-coded 3's that have to be changed in order to change the granularity by hand, bolstering my theory that this might not be useful at all (or it was just a WIP). Again, just guessing...  I might be missing a detail.

[TheBitPriest]

Interesting read. When drawing the three pixel grid, does it have to be perfectly aligned with the room edges?  That is to say, if the image on the right were offset by one pixel in the x or y direction, how would that affect the algorithm?

Originally, I thought, "no."  But turning on a grid in Photoshop worked so beautifully (the lines were visually on top of each other) that I did not double-check it for per-pixel accuracy.  One of the board members sent me a crop of broken masks.  With the debug code, I could see right where they failed and fix them in a matter of minutes by turning on the grid. I did not test any boundary conditions.  I'm just answering mail right now, but when I have some programming time again, I can give you a certain answer by changing the engine to always draw the grid on the screen. 

[MiteWiseacreLives!]

I nominate TheBitPriest for a Life Time Achievement Award.