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