I am currently trying to use A* to create cyclical routes (for plotting driving routes of set distances). I want to find a driving route from my start location that is as close to my specified length as possible. If it is bigger or smaller that is fine, just as close as possible
I have therefore adapted the heuristic function to:
|target distance-distance Travelled so far| + distance left to travel.
for example, I want to travel 20 miles, so my target distance is 20. At some point in the route i may have travelled 18. Therefore my h would be 20-18+2 = 2. I always pick the smallest h value, the idea being a route of 20 miles will be created finished where i starts.
I had 2 immediate issues with this.
- The Start node can't be added to the closed list immediately or it will never create a cyclical route - I believe I have solved this one.
- If the search goes into a cul-de-sac it gets stuck and the openlist becomes empty and the search terminates.
The second problem I cannot think of how to solve. It occurs because the successor node that would get the search out of the cul-de-sac is already in the closed list.
Can anyone help me come up with a general solution to my problem? Furthermore do you for see any other issues with my implementation?
would really appreciate any help you can give.