(* Copyright (C) 2005, 2006, 2007, 2008, 2009, 2010 Free Software Foundation, Inc. *) (* This file is part of GNU Modula-2. GNU Modula-2 is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 3, or (at your option) any later version. GNU Modula-2 is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with gm2; see the file COPYING. If not, write to the Free Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. *) IMPLEMENTATION MODULE Find ; FROM NumberIO IMPORT WriteCard ; FROM StrIO IMPORT WriteString, WriteLn ; CONST MaxX = 10 ; MaxY = 20 ; Infinity = 10000 ; Wall = Infinity ; Door = Infinity-1 ; VAR MapDist: ARRAY [0..MaxX], [0..MaxY] OF CARDINAL ; Xoffset, Yoffset: CARDINAL ; (* FindOptimumRoute - finds the optimum route between two points, x1, y1, x2, y2. The directions are returned in a string, Commands. A boolean is returned if any commands were entered. *) PROCEDURE FindOptimumRoute (x1, y1, x2, y2: INTEGER; VAR Commands: ARRAY OF CHAR) : BOOLEAN ; BEGIN IF IsOptimumRoutePossible(x1, y1, x2, y2) THEN InitMapDist(x1, y1, x2, y2) ; RETURN( CalculateOptimumRoute(x1, y1, x2, y2, Commands) ) ELSE RETURN( FALSE ) END END FindOptimumRoute ; (* IsOptimumRoutePossible - returns true if we can use the optimum route procedure to work out how to get to position, x2, y2 from x1, y1. *) PROCEDURE IsOptimumRoutePossible (x1, y1, x2, y2: INTEGER) : BOOLEAN ; BEGIN RETURN( (Abs(x1, x2) <= MaxX) AND (Abs(y1, y2) <= MaxY) ) END IsOptimumRoutePossible ; (* Min - returns the minimum of two cardinals. *) PROCEDURE Min (a, b: CARDINAL) : CARDINAL ; BEGIN IF a>b THEN RETURN( b ) ELSE RETURN( a ) END END Min ; (* Abs - returns the absolute difference between two INTEGERs. *) PROCEDURE Abs (a, b: INTEGER) : INTEGER ; BEGIN IF a>b THEN RETURN( a-b ) ELSE RETURN( b-a ) END END Abs ; (* CalculateOptimumRoute - calculates the optimum route between two points and putting the route into the string Commands. TRUE is returned if any commands are placed into Commands. *) PROCEDURE CalculateOptimumRoute (x1, y1, x2, y2: INTEGER; VAR Commands: ARRAY OF CHAR) : BOOLEAN ; VAR Distance: CARDINAL ; BEGIN Distance := ScanBackwards(x1, y1, x2, y2, 0) ; RETURN( FALSE ) END CalculateOptimumRoute ; (* ScanBackwards - fills in the DistMap with the distance values from x2, y2 to x1, y1. *) PROCEDURE ScanBackwards (x1, y1, x2, y2: INTEGER; Distance: CARDINAL) : CARDINAL ; VAR ShortDist: CARDINAL ; BEGIN IF ((MapDist[x2, y2]=0) OR (Distance < MapDist[x2, y2])) THEN ShortDist := Infinity ; MapDist[x2, y2] := Distance ; ShortDist := MoveVector(x1, y1, x2, y2, 0, 1, Distance) ; ShortDist := MoveVector(x1, y1, x2, y2, 1, 0, Distance) ; ShortDist := MoveVector(x1, y1, x2, y2, 0, -1, Distance) ; ShortDist := MoveVector(x1, y1, x2, y2, -1, 0, Distance) ; RETURN( ShortDist ) ELSE RETURN( MapDist[x2, y2]+Distance ) END END ScanBackwards ; (* MoveVector - returns a CARDINAL value indicating the distance between x2, y2 and x1, y1. It moves one step from x2, y2 along vector xv, yv. If this vector hits upon a door then we increment the vector - we dont increment the distance as one goes through a door using 1 unit of distance (actually covering 2 units of space). *) PROCEDURE MoveVector (x1, y1, x2, y2: INTEGER ; xv, yv : INTEGER ; Distance: CARDINAL) : CARDINAL ; VAR ShortDist: CARDINAL ; BEGIN IF IsDoor(x2+xv, y2+yv) THEN xv := 2*xv ; yv := 2*yv END ; INC(Distance) ; y2 := y2+yv ; x2 := x2+xv ; IF CheckSquare(x2, y2) THEN ShortDist := ScanBackwards(x1, y1, x2, y2, Distance) ELSE ShortDist := Infinity END ; RETURN( ShortDist ) END MoveVector ; (* CheckSquare - checks to see whether square, x, y, is free. If this square is free then true is returned. *) PROCEDURE CheckSquare (x, y: INTEGER) : BOOLEAN ; BEGIN IF InRange(x, y) AND (MapDist[x, y] # Wall) THEN RETURN( TRUE ) END ; RETURN( FALSE ) END CheckSquare ; (* IsDoor - returns true if point, x, y, is legal and is on a door. *) PROCEDURE IsDoor (x, y: INTEGER) : BOOLEAN ; BEGIN RETURN( InRange(x, y) AND (MapDist[x, y] = Door) ) END IsDoor ; (* InRange - returns a boolean result determining whether, x, y, is a legal index for the MapDist array. *) PROCEDURE InRange (x, y: INTEGER) : BOOLEAN ; BEGIN RETURN( (x <= MaxX) AND (y <= MaxY) AND (x >= 0) AND (y >= 0) ) END InRange ; (* InitMapDist - initializes the MapDist matrix. *) PROCEDURE InitMapDist (x1, y1, x2, y2: INTEGER) ; VAR i, j: CARDINAL ; BEGIN FOR i := 0 TO MaxX DO FOR j := 0 TO MaxY DO MapDist[i, j] := 0 (* Empty *) END END ; (* Work out the Xoffset and Yoffset. We require that our x1, y1 and x2, y2 are as central as possible. *) Xoffset := (MaxX DIV 2) - (Abs(x1, x2) DIV 2) ; Yoffset := (MaxY DIV 2) - (Abs(y1, y2) DIV 2) ; OverlayAdvMap END InitMapDist ; PROCEDURE OverlayAdvMap ; VAR r, w, d: CARDINAL ; BEGIN END OverlayAdvMap ; (* DisplayMap - display the contents of the DistMap. *) PROCEDURE DisplayMap ; VAR x, y: CARDINAL ; BEGIN WriteString('------------------------------------------------------') ; WriteLn ; FOR y := 0 TO MaxY DO FOR x := 0 TO MaxX DO IF MapDist[x, y] = Wall THEN WriteString('######') ELSIF MapDist[x, y] = Door THEN WriteString(' ') ELSE WriteCard(MapDist[x, y], 3) ; WriteString(' ') END END ; WriteLn END END DisplayMap ; (* TestDistance - tests to see whether the ScanBackwards procedure works. *) PROCEDURE TestDistance ; VAR MyDist: CARDINAL ; x, y : CARDINAL ; BEGIN InitMapDist(0, 0, MaxX, MaxY) ; FOR y := 0 TO MaxY DO MapDist[4, y] := Wall END ; MapDist[4, 3] := Door ; FOR y := 0 TO MaxY DO MapDist[7, y] := Wall END ; MapDist[7, 7] := Door ; FOR x := 0 TO MaxX DO MapDist[x, 2] := Wall END ; MapDist[2, 2] := Door ; DisplayMap ; WriteString('Creating distance map between points 0,0 and MaxX, MaxY') ; WriteLn ; MyDist := ScanBackwards(0, 0, MaxX, MaxY, 1) ; WriteString('Distance is') ; WriteCard(MapDist[0,0], 6) ; WriteLn ; DisplayMap END TestDistance ; BEGIN TestDistance END Find.