Pathfinding Methodology in AGS and Other Adventure Games

[creatorlars]

Hello AGS Community -- This is my first post.

I'm creating a LucasArts/Sierra/AGS style adventure game engine in Adobe Flash, and it's almost finished.  I'm having a lot of fun with the project and am looking forward to posting a demo soon.  The reason I'm posting here is to see if anyone has information on how AGS, or older adventure games handled character pathfinding. 

I have just implemented a pathfinding method in my engine based on the A* algorithm, using movement nodes placed beforehand at the corners of big obstacles.  The algorithm detects line of site to the destination and if there is an obstruction, the shortest path to the destination point is calculated as an array of waypoints. 

This seems very clunky and inefficient, however, considering how simple most adventure games are in their pathfinding needs (you want to be able to click on the other side of a table and see the character walk around it -- not have a million enemies chasing you around a maze!).  It seems like there's got to be a simpler, more specialized solution for this type of game.  Any information or advice would be greatly appreciated! 

Cheers,
Lars Larsen

P.S.  If AGS had existed when was 12 years old, the path of my teenage years would have been drastically altered...!   This is such a great project.

[Pumaman]

AGS uses an algorithm that was originally based on Dijkstra and has been gradually twiddled and bastardised over time to improve performance, which has ended up with the method we know and love today.

[creatorlars]

Cool, thanks for the reply.  

From what I understand, A* and Djikstra are variants on a similar algorithm, so maybe I'm not so far off.  I completely understand that this engine is the result of TONS of hard work and that you may not want to divulge your methods or "trade secrets", but in the case that you don't mind, could you elaborate more on the general methodology behind your pathfinding routines?  I am genuinely curious, because the only real examples I can find apply only to tile-based games, and this is much different from a game where a character can occupy any pixel on the screen.  Are you using a line-of-sight type method?  Or do you treat each pixel on the screen as a tile in a grid?  Are you pre-calculating paths or movement nodes when the room loads or does it all happen at runtime? 

My method seems to work okay so far, but involves strategically placing waypoints beforehand, and could perform slowly on rooms with more than a  dozen nodes (which must be placed at the corners of obstacles).  It was very slow until I started precalculating line-of-sight between existing nodes when the room loads... but since the character's current position and target position are usually not _exactly_ at the X/Y of a movement node, it has to calculate those at runtime.  It should be fine in my application, but I know there is a better way....

I pulled up KQ6 the other day, and it SEEMED like there was a slight pause when I tried to complicate the pathfinding engine by putting a lot of obstacles between the player sprite and the destination... maybe I'm imagining things though.

Again, my utmost respect if you'd rather not talk about your methods.   I will probably be hanging out here a lot, and am really impressed by the quality of content and community.

[monkey0506]

The quality of the engine, the content created with it, and the community surrounding it are all the product of not just TONS of hard work, but YEARS of research and development, testing, refining, etc. and so forth. Next year AGS will be turning 10 years old!

As for the pathfinding methods used by AGS, I'm sure that if you could come up with a six pack of beers and a large order of onion rings that you and Chris could work out a deal...

[creatorlars]

I'm sad to have missed out on the past 10 years.   Definitely something special here, I've been playing through a lot of the games. 

I have a fondness for beer and onion rings too, and should you ever venture near Denton, TX -- definitely glad to provide.

[Khris]

I think it's save for me to divulge that AGS uses a grid of 3x3 squares, improving the performance to 900% compared to a single pixel grid.
That's why walkable areas (and non-walkable areas) have to be at least three pixels wide.
(At least this is what I believe is being done, mind you.)

[creatorlars]

Ahhhh.... that makes sense.  I guess when the room loads or the game is compiled, the grid is assembled with each tile being "walkable" or not, and pathing looks in 8 directions from the currently occupied square?  That would probably run a lot better than my line-of-sight method which seems to require too much calculating at runtime (and of course avoid having to place nodes manually.)

[Pumaman]

Yeah there's no particular "trade secret" involved, but basically AGS tries to get better performance by optimising the granularity of the grid depending on the shape and size of the walkable areas. But yes, effectively it treats the screen like a 320x200-tile grid.

[creatorlars]

That's definitely enough to satisfy my curiosity.  Thanks for humoring me.