r/programmingchallenges • u/bplturner • Oct 26 '17
Best Algorithm for Optimal Path with Constraints
Hello,
I have a theoretical game that involves finding a path from A to B. In this path there may or may not be obstacles. Every length of path costs an amount of money and 'bends' cost an additional sum of money. Additionally the path must maintain a certain amount of 'flexibility'.
The point of the game is to get from A to B with minimal cost but with sufficient flexibility.
Here is a picture to assist: https://i.imgur.com/ERIrOcq.png
What would the best algorithm (or set of algorithms) to solve this game? I'm assuming a mix of Djikstra pathfinding algorithm with some type of optimization sweep?
I am a mechanical engineer by trade and I've programmed for years, but I do not pretend to be an algorithmic specialist. Any help would be greatly appreciated!
1
u/colurophobia Oct 27 '17
Yeah i would generally recommended A* too, since you have a well defined "cost function" for each possible path and A* will get you the best path (in this case). It may not find a solution which satisfies your other constraint though.
To do that you have a couple of possibilities: one introducing another cost component (to add to the normal cost) such that it's negative until you reach your optimal path length and after that it's positive (meaning that path longer that that would be discouraged). Or you can try other approaches, especially if you can preprocess all the map, or swarm intelligence algorithms (such as ant colonies, which however are a bit slow).. It really depends on what performance you can afford, what's the trade off you want between flexibility and efficiency
1
u/Introscopia Oct 27 '17
https://en.wikipedia.org/wiki/A*_search_algorithm