Walkable areas

[Hellomoto]

Last year I started writing my own adventure game engine, mostly it worked, however, on creating walkable ares, the whole thing needed to be reprogrammed to incorporate the new areas. I was just wondereing how the script in AGS determines the route which a character takes to get to a different point on the screen. I can understand what happens,  just never figured out how it happens. Could some one help please. I would be very grateful.



Sorry about the English

[BorisZ]

In my expirience, character allways takes the shortest possible route.

[Radiant]

It's slightly complex. If you create an S-shaped path and have the character in the lower left and the destination in the upper right, then sometimes the character walks along the S, and sometimes it just walks straight into the direction of its destination, until it hits the end of the walkable area.
I believe a pathfinding algorithm is used, that times out after a while, after which time the best idea found so far is used.

[Dusk]

I hope this can help you:

http://www.thecodeproject.com/csharp/graphs_astar.asp

bye
D.

[Hellomoto]

Thank you very much for that link. I have not yet had time to implement the code, however it seems very interesting. Is this the same or similar idea as is used for AGS?

[Janik]

Pathfinding is a major artificial intelligence issue in lots of games (I'm sure there's tons of stuff out there, in gamasutra for example). In  real-time strategy games many units move around a large map at the same time, so performance is important. In an adventure game it's only one character at a time, so it's less critical. Still, I've tried drawing labyrinth-like designs in AGS and the character navigates them perfectly, as long as they are more than 3-4 pixels wide.

[TerranRich]

You mean, like a maze? So AGS douobles as a maze-solver then, huh? One more use to add to the list of many.

[Khris]

In my expirience, character allways takes the shortest possible route.

I hope you're kidding...


I googled for "pathfinding algorith", and ended up with loads of cool links.

[Pumaman]

The AGS pathfinding algorithm was loosely based on the djikstra algorithm, but has undergone several refinements and re-writings, and it's still by no means perfect.

What it basically does is shrinks the screen by a factor of 3 so that there are less pixels to check (this is why walkable areas need to be a few pixels wide), and then tries various routes to get to the destination. After a while if it hasn't got there, it gives up and moves as far as it can (because the game can't really sit there for too long calculating a move).