(* Program to find path through maze *)
(* Data structure is a graph - represent this by a list of connections
[(11,1),(11,2), ... (11,0)]
*)
val hamptoncourt = [(0,2),(0,3),(3,4),(3,5),(5,6),(5,7),(7,8),
(7,9),(8,9),(8,10)]
(* Walking is carried out by holding the nodes to visit in a queue
each step takes the first item from the queue and puts the
resulting nodes we can visit on to the end
To do this we need to define
stepone - given the graph and current node returns all the nodes that
are directly linked
*)
fun stepone (_, []) = []
| stepone (node, (node1,node2)::othernodes) =
if node = node1
then
node2::stepone(node,othernodes)
else if node = node2
then
node1::stepone(node,othernodes)
else
stepone(node,othernodes);
(* We need to avoid doing two things
- going round in circles
- repeatedly going forward and back along the same path
to do this we pass forward a list of nodes we have already visited
and terminate the search on this path if we are at on of those nodes
*)
fun member (_, []) = false
| member (node, this::others) = node = this orelse member(node,others);
fun enqueue ([], path) = []
| enqueue (hd::tl, path) = (hd, path)::enqueue(tl, path);
(* Now the code to walk the maze
the outer function is to wrap up our starting position
and create the queue with the node we start at in and no history
The inner function MazeInt then picks each item off the queue
if we have reached the goal we retrun the path (backwards)
if not then we discard paths which bring us to a ndoe we have
visited before, otherwise we explore any new places we can reach
*)
(* The exception is just in case we are given a duff graph that
cannot be walked *)
exception trapped;
fun Maze (start,goal,maze) =
let
fun MazeInt ([], _) = raise trapped
| MazeInt ((first,path)::queue, maze) =
if first = goal
then
first::path
else
if member(first,path)
then
MazeInt(queue, maze)
else
MazeInt(queue @ enqueue(stepone(first,maze),first::path), maze)
in
MazeInt([(start,[])], maze)
end;
(* To extend this to deal with actual path lengths all we need modify
is the queue mangement function - @ - with something more sophisticated
*)