/*  AWM_PATH.P  */


section awm_path => awm_path;


/*
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 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.
*/


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

We use path_search from SEARCH.P, supplying an insert procedure that
implements hill-climbing, using distance towards the goal as its
evaluation function.

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


needs utils;
needs vec;
needs awm;
needs search;


define global awm_path( awm, start, goal, safe );
    lvars awm, start, goal, safe;

    define next_from( point );
        lvars point;
        lvars x0=point.vec_x, y0=point.vec_y;
        [%
            awm_app_vh_neighbours( awm, x0, y0,
                                   procedure(awm,x,y);
                                       lvars awm, x, y;
                                       if safe(awm,x,y) then [% x, y %] endif;
                                   endprocedure
                                 )
        %]
    enddefine;

    define insert( newpoint, path, q );
        lvars newpoint, q, path;
        lvars d, first, rest, f, first_path;

        define dist( p1, p2 );
            lvars p1, p2;
            distance( p1.vec_x, p1.vec_y, p2.vec_x, p2.vec_y );
        enddefine;

        dist( goal, newpoint ) -> d;

        if q /= [] then
            dest(q) -> rest -> f;
            f(1) -> first;
            f(2) -> first_path;
            if d <= dist( goal, first ) then
                [ [^newpoint ^path] ^^q ]
            else
                [ [^first ^first_path] ^^(insert( newpoint, path, rest )) ]
            endif
        else
            [ [^newpoint ^path] ]
        endif;
    enddefine;

    path_search( start,
                 (nonop =)(% goal %),
                 next_from,
                 insert
               );

enddefine;


endsection;