Lee routing

Source: The Art of Prolog

Program source code: lee_routing.pl

/*	
    lee_route(Source,Destination,Obstacles,Path) :-
	Path is a minimal length path from Source to
	Destination which does not cross Obstacles.
*/
:-  op( 900, fy, not).
 
     lee_route(A,B,Obstacles,Path) :- 
	waves(B,[[A],[]],Obstacles,Waves),
	path(A,B,Waves,Path).
 
/*	
    waves(Destination,Wavessofar,Obstacles,Waves) :-
	Waves is a list of waves including Wavessofar
	(except,perhaps,its last wave) that leads to Destination
	without crossing Obstacles.
*/
 
     waves(B,[Wave|Waves],Obstacles,Waves) :- member(B,Wave), !.
     waves(B,[Wave,LastWave|LastWaves],Obstacles,Waves) :- 
         next_wave(Wave,LastWave,Obstacles,NextWave), 
	 waves(B,[NextWave,Wave,LastWave|LastWaves],Obstacles,Waves).
 
/*	
    next_waves(Wave,LastWave,Obstacles,NextWave) :-
	Nextwave is the set of admissible points from Wave,
	that is excluding points from Lastwave, Wave, 
	and points under Obstacles.
*/
 
     next_wave(Wave,LastWave,Obstacles,NextWave) :-  
         findall(X,admissible(X,Wave,LastWave,Obstacles),NextWave).
 
     admissible(X,Wave,LastWave,Obstacles) :-  
         adjacent(X,Wave,Obstacles), 
	 not member(X,LastWave), 
	 not member(X,Wave).
 
     adjacent(X,Wave,Obstacles) :- 
	 member(X1,Wave), 
	 neighbor(X1,X), 
	 not obstructed(X,Obstacles).
 
     neighbor(X1-Y,X2-Y) :- next_to(X1,X2).
     neighbor(X-Y1,X-Y2) :- next_to(Y1,Y2).
 
     next_to(X,X1) :- X1 is X+1.
     next_to(X,X1) :- X > 0, X1 is X-1.
 
     obstructed(Point,Obstacles) :-
	member(Obstacle,Obstacles), obstructs(Point,Obstacle).
 
     obstructs(X-Y,obstacle(X-Y1,X2-Y2)) :- Y1 =< Y, Y =< Y2.
     obstructs(X-Y,obstacle(X1-Y1,X-Y2)) :- Y1 =< Y, Y =< Y2.
     obstructs(X-Y,obstacle(X1-Y,X2-Y2)) :- X1 =< X, X =< X2.
     obstructs(X-Y,obstacle(X1-Y1,X2-Y)) :- X1 =< X, X =< X2.
 
/*
   path(Source,Destination,Waves,Path) :-
	Path is a path from Source to destination going through Waves.
*/
 
     path(A,A,Waves,[A]) :-  !.
     path(A,B,[Wave|Waves],[B|Path]) :- 
         member(B1,Wave), neighbor(B,B1), !, path(A,B1,Waves,Path).
 
%	Testing and Data
 
	test_lee(Name,Path) :-
	   data(Name,A,B,Obstacles), lee_route(A,B,Obstacles,Path).
 
data(test1,1-1,3-3,[]).
data(test2,1-1,5-5,[obstacle(2-3,4-5)]).
data(test,1-1,5-5,[obstacle(2-3,4-5),obstacle(6-6,8-8)]).
 
%	Program 16.6 	Lee routing