4
* Copyright © 2003 Keith Packard
6
* Permission to use, copy, modify, distribute, and sell this software and its
7
* documentation for any purpose is hereby granted without fee, provided that
8
* the above copyright notice appear in all copies and that both that
9
* copyright notice and this permission notice appear in supporting
10
* documentation, and that the name of Keith Packard not be used in
11
* advertising or publicity pertaining to distribution of the software without
12
* specific, written prior permission. Keith Packard makes no
13
* representations about the suitability of this software for any purpose. It
14
* is provided "as is" without express or implied warranty.
16
* KEITH PACKARD DISCLAIMS ALL WARRANTIES WITH REGARD TO THIS SOFTWARE,
17
* INCLUDING ALL IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS, IN NO
18
* EVENT SHALL KEITH PACKARD BE LIABLE FOR ANY SPECIAL, INDIRECT OR
19
* CONSEQUENTIAL DAMAGES OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE,
20
* DATA OR PROFITS, WHETHER IN AN ACTION OF CONTRACT, NEGLIGENCE OR OTHER
21
* TORTIOUS ACTION, ARISING OUT OF OR IN CONNECTION WITH THE USE OR
22
* PERFORMANCE OF THIS SOFTWARE.
29
extend namespace Server {
30
public namespace Boards {
32
* Board layout; each section is named by the color of the triangle,
33
* each section has two sides. These are all layed out
34
* in the "lower right" position with the center of the board at the
35
* top left (0,0) coordinate.
38
TargetOrNone target (Shape s, Color c) {
39
return (TargetOrNone.target) (Target) {
40
color = c, shape = s, active = false
44
RobotOrNone robot (Color c) {
45
return (RobotOrNone.robot) (Robot) {
46
color = c, active = false
50
typedef enum { left, right, above, below } W;
52
Walls walls (W w...) {
55
left = false, right = false, above = false, below = false
57
for (int i = 0; i < dim (w); i++)
60
walls.left = true; break;
62
walls.right = true; break;
64
walls.above = true; break;
66
walls.below = true; break;
72
ObjectLoc[*] red_tri1 = {
73
{ x = 0, y = 2, object = { robot = RobotOrNone.none,
74
target = target (Shape.Square, Color.Yellow),
75
walls = walls (W.right, W.below) }},
76
{ x = 1, y = 5, object = { robot = RobotOrNone.none,
77
target = target (Shape.Circle, Color.Green),
78
walls = walls (W.left, W.below) }},
79
{ x = 4, y = 7, object = { robot = RobotOrNone.none,
80
target = TargetOrNone.none,
81
walls = walls (W.left) }},
82
{ x = 5, y = 3, object = { robot = RobotOrNone.none,
83
target = target (Shape.Octagon, Color.Blue),
84
walls = walls (W.left, W.above) }},
85
{ x = 6, y = 6, object = { robot = RobotOrNone.none,
86
target = target (Shape.Triangle, Color.Red),
87
walls = walls (W.right, W.above) }},
88
{ x = 7, y = 2, object = { robot = RobotOrNone.none,
89
target = TargetOrNone.none,
90
walls = walls (W.above) }}
92
ObjectLoc[*] red_tri2 = {
93
{ x = 0, y = 2, object = { robot = RobotOrNone.none,
94
target = target (Shape.Triangle, Color.Red),
95
walls = walls (W.above, W.right ) }},
96
{ x = 2, y = 5, object = { robot = RobotOrNone.none,
97
target = target (Shape.Octagon, Color.Blue),
98
walls = walls (W.above, W.left ) }},
99
{ x = 4, y = 7, object = { robot = RobotOrNone.none,
100
target = TargetOrNone.none,
101
walls = walls (W.left ) }},
102
{ x = 5, y = 2, object = { robot = RobotOrNone.none,
103
target = target (Shape.Circle, Color.Green),
104
walls = walls (W.left, W.below ) }},
105
{ x = 6, y = 0, object = { robot = RobotOrNone.none,
106
target = target (Shape.Square, Color.Yellow),
107
walls = walls (W.below, W.right ) }},
108
{ x = 7, y = 2, object = { robot = RobotOrNone.none,
109
target = TargetOrNone.none,
110
walls = walls (W.above ) }},
113
ObjectLoc[*] yellow_tri1 = {
114
{ x = 0, y = 2, object = { robot = RobotOrNone.none,
115
target = target (Shape.Whirl, Color.Whirl),
116
walls = walls (W.left, W.above ) }},
117
{ x = 1, y = 6, object = { robot = RobotOrNone.none,
118
target = target (Shape.Circle, Color.Blue),
119
walls = walls (W.above, W.right ) }},
120
{ x = 2, y = 3, object = { robot = RobotOrNone.none,
121
target = target (Shape.Square, Color.Green),
122
walls = walls (W.below, W.right ) }},
123
{ x = 4, y = 7, object = { robot = RobotOrNone.none,
124
target = TargetOrNone.none,
125
walls = walls (W.left ) }},
126
{ x = 5, y = 2, object = { robot = RobotOrNone.none,
127
target = target (Shape.Octagon, Color.Red),
128
walls = walls (W.left, W.above ) }},
129
{ x = 6, y = 4, object = { robot = RobotOrNone.none,
130
target = target (Shape.Triangle, Color.Yellow),
131
walls = walls (W.left, W.below ) }},
132
{ x = 7, y = 1, object = { robot = RobotOrNone.none,
133
target = TargetOrNone.none,
134
walls = walls (W.above ) }},
137
ObjectLoc[*] yellow_tri2 = {
138
{ x = 1, y = 3, object = { robot = RobotOrNone.none,
139
target = target (Shape.Triangle, Color.Yellow),
140
walls = walls (W.below, W.right ) }},
141
{ x = 2, y = 1, object = { robot = RobotOrNone.none,
142
target = target (Shape.Circle, Color.Blue),
143
walls = walls (W.left, W.below ) }},
144
{ x = 3, y = 7, object = { robot = RobotOrNone.none,
145
target = TargetOrNone.none,
146
walls = walls (W.left ) }},
147
{ x = 4, y = 0, object = { robot = RobotOrNone.none,
148
target = target (Shape.Whirl, Color.Whirl),
149
walls = walls (W.above, W.left ) }},
150
{ x = 5, y = 6, object = { robot = RobotOrNone.none,
151
target = target (Shape.Octagon, Color.Red),
152
walls = walls (W.above, W.left ) }},
153
{ x = 6, y = 4, object = { robot = RobotOrNone.none,
154
target = target (Shape.Square, Color.Green),
155
walls = walls (W.above, W.right ) }},
156
{ x = 7, y = 3, object = { robot = RobotOrNone.none,
157
target = TargetOrNone.none,
158
walls = walls (W.above ) }},
161
ObjectLoc[*] green_tri1 = {
162
{ x = 1, y = 2, object = { robot = RobotOrNone.none,
163
target = target (Shape.Square, Color.Blue),
164
walls = walls (W.left, W.below ) }},
165
{ x = 1, y = 6, object = { robot = RobotOrNone.none,
166
target = target (Shape.Octagon, Color.Yellow),
167
walls = walls (W.above, W.left ) }},
168
{ x = 3, y = 7, object = { robot = RobotOrNone.none,
169
target = TargetOrNone.none,
170
walls = walls (W.left ) }},
171
{ x = 4, y = 1, object = { robot = RobotOrNone.none,
172
target = target (Shape.Circle, Color.Red),
173
walls = walls (W.above, W.right ) }},
174
{ x = 6, y = 5, object = { robot = RobotOrNone.none,
175
target = target (Shape.Triangle, Color.Green),
176
walls = walls (W.below, W.right ) }},
177
{ x = 7, y = 2, object = { robot = RobotOrNone.none,
178
target = TargetOrNone.none,
179
walls = walls (W.above ) }},
182
ObjectLoc[*] green_tri2 = {
183
{ x = 1, y = 4, object = { robot = RobotOrNone.none,
184
target = target (Shape.Octagon, Color.Yellow),
185
walls = walls (W.left, W.above ) }},
186
{ x = 3, y = 6, object = { robot = RobotOrNone.none,
187
target = target (Shape.Circle, Color.Red),
188
walls = walls (W.below, W.right ) }},
189
{ x = 4, y = 1, object = { robot = RobotOrNone.none,
190
target = target (Shape.Square, Color.Blue),
191
walls = walls (W.above, W.right ) }},
192
{ x = 6, y = 5, object = { robot = RobotOrNone.none,
193
target = target (Shape.Triangle, Color.Green),
194
walls = walls (W.left, W.below ) }},
195
{ x = 6, y = 7, object = { robot = RobotOrNone.none,
196
target = TargetOrNone.none,
197
walls = walls (W.left ) }},
198
{ x = 7, y = 2, object = { robot = RobotOrNone.none,
199
target = TargetOrNone.none,
200
walls = walls (W.above ) }},
203
ObjectLoc[*] blue_tri1 = {
204
{ x = 1, y = 3, object = { robot = RobotOrNone.none,
205
target = target (Shape.Circle, Color.Yellow),
206
walls = walls (W.left, W.above ) }},
207
{ x = 2, y = 6, object = { robot = RobotOrNone.none,
208
target = target (Shape.Triangle, Color.Blue),
209
walls = walls (W.left, W.below ) }},
210
{ x = 4, y = 7, object = { robot = RobotOrNone.none,
211
target = TargetOrNone.none,
212
walls = walls (W.left ) }},
213
{ x = 5, y = 1, object = { robot = RobotOrNone.none,
214
target = target (Shape.Octagon, Color.Green),
215
walls = walls (W.left, W.above ) }},
216
{ x = 6, y = 5, object = { robot = RobotOrNone.none,
217
target = target (Shape.Square, Color.Red),
218
walls = walls (W.above, W.right ) }},
219
{ x = 7, y = 4, object = { robot = RobotOrNone.none,
220
target = TargetOrNone.none,
221
walls = walls (W.above ) }},
224
ObjectLoc[*] blue_tri2 = {
225
{ x = 1, y = 3, object = { robot = RobotOrNone.none,
226
target = target (Shape.Circle, Color.Yellow),
227
walls = walls (W.right, W.below ) }},
228
{ x = 2, y = 6, object = { robot = RobotOrNone.none,
229
target = target (Shape.Octagon, Color.Green),
230
walls = walls (W.above, W.left ) }},
231
{ x = 4, y = 7, object = { robot = RobotOrNone.none,
232
target = TargetOrNone.none,
233
walls = walls (W.left ) }},
234
{ x = 5, y = 1, object = { robot = RobotOrNone.none,
235
target = target (Shape.Triangle, Color.Blue),
236
walls = walls (W.left, W.below ) }},
237
{ x = 6, y = 5, object = { robot = RobotOrNone.none,
238
target = target (Shape.Square, Color.Red),
239
walls = walls (W.above, W.right ) }},
240
{ x = 7, y = 4, object = { robot = RobotOrNone.none,
241
target = TargetOrNone.none,
242
walls = walls (W.above ) }},
245
(&ObjectLoc[*])[4,2] Locations = {
246
{ &red_tri1, &red_tri2 },
247
{ &yellow_tri1, &yellow_tri2 },
248
{ &green_tri1, &green_tri2 },
249
{ &blue_tri1, &blue_tri2 },
252
* Rotate the one square 90 degrees counter clockwise,
253
* all this really has to do is deal with the walls and
257
ObjectLoc RotateLoc (ObjectLoc a, int rot)
265
t.object.target = a.object.target;
266
t.object.robot = a.object.robot;
267
t.object.walls.below = a.object.walls.left;
268
t.object.walls.above = a.object.walls.right;
269
t.object.walls.left = a.object.walls.above;
270
t.object.walls.right = a.object.walls.below;
280
ObjectLoc TransformLoc (ObjectLoc l, Transform t) {
281
l = RotateLoc (l, t.rot);
287
* Given the description of one square,
288
* place it on the board. Also, place the
289
* "other" walls on adjacent squares as needed.
290
* This duplicates all of the wall information,
291
* but makes it easier to search for collisions
295
PlaceObject (&Board b,
299
l = TransformLoc (l, t);
301
if (l.object.robot != RobotOrNone.none)
302
b[l.x,l.y].robot = l.object.robot;
303
if (l.object.target != TargetOrNone.none)
304
b[l.x,l.y].target = l.object.target;
306
if (l.object.walls.left) {
307
b[l.x, l.y].walls.left = true;
309
b[l.x-1, l.y].walls.right = true;
311
if (l.object.walls.right) {
312
b[l.x, l.y].walls.right = true;
314
b[l.x+1, l.y].walls.left = true;
316
if (l.object.walls.above) {
317
b[l.x, l.y].walls.above = true;
319
b[l.x, l.y - 1].walls.below = true;
321
if (l.object.walls.below) {
322
b[l.x, l.y].walls.below = true;
323
if (l.y < Height - 1)
324
b[l.x, l.y + 1].walls.above = true;
329
PlaceObjects (&Board b,
335
for (i = 0; i < dim(o); i++)
336
PlaceObject (&b, o[i], t);
340
* Each quarter of the board is rotated and positioned
341
* from the data structure above, here are the constants
345
Transform[4] transforms = {
346
{ rot = 2, dx = 0, dy = 0 },
347
{ rot = 1, dx = 8, dy = 0 },
348
{ rot = 3, dx = 0, dy = 8 },
349
{ rot = 0, dx = 8, dy = 8 },
353
* Generate a random board and random robot locations
362
/* empty the board */
363
for (j = 0; j < Height; j++)
364
for (i = 0; i < Width; i++)
366
robot = RobotOrNone.none,
367
target = TargetOrNone.none,
371
* Shuffle the board sections
373
int[4] board_order = { [i] = i };
374
Shuffle::shuffle (&board_order);
375
for (i = 0; i < 4; i++)
378
/* pick which side to use for this section */
379
j = PRNG::randint (2);
381
* Place all of the objects on this side on the board
383
PlaceObjects (&b, Locations[board_order[i], j], transforms[i]);
385
* Add the center walls
388
x = 0, y = 0, object = {
389
target = TargetOrNone.none,
390
robot = RobotOrNone.none,
391
walls = walls (W.below, W.right) }};
392
PlaceObject (&b, l, transforms[i]);
396
* Pick which quadrant each robot appears in
398
Object[4] robot_order = {
399
{ robot = robot (Color.Red),
400
target = TargetOrNone.none,
403
{ robot = robot (Color.Yellow),
404
target = TargetOrNone.none,
407
{ robot = robot (Color.Green),
408
target = TargetOrNone.none,
411
{ robot = robot (Color.Blue),
412
target = TargetOrNone.none,
416
Shuffle::shuffle (&robot_order);
417
for (i = 0; i < 4; i++)
422
l.object = robot_order[i];
423
/* avoid spot zero which is in the center */
424
loc = PRNG::randint(63) + 1;
427
PlaceObject (&b, l, transforms[i]);
431
* Now add walls all the way around the board
433
for (i = 0; i < Width; i++)
435
b[i, 0].walls.above = true;
436
b[i, Height-1].walls.below = true;
437
b[0, i].walls.left = true;
438
b[Width-1, i].walls.right = true;
444
* Locate objects on the board, the predicate matching
445
* function is used to test whether objects should be added
446
* to the returned array
449
ObjectLoc[*] find (&Board b, bool (Object) match) {
450
ObjectLoc[...] ol = {};
452
for (int y = 0; y < Height; y++)
453
for (int x = 0; x < Width; x++)
455
ol[i++] = (ObjectLoc) { x = x, y = y, object = b[x,y] };
459
public ObjectLoc[*] find_robots (&Board b, Color color)
461
bool match (Object o) {
462
union switch (o.robot) {
464
if (r.color == color || color == Color.Whirl)
470
return find (&b, match);
473
public exception invalid_robot (Color color);
475
public ObjectLoc find_robot (&Board b, Color color) {
476
ObjectLoc[*] ol = find_robots (&b, color);
478
raise invalid_robot (color);
482
public ObjectLoc[*] find_active_robot (&Board b)
484
bool match (Object o) {
485
union switch (o.robot) {
493
return find (&b, match);
496
public ObjectLoc[*] find_targets (&Board b, Color color, Shape shape)
498
bool match (Object o) {
499
union switch (o.target) {
501
if (t.color == color && t.shape == shape)
507
return find (&b, match);
510
public ObjectLoc[*] find_active_target (&Board b) {
511
bool match (Object o) {
512
union switch (o.target) {
520
return find (&b, match);
523
public void set_target (&Board b, Color color, Shape shape) {
524
void set_robot_active (ObjectLoc[*] ol, bool active) {
525
for (int o = 0; o < dim (ol); o++)
526
b[ol[o].x, ol[o].y].robot.robot.active = active;
528
void set_target_active (ObjectLoc[*] ol, bool active) {
529
for (int o = 0; o < dim (ol); o++)
530
b[ol[o].x, ol[o].y].target.target.active = active;
532
set_robot_active (find_active_robot (&b), false);
533
set_target_active (find_active_target (&b), false);
535
set_robot_active (find_robots (&b, color), true);
536
set_target_active (find_targets (&b, color, shape), true);
539
public void position_robot (&Board b, Color color, int x, int y) {
540
ObjectLoc ol = find_robot (&b, color);
541
b[ol.x, ol.y].robot = RobotOrNone.none;
542
if (b[x, y].robot != RobotOrNone.none)
543
raise invalid_robot (color);
544
b[x, y].robot = ol.object.robot;
552
bool blocked_wall (Direction direction, Walls walls) {
554
case Direction.North: return walls.above;
555
case Direction.East: return walls.right;
556
case Direction.South: return walls.below;
557
case Direction.West: return walls.left;
562
bool blocked_robot (&Board b, int x, int y) {
563
if (x < 0 || Width <= x) return true;
564
if (y < 0 || Height <= y) return true;
565
return b[x,y].robot != RobotOrNone.none;
568
Delta delta (Direction direction) {
570
case Direction.North: return (Delta) { dx = 0, dy = -1 };
571
case Direction.East: return (Delta) { dx = 1, dy = 0 };
572
case Direction.South: return (Delta) { dx = 0, dy = 1 };
576
return (Delta) { dx = -1, dy = 0 };
579
ObjectLoc find_dst (&Board b, int x, int y, Direction direction) {
580
Delta d = delta (direction);
581
while (!blocked_wall (direction, b[x,y].walls) &&
582
!blocked_robot (&b, x + d.dx, y + d.dy))
587
return (ObjectLoc) { x = x, y = y, object = b[x,y] };
590
public ObjectLoc move_robot (&Board b, Color color, Direction direction) {
591
ObjectLoc src = find_robot (&b, color);
592
ObjectLoc dst = find_dst (&b, src.x, src.y, direction);
596
public bool solved (&Board b) {
597
ObjectLoc[*] target = find_active_target (&b);
599
if (dim(target) != 1)
601
union switch (target[0].object.robot) {