/*  AWM_PATH.PL  */


:- module awm_path;


:- public awm_path/5.



/*
SPECIFICATION
-------------


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.

The module defines one predicate, 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.
*/


/*
IMPLEMENTATION
--------------

We call into AWM_PATH.P.

This module has an associated HELP file, HELP AWM_PATH. Please keep
the two in step.
*/


:- prolog_language( pop11 ).
needs awm_path;
:- prolog_language( prolog ).


awm_path( AWM, Here, There, Safe, Path ) :-
    prolog_eval( awm_path_pl(AWM,Here,There,Safe), Path ).


:- prolog_language( pop11 ).


define awm_path( AWM, Here, There, Safe );
    define safe(
    awm_path( AWM, Here, There, Safe );
enddefine;


:- prolog_language( prolog ).


:- endmodule.