Sign in to follow this  
Temrek

Need ideas for a pathfinding algorithm

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 this post


Link to post
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 this post


Link to post
Share on other sites
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.

Share this post


Link to post
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 this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this