HELP AWM_PATH Jocelyn Ireson-Paine October 1992
This module finds a path within an awm, using hill-climbing search. An
``awm'' is an ``array world-model'', for letting a bug represent a map
of its world. For a description of AWMs and the operations on them, see
HELP AWM. To load this module, do
lib awm_path;
The module defines one routine, awm_path:
PUBLIC awm_path( awm, start, goal, safe ):
Searches for a path from start to goal within awm. The procedure safe
determines which points can be traversed and which are treated as
obstacles. The path is returned as a list of points whose first element
is start and whose final element is goal. Each point is represented as a
two-element list [%x,%y]. If there is no path, the procedure returns
false.
safe must be a procedure of three arguments, safe(awm,x,y) returning
true or false. It returns true if awm(x,y) is passable, and false if
it is an obstacle. You will usually want to define it as
define safe(awm,x,y);
lvars awm, x, y;
awm(x,y) = ` `
enddefine;
Because the search method will not always be the most suitable, I
describe it below. It works as follows:
0) Initialise a queue of points to [% start %].
1) Take the first element off the queue. If there is none,
the search has failed: return false. Otherwise, this is
the next point to be explored.
2) If this point is the goal, return true.
3) Find all the safe horizontal and vertical neighbours of this
point, eliminating any which have already been explored. Add the
others to the front of the queue, before all the points already
there. We do this so that the points added are sorted by
distance to goal: the nearer a point is to goal, the nearer it
is to the front of the queue.
4) Go back to 1.
If you are unfamiliar with search, you will find it helpful to read
TEACH SEARCHING for an introduction, and then HELP SEARCH to see how I
implement and use it.