Jump to content
  • Advertisement

Archived

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

BeanDog

simple pathfinding

This topic is 6899 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I''ve got an array of about 256x256, which stores, among other things, an array of bool''s that say whether or not my unit can move there. How can I make a very good pathfinder from any one spot to any other? ~BenDilts( NULL* AIexperience); Bean Dog

Share this post


Link to post
Share on other sites
Advertisement
You''ll want to look into the algorithm called A* (pronounced ''a star''). It is a farly simple yet powerful pathfinding algorithms. There are better algorithms but they are usually modifications to A*, and they are only needed for very long paths.

You can find a lot of info on A* at Amit''s Game Programming Information.

- WitchLord

Share this post


Link to post
Share on other sites
thanks for the tip.

a* seems way overkill for what I''m doing, though. I am doing a real time strategy game (very early in development). I just got my creatures to move correctly, but (go figure) they don''t go around stuff by themselves. So I was thinking, I could do a really simple algorithm, since my units can either go onto a space or not, and I store my terrain-blocked map squares separate from my unit-blocked ones. I could just do a search straight from the unit to the destination. If the search path hits some terrain, it SPLITS into two other searches going on simultaneously, one going left and one going right, and so on. If two paths ever cross, or a path hits where another has already gone, they will be eliminated. This will repeat until either the destination is reached by one path or all are dead-ended.

This may sound complicated, but it may be easier than it appears. This will only be done once per time that the unit is directed to a new destination, so it won''t slow down the game significantly. I''ll do a one-step-at-a-time procedure if it runs into another unit or building.

Any comments or suggestions?

~BenDilts( void );

Share this post


Link to post
Share on other sites
I know a MUCH BETTER algorithm then A* one....

but cant tell you much because its secret...as it will be incorporated in may new release of a RTS...

All i can tell is that is a better algorithm...(but not faster than yours...
yours above is the fastest...but also has some problems in a labirnth

I may be able to speak after game release...

Share this post


Link to post
Share on other sites
Well, thanks a TON for the info, retard. I was all excited that I got a message, and it was just you bragging your cajones off. Get a life.

Share this post


Link to post
Share on other sites
BeanDog, your search algorithm will work. I believe it is called either depth-first search or breadth-first search depending on how you implement it. I think you should go with that so that you can get on with your game, but later on I would recommend A* as I believe it is the best for what you are doing. And no it is not overkill, it can bring down the pathfinding processing time to perhaps 10% (educated guess) maybe even less. And that in turn allows your game to build intelligent paths for goals at farther distances.

- WitchLord

Edited by - WitchLord on May 19, 2000 8:11:47 PM

Share this post


Link to post
Share on other sites
OK, I''ve got a basic pathfinder working, but it is so SLOW! How am I going to get the more-complex a* to work if a simple approach works so slowly? How would I choose where the waypoints would be? I couldn''t use every block in a 128x128 grid!

Share this post


Link to post
Share on other sites
quote:
Original post by BeanDog

OK, I''ve got a basic pathfinder working, but it is so SLOW! How am I going to get the more-complex a* to work if a simple approach works so slowly? How would I choose where the waypoints would be? I couldn''t use every block in a 128x128 grid!


A* is a more complex algorithm but the complexity helps it be more efficient. As another example, bubble-sort is a ''simple'' algorithm but quicksort will beat it nearly every time. What you save on code, you lose on processing time, mainly.

Share this post


Link to post
Share on other sites
Perhaps I should define "slowly". I direct 50 units 100 squares accurately in about .5 seconds. That is still too slow for a real-time game.

Share this post


Link to post
Share on other sites
I think you should try to implement A* and see just how much faster it is.

Another way to speed up the pathfinding might be to divide you map into small areas that contain for example 8x8 squares, then you first use the pathfinding algorithm to find the way among these. After that you use the pathfinding on the squares in each of the areas to get the exact path.

- WitchLord

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!