Archived

This topic is now archived and is closed to further replies.

Biberpelztrompete

Pathfinding algos

Recommended Posts

Hi, does anybody know a good URL or sth. where I can USEFUL information about some pathfinding algorhythms ? For example BPS or DPS. The code would be enough cause my units just stop when they cannot move on. Thanx

Share this post


Link to post
Share on other sites
quote:
Original post by Biberpelztrompete
Hi,
does anybody know a good URL or sth. where I can USEFUL information about some pathfinding algorhythms ?
For example BPS or DPS. The code would be enough cause my units just stop when they cannot move on.
Thanx


You might visit Amit Patel''s page:

http://www-cs-students.stanford.edu/~amitp/gameprog.html

Good luck,

Eric

Share this post


Link to post
Share on other sites
Umm, good luck, hehe. I really need that because the site is extremly big and I found only some links. They are quite useful, but I couldn''t find a tut or a proggie that DOES pathfinding.
Maybe pathfindig is the wrong word, because I need sth. that make units more intelligent, so they move around each other.

Share this post


Link to post
Share on other sites
quote:
Original post by Biberpelztrompete
Umm, good luck, hehe. I really need that because the site is extremly big and I found only some links. They are quite useful, but I couldn't find a tut or a proggie that DOES pathfinding.
Maybe pathfindig is the wrong word, because I need sth. that make units more intelligent, so they move around each other.


With all due respect, maybe you should go back to Amit's page and look a little closer?

There are tutorials on A* (the premier pathfinding algorithm), sample code in several
computer languages (all of them "DOES [do] pathfinding"), as well as papers that go
into other techniques. This is not something that is trivial. Its going to take some
work on your part to learn how to use it.

What is "sth"?

Eric


Edited by - Geta on June 29, 2001 9:20:31 AM

Share this post


Link to post
Share on other sites
Hmm,
maybe I explained it wrong. First the A* is too complex for my game. The "simple trace"-algo would be quite enough.But the MAIN problem is that one :
I have a unit at (x,y) and one at (x+5,y). They will crash in the next frame. To avoid that crash i stop them. But they should be able to go around the other unit. So i don''t have a map structure and stuff but only the coordinates and dimensions of the objects.
But anyway a huge thanx to Geta ...

Share this post


Link to post
Share on other sites
Guest Anonymous Poster
What you are looking for is collision detection. If you add collision detection to your pathfiding it will solve that problem. You need to have the pathfinding algorithm look for other units as well as landscape objects.

One simple way of handling the 2 units moving into 1 space is to have a minimum distance that they must maintain from other units. You could have this also be related to the speed of the unit.

Share this post


Link to post
Share on other sites
Yeah I know,
I have collision detection, but when 2 units collision they just stop and don''t move around each other. thats my prob. maybe you''re right but isn''t there an easier way ?? converting them into landscape doesn''t seem to be the perfect solution. But I hope it works.

Share this post


Link to post
Share on other sites
quote:
Original post by Biberpelztrompete
Hmm,
maybe I explained it wrong. First the A* is too complex for my game. The "simple trace"-algo would be quite enough.But the MAIN problem is that one :
I have a unit at (x,y) and one at (x+5,y). They will crash in the next frame. To avoid that crash i stop them. But they should be able to go around the other unit. So i don''t have a map structure and stuff but only the coordinates and dimensions of the objects.
But anyway a huge thanx to Geta ...


You may get the behavior you are looking for by implementing Steering Behaviors:

http://www.red3d.com/cwr/steer/

Since you don''t actually have a grid (?) or map structure and your objects are running
around in abstract space, an adaptation of steering behaviors (look at avoidance) can
work with just locations and dimensions of objects.

There is no code on this, but the algorithms are very well explained and fairly easy to
implement if you have any 2D or 3D vector math background.

Good luck,

Eric

Share this post


Link to post
Share on other sites