Debian Codegraph @

gcc/testsuite/gm2/examples/map/pass/BoxMap.mod

raw
1 (* Copyright (C) 2005, 2006, 2007, 2008, 2009, 2010
2 Free Software Foundation, Inc. *)
3 (* This file is part of GNU Modula-2.
4
5 GNU Modula-2 is free software; you can redistribute it and/or modify it under
6 the terms of the GNU General Public License as published by the Free
7 Software Foundation; either version 3, or (at your option) any later
8 version.
9
10 GNU Modula-2 is distributed in the hope that it will be useful, but WITHOUT ANY
11 WARRANTY; without even the implied warranty of MERCHANTABILITY or
12 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
13 for more details.
14
15 You should have received a copy of the GNU General Public License along
16 with gm2; see the file COPYING. If not, write to the Free Software
17 Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. *)
18 IMPLEMENTATION MODULE BoxMap ;
19
20 (*
21 Title : MakeMap
22 Author : Gaius Mulley
23 Date : 18/7/88
24 LastEdit : 18/7/88
25 System : LOGITECH MODULA-2/86
26 Description: Generates a simple random box map for Dungeon
27 *)
28
29 IMPORT Break ;
30 FROM StdIO IMPORT Write, Read ;
31 FROM StrIO IMPORT WriteString, WriteLn ;
32 FROM NumberIO IMPORT WriteCard, ReadCard ;
33 FROM Assertion IMPORT Assert ;
34 FROM Geometry IMPORT IsSubLine, IsSubRange, IsIntersectingRange,
35 IntersectionLength, IsPointOnLine, Abs, Min, Max ;
36 FROM MakeBoxes IMPORT InitBoxes, KillBoxes,
37 AddBoxes, GetAndDeleteRandomBox ;
38 FROM StoreCoords IMPORT InitCoords, KillCoords,
39 GetAndDeleteRandomCoord, AddCoord, CoordsExist ;
40 FROM Chance IMPORT InitRandom, KillRandom,
41 GetAndDeleteRandom, AddRandom,
42 GetRand ;
43
44 CONST
45 MaxCard = 65535 ;
46
47 MaxStack = 500 ;
48
49 TYPE
50 Square = RECORD
51 Contents : (Empty, Secret, Door, Wall, Treasure) ;
52 RoomOfSquare: CARDINAL ;
53 END ;
54
55 Map = ARRAY [1..MaxX], [1..MaxY] OF Square ;
56
57 StackEntity = RECORD
58 PerimeterIndex : CARDINAL ; (* Untried Coords *)
59 BoxIndex : CARDINAL ; (* Untried boxes *)
60 OrientationIndex: CARDINAL ; (* Untried orient's *)
61 END ;
62
63 VAR
64 CurrentMap : Map ;
65 Stack : ARRAY [1..MaxStack] OF StackEntity ;
66 StackPtr : CARDINAL ;
67
68
69 (*
70 InitializeMap - Initializes CurrentMap.
71 CurrentMap has its boarder set to a Wall and middle
72 is set to Empty.
73 *)
74
75 PROCEDURE InitializeMap ;
76 VAR
77 i, j: CARDINAL ;
78 BEGIN
79 FOR i := 1 TO MaxX DO
80 FOR j := 1 TO MaxY DO
81 WITH CurrentMap[i, j] DO
82 Contents := Empty ;
83 RoomOfSquare := 0
84 END
85 END
86 END
87 END InitializeMap ;
88
89
90 (*
91 Init - Initialize the module and start the generation of a map.
92 *)
93
94 PROCEDURE Init ;
95 BEGIN
96 NoOfBoxes := 0 ;
97 (* Initialize box 0 the edge of the map *)
98 WITH Boxes[0] DO
99 x1 := 1 ;
100 x2 := MaxX ;
101 y1 := 1 ;
102 y2 := MaxY
103 END ;
104 StackPtr := 0
105 END Init ;
106
107
108 (*
109 CreateBoxMap - builds a map with central corridors and ajoining rooms.
110 *)
111
112 PROCEDURE CreateBoxMap ;
113 BEGIN
114 Init ;
115 CorridorMap ;
116 RoomMap
117 END CreateBoxMap ;
118
119
120 (*
121 CorridorMap - makes a map based arround central corridors.
122 *)
123
124 PROCEDURE CorridorMap ;
125 BEGIN
126 CreateCorridors ;
127 NoOfCorridorBoxes := NoOfBoxes
128 END CorridorMap ;
129
130
131 (*
132 CleanUpStack - cleans up the temporary stack where alternative rooms were
133 stored but are no longer needed.
134 *)
135
136 PROCEDURE CleanUpStack ;
137 BEGIN
138 WHILE StackPtr>0 DO
139 WITH Stack[StackPtr] DO
140 KillBoxes(BoxIndex) ;
141 KillCoords(PerimeterIndex) ;
142 KillRandom(OrientationIndex)
143 END ;
144 DEC(StackPtr)
145 END
146 END CleanUpStack ;
147
148
149 (*
150 RoomMap - creates the rooms on the map which fill in space left by the
151 corridors.
152 *)
153
154 PROCEDURE RoomMap ;
155 BEGIN
156 WriteString('Starting Room building') ; WriteLn ;
157 CreateRooms
158 END RoomMap ;
159
160
161 (*
162 CreateCorridors - creates a length of corridor on the map.
163 *)
164
165 PROCEDURE CreateCorridors ;
166 VAR
167 Length,
168 LengthLeft: CARDINAL ;
169 BEGIN
170 LengthLeft := TotalCorridorLength ;
171 InitBoxCorridor ; (* Place new Box on the stack *)
172 REPEAT
173 IF MakeCorridor()
174 THEN
175 WITH Boxes[NoOfBoxes] DO
176 Length := Max(Abs(x1, x2), Abs(y1, y2))
177 END ;
178 IF LengthLeft>Length
179 THEN
180 DEC(LengthLeft, Length) ;
181 InitBoxCorridor (* Place new corridors on the stack *)
182 ELSE
183 LengthLeft := 0 (* All done *)
184 END
185 ELSE
186 IF StackPtr>0
187 THEN
188 (* Retract last corridor and try another *)
189 WriteString('Backtracking') ; WriteLn ;
190 WriteString('HALTing - quicker than backtracking') ; WriteLn ;
191 HALT ;
192 WITH Boxes[NoOfBoxes] DO
193 INC(LengthLeft, Max(Abs(x1, x2), Abs(y1, y2)))
194 END ;
195 KillBox ;
196 UnMakeBox
197 ELSE
198 WriteString('Run out of ideas! MaxCorridorLength too large!') ;
199 WriteLn ;
200 LengthLeft := 0 (* Fail safe exit *)
201 END
202 END
203 UNTIL LengthLeft=0
204 END CreateCorridors ;
205
206
207 (*
208 CreateRooms - places rooms inbetween the corridors on the map.
209 *)
210
211 PROCEDURE CreateRooms ;
212 VAR
213 Finished: BOOLEAN ;
214 BEGIN
215 InitBoxRoom ;
216 Finished := FALSE ;
217 REPEAT
218 IF MakeRoom()
219 THEN
220 InitBoxRoom ;
221 Finished := NOT CoordsExist(Stack[StackPtr].PerimeterIndex)
222 ELSE
223 Finished := TRUE ;
224 (*
225 IF StackPtr>0
226 THEN
227 (* Retract last room and try another *)
228 WriteString('Backtracking room') ; WriteLn ;
229 KillBox ;
230 UnMakeBox
231 ELSE
232 WriteString('Run out of ideas! Trying to create rooms!') ;
233 WriteLn ;
234 END
235 *)
236 END
237 UNTIL Finished ;
238 END CreateRooms ;
239
240
241 (*
242 MakeCorridor - returns true if a corridor was legally placed
243 onto the map.
244 *)
245
246 PROCEDURE MakeCorridor () : BOOLEAN ;
247 VAR
248 Success : BOOLEAN ;
249 x, y : CARDINAL ;
250 BEGIN
251 WITH Stack[StackPtr] DO
252 (*
253 Perimeter has been previously pushed.
254 We now try to place a piece of corridor
255 on a selected perimeter coordinate.
256 *)
257 Success := FALSE ;
258 REPEAT
259 GetAndDeleteRandomCoord(PerimeterIndex, x, y) ;
260 x := Min(x, MaxX) ;
261 y := Min(y, MaxY) ;
262 IF x#0 (* x=0 means no more coordinates to fetch *)
263 THEN
264 Success := PutCorridorOntoMap(x, y)
265 END
266 UNTIL Success OR (x=0) (* x=0 and y=0 means no coordinates left *)
267 (* when x=0 y is also 0. *)
268 END ;
269 RETURN( Success )
270 END MakeCorridor ;
271
272
273 (*
274 MakeRoom - returns true if a room was legally placed
275 onto the map.
276 *)
277
278 PROCEDURE MakeRoom () : BOOLEAN ;
279 VAR
280 Success : BOOLEAN ;
281 x, y : CARDINAL ;
282 BEGIN
283 WITH Stack[StackPtr] DO
284 (*
285 Perimeter has been previously pushed.
286 We now try to place a piece of corridor
287 on a selected perimeter coordinate.
288 *)
289 Success := FALSE ;
290 REPEAT
291 GetAndDeleteRandomCoord(PerimeterIndex, x, y) ;
292 IF x#0 (* x=0 means no more coordinates to fetch *)
293 THEN
294 Success := PutRoomOntoMap(x, y)
295 END
296 UNTIL Success OR (x=0) (* x=0 and y=0 means no coordinates left *)
297 (* when x=0 y is also 0. *)
298 END ;
299 RETURN( Success )
300 END MakeRoom ;
301
302
303 (*
304 UnMakeBox - deletes the last box placed in the Box list.
305 *)
306
307 PROCEDURE UnMakeBox ;
308 BEGIN
309 (*
310 IF NoOfCorridorBoxes>0
311 THEN
312 FindSpaceNextToRoom
313 END ;
314 *)
315 DEC(NoOfBoxes)
316 END UnMakeBox ;
317
318
319 (*
320 KillSurroundingBoxes - finds a pocket of space on the map and deletes
321 all neighbouring boxes.
322 *)
323
324 (*
325 PROCEDURE KillSurroundingBoxes ;
326 VAR
327 x, y,
328 i, j,
329 Swap, b: CARDINAL ;
330 BEGIN
331 GetFreeSpace(x, y) ;
332 i := x ;
333 j := y ;
334 Swap := NoOfBoxes ;
335 REPEAT
336 b := 1 ;
337 WHILE b<=Swap DO
338 IF IsPointOnBox(b, i, j)
339 THEN
340 SwapBox(b, Swap) ;
341 DEC(Swap)
342 END ;
343 INC(b)
344 END ;
345 WalkClockWise(i, j)
346 UNTIL (x=i) AND (y=j) ;
347 RenewBoxes(Swap, Swap)
348 END KillSurroundingBoxes ;
349 *)
350
351
352 (*
353 SwapBox - swaps two boxes, i and j, arround on the stack.
354 *)
355
356 PROCEDURE SwapBox (i, j: CARDINAL) ;
357 VAR
358 s: StackEntity ;
359 b: Box ;
360 BEGIN
361 b := Boxes[i] ;
362 Boxes[i] := Boxes[j] ;
363 Boxes[j] := b ;
364 s := Stack[i] ;
365 Stack[i] := Stack[j] ;
366 Stack[j] := s
367 END SwapBox ;
368
369
370 (*
371 FindSpaceNextToRoom - finds a pocket of space on the map and places
372 a room near this onto the top of the box stack.
373 *)
374
375 PROCEDURE FindSpaceNextToRoom ;
376 VAR
377 t: Box ;
378 x, y, b, d,
379 Nearest,
380 Distance : CARDINAL ;
381 BEGIN
382 GetSpaceCoord(x, y) ;
383 Nearest := 1 ;
384 Distance := DistanceAppartPoint(1, x, y) ;
385 b := NoOfBoxes-1 ;
386 WHILE b>1 DO
387 d := DistanceAppartPoint(b, x, y) ;
388 IF d<Distance
389 THEN
390 Distance := d ;
391 Nearest := b
392 END ;
393 DEC(b)
394 END ;
395 SwapBox(Nearest, NoOfBoxes)
396 END FindSpaceNextToRoom ;
397
398
399 (*
400 GetSpaceCoord - Sets x and y to a coordinate which has no room on it.
401 *)
402
403 PROCEDURE GetSpaceCoord (VAR x, y: CARDINAL) ;
404 VAR
405 Space: BOOLEAN ;
406 BEGIN
407 Space := FALSE ;
408 x := 1 ;
409 WHILE (NOT Space) AND (x<=MaxX) DO
410 y := 1 ;
411 WHILE (NOT Space) AND (y<=MaxY) DO
412 IF NOT IsSpace(x, y)
413 THEN
414 INC(y)
415 ELSE
416 Space := TRUE
417 END
418 END ;
419 IF NOT Space
420 THEN
421 INC(x)
422 END
423 END
424 END GetSpaceCoord ;
425
426
427 (*
428 Reschedule - reorders boxes on the stack, all boxes that touch the
429 top box are placed n-1 n-2 etc on the stack,
430 efficient recursive backtracking!
431 *)
432
433 PROCEDURE Reschedule (Lowest: CARDINAL) ;
434 VAR
435 b,
436 Swap: CARDINAL ;
437 t : Box ;
438 BEGIN
439 Swap := NoOfBoxes-1 ;
440 b := Lowest+1 ;
441 WITH Boxes[NoOfBoxes] DO
442 WHILE Swap>b DO
443 IF IsTouchingBox(b, x1, y1, x2, y2)
444 THEN
445 SwapBox(b, Swap) ;
446 INC(b)
447 END ;
448 DEC(Swap)
449 END
450 END
451 END Reschedule ;
452
453
454 (*
455 InitBoxCorridor - initializes a new corridor on the Stack,
456 the perimeter of the map is also pushed.
457 *)
458
459 PROCEDURE InitBoxCorridor ;
460 BEGIN
461 INC(StackPtr) ;
462 WITH Stack[StackPtr] DO
463 PerimeterIndex := InitCoords() ;
464 PushPerimeterOfBoxes(PerimeterIndex, FALSE) ;
465 OrientationIndex := 0 ;
466 BoxIndex := 0
467 END
468 END InitBoxCorridor ;
469
470
471 (*
472 InitBoxRoom - initializes a new corridor on the Stack,
473 the perimeter of the map is also pushed.
474 *)
475
476 PROCEDURE InitBoxRoom ;
477 BEGIN
478 (*
479 This is a really nasty kludge - because of memory space limitations
480 the StoreCoords module is pushed for space when creating large size
481 maps.
482 The kludge to get arround this is to kill all perimeter coordinates of the
483 previous box. This can be done since we never invoke backtracking
484 when creating boxrooms - but we may when we come up with a suitable
485 reliable algorithm, however, until then we can take advantage of
486 no backtracking and delete all perimeter coords of the last box.
487 *)
488 IF StackPtr>1
489 THEN
490 (* Ok delete perimeter coord *)
491 KillCoords(Stack[StackPtr].PerimeterIndex) ;
492 KillBoxes(Stack[StackPtr].BoxIndex)
493 END ;
494 (* All done - kludge over *)
495 INC(StackPtr) ;
496 WITH Stack[StackPtr] DO
497 PerimeterIndex := InitCoords() ;
498 PushPerimeterOfBoxes(PerimeterIndex, TRUE) ;
499 OrientationIndex := 0 ;
500 BoxIndex := 0
501 END
502 END InitBoxRoom ;
503
504
505 (*
506 KillBox - pops the last Box from the stack.
507 *)
508
509 PROCEDURE KillBox ;
510 BEGIN
511 WITH Stack[StackPtr] DO
512 KillCoords(PerimeterIndex)
513 END ;
514 DEC(StackPtr)
515 END KillBox ;
516
517
518 (*
519 PutCorridorOntoMap - returns true if it has placed a corridor
520 onto a map.
521 Otherwise no corridor has been placed onto
522 this map.
523 *)
524
525 PROCEDURE PutCorridorOntoMap (x, y: CARDINAL) : BOOLEAN ;
526 VAR
527 LenX,
528 LenY : CARDINAL ;
529 Success : BOOLEAN ;
530 BEGIN
531 CheckInitBoxCorridorIndex ;
532 WITH Stack[StackPtr] DO
533 Success := FALSE ;
534 REPEAT
535 IF GetBox(LenX, LenY)
536 THEN
537 Success := PlaceCorridorBox(x, y, LenX-1, LenY-1)
538 END
539 UNTIL Success OR (LenX=0) ;
540 END ;
541 CheckKillBoxIndex(LenX=0) ;
542 RETURN( Success )
543 END PutCorridorOntoMap ;
544
545
546 (*
547 PutRoomOntoMap - returns true if it has placed a room
548 onto a map.
549 Otherwise no room has been placed onto
550 this map.
551 *)
552
553 PROCEDURE PutRoomOntoMap (x, y: CARDINAL) : BOOLEAN ;
554 VAR
555 LenX,
556 LenY : CARDINAL ;
557 Success : BOOLEAN ;
558 BEGIN
559 CheckInitBoxRoomIndex ;
560 WITH Stack[StackPtr] DO
561 Success := FALSE ;
562 REPEAT
563 IF GetBox(LenX, LenY)
564 THEN
565 Success := PlaceRoomBox(x, y, LenX-1, LenY-1)
566 END
567 UNTIL Success OR (LenX=0) ;
568 END ;
569 CheckKillBoxIndex(LenX=0) ;
570 RETURN( Success )
571 END PutRoomOntoMap ;
572
573
574 (*
575 GetBox - returns true if a box can be returned.
576 It chooses one box from the box index,
577 from the stack.
578 The lengths of the Box are returned
579 in LengthX and LengthY.
580 *)
581
582 PROCEDURE GetBox (VAR LengthX, LengthY: CARDINAL) : BOOLEAN ;
583 BEGIN
584 WITH Stack[StackPtr] DO
585 GetAndDeleteRandomBox(BoxIndex, LengthX, LengthY)
586 END ;
587 RETURN(LengthX#0) (* LengthX#0 means found legal size box *)
588 END GetBox ;
589
590
591 (*
592 CheckInitBoxCorridorIndex - checks to see whether the current
593 stacked box needs
594 a list of legal corridor sizes stacked.
595 *)
596
597 PROCEDURE CheckInitBoxCorridorIndex ;
598 BEGIN
599 WITH Stack[StackPtr] DO
600 IF BoxIndex=0
601 THEN
602 (* Without stacked box list of legal sized corridors *)
603 BoxIndex := InitBoxes() ;
604 AddBoxes(BoxIndex, MinCorridorLength, CorridorWidth,
605 MaxCorridorLength, CorridorWidth) ;
606 AddBoxes(BoxIndex, CorridorWidth, MinCorridorLength,
607 CorridorWidth, MaxCorridorLength)
608 END
609 END
610 END CheckInitBoxCorridorIndex ;
611
612
613 (*
614 CheckInitBoxRoomIndex - checks to see whether the current stack box
615 needs a list of legal corridor sizes stacked.
616 *)
617
618 PROCEDURE CheckInitBoxRoomIndex ;
619 BEGIN
620 WITH Stack[StackPtr] DO
621 IF BoxIndex=0
622 THEN
623 (* Without stacked box list of legal sized rooms *)
624 BoxIndex := InitBoxes() ;
625 AddBoxes(BoxIndex, MinRoomLength, MinRoomLength,
626 MaxRoomLength, MaxRoomLength)
627 END
628 END
629 END CheckInitBoxRoomIndex ;
630
631
632 (*
633 CheckKillBoxIndex - if NeedToKill is set then the list of boxes
634 on the stack is killed.
635 Ideally this procedure should be a macro.
636 *)
637
638 PROCEDURE CheckKillBoxIndex (NeedToKill: BOOLEAN) ;
639 BEGIN
640 IF NeedToKill
641 THEN
642 WITH Stack[StackPtr] DO
643 KillBoxes(BoxIndex) ;
644 BoxIndex := 0
645 END
646 END
647 END CheckKillBoxIndex ;
648
649
650 (*
651 PlaceCorridorBox - returns true if a box can make a corridor at
652 position x, y.
653 All 4 orientations are tried.
654
655
656 2 1
657 4 3
658
659 Ie 1: (x, y) (x+LenX, y+LenY)
660 2: (x, y) (x-LenX, y+LenY)
661 3: (x, y) (x+LenX, y-LenY)
662 4: (x, y) (x-LenX, y-LenY)
663 *)
664
665 PROCEDURE PlaceCorridorBox (x, y: CARDINAL; LenX, LenY: CARDINAL) : BOOLEAN ;
666 VAR
667 Success: BOOLEAN ;
668 i : CARDINAL ;
669 BEGIN
670 CheckInitOrientationIndex ;
671 WITH Stack[StackPtr] DO
672 Success := FALSE ;
673 REPEAT
674 i := GetAndDeleteRandom(OrientationIndex) ;
675 CASE i OF
676
677 1: Success := AttemptToPlaceCorridor(x, y, x+LenX, y+LenY) |
678
679 2: IF x>LenX
680 THEN
681 Success := AttemptToPlaceCorridor(x-LenX, y, x, y+LenY)
682 END |
683
684 3: IF y>LenY
685 THEN
686 Success := AttemptToPlaceCorridor(x, y-LenY, x+LenX, y)
687 END |
688
689 4: IF (x>LenX) AND (y>LenY)
690 THEN
691 Success := AttemptToPlaceCorridor(x-LenX, y-LenY, x, y)
692 END
693
694 ELSE
695 END
696 UNTIL Success OR (i=0) ;
697 END ;
698 CheckKillOrientationIndex(i=0) ;
699 RETURN( Success )
700 END PlaceCorridorBox ;
701
702
703 (*
704 PlaceRoomBox - returns true if a box can make a corridor at
705 position x, y.
706 All 4 orientations are tried.
707
708
709 2 1
710 4 3
711
712 Ie 1: (x, y) (x+LenX, y+LenY)
713 2: (x, y) (x-LenX, y+LenY)
714 3: (x, y) (x+LenX, y-LenY)
715 4: (x, y) (x-LenX, y-LenY)
716 *)
717
718 PROCEDURE PlaceRoomBox (x, y: CARDINAL; LenX, LenY: CARDINAL) : BOOLEAN ;
719 VAR
720 Success: BOOLEAN ;
721 i : CARDINAL ;
722 BEGIN
723 CheckInitOrientationIndex ;
724 WITH Stack[StackPtr] DO
725 Success := FALSE ;
726 REPEAT
727 i := GetAndDeleteRandom(OrientationIndex) ;
728 CASE i OF
729
730 1: Success := AttemptToPlaceRoom(x, y, x+LenX, y+LenY) |
731
732 2: IF x>LenX
733 THEN
734 Success := AttemptToPlaceRoom(x-LenX, y, x, y+LenY)
735 END |
736
737 3: IF y>LenY
738 THEN
739 Success := AttemptToPlaceRoom(x, y-LenY, x+LenX, y)
740 END |
741
742 4: IF (x>LenX) AND (y>LenY)
743 THEN
744 Success := AttemptToPlaceRoom(x-LenX, y-LenY, x, y)
745 END
746
747 ELSE
748 END
749 UNTIL Success OR (i=0) ;
750 END ;
751 CheckKillOrientationIndex(i=0) ;
752 RETURN( Success )
753 END PlaceRoomBox ;
754
755
756 (*
757 CheckInitOrientationIndex - checks to see whether the current stacked
758 entity needs a new orientation index to also
759 be stacked.
760 *)
761
762 PROCEDURE CheckInitOrientationIndex ;
763 BEGIN
764 WITH Stack[StackPtr] DO
765 IF OrientationIndex=0
766 THEN
767 OrientationIndex := InitRandom() ;
768 AddRandom(OrientationIndex, 4)
769 END
770 END
771 END CheckInitOrientationIndex ;
772
773
774 (*
775 CheckKillOrientationIndex - checks to see whether the current stacked
776 entities orientation index needs to be
777 deleted.
778 This procedure ideally should be a macro..
779 *)
780
781 PROCEDURE CheckKillOrientationIndex (NeedToKill: BOOLEAN) ;
782 BEGIN
783 IF NeedToKill
784 THEN
785 WITH Stack[StackPtr] DO
786 KillRandom(OrientationIndex) ;
787 OrientationIndex := 0
788 END
789 END
790 END CheckKillOrientationIndex ;
791
792
793 (*
794 PushPerimeterOfBoxes - pushes all the current perimeter of the box map onto
795 the perimeter stack.
796 *)
797
798 PROCEDURE PushPerimeterOfBoxes (CoordIndex: CARDINAL; NoOpt: BOOLEAN) ;
799 VAR
800 i: CARDINAL ;
801 BEGIN
802 IF NoOfBoxes=0
803 THEN
804 (* Perimeter is center square in map *)
805 AddCoord(CoordIndex, MaxX DIV 2, MaxY DIV 2)
806 ELSE
807 i := 1 ;
808 WHILE i<=NoOfBoxes DO
809 PushPerimeterOfWalls(CoordIndex, i, NoOpt) ;
810 INC(i)
811 END
812 END
813 END PushPerimeterOfBoxes ;
814
815
816 (*
817 PushPerimeterOfWalls - pushes all coordinates of a box wall which are
818 external to the group of boxes.
819 Ie any wall which does is not shared by an
820 adjacent box MUST be external.
821 NoOpt determines whether optimization should be
822 applied to the restricting of perimeter coords.
823 Optimiztion tests for the minimum size of a room
824 to any wall, if this fails the coord is not added
825 to the perimeter list.
826 However this should not be used when pushing the
827 room perimeter since optimization is too restrictive.
828 (Corridor restrictions etc).
829 *)
830
831 PROCEDURE PushPerimeterOfWalls (CoordIndex: CARDINAL; b: CARDINAL;
832 NoOpt: BOOLEAN) ;
833 VAR
834 i, j: CARDINAL ;
835 BEGIN
836 WITH Boxes[b] DO
837 FOR i := x1 TO x2 DO
838 IF IsExternalHorizWallPerimeter(b, i, y1) AND
839 (NoOpt OR IsEnoughSpacePointToBox(i, y1))
840 THEN
841 AddCoord(CoordIndex, i, y1)
842 END ;
843 IF IsExternalHorizWallPerimeter(b, i, y2) AND
844 (NoOpt OR IsEnoughSpacePointToBox(i, y2))
845 THEN
846 AddCoord(CoordIndex, i, y2)
847 END
848 END ;
849 FOR j := y1 TO y2 DO
850 IF IsExternalVertWallPerimeter(b, x1, j) AND
851 (NoOpt OR IsEnoughSpacePointToBox(x1, j))
852 THEN
853 AddCoord(CoordIndex, x1, j)
854 END ;
855 IF IsExternalVertWallPerimeter(b, x2, j) AND
856 (NoOpt OR IsEnoughSpacePointToBox(x2, j))
857 THEN
858 AddCoord(CoordIndex, x2, j)
859 END
860 END
861 END
862 END PushPerimeterOfWalls ;
863
864
865 (*
866 IsExternalHorizWallPerimeter - returns true if coordinates,
867 x and y are not on any Horiz
868 wall of any box except b.
869 This routine allows point z, y to be
870 on a Vertical wall, but NOT on another
871 Horizontal wall.
872 *)
873
874 PROCEDURE IsExternalHorizWallPerimeter (b: CARDINAL;
875 x, y: CARDINAL) : BOOLEAN ;
876 VAR
877 i : CARDINAL ;
878 Found: BOOLEAN ;
879 BEGIN
880 Found := FALSE ;
881 IF NOT IsCornerPerimeter(b, x, y)
882 THEN
883 i := 0 ;
884 WHILE (i<=NoOfBoxes) AND (NOT Found) DO
885 IF i#b
886 THEN
887 WITH Boxes[i] DO
888 IF IsPointOnLine(x, y, x1, y1, x2, y1)
889 THEN
890 Found := TRUE
891 ELSIF IsPointOnLine(x, y, x1, y2, x2, y2)
892 THEN
893 Found := TRUE
894 END
895 END
896 END ;
897 INC(i)
898 END
899 END ;
900 RETURN( NOT Found )
901 END IsExternalHorizWallPerimeter ;
902
903
904 (*
905 IsExternalVertWallPerimeter - returns true if coordinates,
906 x and y are not on any Vertical
907 wall of any box except b.
908 This routine allows point z, y to be
909 on a Horizontal wall, but NOT on another
910 Vertical wall.
911 *)
912
913 PROCEDURE IsExternalVertWallPerimeter (b: CARDINAL;
914 x, y: CARDINAL) : BOOLEAN ;
915 VAR
916 i : CARDINAL ;
917 Found: BOOLEAN ;
918 BEGIN
919 Found := FALSE ;
920 IF NOT IsCornerPerimeter(b, x, y)
921 THEN
922 i := 0 ;
923 WHILE (i<=NoOfBoxes) AND (NOT Found) DO
924 IF i#b
925 THEN
926 WITH Boxes[i] DO
927 IF IsPointOnLine(x, y, x1, y1, x1, y2)
928 THEN
929 Found := TRUE
930 ELSIF IsPointOnLine(x, y, x2, y1, x2, y2)
931 THEN
932 Found := TRUE
933 END
934 END
935 END ;
936 INC(i)
937 END
938 END ;
939 RETURN( NOT Found )
940 END IsExternalVertWallPerimeter ;
941
942
943 (*
944 AttemptToPlaceCorridor - attempts to place a corridor x1, y1 x2, y2
945 onto the map.
946 If it succeeds it returns true
947 otherwise false
948 *)
949
950 PROCEDURE AttemptToPlaceCorridor (x1, y1, x2, y2: CARDINAL) : BOOLEAN ;
951 VAR
952 Success: BOOLEAN ;
953 BEGIN
954 IF IsCorridorSatisfied(x1, y1, x2, y2)
955 THEN
956 AddBox(x1, y1, x2, y2) ;
957 Success := TRUE
958 ELSE
959 Success := FALSE
960 END ;
961 RETURN( Success )
962 END AttemptToPlaceCorridor ;
963
964
965 (*
966 AttemptToPlaceRoom - attempts to place a room x1, y1 x2, y2
967 onto the map.
968 If it succeeds it returns true
969 otherwise false
970 *)
971
972 PROCEDURE AttemptToPlaceRoom (x1, y1, x2, y2: CARDINAL) : BOOLEAN ;
973 VAR
974 Success: BOOLEAN ;
975 BEGIN
976 IF IsRoomSatisfied(x1, y1, x2, y2)
977 THEN
978 AddBox(x1, y1, x2, y2) ;
979 Success := TRUE
980 ELSE
981 Success := FALSE
982 END ;
983 RETURN( Success )
984 END AttemptToPlaceRoom ;
985
986
987 (*
988 IsCorridorSatisfied - returns true if a Corridor x1, y1 x2, y2
989 may be placed onto the map without
990 contraveining the various rules.
991 *)
992
993 PROCEDURE IsCorridorSatisfied (x1, y1, x2, y2: CARDINAL) : BOOLEAN ;
994 VAR
995 Success: BOOLEAN ;
996 BEGIN
997 (* Put(x1, y1, x2, y2) ; *)
998 IF (x2>MaxX) OR (y2>MaxY)
999 THEN
1000 (* WriteString('Failed SIZE') ; WriteLn *)
1001 Success := FALSE
1002 ELSIF NOT DistanceAppartEdge(x1, y1, x2, y2)
1003 THEN
1004 Success := FALSE
1005 ELSIF IsOverLappingBox(x1, y1, x2, y2)
1006 THEN
1007 (* WriteString('Failed OVERLAP') ; *)
1008 Success := FALSE
1009 ELSIF NOT IsCorridorJoin(x1, y1, x2, y2)
1010 THEN
1011 (* WriteString('Failed CORRIDOR JOIN') ; *)
1012 Success := FALSE
1013 ELSIF NOT IsEnoughSpaceBetweenCorridors(x1, y1, x2, y2)
1014 THEN
1015 (* WriteString('Failed SPACE') ; *)
1016 Success := FALSE
1017 ELSE
1018 Success := TRUE
1019 END ;
1020 RETURN( Success )
1021 END IsCorridorSatisfied ;
1022
1023
1024 (*
1025 IsRoomSatisfied - returns true if a box x1, y1 x2, y2
1026 may be placed onto the map without
1027 contraveining the various rules.
1028 *)
1029
1030 PROCEDURE IsRoomSatisfied (x1, y1, x2, y2: CARDINAL) : BOOLEAN ;
1031 VAR
1032 Success: BOOLEAN ;
1033 BEGIN
1034 (* Put(x1, y1, x2, y2) ; *)
1035 IF (x2>MaxX) OR (y2>MaxY)
1036 THEN
1037 (* WriteString('Failed SIZE') ; WriteLn ; *)
1038 Success := FALSE
1039 ELSIF IsOverLappingBox(x1, y1, x2, y2)
1040 THEN
1041 (* WriteString('Failed OVERLAP') ; *)
1042 Success := FALSE
1043 ELSIF NOT DistanceAppartEdge(x1, y1, x2, y2)
1044 THEN
1045 Success := FALSE
1046 ELSIF NOT IsBoxRoomLegal(x1, y1, x2, y2)
1047 THEN
1048 (* WriteString('Failed Legal') ; *)
1049 Success := FALSE
1050 ELSIF NOT IsRoomJoin(x1, y1, x2, y2)
1051 THEN
1052 (* WriteString('Failed ROOM JOIN') ; *)
1053 Success := FALSE
1054 ELSIF NOT IsEnoughSpaceBetweenRooms(x1, y1, x2, y2)
1055 THEN
1056 (* WriteString('Failed SPACE') ; *)
1057 Success := FALSE
1058 ELSE
1059 Success := TRUE
1060 (* ; WriteString('SUCCESS') ; *)
1061 END ;
1062 RETURN( Success )
1063 END IsRoomSatisfied ;
1064
1065
1066 (*
1067 IsEnoughSpacePointToBox - returns true if there is enough space
1068 between a point, x, y and all the boxes.
1069 This routine is called before perimeter
1070 coordinates are pushed, therefore coordinates
1071 pushed are not doomed to failure due to lack
1072 of space.
1073 This routine consists of a reduced
1074 IsEnoughSpaceBetweenBoxes procedure.
1075 *)
1076
1077 PROCEDURE IsEnoughSpacePointToBox (x, y: CARDINAL) : BOOLEAN ;
1078 VAR
1079 ok : BOOLEAN ;
1080 i : CARDINAL ;
1081 Distance: CARDINAL ;
1082 BEGIN
1083 ok := TRUE ;
1084 i := 0 ; (* 0 = Perimeter of map *)
1085 WHILE ok AND (i<=NoOfBoxes) DO
1086 Distance := DistanceAppartPoint(i, x, y) ;
1087 IF Distance#0
1088 THEN
1089 ok := (Distance>=MinDistanceBetweenRooms)
1090 END ;
1091 INC(i)
1092 END ;
1093 RETURN( ok )
1094 END IsEnoughSpacePointToBox ;
1095
1096
1097 (*
1098 IsEnoughSpaceBetweenCorridors - returns true if there is enough
1099 space between box x1, y1 x2, y2
1100 and the other boxes.
1101 Also tests for right angle connection.
1102 *)
1103
1104 PROCEDURE IsEnoughSpaceBetweenCorridors (x1, y1, x2, y2: CARDINAL) : BOOLEAN ;
1105 VAR
1106 ok : BOOLEAN ;
1107 i : CARDINAL ;
1108 Distance: CARDINAL ;
1109 BEGIN
1110 ok := TRUE ;
1111 i := 1 ;
1112 WHILE ok AND (i<=NoOfBoxes) DO
1113 IF IsTouchingBox(i, x1, y1, x2, y2)
1114 THEN
1115 (* Check for a box that is not at right angles to new box. *)
1116 (* We are only allowed to touch a box at right angles. *)
1117 IF NOT IsDifferentOrientationBox(i, x1, y1, x2, y2)
1118 THEN
1119 (* touching a box which is not at right angles *)
1120 ok := FALSE
1121 END
1122 ELSIF FreeSpace(i, x1, y1, x2, y2)
1123 THEN
1124 Distance := DistanceAppartBox(i, x1, y1, x2, y2) ;
1125 (*
1126 Distance := Min(
1127 DistanceAppartBox(i, x1, y1, x2, y2),
1128 DistanceAppartDiagonal(i, x1, y1, x2, y2)
1129 ) ;
1130 *)
1131 IF Distance=0
1132 THEN
1133 ELSE
1134 ok := (Distance>=MinDistanceBetweenCorridors)
1135 END
1136 END ;
1137 INC(i)
1138 END ;
1139 RETURN( ok )
1140 END IsEnoughSpaceBetweenCorridors ;
1141
1142
1143 (*
1144 IsBoxRoomLegal - returns true if a box x1, y1, x2, y2 does not
1145 have a wall which is next to but not sharing
1146 another wall.
1147 *)
1148
1149 PROCEDURE IsBoxRoomLegal (x1, y1, x2, y2: CARDINAL) : BOOLEAN ;
1150 VAR
1151 ok : BOOLEAN ;
1152 i : CARDINAL ;
1153 Distance: CARDINAL ;
1154 CoveredN,
1155 CoveredS,
1156 CoveredE,
1157 CoveredW: BOOLEAN ;
1158 BEGIN
1159 CoveredN := IsFullyCovered(x1, y2, x2, y2) ;
1160 CoveredS := IsFullyCovered(x1, y1, x2, y1) ;
1161 CoveredE := IsFullyCovered(x2, y1, x2, y2) ;
1162 CoveredW := IsFullyCovered(x1, y1, x1, y2) ;
1163 ok := TRUE ;
1164 i := 1 ;
1165 WHILE ok AND (i<=NoOfBoxes) DO
1166 IF NOT IsTouchingBox(i, x1, y1, x2, y2)
1167 THEN
1168 IF (x1>1) AND (NOT CoveredW)
1169 THEN
1170 ok := NOT IsTouchingBox(i, x1-1, y1, x2, y2)
1171 END ;
1172 IF ok AND (y1>1) AND (NOT CoveredS)
1173 THEN
1174 ok := NOT IsTouchingBox(i, x1, y1-1, x2, y2)
1175 END ;
1176 IF ok AND (x2<MaxX) AND (NOT CoveredE)
1177 THEN
1178 ok := NOT IsTouchingBox(i, x1, y1, x2+1, y2)
1179 END ;
1180 IF ok AND (y2<MaxY) AND (NOT CoveredN)
1181 THEN
1182 ok := NOT IsTouchingBox(i, x1, y1, x2, y2+1)
1183 END
1184 END ;
1185 INC(i)
1186 END ;
1187 RETURN( ok )
1188 END IsBoxRoomLegal ;
1189
1190
1191 (*
1192 IsFullyCovered - returns true if every point on the line
1193 x1, y1, x2, y2 is covered. The line must
1194 either be horizontal or vertical.
1195 *)
1196
1197 PROCEDURE IsFullyCovered (x1, y1, x2, y2: CARDINAL) : BOOLEAN ;
1198 VAR
1199 i : CARDINAL ;
1200 Covered: BOOLEAN ;
1201 BEGIN
1202 Covered := TRUE ;
1203 IF x1=x2
1204 THEN
1205 (* Vertical *)
1206 i := y1 ;
1207 WHILE Covered AND (i<=y2) DO
1208 Covered := IsSpace(x1, i) ;
1209 INC(i)
1210 END
1211 ELSIF y1=y2
1212 THEN
1213 (* Horizontal *)
1214 i := x1 ;
1215 WHILE Covered AND (i<=x2) DO
1216 Covered := IsSpace(i, y1) ;
1217 INC(i)
1218 END
1219 END ;
1220 RETURN( Covered )
1221 END IsFullyCovered ;
1222
1223
1224 (*
1225 IsEnoughSpaceBetweenRooms - returns true if there is enough
1226 space between box x1, y1 x2, y2
1227 and the other boxes.
1228 *)
1229
1230 PROCEDURE IsEnoughSpaceBetweenRooms (x1, y1, x2, y2: CARDINAL) : BOOLEAN ;
1231 VAR
1232 ok : BOOLEAN ;
1233 i : CARDINAL ;
1234 Distance: CARDINAL ;
1235 BEGIN
1236 ok := TRUE ;
1237 i := 1 ;
1238 WHILE ok AND (i<=NoOfBoxes) DO
1239 IF NOT IsTouchingBox(i, x1, y1, x2, y2)
1240 THEN
1241 (* Dont test the walls of the box for contraveining the space rule *)
1242 (*
1243 IF (x1+1<x2-1) AND (y1+1<y2-1) AND FreeSpace(i, x1+1, y1+1, x2-1, y2-1)
1244 THEN
1245 Distance := DistanceAppartDiagonal(i, x1+1, y1+1, x2-1, y2-1) ;
1246 *)
1247 IF FreeSpace(i, x1, y1, x2, y2)
1248 THEN
1249 (*
1250 Distance := DistanceAppartDiagonal(i, x1, y1, x2, y2) ;
1251 *)
1252 Distance := Max( DistanceAppartDiagonal(i, x1, y1, x2, y2),
1253 DistanceAppartBox(i, x1, y1, x2, y2) ) ;
1254 (* WriteString('Dist') ; WriteCard(Distance, 6) ; WriteLn ; *)
1255 IF Distance=0
1256 THEN
1257 (* touching a box *)
1258 ELSE
1259 Assert(NOT IsTouchingBox(i, x1, y1, x2, y2)) ;
1260 ok := (Distance>=MinDistanceBetweenRooms)
1261 END
1262 END
1263 END ;
1264 INC(i)
1265 END ;
1266 RETURN( ok )
1267 END IsEnoughSpaceBetweenRooms ;
1268
1269
1270 (*
1271 FreeSpace - returns true if there exists free space between box
1272 X1, Y1, X2, Y2 and box b.
1273 Should not be called if box b touches X1, Y1, X2, Y2.
1274 *)
1275
1276 PROCEDURE FreeSpace (b: CARDINAL; X1, Y1, X2, Y2: CARDINAL) : BOOLEAN ;
1277 VAR
1278 Free : BOOLEAN ;
1279 xs, xe,
1280 ys, ye,
1281 i, j : CARDINAL ;
1282 BEGIN
1283 WITH Boxes[b] DO
1284 IF Abs(X1, x2)<Abs(X2, x1)
1285 THEN
1286 xs := Min(X1, x2) ;
1287 xe := Max(X1, x2)
1288 ELSE
1289 xs := Min(X2, x1) ;
1290 xe := Max(X2, x1)
1291 END ;
1292 IF Abs(Y1, y2)<Abs(Y2, y1)
1293 THEN
1294 ys := Min(Y1, y2) ;
1295 ye := Max(Y1, y2)
1296 ELSE
1297 ys := Min(Y2, y1) ;
1298 ye := Max(Y2, y1)
1299 END ;
1300 Free := FALSE ;
1301 i := xs ;
1302 WHILE (NOT Free) AND (i<=xe) DO
1303 j := ys ;
1304 WHILE (NOT Free) AND (j<=ye) DO
1305 Free := IsSpace(i, j) ;
1306 INC(j)
1307 END ;
1308 INC(i)
1309 END
1310 END ;
1311 (* IF Free THEN WriteString('FREE') END ; *)
1312 RETURN( Free )
1313 END FreeSpace ;
1314
1315
1316 (*
1317 IsSpace - returns true if point x, y is not in any box.
1318 A wall is counted as in the box.
1319 *)
1320
1321 PROCEDURE IsSpace (x, y: CARDINAL) : BOOLEAN ;
1322 VAR
1323 b : CARDINAL ;
1324 InBox: BOOLEAN ;
1325 BEGIN
1326 InBox := FALSE ;
1327 b := 1 ; (* Not zero of course !! *)
1328 WHILE (NOT InBox) AND (b<=NoOfBoxes) DO
1329 WITH Boxes[b] DO
1330 InBox := IsSubRange(x1, x2, x) AND IsSubRange(y1, y2, y)
1331 END ;
1332 INC(b)
1333 END ;
1334 RETURN( NOT InBox )
1335 END IsSpace ;
1336
1337
1338 (*
1339 DistanceAppartEdge - returns true if the box, x1, y1, x2, y2, is a
1340 required distance away from the edge of the
1341 map.
1342 Cannot use room zero for this test as we are inside
1343 it and may touch one wall but be too near another!
1344 *)
1345
1346 PROCEDURE DistanceAppartEdge (x1, y1, x2, y2: CARDINAL) : BOOLEAN ;
1347 VAR
1348 ok : BOOLEAN ;
1349 Distance: CARDINAL ;
1350 BEGIN
1351 ok := TRUE ;
1352 Distance := Abs(x1, 1) ;
1353 IF (Distance>0) AND ok
1354 THEN
1355 ok := (Distance>=MinDistanceBetweenRooms)
1356 END ;
1357 Distance := Abs(x2, MaxX) ;
1358 IF (Distance>0) AND ok
1359 THEN
1360 ok := (Distance>=MinDistanceBetweenRooms)
1361 END ;
1362 Distance := Abs(y1, 1) ;
1363 IF (Distance>0) AND ok
1364 THEN
1365 ok := (Distance>=MinDistanceBetweenRooms)
1366 END ;
1367 Distance := Abs(y2, MaxY) ;
1368 IF (Distance>0) AND ok
1369 THEN
1370 ok := (Distance>=MinDistanceBetweenRooms)
1371 END ;
1372 RETURN( ok )
1373 END DistanceAppartEdge ;
1374
1375
1376 (*
1377 DistanceAppartPoint - returns the distance appart between box, b,
1378 and point X, Y.
1379 *)
1380
1381 PROCEDURE DistanceAppartPoint (b: CARDINAL; X, Y: CARDINAL) : CARDINAL ;
1382 VAR
1383 Xmin,
1384 Ymin: CARDINAL ;
1385 BEGIN
1386 WITH Boxes[b] DO
1387 IF IsSubRange(x1, x2, X)
1388 THEN
1389 Ymin := Min( Abs(y1, Y), Abs(y2, Y) )
1390 ELSE
1391 Ymin := MaxCard
1392 END ;
1393 IF IsSubRange(y1, y2, Y)
1394 THEN
1395 Xmin := Min( Abs(x1, X), Abs(x2, X) )
1396 ELSE
1397 Xmin := MaxCard
1398 END
1399 END ;
1400 RETURN( Min(Xmin, Ymin) )
1401 END DistanceAppartPoint ;
1402
1403
1404 (*
1405 DistanceAppartBox - returns the distance appart between box, b,
1406 and box X1, Y1, X2, Y2
1407 *)
1408
1409 PROCEDURE DistanceAppartBox (b: CARDINAL; X1, Y1, X2, Y2: CARDINAL) : CARDINAL ;
1410 VAR
1411 Xmin,
1412 Ymin: CARDINAL ;
1413 BEGIN
1414 WITH Boxes[b] DO
1415 IF IsIntersectingRange(x1, x2, X1, X2)
1416 THEN
1417 Ymin := Min(
1418 Min( Abs(y1, Y1), Abs(y2, Y2) ),
1419 Min( Abs(y1, Y2), Abs(Y1, y2) )
1420 )
1421 ELSE
1422 Ymin := MaxCard
1423 END ;
1424 IF IsIntersectingRange(y1, y2, Y1, Y2)
1425 THEN
1426 Xmin := Min(
1427 Min( Abs(x1, X1), Abs(x2, X2) ),
1428 Min( Abs(x1, X2), Abs(X1, x2) )
1429 )
1430 ELSE
1431 Xmin := MaxCard
1432 END
1433 END ;
1434 RETURN( Min(Xmin, Ymin) )
1435 END DistanceAppartBox ;
1436
1437
1438 (*
1439 DistanceAppartDiagonal - returns the diagonal
1440 distance appart between X1, Y1, X2, Y2
1441 and box b.
1442 *)
1443
1444 PROCEDURE DistanceAppartDiagonal (b: CARDINAL;
1445 X1, Y1, X2, Y2: CARDINAL) : CARDINAL ;
1446 BEGIN
1447 WITH Boxes[b] DO
1448 RETURN(
1449 Min(
1450 Min( Abs(x1, X2), Abs(x2, X1) ),
1451 Min( Abs(y1, Y2), Abs(y2, Y1) )
1452 )
1453 )
1454 END
1455 END DistanceAppartDiagonal ;
1456
1457
1458 (*
1459 IsCorridorJoin - returns true if a box corridor x1, y1 x2, y2
1460 joins another corridor at right angles without
1461 cutting off the potential corridor door.
1462
1463 A corridor is thought of as
1464
1465 ##########################
1466 | |
1467 | |
1468 ##########################
1469
1470 and may only be placed together in a way such that
1471 they meet -| or - etc
1472 |
1473
1474 False is returned if this box corridor does not
1475 correctly form a T junction with another.
1476 *)
1477
1478 PROCEDURE IsCorridorJoin (x1, y1, x2, y2: CARDINAL) : BOOLEAN ;
1479 VAR
1480 ok,
1481 DoorFound: BOOLEAN ;
1482 b : CARDINAL ;
1483 BEGIN
1484 ok := TRUE ;
1485 IF NoOfBoxes=0
1486 THEN
1487 DoorFound := TRUE
1488 ELSE
1489 DoorFound := FALSE ;
1490 b := 1 ;
1491 WHILE ok AND (b<=NoOfBoxes) DO
1492 (* WriteString('Box') ; WriteCard(b, 2) ; *)
1493 IF IsTouchingBox(b, x1, y1, x2, y2)
1494 THEN
1495 (* WriteString('TouchingBox') ; *)
1496 IF IsDifferentOrientationBox(b, x1, y1, x2, y2)
1497 THEN
1498 (* WriteString('Different Orientation') ; *)
1499 IF NOT DoorFound
1500 THEN
1501 DoorFound := IsCorridorWallJoinBox(b, x1, y1, x2, y2)
1502 END
1503 (* ; IF ok THEN WriteString('WallJoin') END ; *)
1504 ELSE
1505 ok := FALSE (* Dont allow parallel corridors to touch *)
1506 END
1507 END ;
1508 INC(b)
1509 END
1510 END ;
1511 RETURN( ok AND DoorFound )
1512 END IsCorridorJoin ;
1513
1514
1515 (*
1516 IsRoomJoin - returns true if a box room x1, y1 x2, y2
1517 joins another room with enough space for a door.
1518 *)
1519
1520 PROCEDURE IsRoomJoin (x1, y1, x2, y2: CARDINAL) : BOOLEAN ;
1521 VAR
1522 DoorFound: BOOLEAN ;
1523 b : CARDINAL ;
1524 BEGIN
1525 IF NoOfBoxes=0
1526 THEN
1527 DoorFound := TRUE
1528 ELSE
1529 DoorFound := FALSE ;
1530 b := 1 ;
1531 WHILE (NOT DoorFound) AND (b<=NoOfBoxes) DO
1532 (* WriteString('Box') ; WriteCard(b, 2) ; *)
1533 IF IsTouchingBox(b, x1, y1, x2, y2)
1534 THEN
1535 IF NOT DoorFound
1536 THEN
1537 DoorFound := IsRoomWallJoinBox(b, x1, y1, x2, y2)
1538 END
1539 END ;
1540 INC(b)
1541 END
1542 END ;
1543 RETURN( DoorFound )
1544 END IsRoomJoin ;
1545
1546
1547 (*
1548 IsCorridorWallJoinBox - returns true if box, b, and box X1, Y1 X2, Y2
1549 form a correct join ie covering the potential
1550 door.
1551 *)
1552
1553 PROCEDURE IsCorridorWallJoinBox (b: CARDINAL;
1554 X1, Y1, X2, Y2: CARDINAL) : BOOLEAN ;
1555 VAR
1556 Success: BOOLEAN ;
1557 BEGIN
1558 WITH Boxes[b] DO
1559 Success := (((X1=x1) OR (X1=x2) OR (X2=x1) OR (X2=x2))
1560 AND IsSubLine(Y1, Y2, y1, y2)) OR
1561 (((Y1=y1) OR (Y1=y2) OR (Y2=y1) OR (Y2=y2))
1562 AND IsSubLine(X1, X2, x1, x2)) ;
1563 RETURN( Success )
1564 END
1565 END IsCorridorWallJoinBox ;
1566
1567
1568 (*
1569 IsRoomWallJoinBox - returns true if box, b, and box X1, Y1 X2, Y2
1570 form a correct join ie covering the potential
1571 door.
1572 *)
1573
1574 PROCEDURE IsRoomWallJoinBox (b: CARDINAL;
1575 X1, Y1, X2, Y2: CARDINAL) : BOOLEAN ;
1576 VAR
1577 DoorWidth: CARDINAL ;
1578 BEGIN
1579 DoorWidth := 0 ;
1580 WITH Boxes[b] DO
1581 IF (X1=x2) OR (x1=X2)
1582 THEN
1583 DoorWidth := IntersectionLength(Y1, Y2, y1, y2) ;
1584 IF (IsSubRange(Y1, Y2, y1) OR IsSubRange(y1, y2, Y1)) AND (DoorWidth>1)
1585 THEN
1586 DEC(DoorWidth)
1587 END ;
1588 IF (IsSubRange(Y1, Y2, y2) OR IsSubRange(y1, y2, Y2)) AND (DoorWidth>1)
1589 THEN
1590 DEC(DoorWidth)
1591 END
1592 ELSIF (Y1=y2) OR (y1=Y2)
1593 THEN
1594 DoorWidth := IntersectionLength(X1, X2, x1, x2) ;
1595 IF (IsSubRange(X1, X2, x1) OR IsSubRange(x1, x2, X1)) AND (DoorWidth>1)
1596 THEN
1597 DEC(DoorWidth)
1598 END ;
1599 IF (IsSubRange(X1, X2, x2) OR IsSubRange(x1, x2, X2)) AND (DoorWidth>1)
1600 THEN
1601 DEC(DoorWidth)
1602 END
1603 END ;
1604 RETURN( DoorWidth>=MinDoorLength )
1605 END
1606 END IsRoomWallJoinBox ;
1607
1608
1609 (*
1610 IsDifferentOrientationBox - returns true if box b has a different
1611 orientation to box X1, Y1 X2, Y2.
1612 *)
1613
1614 PROCEDURE IsDifferentOrientationBox (b: CARDINAL;
1615 X1, Y1, X2, Y2: CARDINAL) : BOOLEAN ;
1616 BEGIN
1617 WITH Boxes[b] DO
1618 IF Abs(X1, X2) = Abs(Y1, Y2)
1619 THEN
1620 RETURN( TRUE ) (* Square X1, Y1, X2, Y2 *)
1621 ELSIF Abs(X1, X2) > Abs(Y1, Y2)
1622 THEN
1623 RETURN( Abs(x1, x2) <= Abs(y1, y2) )
1624 ELSE
1625 RETURN( Abs(x1, x2) >= Abs(y1, y2) )
1626 END
1627 END
1628 END IsDifferentOrientationBox ;
1629
1630
1631 (*
1632 IsTouchingBox - returns true if a box X1, Y1 X2, Y2 touches box b
1633 or if it intersects with this box.
1634 *)
1635
1636 PROCEDURE IsTouchingBox (b: CARDINAL; X1, Y1, X2, Y2: CARDINAL) : BOOLEAN ;
1637 BEGIN
1638 WITH Boxes[b] DO
1639 RETURN( NOT ((X2<x1) OR (X1>x2) OR (Y2<y1) OR (Y1>y2)) )
1640 END
1641 END IsTouchingBox ;
1642
1643
1644 (*
1645 IsCornerPerimeter - returns true if box, b, has a corner x, y which
1646 is a perimeter.
1647 *)
1648
1649 PROCEDURE IsCornerPerimeter (b: CARDINAL; x, y: CARDINAL) : BOOLEAN ;
1650 VAR
1651 Perimeter: BOOLEAN ;
1652 i, j : CARDINAL ;
1653 BEGIN
1654 IF IsCorner(b, x, y)
1655 THEN
1656 Perimeter := FALSE ;
1657 i := x-1 ;
1658 j := y-1 ;
1659 WHILE (NOT Perimeter) AND (i<=x+1) DO
1660 j := y-1 ;
1661 WHILE (NOT Perimeter) AND (j<=y+1) DO
1662 IF IsSubRange(1, MaxX, i) AND IsSubRange(1, MaxY, j)
1663 THEN
1664 Perimeter := IsSpace(i, j)
1665 END ;
1666 INC(j, 2)
1667 END ;
1668 INC(i, 2)
1669 END ;
1670 RETURN( Perimeter )
1671 ELSE
1672 RETURN( FALSE )
1673 END
1674 END IsCornerPerimeter ;
1675
1676
1677 (*
1678 IsCorner - returns true if box, b, has a corner x, y.
1679 *)
1680
1681 PROCEDURE IsCorner (b: CARDINAL; x, y: CARDINAL) : BOOLEAN ;
1682 BEGIN
1683 WITH Boxes[b] DO
1684 RETURN( ((x1=x) OR (x2=x)) AND ((y1=y) OR (y2=y)) )
1685 END
1686 END IsCorner ;
1687
1688
1689 (*
1690 IsOverLappingBox - returns true if box X1, Y1 X2, Y2 overlaps
1691 with another box NOT including edges touching.
1692 *)
1693
1694 PROCEDURE IsOverLappingBox (X1, Y1, X2, Y2: CARDINAL) : BOOLEAN ;
1695 VAR
1696 b : CARDINAL ;
1697 Found: BOOLEAN ;
1698 BEGIN
1699 Found := FALSE ;
1700 b := 1 ;
1701 WHILE (NOT Found) AND (b<=NoOfBoxes) DO
1702 WITH Boxes[b] DO
1703 Found := IsIntersection(x1, y1, x2, y2, X1, Y1, X2, Y2)
1704 END ;
1705 INC(b)
1706 END ;
1707 RETURN( Found )
1708 END IsOverLappingBox ;
1709
1710
1711 (*
1712 IsIntersection - returns true if two boxes x1, y1 x2, y2 intersects
1713 with X1, Y1 X2, Y2. Wall touching is allowed.
1714 *)
1715
1716 PROCEDURE IsIntersection (x1, y1, x2, y2,
1717 X1, Y1, X2, Y2: CARDINAL) : BOOLEAN ;
1718 BEGIN
1719 RETURN( NOT ( (x2<=X1) OR (x1>=X2) OR (y2<=Y1) OR (y1>=Y2) ) )
1720 END IsIntersection ;
1721
1722
1723 (*
1724 AddBox - adds a box to the list of boxes and
1725 adds a box to the Map.
1726 *)
1727
1728 PROCEDURE AddBox (X1, Y1, X2, Y2: CARDINAL) ;
1729 BEGIN
1730 IF NoOfBoxes=MaxBoxes
1731 THEN
1732 WriteString('Too many boxes in Module MakeMap') ; WriteLn ;
1733 HALT
1734 ELSE
1735 INC(NoOfBoxes) ;
1736 WITH Boxes[NoOfBoxes] DO
1737 x1 := X1 ;
1738 y1 := Y1 ;
1739 x2 := X2 ;
1740 y2 := Y2
1741 END
1742 END
1743 END AddBox ;
1744
1745
1746 (*
1747 GetCh - waits for a character to be pressed.
1748 *)
1749
1750 PROCEDURE GetCh ;
1751 VAR
1752 ch: CHAR ;
1753 BEGIN
1754 Read(ch)
1755 END GetCh ;
1756
1757
1758 BEGIN
1759 Init
1760 END BoxMap.