]> git.cworth.org Git - loudgame/blob - lg-loa.c
f6a8f4c182e10811b093ed1bf5651fe09779463f
[loudgame] / lg-loa.c
1 /*
2  * Copyright (C) 2008 Carl Worth
3  *
4  * This program is free software: you can redistribute it and/or modify
5  * it under the terms of the GNU General Public License as published by
6  * the Free Software Foundation, either version 3 of the License, or
7  * (at your option) any later version.
8  *
9  * This program is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with this program.  If not, see http://www.gnu.org/licenses/ .
16  *
17  * Author: Carl Worth <cworth@cworth.org>
18  */
19
20 #include "loudgame.h"
21
22 #include <stdio.h>
23 #include <stdlib.h>
24 #include <stdint.h>
25
26 #include <string.h>
27 #include <ctype.h>
28 #include <assert.h>
29
30 typedef int loa_bool_t;
31
32 #ifndef FALSE
33 #define FALSE 0
34 #endif
35 #ifndef TRUE
36 #define TRUE  1
37 #endif
38
39 typedef enum {
40     PLAYER_BLACK,
41     PLAYER_WHITE
42 } player_t;
43
44 typedef enum {
45     CELL_BLACK = PLAYER_BLACK,
46     CELL_WHITE = PLAYER_WHITE,
47     CELL_EMPTY
48 } cell_t;
49
50 /* The implementation of board_group_size depends on the square of
51  * BOARD_SIZE being less than or equal to 64. */
52 #define BOARD_SIZE 8
53 #define DIAG_ARRAY_SIZE (2 * BOARD_SIZE - 1)
54
55 typedef struct {
56     cell_t cells[BOARD_SIZE][BOARD_SIZE];
57
58     /* Number of black and white pieces */
59     int num_pieces[2];
60
61     /* Number of pieces (of either color) in each row, column, and
62      * diagonal. */
63     int row_pieces[BOARD_SIZE];
64     int col_pieces[BOARD_SIZE];
65     int diag_grave_pieces[DIAG_ARRAY_SIZE];
66     int diag_acute_pieces[DIAG_ARRAY_SIZE];
67 } board_t;
68
69 typedef struct _loa_game {
70     loudgame_t lg;
71     board_t board;
72     player_t current;
73 } loa_game_t;
74
75 static int
76 board_group_size_recursive (board_t *board, int x, int y,
77                             cell_t cell,
78                             uint64_t *visited)
79 {
80     uint64_t bit;
81
82     if (x < 0 || y < 0)
83         return 0;
84
85     if (x >= BOARD_SIZE || y >= BOARD_SIZE)
86         return 0;
87
88     bit = 1ll << (x * BOARD_SIZE + y);
89     if (*visited & bit)
90         return 0;
91
92     *visited |= bit;
93
94     if (board->cells[x][y] != cell)
95         return 0;
96
97     return 1 +
98         board_group_size_recursive (board, x-1, y-1, cell, visited) +
99         board_group_size_recursive (board, x-1, y  , cell, visited) +
100         board_group_size_recursive (board, x-1, y+1, cell, visited) +
101         board_group_size_recursive (board, x  , y-1, cell, visited) +
102         board_group_size_recursive (board, x  , y  , cell, visited) +
103         board_group_size_recursive (board, x  , y+1, cell, visited) +
104         board_group_size_recursive (board, x+1, y-1, cell, visited) +
105         board_group_size_recursive (board, x+1, y  , cell, visited) +
106         board_group_size_recursive (board, x+1, y+1, cell, visited);
107 }
108
109 static int
110 board_group_size (board_t *board, int x, int y)
111 {
112     uint64_t visited = 0ll;
113     cell_t cell = board->cells[x][y];
114
115     return board_group_size_recursive (board, x, y, cell, &visited);
116 }
117
118 static int
119 board_is_won (board_t *board, int x, int y)
120 {
121     cell_t cell = board->cells[x][y];
122
123     if (cell == CELL_EMPTY)
124         return 0;
125
126     if (board_group_size (board, x, y) == board->num_pieces[cell])
127         return 1;
128
129     return 0;
130 }
131
132 /* Given an (x,y) position on the board, return the index of the array
133  * used to count pieces in diagonal rows running from upper-left to
134  * lower-right, (like a grave accent: à or like a backslash: \).
135  *
136  * This is the array to look into when a move occurs with dx and dy of
137  * the same sign. */
138 static int
139 _grave_index (int x, int y)
140 {
141     return x - y + BOARD_SIZE - 1;
142 }
143
144 /* Given an (x,y) position on the board, return the index of the array
145  * used to count pieces in diagonal rows running from lower-left to
146  * upper-right, (like an acute accent: á or like a forward slash: /).
147  *
148  * This is the array to look into when a move occurs with dx and dy of
149  * opposite sign, (one positive, one negative). */
150 static int
151 _acute_index (int x, int y)
152 {
153     return x + y;
154 }
155
156 static loa_bool_t
157 board_move_legal (board_t *board, int x1, int y1, int x2, int y2, char **error)
158 {
159     int x, y;
160     int dx, dy;
161     int step_x, step_y;
162
163     if (board->cells[x1][y1] == CELL_EMPTY) {
164         *error = "There is no piece there to move";
165         return FALSE;
166     }
167
168     if (board->cells[x2][y2] == board->cells[x1][y1]) {
169         *error = "You cannot capture your own piece";
170         return FALSE;
171     }
172
173     dx = x2 - x1;
174     dy = y2 - y1;
175
176     /* Here's the meat of Lines of Action legaility: Does the distance
177      * moved exactly match the number of pieces (of either color) in
178      * the row, column, or diagonal of the movement. */
179     if (dx == 0) { 
180         /* Column */
181         if (abs (dy) != board->col_pieces[x1]) {
182             *error = "The move distance does not match the number of pieces in that column";
183             return FALSE;
184         }
185     } else if (dy == 0) {
186         /* Row */
187         if (abs (dx) != board->row_pieces[y1]) {
188             *error = "The move distance does not match the number of pieces in that row";
189             return FALSE;
190         }
191     } else {
192         if (abs (dx) != abs (dy)) {
193             *error = "That move is not in a row, column, or diagonal";
194             return FALSE;
195         }
196         /* Diagonal */
197         if ((dx > 0) == (dy > 0)) {
198             if (abs (dx) != board->diag_grave_pieces[_grave_index (x1, y1)]) {
199                 *error = "The move distance does not match the number of pieces in that diagonal";
200                 return FALSE;
201             }
202         } else {
203             if (abs (dx) != board->diag_acute_pieces[_acute_index (x1, y1)]) {
204                 *error = "The move distance does not match the number of pieces in that diagonal";
205                 return FALSE;
206             }
207         }
208     }
209
210     /* Finally, we have to ensure that no opponent pieces are being
211      * jumped. */
212     step_x = dx ? ((dx < 0) ? -1 : +1) : 0;
213     step_y = dy ? ((dy < 0) ? -1 : +1) : 0;
214     for (x = x1 + step_x, y = y1 + step_y;
215          x != x2 || y != y2;
216          x += step_x, y += step_y)
217     {
218         if (board->cells[x][y] != CELL_EMPTY &&
219             board->cells[x][y] != board->cells[x1][y1])
220         {
221             *error = "You cannot jump an opponent's piece";
222             return FALSE;
223         }
224     }
225
226     return TRUE;
227 }
228
229 static void
230 board_add_piece (board_t *board, int x, int y, cell_t cell)
231 {
232     assert (cell == CELL_BLACK || cell == CELL_WHITE);
233     assert (board->cells[x][y] == CELL_EMPTY);
234
235     board->col_pieces[x]++;
236     board->row_pieces[y]++;
237     board->diag_grave_pieces[_grave_index (x, y)]++;
238     board->diag_acute_pieces[_acute_index (x, y)]++;
239
240     board->num_pieces[cell]++;
241
242     board->cells[x][y] = cell;
243 }
244
245 static cell_t
246 board_remove_piece (board_t *board, int x, int y)
247 {
248     cell_t cell;
249
250     cell = board->cells[x][y];
251
252     if (cell == CELL_EMPTY)
253         return CELL_EMPTY;
254
255     board->col_pieces[x]--;
256     board->row_pieces[y]--;
257     board->diag_grave_pieces[_grave_index (x, y)]--;
258     board->diag_acute_pieces[_acute_index (x, y)]--;
259
260     board->num_pieces[cell]--;
261
262     board->cells[x][y] = CELL_EMPTY;
263
264     return cell;
265 }
266
267 static void
268 board_init (board_t *board)
269 {
270     int i, x, y;
271
272     for (x = 0; x < BOARD_SIZE; x++)
273         for (y = 0; y < BOARD_SIZE; y++)
274             board->cells[x][y] = CELL_EMPTY;
275
276     board->num_pieces[CELL_BLACK] = 0;
277     board->num_pieces[CELL_WHITE] = 0;
278
279     for (i = 0; i < BOARD_SIZE; i++) {
280         board->row_pieces[i] = 0;
281         board->col_pieces[i] = 0;
282     }
283
284     for (i = 0; i < DIAG_ARRAY_SIZE; i++) {
285         board->diag_grave_pieces[i] = 0;
286         board->diag_acute_pieces[i] = 0;
287     }
288
289     for (i = 1; i < BOARD_SIZE - 1; i++) {
290         board_add_piece (board, i, 0, CELL_BLACK);
291         board_add_piece (board, i, BOARD_SIZE - 1, CELL_BLACK);
292         board_add_piece (board, 0, i, CELL_WHITE);
293         board_add_piece (board, BOARD_SIZE - 1, i, CELL_WHITE);
294     }
295 }
296
297 /* A few different ideas for displaying boards:
298  *
299  * 8│ │●│●│●│●│●│●│ |       8| |*|*|*|*|*|*| |
300  * 7│○│ │ │ │ │ │ │○|       7|o| | | | | | |o|
301  * 6│○│ │ │ │ │ │ │○|       6|o| | | | | | |o|
302  * 5│○│ │ │ │ │ │ │○|       5|o| | | | | | |o|
303  * 4│○│ │ │ │ │ │ │○|       4|o| | | | | | |o|
304  * 3│○│ │ │ │ │ │ │○|       3|o| | | | | | |o|
305  * 2│○│ │ │ │ │ │ │○|       2|o| | | | | | |o|
306  * 1│ │●│●│●│●│●│●│ |       1| |*|*|*|*|*|*| |
307  *   A B C D E F G H      A B C D E F G H
308  *
309  *  ┌───┬───┬───┬───┬───┬───┬───┬───┐   ------------------------------- 
310  * 8│   │ ● │ ● │ ● │ ● │ ● │ ● │   │     8|   | * | * | * | * | * | * |   |
311  *  ├───┼───┼───┼───┼───┼───┼───┼───┤  |---+---+---+---+---+---+---+---|
312  * 7│ ○ │   │   │   │   │   │   │ ○ │     7| o |   |   |   |   |   |   | o |
313  *  ├───┼───┼───┼───┼───┼───┼───┼───┤  |---+---+---+---+---+---+---+---|
314  * 6│ ○ │   │   │   │   │   │   │ ○ │     6| o |   |   |   |   |   |   | o |
315  *  ├───┼───┼───┼───┼───┼───┼───┼───┤  |---+---+---+---+---+---+---+---|
316  * 5│ ○ │   │   │   │   │   │   │ ○ │     5| o |   |   |   |   |   |   | o |
317  *  ├───┼───┼───┼───┼───┼───┼───┼───┤  |---+---+---+---+---+---+---+---|
318  * 4│ ○ │   │   │   │   │   │   │ ○ │     4| o |   |   |   |   |   |   | o |
319  *  ├───┼───┼───┼───┼───┼───┼───┼───┤  |---+---+---+---+---+---+---+---|
320  * 3│ ○ │   │   │   │   │   │   │ ○ │     3| o |   |   |   |   |   |   | o |
321  *  ├───┼───┼───┼───┼───┼───┼───┼───┤  |---+---+---+---+---+---+---+---|
322  * 2│ ○ │   │   │   │   │   │   │ ○ │     2| o |   |   |   |   |   |   | o |
323  *  ├───┼───┼───┼───┼───┼───┼───┼───┤  |---+---+---+---+---+---+---+---|
324  * 1│   │ ● │ ● │ ● │ ● │ ● │ ● │   │     1|   | * | * | * | * | * | * |   |
325  *  └───┴───┴───┴───┴───┴───┴───┴───┘   ------------------------------- 
326  *    A   B   C   D   E   F   G   H        A   B   C   D   E   F   G   H
327  */
328 static char *
329 board_to_string (board_t *board)
330 {
331     int x, y;
332     /* In order of BLACK, WHITE, EMPTY */
333     const char* cell_strings[] = {"●","○"," "};
334     const char   board_header[] = "┌───┬───┬───┬───┬───┬───┬───┬───┐";
335     const char     row_header[] = "│ ";
336     const char cell_separator[] =    " │ ";
337     const char     row_footer[] =                                " │";
338     const char  row_separator[] = "├───┼───┼───┼───┼───┼───┼───┼───┤";
339     const char   board_footer[] = "└───┴───┴───┴───┴───┴───┴───┴───┘";
340     char *board_string = g_strdup ("");
341
342 #define APPEND(str) do {                                        \
343     char *_new = g_strconcat (board_string, (str), NULL);       \
344     free (board_string);                                        \
345     board_string = _new;                                        \
346 } while (0)
347
348 #define APPENDF(format, ...) do {                               \
349     char *str = g_strdup_printf (format, ## __VA_ARGS__);       \
350     APPEND (str);                                               \
351     free (str);                                                 \
352 } while (0)
353
354     APPENDF (" %s\n", board_header);
355     for (y = 0; y < BOARD_SIZE; y++) {
356         APPENDF ("%d%s", BOARD_SIZE - y, row_header);
357         for (x = 0; x < BOARD_SIZE; x++) {
358             APPENDF ("%s", cell_strings[board->cells[x][y]]);
359             if (x != BOARD_SIZE - 1)
360                 APPENDF ("%s", cell_separator);
361         }
362         APPENDF ("%s\n", row_footer);
363         if (y != BOARD_SIZE -1)
364             APPENDF (" %s\n", row_separator);
365     }
366     APPENDF (" %s\n", board_footer);
367
368     APPENDF ("   ");
369     for (x = 0; x < BOARD_SIZE; x++) {
370         APPENDF ("%c", 'A' + x);
371         if (x != BOARD_SIZE - 1)
372             APPENDF ("   ");
373     }
374     APPENDF ("\n");
375
376     return board_string;
377 }
378
379 static void
380 loa_game_new_game (loa_game_t *game)
381 {
382     board_init (&game->board);
383     game->current = PLAYER_BLACK;
384 }
385
386 static void
387 loa_game_next_player (loa_game_t *game)
388 {
389     if (game->current == PLAYER_BLACK)
390         game->current = PLAYER_WHITE;
391     else
392         game->current = PLAYER_BLACK;
393 }
394
395 static loa_bool_t
396 loa_game_move (loa_game_t *game, const char * peer,
397                int x1, int y1, int x2, int y2)
398 {
399     board_t *board = &game->board;
400     cell_t cell;
401     char *error;
402
403     if (x1 < 0 || y1 < 0 || x1 >= BOARD_SIZE || y1 >= BOARD_SIZE) {
404         loudgame_sendf (&game->lg, peer, "Invalid coordinates (not on board).");
405         return FALSE;
406     }
407
408     if (board->cells[x1][y1] != game->current) {
409         loudgame_sendf (&game->lg, peer, "Cell at (%d,%d) does not belong to current player.",
410                         x1, y1);
411         return FALSE;
412     }
413
414     if (! board_move_legal (&game->board, x1, y1, x2, y2, &error)) {
415         loudgame_sendf (&game->lg, peer, "Illegal move: %s.");
416         return FALSE;
417     }
418
419     cell = board_remove_piece (board, x1, y1);
420     board_remove_piece (board, x2, y2);
421     board_add_piece (board, x2, y2, cell);
422
423     loa_game_next_player (game);
424
425     return TRUE;
426 }
427
428 static void
429 loa_game_handle_show (loa_game_t *game,
430                       const char *peer)
431 {
432     LmMessage *reply;
433     LmMessageNode *html, *body, *span;
434     gboolean result;
435     GError *error = NULL;
436     char *board_string;
437     char *line, *newline;
438
439     reply = lm_message_new (peer, LM_MESSAGE_TYPE_MESSAGE);
440     html = lm_message_node_add_child (reply->node, "html", "");
441     lm_message_node_set_attribute (html,
442                                    "xmlns",
443                                    "http://jabber.org/protocol/xhtml-im");
444     body = lm_message_node_add_child (html, "body", "");
445     lm_message_node_set_attribute (body,
446                                    "xmlns",
447                                    "http://www.w3.org/1999/xhtml");
448
449     if (game->current == PLAYER_BLACK)
450         lm_message_node_add_child (body, "span", "Black to move:");
451     else
452         lm_message_node_add_child (body, "span", "White to move:");
453
454     board_string = board_to_string (&game->board);
455
456     line = board_string;
457     while (1) {
458         newline = strchr (line, '\n');
459         if (newline)
460             *newline = '\0';
461         lm_message_node_add_child (body, "br", "");
462         span = lm_message_node_add_child (body, "span", line);
463         lm_message_node_set_attribute (span, "style",
464                                        "font-family: Monospace;");
465         if (! newline)
466             break;
467         line = newline + 1;
468     }
469
470     free (board_string);
471
472     result = lm_connection_send (game->lg.connection, reply, &error);
473     lm_message_unref (reply);
474
475     if (! result) {
476         g_error ("lm_connection_send failed: %s\n",
477                  error->message);
478         loudgame_quit (&game->lg, 1);
479     }
480 }
481
482 static void
483 loa_game_handle_move (loa_game_t *game,
484                       const char *peer,
485                       const char *move)
486 {
487     char xc1, xc2;
488     int x1, y1, x2, y2;
489     int matched;
490
491     matched = sscanf (move, " %c %d %c %d ", &xc1, &y1, &xc2, &y2);
492     if (matched != 4) {
493         loudgame_sendf (&game->lg, peer,
494                         "Error: The 'move' command requires a move of the form 'b1d3'");
495         return;
496     }
497
498     x1 = tolower (xc1) - 'a';
499     x2 = tolower (xc2) - 'a';
500     /* We use an upper-left origin internally. */
501     y1 = BOARD_SIZE - y1;
502     y2 = BOARD_SIZE - y2;
503     if (! loa_game_move (game, peer, x1, y1, x2, y2))
504         return;
505
506     loudgame_broadcastf (&game->lg, "%c%d%c%d",
507                          'a' + x1, BOARD_SIZE - y1,
508                          'a' + x2, BOARD_SIZE - y2);
509
510     if (board_is_won (&game->board, x2, y2))
511         loudgame_broadcastf (&game->lg, "%s wins", peer);
512 }
513
514 static void
515 loa_game_handle_pass (loa_game_t *game, const char *peer)
516 {
517     loudgame_broadcastf (&game->lg, "%s passes", peer);
518
519     loa_game_next_player (game);
520 }
521
522 static void
523 loa_game_handle_help (loa_game_t *game, const char *peer)
524 {
525     loudgame_sendf (&game->lg, peer,
526                     "I'm a bot that allows you to play the game Lines of Action.\n"
527                     "Here are some generic commands I understand:\n"
528                     LOUDGAME_HELP
529                     "\n"
530                     "And some game-specific commands:\n"
531                     "\tshow     \t\tShow the current board\n"
532                     "\tmove aNbN\tMove a piece, (eg. 'move b1d3')\n"
533                     "\tpass     \t\tSkip a turn (only legal if no moves are possible)\n"
534                     "\tnew      \t\tBegin a new game\n"
535                     "\thelp     \t\tThis help message\n"
536                     "\trules    \t\tA description of the Lines of Action rules\n"
537                     "\n"
538                     "Lines of Action was invented by Claude Soucie and first made popular\n"
539                     "when its rules were published by Sid Sackson in \"A Gamut of Games\" (1969).\n"
540                     "\n"
541                     "If you are new to Lines of Action, type 'rules' now to learn the rules.\n");
542 }
543
544 static void
545 loa_game_handle_rules (loa_game_t *game, const char *peer)
546 {
547     loudgame_sendf (&game->lg, peer,
548                     "Lines of Action can be played with a standard (English) checkers set,\n"
549                     "that is an 8x8 board and 12 markers each of contrasting colors ('black' and\n"
550                     "'white'). The initial placement has 6 each of the black pieces on the top\n"
551                     "and bottom rows, and 6 each of the white pieces on the left and right columns\n"
552                     "leaving the four corner spaces empty. Play begins with the black player and\n"
553                     "then alternates.\n"
554                     "\n"
555                     "On each move a piece is moved in a straight line in any of eight directions,\n"
556                     "(similar to a queen's move in chess), but must be moved exactly the same\n"
557                     "number of spaces as there are pieces (of either color) in the row, column,\n"
558                     "or diagonal of the move. A piece may jump over pieces of its own color, but\n"
559                     "may not jump a piece of the opposite color. The final square of the move can\n"
560                     "be either empty or can contain a piece of the opposing color, in which case\n"
561                     "that piece is removed from the game.\n"
562                     "\n"
563                     "If a player has no possible move, then that player must pass, (but if the\n"
564                     "player has a possible move, then the player cannot pass).\n"
565                     "\n"
566                     "The goal of the game is to connect all of your remaining pieces into\n"
567                     "a single, connected group. Pieces that are diagonally adjacent are\n"
568                     "considered connected.\n"
569                     "\n"
570                     "If a move simultaneously creates a winning condition for both players, this\n"
571                     "is considered a win for the player making the move.\n"
572                     "\n"
573                     "Notes on this implementation:\n"
574                     "\n"
575                     "This implementation enforces the move rules described above, but will\n"
576                     "allow any person to make moves, (that is, you can control both\n"
577                     "colors). Think of it as being somewhat like a physical board where\n"
578                     "any person could move the pieces at any time, but generally two people\n"
579                     "will take turns and others will politely watch.\n"
580                     "\n"
581                     "Also, the game won't currently show you the board again after a\n"
582                     "player makes a move, so you'll need to keep typing 'show' to see\n"
583                     "updates. Yes, this is a bug, and yes it will be fixed soon.\n"
584                     "\n"
585                     "Lines of Action was invented by Claude Soucie and first made popular\n"
586                     "when its rules were published by Sid Sackson in \"A Gamut of Games\" (1969).\n");
587 }
588
589 static void
590 loa_game_handle_new (loa_game_t *game, const char *peer)
591 {
592     loudgame_broadcastf (&game->lg, "%s has started a new game", peer);
593     loa_game_new_game (game);
594 }
595
596 static void
597 loa_game_handle_message (loudgame_t *lg,
598                          const char *peer,
599                          const char *message)
600 {
601     loa_game_t *game = (loa_game_t *) lg;
602
603     if (strcmp (message, "show") == 0)
604         loa_game_handle_show (game, peer);
605     else if (strncmp (message, "move", 4) == 0)
606         loa_game_handle_move (game, peer, message + 4);
607     else if (strcmp (message, "pass") == 0)
608         loa_game_handle_pass (game, peer);
609     else if (strcmp (message, "new") == 0)
610         loa_game_handle_new (game, peer);
611     else if (strcmp (message, "help") == 0)
612         loa_game_handle_help (game, peer);
613     else if (strcmp (message, "rules") == 0)
614         loa_game_handle_rules (game, peer);
615     else
616         loudgame_sendf (lg, peer, "Unknown command: '%s'. Use 'help' to get a list of valid commands.", message);
617 }
618
619 static int
620 loa_game_init (loa_game_t *game, int argc, char *argv[])
621 {
622     int err;
623
624     err = loudgame_init (&game->lg, argc, argv);
625     if (err)
626         return err;
627
628     loa_game_new_game (game);
629
630     return 0;
631 }
632
633 int
634 main (int argc, char **argv)
635 {
636     loa_game_t game;
637     int err;
638
639     err = loa_game_init (&game, argc, argv);
640     if (err)
641         return err;
642
643     game.lg.handle_message = loa_game_handle_message;
644
645     err = loudgame_run (&game.lg);
646     if (err)
647         return err;
648
649     return 0;
650 }