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.

It looks like you should look into A*.

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

Quote: Original post by Palidine
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

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.

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?

Quote: Original post by Palidine
A* 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.