Backtracking in A star

Question

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?

Defecate

If I'm not mistaken, there is no backtracking in A*. Also, shouldn't that field be labelled 4, 3 instead? – Acedia

It is 3,3 , i didnt want to write the text over the cell. – Defecate

Added answer, btw I fgured out that the you use 4-neighbors and blue squares are walls but what are the green ones ? ... you should add this info to your question. The costs are really confusing are they representing energy or something similar? if just distance then they are wrong (see my answer) – Broth

Hi the costs would be from a star H cost(manhattan) and g cost a static 10 for my vase – Defecate

Answer 1

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.

Broth

Hello, yes its a 2d grid map, however i have a question, if the gCost is the same for all paths up,left,down,right,however the H cost is not, Do i still need to include it into the calculation? – Defecate

@Defecate what is gcost and Hcost? you can use any movement costing scheme not just incrementing for example you can adding bigger number for turning movements to adjust change of direction or whatever you need but the cost on next step must be always different then the previous one... – Broth

@Defecate so the gcost is yet unused space. you have to include ifs to 1. fill only empty space (not walls) 2. use only filled space while backtracking. I usually use negative or very big values for clear space and walls so the will not colide with the distances used while filling – Broth

can i use a boolean variable like isVisited instead of ints? – Defecate

@Defecate yes but in separate array, I prefer to have everything in single value – Broth

Answer 2

You can follow backpointers from the two nodes until you reach the common ancestor (0,2), then print the nodes you visited when following from (2,0), followed by the the nodes you visited when following from (3,3), printed in reverse.

To find the common ancestor of two nodes in an A* search tree, just maintain the two "current nodes", and follow the backpointer of whichever has the higher g-cost, until the two current nodes are in the same place.

It bears mentioning that this is a weird thing to do, though. A* is not a stack-based traversal, so it doesn't backtrack.

Pricket

Yes, im aware it does not backtrack , but im wondering how can it be modified to have backtracking – Defecate