(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.

[Adeel]

I nominate TheBitPriest for a Life Time Achievement Award.

+1

E: And Crimson Wizard too.

[selmiak]

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

Why not add something like this to the editor?

[TheBitPriest]

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

To answer your question, I will post a few screens. 

First: A tool for everyone.  The following screen is the "grid."   You can use it to look at your backgrounds, play with pathfinding, etc. 



Second: Below is a test room with a 1 pixel path connecting two areas. 



Although I did not back out all of my changes to the iteration limits on Search B in order to confirm my theory, I believe that the engine, as is, will also navigate a similar 1-pixel path using AGS's original pathfinding algorithm.  It's just that you can make a map where Search B will always fail, because it's broken.  Plus, you really don't want to perform two searches every time the player moves in your game.  Search B is slower.

You can see the good ol' Captain walking right on the grid below (this is a later screen shot from when I starting testing the player's starting position).



Now, here's the caveat:  While testing this, there was one time when the grid did not match up.    I was surprised, but I almost starting writing a post saying that the search will start from the player's position, even though I could never get a different grid to draw, and even though I was 99% positive that I wasn't missing some variable, some constant, some anything anywhere, in the code.   However, I went back in and set the player's starting position as (0,0) then (1,0), (2,0), (3,0), (1,1), (1,2), and a few more, and the player followed the grid every time.  What did I see?   I have no idea.  I could not get it to happen twice.  Of course, I was not running it in C++ debugger at the time, so I could not break and watch the variables.    So...   "buyer beware"?    "Your mileage may vary."    I wish I could say something concrete...

Anyway, I'd do some more investigation, but I'm out of time for today.  It's off to "real (non-programmer) life."   

[TheBitPriest]

You (all) are too kind.  I really haven't done anything yet... Let's wait and see if I can make an actual contribution (like the programmers that have been around here for a long time), and see if I can make this a little better!  This is just one little piece of a project that has generated amazing games for over a decade, and I am enjoying sinking my teeth into it.  After a hiatus of just about as much time, getting back into game development is helping me keep my head clear! 

At the very least, path finding is a little more "documented" now. 

I would really like to play around with optimizing this code when I have a chance!

[Billbis]

Now, here's the caveat: While testing this, there was one time when the grid did not match up. [...] What did I see? I have no idea.

It may be related to the bug with straight line movements. By the way, have you look at it? I'm curious to understand what is wrong with the "old pathfinder".

[TheBitPriest]

It may be related to the bug with straight line movements. By the way, have you look at it? I'm curious to understand what is wrong with the "old pathfinder".

While I cannot give you an answer (yet) for the odd movement in the opposite direction (!), I can tell you a few things about this bug.

First, you are correct in assuming that the "old" path finding system is at fault (Search B in this thread).  It is broken.  As you observed in the source code, when you are moving along a straight line, AGS forces this search.  The comment says that it's for key presses (I have not investigated anything related to keyboard movement).  In the case that you set up, it returned a very unusual path.  The path finding system does not use any trigonometry.  The path following system does.  I did not look into any trigonometric issues, because the old method was moving so slowly on this large map that I stopped looking into the problem.  I think any solution to these bugs will involve a rewrite of the system, discarding Search B.

Abandoning Search B, I forced the engine to use Search A, and the expected behavior took place.   The player moved to the lower right hand corner of the screen.



In this partial screenshot, you can see Search A finding the proper path.  Now, I'm not sure if this is part of your bug, but just FYI, the "proper" path will be the lower left hand corner of the screen.  This might be counter-intuitive, but I think AGSers have been used to this behavior.   When you click outside of a walkable area, AGS looks for the closest walkable area to your chosen location by doing a distance calculation from every other pixel (3 pix granularity) in a 100x100 square around your chosen location.  If this fails, AGS searches the entire screen at a 5 pixel granularity, doing distance calculations.  These attempts are represented in the screen above as blue circles.  The large blue circle is the "found" location.  This is where AGS assumes you want to go, even though you have chosen a point much further away in a non-walkable area. 

Again FYI, the first movement in your test works correctly because the path finding system is not involved at all.  When you move around in a large area without any obstacles, AGS simply moves the character along a straight line. 

[EDIT:  Answer below]

Okay... the bug with Search B was "bugging" me, so I took one more look.   Here's the issue.  The problem is with your walkable area.  The bug in Search B causes it to "double back" when it hits a boundary.  In your case, it hit a "snag" (a pixel) and doubled back to the location on the right.  Then your original (AGS chosen blue circle) was within the line of sight, so the engine went there, back to the left.  If you smooth out this corner, the bug that you've reported goes away.  It's still there, but your new walkable area avoids it.  It's not intrinsic to straight lines movements.  It's just another side effect of the older, broken path finding code.

...at least this is my theory based on observation, not tracing the code.

[Billbis]

Many thanks for your answer, TheBitPriest.
I also support a discarding of "the old pathfinder", but we should explore how it react with Keyboard movement.
I'd totally missed the small "snag" at the corner of the walkable area. Nicely spot! This explain a lot, like why this bug was so hard to reproduce but still quite frequent.
By the way, I fill a bit childish to mention this, but this walkable area was not drawn by me but come from a game in development by an AGS user lurking in the french AGS forum. So the problem was his walkable area.

[subspark]

Polygons people, polygons. Lets not do away with the bitmap pathfinder but work in a very reliable alternative... P...P...Polygons!

[Khris]

I was thinking about this actually. And it's a great idea in principle.
There's a huge "but" though: what about moveable, solid stuff arbitrarily placed in a room?
Taking a chunk out of a painted area is simple, but how would one do this when the area consists of polygons? I mean it's possible, but dynamic splicing of arbitrary polygons...is implementing that really worth the trouble? Or am I missing something?

[Ryan Timothy B]

Taking a chunk out of a painted area is simple, but how would one do this when the area consists of polygons?

By adding the polygon (rectangular) area of object as a blocking area; likely by finding the path first, then looking to see if there's an obstacle. You shouldn't need to splice the walkable area polygons for this purpose whatsoever.

[Khris]

But it's about finding the shortest path, not just walking around obstacles; polygon pathfinding is very different from using A* and a grid. How would you do this if you add blocking polygons into the mix?

Here's a simple example:


Green is the original path, but if you add the red, blocking polygon, how is the algorithm supposed to recalculate the path unless you literally subtract the red one from the walkable ones, creating a different map in the process? I mean it looks obvious what the new path should be, but then I can also read most captchas. Teaching it to a computer is the hard part.
It's already not exactly trivial to teach it to find the green path.

Edit:
On the other hand, looking at that image again, subtracting one polygon from another looks pretty straightforward.

[TheBitPriest]

It looks like some good ideas are brewing! 

I put an implementation of A* in the engine last night.  It works.  It's not that much more efficient than the Dijkstra search (Search A), but I have not spent any time on optimizations.  It does visit fewer nodes... as it should... fwiw.   

I'm thinking of improving it by spacing the nodes like this:



Starting from the orange location and using the Euclidean distance from each center point as the heuristic, it would follow this this path to get to the yellow destination.   When the path is found, the character would follow the line from the parent's center to the location.  This allows pixel-perfect paths, created in the same raster-painting tool used for the backgrounds, but with fewer nodes to search.



But even as I write this, I'm thinking:  Wouldn't it be sufficient to just use waypoints?  I kind of like having pixel-perfect walkable masks, and the moment is not slow in general -- it's the path-finding.  We only really need to find a path through areas that cannot be traversed directly, and this is what the engine currently does.  We only go to path-finding when the destination is not within sight.    So, if we added waypoints with a line-of-sight check at each point, wouldn't this solve the problems?  I might be missing something here...



It would be so so easy to implement a proof of concept that the next time I'm in the engine's code I'll throw one together. 

(Although, I should have put that left vertex a little bit closer to the bend to keep the player for making strange turns or backtracking, but that's an adjustment left to the person dropping the vertices)

[TheBitPriest]

But, then, this looks amazing...

Polygon Example Video.

Is this guy on the forums?   

[Ryan Timothy B]

But, then, this looks amazing...
Polygon Example Video.

If AGS was like this, creating walkable areas, hotspots, regions, etc would be so beautifully easy and quick. Also would be nice if you could drag vertexes around or add/remove them.

EDIT:

But it's about finding the shortest path, not just walking around obstacles; polygon pathfinding is very different from using A* and a grid. How would you do this if you add blocking polygons into the mix?

AGS should have a STATIC property for objects and characters that never move. They should be added into the polygon grid for that room as an obstacle by splicing the walkable area (until it moves - which should unflag the static property, or if it's removed; which then recalculates the polygon grid).

Anything like a waiter who walks back and forth, it should find the shortest path first and ignoring the waiter, then once it finds the path have it check if the waiter is in the way, or will be in the way, and then branch the route around it (if not possible, check the second shortest path for any obstacles). You still need to check it constantly as it moves, splicing the polygon grid every frame (when something is moving) is a waste in my opinion.

EDIT AGAIN:
With this system, having a customizable baseline area would be quite handy and make for smoother looking navigation around things (eg: sphere, rectangle, oval).

[Khris]

I have started coding a little something, basic walkable area functionality is available.
There are some kinks to work out with how holes are added into the mix; I'll really try hard and not let this die

https://www.dropbox.com/s/jboub3uy0g886z4/PolyWalk.zip
(left click to set starting point, right click to toggle second walkable area, Esc to quit)

Spoiler

[close]

[Ryan Timothy B]

A question on how AGS handles walkable areas, if a character's BlockingWidth is set to 10, can it squeeze between walkable areas that are a width of 5? If yes, should it not be able to?

[Khris]

I'm pretty sure that solid areas only affect other characters.
It is assumed that walkable areas are drawn in a way that already incorporates the distance to walls; you don't floodfill the entire ground area but leave the edges blank near walls and trees, etc. It's the area where the character's pivot pixel is allowed to move, not the character itself.

[Ryan Timothy B]

It is assumed that walkable areas are drawn in a way that already incorporates the distance to walls; you don't floodfill the entire ground area but leave the edges blank near walls and trees, etc.

True, I hadn't thought of that. That's one reason why it sucks though, if you have a fat character and a skinny character, you need to adjust your walkable areas to suit the fat character otherwise you'll have clipping.

[TheBitPriest]

Nice progress! I have not gone back to this since last week.  Looks like a good start...

[TheBitPriest]

Anything new, Khris?  Was that demo in the engine, script, or other?  I was not able to download the link.

I was thinking... if you did code that in AGS, a module might be able to provide improve path-finding (although, not elegantly).  Anyway, just some random thoughts to bump this thread.  I hope to be able to get enough "hobby time" to get into some coding again soon. 

At the worst:  We now have AGS path-finding documented, and by using the grid above as a check, no one should ever have a broken or ridiculously inefficient walkable area again.

[Khris]

I tried the link, also when signed out of Dropbox, and it works fine for me. Here's a mirror: http://khris.agser.me/PolyWalk.zip

It's in module form for now. I didn't get to code the polygon arithmetics yet, maybe I'll have time later today. But I plan to finish this, maybe even add an editor (currently, you have to do lots of "PolyWalk.AddNode(134, 23);")

But yes, if I hit a wall or something, at least the pixel based pathfinding issues can now be worked around.