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