« back to all changes in this revision
Viewing changes to server-boards.5c
- browse files at revision 1
- compare with another revision
- download diff
- download tarball
- view history from revision 1
- Committer: Package Import Robot
- Author(s): Keith Packard
- Date: 2012-03-19 21:46:32 UTC
- Revision ID: package-import@ubuntu.com-20120319214632-zna7p3rikn2y1qf4
Tags: 0.1
Initial release
- files added:
- debian
- debian/source
- svg
added
removed
server-boards.5c
1
/*
2
* $Id$
3
*
4
* Copyright © 2003 Keith Packard
5
*
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.
15
*
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.
23
*/
24
25
autoload RR
26
autoload Server
27
autoload Shuffle
28
29
extend namespace Server {
30
public namespace Boards {
31
/*
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.
36
*/
37
38
TargetOrNone target (Shape s, Color c) {
39
return (TargetOrNone.target) (Target) {
40
color = c, shape = s, active = false
41
};
42
}
43
44
RobotOrNone robot (Color c) {
45
return (RobotOrNone.robot) (Robot) {
46
color = c, active = false
47
};
48
}
49
50
typedef enum { left, right, above, below } W;
51
52
Walls walls (W w...) {
53
Walls
54
walls = {
55
left = false, right = false, above = false, below = false
56
};
57
for (int i = 0; i < dim (w); i++)
58
switch (w[i]) {
59
case W.left:
60
walls.left = true; break;
61
case W.right:
62
walls.right = true; break;
63
case W.above:
64
walls.above = true; break;
65
case W.below:
66
walls.below = true; break;
67
}
68
return
69
walls;
70
}
71
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) }}
91
};
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 ) }},
111
};
112
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 ) }},
135
};
136
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 ) }},
159
};
160
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 ) }},
180
};
181
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 ) }},
201
};
202
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 ) }},
222
};
223
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 ) }},
243
};
244
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 },
250
};
251
/*
252
* Rotate the one square 90 degrees counter clockwise,
253
* all this really has to do is deal with the walls and
254
* the position
255
*/
256
257
ObjectLoc RotateLoc (ObjectLoc a, int rot)
258
{
259
while (rot-- > 0)
260
{
261
ObjectLoc t;
262
263
t.x = a.y;
264
t.y = 7 - a.x;
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;
271
a = t;
272
}
273
return a;
274
}
275
276
typedef struct {
277
int rot, dx, dy;
278
} Transform;
279
280
ObjectLoc TransformLoc (ObjectLoc l, Transform t) {
281
l = RotateLoc (l, t.rot);
282
l.x += t.dx;
283
l.y += t.dy;
284
return l;
285
}
286
/*
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
292
*/
293
294
void
295
PlaceObject (&Board b,
296
ObjectLoc l,
297
Transform t)
298
{
299
l = TransformLoc (l, t);
300
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;
305
306
if (l.object.walls.left) {
307
b[l.x, l.y].walls.left = true;
308
if (l.x > 0)
309
b[l.x-1, l.y].walls.right = true;
310
}
311
if (l.object.walls.right) {
312
b[l.x, l.y].walls.right = true;
313
if (l.x < Width - 1)
314
b[l.x+1, l.y].walls.left = true;
315
}
316
if (l.object.walls.above) {
317
b[l.x, l.y].walls.above = true;
318
if (l.y > 0)
319
b[l.x, l.y - 1].walls.below = true;
320
}
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;
325
}
326
}
327
328
void
329
PlaceObjects (&Board b,
330
&ObjectLoc[*] o,
331
Transform t)
332
{
333
int i;
334
335
for (i = 0; i < dim(o); i++)
336
PlaceObject (&b, o[i], t);
337
}
338
339
/*
340
* Each quarter of the board is rotated and positioned
341
* from the data structure above, here are the constants
342
* used for that
343
*/
344
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 },
350
};
351
352
/*
353
* Generate a random board and random robot locations
354
*/
355
356
public Board
357
random_board ()
358
{
359
Board b;
360
int i, j;
361
362
/* empty the board */
363
for (j = 0; j < Height; j++)
364
for (i = 0; i < Width; i++)
365
b[i, j] = (Object) {
366
robot = RobotOrNone.none,
367
target = TargetOrNone.none,
368
walls = walls () };
369
370
/*
371
* Shuffle the board sections
372
*/
373
int[4] board_order = { [i] = i };
374
Shuffle::shuffle (&board_order);
375
for (i = 0; i < 4; i++)
376
{
377
378
/* pick which side to use for this section */
379
j = PRNG::randint (2);
380
/*
381
* Place all of the objects on this side on the board
382
*/
383
PlaceObjects (&b, Locations[board_order[i], j], transforms[i]);
384
/*
385
* Add the center walls
386
*/
387
ObjectLoc l = {
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]);
393
}
394
395
/*
396
* Pick which quadrant each robot appears in
397
*/
398
Object[4] robot_order = {
399
{ robot = robot (Color.Red),
400
target = TargetOrNone.none,
401
walls = walls ()
402
},
403
{ robot = robot (Color.Yellow),
404
target = TargetOrNone.none,
405
walls = walls ()
406
},
407
{ robot = robot (Color.Green),
408
target = TargetOrNone.none,
409
walls = walls ()
410
},
411
{ robot = robot (Color.Blue),
412
target = TargetOrNone.none,
413
walls = walls ()
414
},
415
};
416
Shuffle::shuffle (&robot_order);
417
for (i = 0; i < 4; i++)
418
{
419
ObjectLoc l;
420
int loc;
421
422
l.object = robot_order[i];
423
/* avoid spot zero which is in the center */
424
loc = PRNG::randint(63) + 1;
425
l.x = loc % 8;
426
l.y = loc // 8;
427
PlaceObject (&b, l, transforms[i]);
428
}
429
430
/*
431
* Now add walls all the way around the board
432
*/
433
for (i = 0; i < Width; i++)
434
{
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;
439
}
440
return b;
441
}
442
443
/*
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
447
*/
448
449
ObjectLoc[*] find (&Board b, bool (Object) match) {
450
ObjectLoc[...] ol = {};
451
int i = 0;
452
for (int y = 0; y < Height; y++)
453
for (int x = 0; x < Width; x++)
454
if (match (b[x,y]))
455
ol[i++] = (ObjectLoc) { x = x, y = y, object = b[x,y] };
456
return ol;
457
}
458
459
public ObjectLoc[*] find_robots (&Board b, Color color)
460
{
461
bool match (Object o) {
462
union switch (o.robot) {
463
case robot r:
464
if (r.color == color || color == Color.Whirl)
465
return true;
466
default:
467
}
468
return false;
469
}
470
return find (&b, match);
471
}
472
473
public exception invalid_robot (Color color);
474
475
public ObjectLoc find_robot (&Board b, Color color) {
476
ObjectLoc[*] ol = find_robots (&b, color);
477
if (dim (ol) != 1)
478
raise invalid_robot (color);
479
return ol[0];
480
}
481
482
public ObjectLoc[*] find_active_robot (&Board b)
483
{
484
bool match (Object o) {
485
union switch (o.robot) {
486
case robot r:
487
if (r.active)
488
return true;
489
default:
490
}
491
return false;
492
}
493
return find (&b, match);
494
}
495
496
public ObjectLoc[*] find_targets (&Board b, Color color, Shape shape)
497
{
498
bool match (Object o) {
499
union switch (o.target) {
500
case target t:
501
if (t.color == color && t.shape == shape)
502
return true;
503
default:
504
}
505
return false;
506
}
507
return find (&b, match);
508
}
509
510
public ObjectLoc[*] find_active_target (&Board b) {
511
bool match (Object o) {
512
union switch (o.target) {
513
case target t:
514
if (t.active)
515
return true;
516
default:
517
}
518
return false;
519
}
520
return find (&b, match);
521
}
522
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;
527
}
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;
531
}
532
set_robot_active (find_active_robot (&b), false);
533
set_target_active (find_active_target (&b), false);
534
535
set_robot_active (find_robots (&b, color), true);
536
set_target_active (find_targets (&b, color, shape), true);
537
}
538
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;
545
}
546
547
typedef struct {
548
int dx;
549
int dy;
550
} Delta;
551
552
bool blocked_wall (Direction direction, Walls walls) {
553
switch (direction) {
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;
558
}
559
return false;
560
}
561
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;
566
}
567
568
Delta delta (Direction direction) {
569
switch (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 };
573
case Direction.West:
574
default:
575
}
576
return (Delta) { dx = -1, dy = 0 };
577
}
578
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))
583
{
584
x += d.dx;
585
y += d.dy;
586
}
587
return (ObjectLoc) { x = x, y = y, object = b[x,y] };
588
}
589
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);
593
return dst;
594
}
595
596
public bool solved (&Board b) {
597
ObjectLoc[*] target = find_active_target (&b);
598
599
if (dim(target) != 1)
600
return false;
601
union switch (target[0].object.robot) {
602
case robot r:
603
return r.active;
604
default:
605
}
606
return false;
607
}
608
}
609
}
Loggerhead is a web-based interface for Breezy
Version: 2.0.1