1 | {
|
---|
2 | Base maze implementation classes for the Lazarus Mazes program
|
---|
3 |
|
---|
4 | Copyright (C) 2012 G.A. Nijland (eny @ lazarus forum http://www.lazarus.freepascal.org/)
|
---|
5 |
|
---|
6 | This source is free software; you can redistribute it and/or modify it under the terms of the GNU General Public
|
---|
7 | License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later
|
---|
8 | version.
|
---|
9 |
|
---|
10 | This code is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied
|
---|
11 | warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
|
---|
12 | details.
|
---|
13 |
|
---|
14 | A copy of the GNU General Public License is available on the World Wide Web at
|
---|
15 | <http://www.gnu.org/copyleft/gpl.html>. You can also obtain it by writing to the Free Software Foundation, Inc., 59
|
---|
16 | Temple Place - Suite 330, Boston, MA 02111-1307, USA.
|
---|
17 | }
|
---|
18 | unit Maze;
|
---|
19 |
|
---|
20 | {$mode objfpc}{$H+}
|
---|
21 |
|
---|
22 | interface
|
---|
23 |
|
---|
24 | uses
|
---|
25 | ContNrs, Classes, SysUtils;
|
---|
26 |
|
---|
27 | type
|
---|
28 | // Replacement for TPoint so we can work with rows and columns
|
---|
29 | TCellPoint = record
|
---|
30 | Row: integer;
|
---|
31 | Col: integer;
|
---|
32 | end;
|
---|
33 |
|
---|
34 | // The 4 directions one can go to from withint a cell.
|
---|
35 | // Do not change the order North, South, East, West; ever!
|
---|
36 | TDirection = (dirNorth, dirSouth, dirEast, dirWest);
|
---|
37 | TDirectionSet = set of TDirection;
|
---|
38 |
|
---|
39 | // For solving and displaying, keep the state of a cell
|
---|
40 | TCellState = (csEmpty, csStart, csVisited, csExit);
|
---|
41 |
|
---|
42 | { TMazeCell }
|
---|
43 | TMazeCell = class
|
---|
44 | private
|
---|
45 | FWalls : TDirectionSet;
|
---|
46 | FNeighbours: array[TDirection] of TMazeCell;
|
---|
47 | FTag : integer; // For external use (like TComponent.Tag); default = 0
|
---|
48 | FState : TCellState; // E.g. for coloring; default = csEmpty
|
---|
49 |
|
---|
50 | function OppositeDirection(const pDirection: TDirection): TDirection;
|
---|
51 | function GetCanGoDirection(const pDirection: TDirection): boolean;
|
---|
52 | function GetNeighbour(const pDirection: TDirection): TMazeCell;
|
---|
53 | procedure SetCanGoDirection(const pDirection: TDirection; pCanGo: boolean);
|
---|
54 | procedure SetNeighbour(const pDirection: TDirection; pNeighbour: TMazeCell);
|
---|
55 |
|
---|
56 | public
|
---|
57 | constructor Create;
|
---|
58 |
|
---|
59 | property Tag: integer read FTag write FTag;
|
---|
60 | property State: TCellState read FState write FState;
|
---|
61 | property CanGo[const pDirection: TDirection]: boolean read GetCanGoDirection write SetCanGoDirection;
|
---|
62 | property Neighbour[const pDirection: TDirection]: TMazeCell read GetNeighbour write SetNeighbour;
|
---|
63 | end;
|
---|
64 |
|
---|
65 | TMazeRect = array of array of TMazeCell;
|
---|
66 |
|
---|
67 | { TMaze }
|
---|
68 |
|
---|
69 | TMaze = class
|
---|
70 | private
|
---|
71 | FAllCells: TFPObjectList;
|
---|
72 | FMaze : TMazeRect;
|
---|
73 | FWidth : integer;
|
---|
74 | FHeight : integer;
|
---|
75 | FStart : TCellPoint;
|
---|
76 |
|
---|
77 | function GetCell(const pRow, pCol: integer): TMazeCell;
|
---|
78 |
|
---|
79 | public
|
---|
80 | class function CellPoint(const pRow, pCol: integer): TCellPoint;
|
---|
81 | constructor Create(const pWidth, pHeight: integer);
|
---|
82 | destructor Destroy; override;
|
---|
83 |
|
---|
84 | procedure ResetTags(const pValue: integer = 0);
|
---|
85 | procedure ResetState;
|
---|
86 | function GetCell(const pPosition: TCellPoint): TMazeCell;
|
---|
87 | function StartCell: TMazeCell;
|
---|
88 | procedure SetStartCell(const pRow, pCol: integer);
|
---|
89 | function GetStartPosition: TCellPoint;
|
---|
90 |
|
---|
91 | property Width : integer read FWidth;
|
---|
92 | property Height: integer read FHeight;
|
---|
93 |
|
---|
94 | property Cell[const pRow, pCol: integer]: TMazeCell read GetCell; default;
|
---|
95 |
|
---|
96 | end;
|
---|
97 |
|
---|
98 | implementation
|
---|
99 |
|
---|
100 | { TMazeCell }
|
---|
101 |
|
---|
102 | function TMazeCell.OppositeDirection(const pDirection: TDirection): TDirection;
|
---|
103 | begin
|
---|
104 | case pDirection of
|
---|
105 | dirNorth: result := dirSouth;
|
---|
106 | dirSouth: result := dirNorth;
|
---|
107 | dirEast : result := dirWest;
|
---|
108 | dirWest : result := dirEast
|
---|
109 | end;
|
---|
110 | end;
|
---|
111 |
|
---|
112 | function TMazeCell.GetCanGoDirection(const pDirection: TDirection): boolean;
|
---|
113 | begin
|
---|
114 | result := not (pDirection in FWalls)
|
---|
115 | end;
|
---|
116 |
|
---|
117 | function TMazeCell.GetNeighbour(const pDirection: TDirection): TMazeCell;
|
---|
118 | begin
|
---|
119 | result := FNeighbours[pDirection];
|
---|
120 | end;
|
---|
121 |
|
---|
122 | procedure TMazeCell.SetCanGoDirection(const pDirection: TDirection; pCanGo: boolean);
|
---|
123 | begin
|
---|
124 | if pCanGo then
|
---|
125 | begin
|
---|
126 | // Remove wall
|
---|
127 | FWalls := FWalls - [ pDirection ];
|
---|
128 | // Fix neighbour also; must use local F-var to prevent loop!
|
---|
129 | if assigned(Neighbour[pDirection]) then
|
---|
130 | with Neighbour[pDirection] do
|
---|
131 | FWalls := FWalls - [ OppositeDirection(pDirection) ];
|
---|
132 | end
|
---|
133 | else
|
---|
134 | begin
|
---|
135 | // Set wall
|
---|
136 | FWalls := FWalls + [ pDirection ];
|
---|
137 | // Fix neighbour also; must use local F-var to prevent loop!
|
---|
138 | if assigned(Neighbour[pDirection]) then
|
---|
139 | with Neighbour[pDirection] do
|
---|
140 | FWalls := FWalls + [ OppositeDirection(pDirection) ];
|
---|
141 | end;
|
---|
142 | end;
|
---|
143 |
|
---|
144 | procedure TMazeCell.SetNeighbour(const pDirection: TDirection; pNeighbour: TMazeCell);
|
---|
145 | begin
|
---|
146 | // Register the neighbour
|
---|
147 | FNeighbours[pDirection] := pNeighbour;
|
---|
148 | // And give self to neighbour; must use local F-var to prevent loop!
|
---|
149 | pNeighbour.FNeighbours[OppositeDirection(pDirection)] := self
|
---|
150 | end;
|
---|
151 |
|
---|
152 | constructor TMazeCell.Create;
|
---|
153 | begin
|
---|
154 | FWalls := [ dirNorth, dirSouth, dirEast, dirWest]; // Default: all directions blocked
|
---|
155 | end;
|
---|
156 |
|
---|
157 | { TMaze }
|
---|
158 | function TMaze.GetCell(const pRow, pCol: integer): TMazeCell;
|
---|
159 | begin
|
---|
160 | result := FMaze[pRow][pCol]
|
---|
161 | end;
|
---|
162 |
|
---|
163 | class function TMaze.CellPoint(const pRow, pCol: integer): TCellPoint;
|
---|
164 | begin
|
---|
165 | result.Row := pRow;
|
---|
166 | result.Col := pCol
|
---|
167 | end;
|
---|
168 |
|
---|
169 | constructor TMaze.Create(const pWidth, pHeight: integer);
|
---|
170 | var row, col: integer;
|
---|
171 | MC: TMazeCell;
|
---|
172 | begin
|
---|
173 | // Register size of the maze
|
---|
174 | FWidth := pWidth;
|
---|
175 | FHeight := pHeight;
|
---|
176 | FStart.col := PWidth div 2;
|
---|
177 | FStart.row := pHeight div 2;
|
---|
178 |
|
---|
179 | // Create the garbage bin for all cells
|
---|
180 | FAllCells := TFPObjectList.Create;
|
---|
181 |
|
---|
182 | // Initialize maze with number of rows
|
---|
183 | SetLength(FMaze, Height);
|
---|
184 |
|
---|
185 | // Initialize all rows with the number of columns
|
---|
186 | for row := 0 to Height-1 do
|
---|
187 | begin
|
---|
188 | // Allocate the columns in the row
|
---|
189 | SetLength(FMaze[row], Width);
|
---|
190 | // And add all cells
|
---|
191 | for col := 0 to FWidth-1 do
|
---|
192 | begin
|
---|
193 | // Create new cell and store it.
|
---|
194 | MC := TMazeCell.Create;
|
---|
195 | FMaze[row][col] := MC;
|
---|
196 | FAllCells.Add(MC);
|
---|
197 |
|
---|
198 | // Set up the neighbouts.
|
---|
199 | // Only West and North are required, because the maze cell
|
---|
200 | // will register itself with the neighbour as East or South
|
---|
201 | if col > 0 then MC.Neighbour[dirWest] := FMaze[row][col-1];
|
---|
202 | if row > 0 then MC.Neighbour[dirNorth] := FMaze[row-1][col];
|
---|
203 | end;
|
---|
204 | end;
|
---|
205 | end;
|
---|
206 |
|
---|
207 | destructor TMaze.Destroy;
|
---|
208 | begin
|
---|
209 | FreeAndNil(FAllCells); // Clean up all cells
|
---|
210 | inherited Destroy;
|
---|
211 | end;
|
---|
212 |
|
---|
213 | procedure TMaze.ResetTags(const pValue: integer);
|
---|
214 | var
|
---|
215 | row,col: integer;
|
---|
216 | begin
|
---|
217 | for row := 0 to Height-1 do
|
---|
218 | for col := 0 to Width-1 do
|
---|
219 | FMaze[row][col].Tag := pValue;
|
---|
220 | end;
|
---|
221 |
|
---|
222 | procedure TMaze.ResetState;
|
---|
223 | var
|
---|
224 | row,col: integer;
|
---|
225 | begin
|
---|
226 | for row := 0 to Height - 1 do
|
---|
227 | for col := 0 to Width - 1 do
|
---|
228 | if FMaze[row, col].State = csVisited then FMaze[row, col].State := csEmpty;
|
---|
229 | end;
|
---|
230 |
|
---|
231 | function TMaze.GetCell(const pPosition: TCellPoint): TMazeCell;
|
---|
232 | begin
|
---|
233 | result := FMaze[pPosition.row][pPosition.col]
|
---|
234 | end;
|
---|
235 |
|
---|
236 | function TMaze.StartCell: TMazeCell;
|
---|
237 | begin
|
---|
238 | result := FMaze[FStart.row, FStart.col]
|
---|
239 | end;
|
---|
240 |
|
---|
241 | procedure TMaze.SetStartCell(const pRow, pCol: integer);
|
---|
242 | begin
|
---|
243 | FStart.Row := pRow;
|
---|
244 | FStart.Col := pCol;
|
---|
245 | Cell[pRow,pCol].State := csStart;
|
---|
246 | end;
|
---|
247 |
|
---|
248 | function TMaze.GetStartPosition: TCellPoint;
|
---|
249 | begin
|
---|
250 | result := FStart;
|
---|
251 | end;
|
---|
252 |
|
---|
253 | end.
|
---|
254 |
|
---|