simple path finding

I'm not sure if these games use them, but I have found that a lot of simple path finding work is done using the A* algorithm.

hi klee

thanks for getting back to me

I think monkey island must have a some sort of path finding if you click on an
object guybrush would make is way over to it.

I have taken a look at the A* algorithm but it doesn't seem appropriate.

Ideally I am looking to use the same method as monkey island.

thanks again

Ian

I recently had to implement something like that. What I did was manually creating nodegraphs (using a visual editor) and collision polygons, and whenever the character had to move somewhere, I dynamically added both the characters position and the destination to the nodegraph, using the collision polygons as blockers (e.g. they would only connect to any other node in the vicinity to which they had a clear line of sight). I then ran an A* algorithm on it, stored the resulting route, and removed the two temporary nodes from the nodegraph.

It worked well enough for our game, although setting up a good nodegraph can take some time. If you're working with a lot of levels, you may want to generate them instead.


I've also read about another approach, navigation meshes, but I've never tried that. It appears to be more scalable but also more difficult to implement. Maybe I'll give it a try in a future project. :)

For an adventure game where the scenes are fairly static and the navigation requirements are not very demanding, a node graph is probably the simplest approach. You basically set up a series of points (nodes) on the screen with lines connecting the nodes that are not blocked. Then you run A* between the nodes and there's your path. Just google pathfinding node graph for plenty of hits (unfortunately, you can't google for "A*" but "pathfinding" works just as well, I find).

Another thing you can do is augment the node graph with additional information. For example, you could store a "depth" value which describes how far away that node is from the "camera". This can then be used to scale the character up/down to give the illusion of depth.

Quote:

I have taken a look at the A* algorithm but it doesn't seem appropriate.

Why doesn't it seem appropriate? A* can be applied in a wide variety of contexts, and is more or less the go-to algorithm for pathfinding in games.