Backtracking in A star
Blue-Walls
Green highlighted cells = open list
Red Highlighted cells = closed list
Hello, can anyone tell me how can i implement backtracking in a a star search algorithm? I've implemented the a star search according to wiki, but it does not backtrack, what i mean by backtrack is that the open list(green cells) contains 2,0 and 3,3 as shown in the picture, upon reaching 2,0 the current node would "jump" to 3,3 since the cost is now more than 3,3 and continue the search from there, how can it be done so that it would backtrack from 2,0->2,1->2,2... all the way back to 3,3 and start the search from there?
your image is like 2d grid map
But your text suggest graph approach which is a bit confusing.
- For 2D grid map the costs must be different between cells on path
You got too much of cost=100 in there and therefore you can not backtrack the path. You have to increase or decrease cost on each step and fill only cells that are near last filled cells. That can be done by recursion on big maps or by scanning whole map or bounding box for last filled number on small maps.
- Look here for mine C++ A* implementation
The backtracking
Can be done by scanning neighbors of start/end cells after A* filling moving always to the smallest/biggest cost
In this example start filling from (2,0) until (3,3) is hit and then backtrack from (3,2) cost=8 to the smallest cost (always cost-1 for incremental filling). If you need the path in reverse order then start filling from (3,3) instead ...
speedup
Sometimes double filling speed up the process so: Start filling from both ends and stop when they join. To recognize which cell is filled from which point you can use positive and negative values, or some big enough ranges for costs.