MindGuerrillas

In the previous example the first move the search made was to look south-east to node 'j'. This was OK since, luckily, the best path involved going around the bottom of the obstacle and so we were always going in the right direction. What though if there were no way around the obstacle in that direction? What if node 'o' was blocked off too?

Well A* handles that too without the need to change anything. In this example A* will start off looking in the same direction it did in the first example. This time though it will find it's path blocked at the bottom of the grid and will backtrack to find an alternative route.

The steps taken are shown below. As before, the table shown represents the Open list.

Step 1

As always, the starting node is selected, added to the Closed list, and it's successors are added to the Open List.

NODE	G	N	F	parent
a	1	5	6	e
b	1	4	5	e
f	1	3	4	e
i	1	3	4	e
j	1	2	3	e

Step 2

As in the first example, 'j' has the lowest score (3) and so is chosen and added to the Closed list. Nodes 'm' and 'n' are added to the Open list.

NODE	G	N	F	parent
a	1	5	6	e
b	1	4	5	e
f	1	3	4	e
i	1	3	4	e
m	2	4	6	j
n	2	3	5	j

Step 3

Unlike the first example, we can no longer continue moving directly towards the target as our path is now blocked by 'o'. We must backtrack and look again for the best next step. Nodes 'f' and 'i' both scored 4 but 'i' is chosen next on a LIFO basis. At this stage no new nodes are added to the Open list as they are all already on either the Open or Closed lists.

NODE	G	N	F	parent
a	1	5	6	e
b	1	4	5	e
f	1	3	4	e
m	2	4	6	j
n	2	3	5	j

Step 4

Node 'f' is next with a score of 4. It's new successor 'c' is added to the Open list.

NODE	G	N	F	parent
a	1	5	6	e
b	1	4	5	e
m	2	4	6	j
n	2	3	5	j
c	2	3	5	f

Step 5

Nodes 'b', 'n' and 'c' all score 5. LIFO says that the tie should be split by choosing 'c'. It's successors, 'd' and 'h' are added to the Open list.

NODE	G	N	F	parent
a	1	5	6	e
b	1	4	5	e
m	2	4	6	j
n	2	3	5	j
d	3	2	5	c
h	3	1	4	c

Step 6

The lowest cost node is now 'h'. It's added to the Closed list and it's successor 'l' is added to the Open list.

NODE	G	N	F	parent
a	1	5	6	e
b	1	4	5	e
m	2	4	6	j
n	2	3	5	j
d	3	2	5	c
l	4	0	4	h

NODE	G	N	F	parent
e	0	4	4	--
j	1	2	3	e
i	1	3	4	e
f	1	3	4	e
c	2	3	5	f
h	3	1	4	c
l	4	0	4	h

The target node 'l' is now on the Open list and is also the next chosen node due to it's score of 4. This ends the search with a successful result. The closed table at this stage looks like this.

To get the path to the target we look at the Closed list. Starting at the target node 'l' we look at it's parent 'h' and so on until we reach the starting node 'e'.

In this case the final result is:  e > f > c > h > l