Let me say what kind of game I am making before people start throwing out suggestions. I am making a single screen point and click adventure game like the old sierra games. The character moves to the point on the screen at which the player clicks. I was using a *, but I cannot get it to work correctly for my game. And, I just think that there is a better way of doing things. I was thinking of my own idea for pathfinding. This would be similiar to a*. What I would do is I would set a bunch of "way-points", which for the most part are the areas at where the character can walk. So I would set these all along the paths and such. Then, the game would figure out which order of waypoints he has to walk to to reach the goal. I don''t have a clue how to code this though. ANY suggestions on how to do pathfinding in my game would be MUCH APPRECIATED! Thank you very much, Muzlack Oofmay Sponge Factory --Muzlack

Use A* using the WayPoints as the nodes in the tree. The characters current WayPoint would be the root node, and the next level of the tree is any waypoint connected to the one the character is at. So, each WayPoint should keep track (have a list) of waypoints it is connected to.
If you''re having troube with A* you could use a simpler algorithm such as breadth first, which will work fine as long as you don''t have too many waypoints.

At the risk of getting flamed again, here''s my little article on nodal pathfinding:

http://www.geocities.com/bpj1138/shortest_path.html

You can also find a nodal path editor application on my site (Java), if you so desire.

--bart

quote: Original post by Anonymous Poster
If you''re having troube with A* you could use a simpler algorithm such as breadth first, which will work fine as long as you don''t have too many waypoints.

True, but you could speed it up by using some kind of Least Cost Search insted (Test the best direction first). This will work as the playfield is so small.


// Javelin
-- Why do something today when you can do it tomorrow... --

For a 2D adventure engine such as yours, I used this method

Path Finding In Complex Maps And The Black Art Of Linear Algebra

It''s simple, it''s accurate, and it''s blazingly fast.

2D when? 2D!Now

any ideas why this works? quite interesting though..

quote: Original post by llyod
For a 2D adventure engine such as yours, I used this method

Path Finding In Complex Maps And The Black Art Of Linear Algebra

It's simple, it's accurate, and it's blazingly fast.

Heh, that sounds very similar to the stuff I once wrote here.

It also has O(k) speed where k is the length of the shortest path from beginning to end.

But my algo was meant for tile-based maps with complex shapes. For simple scenes, it'd eat way too much memory.


[edited by - Hans on April 20, 2002 1:59:20 PM]

quote: Original post by Hans
Heh, that sounds very similar to the stuff I once wrote here.

Hans, did you realise that your method was the same as the Distance Transform Method, which was first published by Jarvis in 1985?

... and to answer bpj1138's question... the method referenced by lloyd is based on the policy iteration algorithm and is just a linear algebra implementation of that algorithm for simple domains.

Cheers,

Timkin

[edited by - Timkin on April 20, 2002 8:18:40 PM]

quote: Original post by Timkin
Hans, did you realise that your method was the same as the Distance Transform Method, which was first published by Jarvis in 1985?

Huh? I had no idea.. Gotta search for that and see how different/similar it is

Here''s my bib reference to the paper...

@article{Jarvis85,	author = "Jarvis, R. A.",	title = "Collision-free trajectory planning using the distance transforms",	journal = "Mechanical Engineering Transactions of the Institute of Engineers",	year = 1985,	volume = ME10,	number = 3,} 

You might find a copy at www.citeseer.com

Cheers,

Timkin