# 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.

## 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?

##### 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.

1. 1
Rutin
40
2. 2
3. 3
4. 4
5. 5

• 18
• 20
• 12
• 14
• 9
• ### Forum Statistics

• Total Topics
633363
• Total Posts
3011511
• ### Who's Online (See full list)

There are no registered users currently online

×