(solved) Pathfinding granularity

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