Sign in to follow this  
ianmclean0001

simple path finding

Recommended Posts

Hi there I am hope I am posting the the right place. I am curious to know how games like monkey island, full throttle and machinarium handle the character path finding. Is there some like of way point that are using to determine the best path the character can move to. Hope you can help thanks Ian :)

Share this post


Link to post
Share on other sites
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

Share this post


Link to post
Share on other sites
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. :)

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this