# Need ideas for a pathfinding algorithm

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

## Recommended Posts

I need ideas for designing a pathfinding system. The game its for is about giding objects to specifik places and the resource needed for that is turns. So essentially the AI need to do as few turns as possible, the algorithm should also support free turns (these does not count against a players resources) and unstable free turns (these are prefered to regular turns but avoided in favor of no turns if possible or regular free turns). Actually finding the shortest path is less important (but useful) then finding a path with as few turns as possible. Also, it needs to be quick. As it might need to do these pathfinding checks a couple of hundred times in a second (although, between fifty and sixty times is much more common). There is a limit to the amount of turns a player can spend as well (typcially between 3 and 5), so that should help reducing processing time as well. The game is also tilebased. Thank you.

##### Share on other sites
It looks like you should look into A*.

##### Share on other sites
A* will always find the shortest path, so that's generally a good place to start.

What do you mean by "as few turns as possible". Do you mean as few rounds as possible or do you mean actually make the unit not turn left or right whenever possible?

-me

##### Share on other sites
Quote:
 Original post by PalidineA* will always find the shortest path, so that's generally a good place to start.What do you mean by "as few turns as possible". Do you mean as few rounds as possible or do you mean actually make the unit not turn left or right whenever possible?-me

The last one. The fewer turns needed, the more resources can be expended on other things. To clarify, free turns and unstable free turns are only done based on terrain.

##### Share on other sites
While I was thinking of doing an adaption of A*, mainly by adding a large movement cost for turning (To clarify, I mean turns as in changes of direction. The game itself is realtime) but I am unsure if that would not mean certain tiles will be blocked and closed when another possible travel path might need them, resulting in screwy paths or areas blocked off from certain starting points?

##### Share on other sites
Quote:
 Original post by PalidineA* will always find the shortest path, so that's generally a good place to start.
It is only guaranteed to find a (not the, as there can be several) shortest path if the heuristic function is underestimating (admissible). But yes, it's a good starting point.

1. 1
2. 2
3. 3
Rutin
15
4. 4
5. 5

• 13
• 26
• 10
• 11
• 9
• ### Forum Statistics

• Total Topics
633725
• Total Posts
3013567
×