Jump to content
  • Advertisement
Sign in to follow this  

Smart Path Finding - Tile Based World

This topic is 2948 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

Hey all, just doing some research - links would be appreciated to anything that might be useful.

The gist: RTS-style path finding, units can overlap when moving but cannot overlap when stopped, thus A* works very well since the only obstacles are walls. The problem however comes into play when a unit decides to stop:
-If the tile is empty, stop ok.
-Else find nearest empty tile.

Anyone know of a good algorithm / theory for finding the nearest tile of the intended destination. Ie. Player clicks a spot, all units move as closer as possible to that spot.

My current algorithm is too resource heavy and too stupid. Every time a unit needs an empty cell it recalculates a modified astar (open list) to find the nearest empty tile of the intended destination. If 50 units are calculating this every five seconds, there is a lot of repetitiveness in the algorithm. Also, I tend to see units pathing to the same tile and then following each other to other nearby tiles. Pretty stupid behavior, thus need a better algorithm :P

I am also open to formation / leader algorithms. They seem more up my alley, but I don't think they would apply to the game in question. Units are too spread out to make a single path finding unit (for a clump of units) the best approach.

I was thinking of something like an "Director" function that creates the desired path for a subset of units and 'directs' them how to follow the path and where to go when they wish to stop. Anyone know if a theory exists around this?

Thanks in advance for any advice

Share this post

Link to post
Share on other sites
Have them reserve tiles. As you iterate through each unit, they can only look at the tiles that haven't been reserved. When they find the nearest one, they reserve it first and then move there.

By the way, this can be done prior to arrival so that they don't go to the single place and then spread out.

Share this post

Link to post
Share on other sites
Sign in to follow this  

  • Advertisement

Important Information

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

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!