lib/othello.c

   1 /*
   2  * =====================================================================================
   3  *
   4  *       Filename:  othello.c
   5  *
   6  *    Description:  Handle the othello board content
   7  *
   8  *        Version:  1.0
   9  *        Created:  25/04/2017 15:16:08
  10  *       Revision:  none
  11  *       Compiler:  gcc
  12  *
  13  *         Author:  Jerome Benoit (fraggle), jerome.benoit@piment-noir.org
  14  *   Organization:  Piment Noir
  15  *
  16  * =====================================================================================
  17  */
  18
  19 #include <stdlib.h>
  20 #include <stdbool.h>
  21 #include <string.h>
  22
  23 #include "othello.h"
  24 #include "debug.h"
  25
  26 /**
  27  * Get current round player integer
  28  * @param  round_count current round integer
  29  * @return             current round player
  30  */
  31 unsigned int current_player(unsigned int round_count) {
  32
  33     if (round_count % 2 != 0) {
  34         return player_two;
  35     } else {
  36         return player_one;
  37     }
  38 }
  39
  40 /**
  41  * Get current round opponent integer
  42  * @param  current_player current round player
  43  * @return                current round opponent integer
  44  */
  45 static unsigned int current_opponent(unsigned int current_player) {
  46
  47     if (current_player == player_one) {
  48         return player_two;
  49     } else {
  50         return player_one;
  51     }
  52 }
  53
  54 /* for consistency with ncurses, the board coordinates are in the following order:
  55  * O--x-->
  56  * |
  57  * y
  58  * |
  59  * v
  60  * The origin O has (1, 1) coordinates */
  61
  62 /**
  63  * Get pawn value at coordinates (y,x)
  64  * @param  y          y coordinate
  65  * @param  x          x coordinate
  66  * @param  pawn_array array of played pawns
  67  * @return            pawn integer type
  68  */
  69 unsigned int get_box_value(unsigned int y, unsigned int x, unsigned int pawn_array[board_size][board_size]) {
  70
  71     return pawn_array[y-1][x-1];
  72 }
  73
  74 bool is_box_type(unsigned int y, unsigned int x, unsigned int pawn_array[board_size][board_size], unsigned int type) {
  75
  76     if (type > 2) {
  77         return NULL;
  78     }
  79     if (get_box_value(y, x, pawn_array) == type) {
  80         return true;
  81     } else {
  82         return false;
  83     }
  84 }
  85
  86 static bool is_valid_coordinates(unsigned int y, unsigned int x) {
  87
  88     if ((y > 0 && y < board_size + 1) && \
  89             (x > 0 && x < board_size + 1)) {
  90         return true;
  91     } else {
  92         return false;
  93     }
  94 }
  95
  96 /**
  97  * Helper function to set a correct value at the (y,x) coordinates in the pawns array
  98  * @param y      [description]
  99  * @param x      [description]
 100  * @param type   [description]
 101  * @param pawn_array [description]
 102  */
 103 void set_pawn(unsigned int y, unsigned int x, unsigned int type, unsigned int pawn_array[board_size][board_size]) {
 104
 105     if (type > 0 && type < 3 && \
 106             is_valid_coordinates(y, x)) {
 107         pawn_array[y-1][x-1] = type;
 108     } //FIXME: else case should set invalid values to permit to catch errors
 109 }
 110
 111 /* reverse the pawn at (y, x) coordinates if it exists */
 112 static void reverse_pawn(unsigned int y, unsigned int x, unsigned int pawn_array[board_size][board_size]) {
 113
 114     if (is_box_type(y, x, pawn_array, black)) {
 115         set_pawn(y, x, white, pawn_array);
 116     } else if (is_box_type(y, x, pawn_array, white)) {
 117         set_pawn(y, x, black, pawn_array);
 118     }
 119 }
 120
 121 void zero_pawns(unsigned int pawn_array[board_size][board_size]) {
 122
 123     for (unsigned int i = 1; i <= board_size; i++) {
 124         for (unsigned int j = 1; j <= board_size; j++) {
 125             set_pawn(i, j, empty, pawn_array);
 126          }
 127     }
 128 }
 129
 130 /**
 131  * Set the pawns in the start position
 132  * @param pawn_array array of played pawns
 133  */
 134 void init_pawns(unsigned int pawn_array[board_size][board_size]) {
 135
 136     /* the 2D array zeroing is not necessary if it is properly initialized to zero */
 137     zero_pawns(pawn_array);
 138     set_pawn(5, 4, black, pawn_array);
 139     set_pawn(4, 5, black, pawn_array);
 140     set_pawn(4, 4, white, pawn_array);
 141     set_pawn(5, 5, white, pawn_array);
 142 }
 143
 144 unsigned int count_pawns_type(unsigned int pawn_array[board_size][board_size], unsigned int type) {
 145     unsigned int count = 0;
 146
 147     if (type > 2) {
 148         return 0;
 149     }
 150     for (unsigned int i = 1; i <= board_size; i++) {
 151         for (unsigned int j = 1; j <= board_size; j++) {
 152             if (is_box_type(i, j, pawn_array, type)) {
 153                 count++;
 154             }
 155         }
 156     }
 157     return count;
 158 }
 159
 160 static void direction_to_coordinates(unsigned int direction, unsigned int* start_y, unsigned int* start_x) {
 161
 162     if (direction == north) {
 163         *start_y = *start_y - 1;
 164     } else if (direction == north_east) {
 165         *start_y = *start_y - 1;
 166         *start_x = *start_x + 1;
 167     } else if (direction == east) {
 168         *start_x = *start_x + 1;
 169     } else if (direction == south_east) {
 170         *start_y = *start_y + 1;
 171         *start_x = *start_x + 1;
 172     } else if (direction == south) {
 173         *start_y = *start_y + 1;
 174     } else if (direction == south_west) {
 175         *start_y = *start_y + 1;
 176         *start_x = *start_x - 1;
 177     } else if (direction == west) {
 178         *start_x = *start_x - 1;
 179     } else if (direction == north_west) {
 180         *start_y = *start_y - 1;
 181         *start_x = *start_x - 1;
 182     }
 183 }
 184
 185 bool is_board_full(unsigned int pawn_array[board_size][board_size]) {
 186
 187     /* an alternate method is to test the round count vs. 60 */
 188     for (unsigned int i = 1; i <= board_size; i++) {
 189         for (unsigned int j = 1; j <= board_size; j++) {
 190             if (is_box_type(i, j, pawn_array , empty)) {
 191                 return false;
 192             }
 193         }
 194     }
 195     return true;
 196 }
 197
 198 unsigned int eval_winner(unsigned int nb_white, unsigned int nb_black) {
 199
 200     if (nb_white > nb_black) {
 201         return player_two;
 202     } else if (nb_white < nb_black) {
 203         return player_one;
 204     } else {
 205         return 0;
 206     }
 207 }
 208
 209 static unsigned int count_pawn_to_reverse_one_direction(unsigned int y, unsigned int x, unsigned int direction, unsigned int current_player, unsigned int pawn_array[board_size][board_size]) {
 210     unsigned int nb_pawns_reversed = 0;
 211     unsigned int moving_y = y, moving_x = x;
 212
 213     /* count the pawns to reverse in the chosen direction */
 214     direction_to_coordinates(direction, &moving_y, &moving_x);
 215     while (true) {
 216         if (!is_valid_coordinates(moving_y, moving_x) || is_box_type(moving_y, moving_x, pawn_array, empty)) {
 217             return 0;
 218         }
 219         if (is_box_type(moving_y, moving_x, pawn_array, current_player)) {
 220             break;
 221         }
 222         nb_pawns_reversed++;
 223         direction_to_coordinates(direction, &moving_y, &moving_x);
 224     }
 225     return nb_pawns_reversed;
 226 }
 227
 228 /* revert the pawns if needed in one direction */
 229 static unsigned int reverse_one_direction(unsigned int y, unsigned int x, unsigned int direction, unsigned int current_player, unsigned int pawn_array[board_size][board_size], bool dry_run) {
 230     unsigned int nb_pawns_reversed = 0;
 231     unsigned int moving_y = y, moving_x = x;
 232
 233     nb_pawns_reversed = count_pawn_to_reverse_one_direction(moving_y, moving_x, direction, current_player, pawn_array);
 234
 235     /* now reverse the needed pawns */
 236     if (nb_pawns_reversed > 0 && !dry_run) {
 237         moving_y = y, moving_x = x;
 238         direction_to_coordinates(direction, &moving_y, &moving_x);
 239         while (!is_box_type(moving_y, moving_x, pawn_array, current_player)) {
 240             reverse_pawn(moving_y, moving_x, pawn_array);
 241             direction_to_coordinates(direction, &moving_y, &moving_x);
 242         }
 243     }
 244     return nb_pawns_reversed;
 245 }
 246
 247 /* loop optimized version of valid_shot function changing nothing to the pawns 2D array */
 248 bool is_legal_shot(unsigned int y, unsigned int x, unsigned int current_player, unsigned int pawn_array[board_size][board_size]) {
 249     unsigned int nb_pawns_reversed = 0;
 250
 251     if (!is_valid_coordinates(y, x) || !is_box_type(y, x, pawn_array, empty)) {
 252         return false;
 253     }
 254
 255     for (unsigned int direction = north; direction <= north_west; direction++) {
 256         nb_pawns_reversed += reverse_one_direction(y, x, direction, current_player, pawn_array, true);
 257         if (nb_pawns_reversed > 0) {
 258             return true;
 259         }
 260     }
 261     return false;
 262 }
 263
 264 /* play the shot if legal and flip or reverse the necessary pawns */
 265 unsigned int valid_shot(unsigned int y, unsigned int x, unsigned int current_player, unsigned int pawn_array[board_size][board_size]) {
 266     unsigned int nb_pawns_reversed = 0;
 267
 268     if (!is_valid_coordinates(y, x) || !is_box_type(y, x, pawn_array, empty)) {
 269         return 0;
 270     }
 271
 272     for (unsigned int direction = north; direction <= north_west; direction++) {
 273         nb_pawns_reversed += reverse_one_direction(y, x, direction, current_player, pawn_array, false);
 274     }
 275
 276     if (nb_pawns_reversed == 0) {
 277         return nb_pawns_reversed;
 278     }
 279
 280     set_pawn(y, x, current_player, pawn_array);
 281     return nb_pawns_reversed;
 282 }
 283
 284 static void add_shots_list_cell(unsigned int y, unsigned int x, unsigned int type, struct shots_list_s* shots_list) {
 285     struct shots_list_s* list_cell = (struct shots_list_s*)malloc(sizeof(struct shots_list_s));
 286     if (!list_cell) {
 287         exit(EXIT_FAILURE);
 288     }
 289
 290     if (type > 0 && type < 5 && is_valid_coordinates(y, x)) {
 291         list_cell->y = y;
 292         list_cell->x = x;
 293         list_cell->type = type;
 294         list_add_tail(&(list_cell->list), &(shots_list->list));
 295     }
 296 }
 297
 298 void free_shots_list(struct shots_list_s* shots_list) {
 299     struct shots_list_s* list_counter;
 300
 301     while (!list_empty(&shots_list->list)) {
 302         list_counter = list_entry(shots_list->list.next, struct shots_list_s, list);
 303         list_del(&(list_counter->list));
 304         free(list_counter);
 305     }
 306 }
 307
 308 void build_playable_shots_list(unsigned int current_player, struct shots_list_s* shots_list, unsigned int pawn_array[board_size][board_size]) {
 309
 310     for (unsigned int i = 0; i <= board_size; i++) {
 311         for (unsigned int j = 0; j <= board_size; j++) {
 312             if (is_legal_shot(i, j, current_player, pawn_array)) {
 313                 add_shots_list_cell(i, j, hint_allowed, shots_list);
 314             /* FIXME: a neighbourhood detection is needed
 315             } else if (is_box_type(i, j, pawn_array, empty)){
 316                 add_shots_list_cell(i, j, hint_forbidden, shots_list);
 317             */
 318             }
 319         }
 320     }
 321 }