# How to display each step of an A star algorithm?

I wrote a pathfinding program: A*, which is an extension of Dijkstra. I want to see the result of each step at a time. Which function should I use? The main program is the notebook Astar, which is implemented based on a data structure called priority queue. The package PriorityQueue.m is put in location F:\ by default. For example, here are some results of a whole run.

• You probably want to use some of the Dynamics constructs. Check the help for Dynamic and DynamicModule for a start – Dr. belisarius Dec 27 '13 at 5:44
• @belisarius Thanks for your rapid response, I'm still wondering why Manipulate and Animate failed. I haven't tried Dynamic. Is it used like this DynamicModule[{b=0.1}, {Slider[Dynamic[b]], Dynamic[Plot[Sin[x], {x, 0, 10*b}]]}] – novice Dec 27 '13 at 5:54
• What is t in your Manipulate? you have {t, 1, 10, 1} and you are not using it anywhere? – Nasser Dec 27 '13 at 6:30
• @Nasser, "t" is used to control the steps. Initially I thought Manipulate act like For loop with controled steps. – novice Dec 27 '13 at 6:42
• You can't have a control variable that is not being referenced in the Manipulate expression or appears there. It does not work like that. There should be a dependency in the expression for it to work. – Nasser Dec 27 '13 at 6:44

Is this what you want?

Clear["Global*"];
SetDirectory[NotebookDirectory[]];
Needs["PriorityQueue"]
(* new cell *)

Manipulate[
tick;
If[! PriorityQueueEmptyQueue[open],
cnode = PriorityQueueTopQueue[open];
cnodeID = cnode[[1]];
cnodec = nodeC[[(Flatten[Position[nodeC, cnodeID]][[1]])]][[2]];
dis = EuclideanDistance[cnodec, goal];
If[dis > 0.2,
enodes = Flatten[{findNeighbor[map, cnodeID]}];
For[i = 1, i <= Length[enodes], i++,
enodec = nodeC[[(Flatten[Position[nodeC, enodes[[i]]]][[1]])]][[2]];
dis = EuclideanDistance[enodec, goal];
If[! PriorityQueueContain[closed, enodes[[i]]] && !
PriorityQueueContain[open, enodes[[i]]],
g = PriorityQueueFindItem[open, cnodeID][[3]] + 0.2;
h = dis;
f = h + g;
If[PriorityQueueContain[open, enodes[[i]]],
If[PriorityQueueFindItem[open, enodes][[5]] > f
, PriorityQueueChange[open, enodes[[i]], {enodes[[i]], cnodeID, g, h, f}]],
PriorityQueueEnQueue[open, {enodes[[i]], cnodeID, g, h, f}];
]
]
];
];
PriorityQueueEnQueue[closed, cnode];
PriorityQueueRemoveQueue[open, cnodeID];
];

GraphPlot[map,
EdgeRenderingFunction -> ({Black, Thickness[0.001], Line[#1]} &),
VertexCoordinateRules -> nodeC,
VertexRenderingFunction -> (If[#2 == goalID, {Green,
EdgeForm[Black], Disk[#1, 0.1]},
If[Contain[open, #2], {Red, EdgeForm[Black], Disk[#1, 0.1]},
If[Contain[closed, #2], {Yellow, EdgeForm[Black],
Disk[#1, 0.1]}, {Blue, PointSize[Small], Point[#1]}]]] &)
],

Grid[{{Button[Text[Style["step", 12]], tick += del,ImageSize -> {80, 35}]}}],
{{tick, 0}, None},
{{del, \$MachineEpsilon}, None},
TrackedSymbols :> {tick},

Initialization :>
(
findNeighbor[graph_, node_] := DeleteCases[VertexList[
NeighborhoodGraph[graph, node]], node];
map = GridGraph[{10, 10}];
coord = (AbsoluteOptions[map, VertexCoordinates])[[1]][[2]];
nodeC =Table[Apply[(#1 -> #2) &, {i, coord[[i]]}], {i, 1, Length[coord]}];
startID = 1;
goalID = 80;
start = nodeC[[(Flatten[Position[nodeC, startID]][[1]])]][[2]] + 0.1;
goal = nodeC[[(Flatten[Position[nodeC, goalID]][[1]])]][[2]] + 0.1;
open = PriorityQueueMakeQueue[];
closed = PriorityQueueMakeQueue[];
dis = fstart = hstart = EuclideanDistance[start, goal];
PriorityQueueEnQueue[open, {startID, startID, 0, hstart, fstart}];
)
]

• Yes exactly. Better if the content in the open and closed lists are shown together. – novice Dec 27 '13 at 6:46
• @novice, making things global for no reason is not a good way to do things, that is why I put data used by Manipulate in its Initialization section. If you make an official demo using demo style sheet, you have to do it this way. But feel free to change it as you like. – Nasser Dec 27 '13 at 6:49
• Would make for a nice Demonstration, if one or both of you care to submit it. – Daniel Lichtblau Dec 28 '13 at 16:18
• @Daniel Lichtblau,I add 2 more examples. I'm willing to submit it. Where should I submit it to? – novice Dec 30 '13 at 5:44
• @novice You can submit it here demonstrations.wolfram.com/participate.html but notice that the process is not just sending a notebook. It is more involved than this. The demo has to be in demo style sheet and has to follow many guidelines. All are explained above. In addition, you can't load an external package in a demo (since this package will not exist when CDF is deployed), so you would have to include all the code of the package priority queue into your demonstration. – Nasser Dec 30 '13 at 6:29