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 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 (x,y)
  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(int y, 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(int y, 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(int y, 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 /* helper function to set a correct value at the (y, x) coordinates in the pawns array */
  97 void set_pawn(int y, int x, unsigned int type, unsigned int pawn_array[board_size][board_size]) {
  98
  99     if (type > 0 && type < 3 && \
 100             is_valid_coordinates(y, x)) {
 101         pawn_array[y-1][x-1] = type;
 102     } //FIXME: else case should set invalid values to permit to catch errors
 103 }
 104
 105 /* reverse the pawn at (y, x) coordinates if it exists */
 106 static void reverse_pawn(int y, int x, unsigned int pawn_array[board_size][board_size]) {
 107
 108     if (is_box_type(y, x, pawn_array, black)) {
 109         set_pawn(y, x, white, pawn_array);
 110     } else if (is_box_type(y, x, pawn_array, white)) {
 111         set_pawn(y, x, black, pawn_array);
 112     }
 113 }
 114
 115 void zero_pawns(unsigned int pawn_array[board_size][board_size]) {
 116
 117     for (int i = 1; i <= board_size; i++) {
 118         for (int j = 1; j <= board_size; j++) {
 119             set_pawn(i, j, empty, pawn_array);
 120          }
 121     }
 122 }
 123
 124 /* set the pawns in the start position */
 125 void init_pawns(unsigned int pawn_array[board_size][board_size]) {
 126
 127     /* the 2D array zeroing is not necessary if it is properly initialized to zero */
 128     zero_pawns(pawn_array);
 129     set_pawn(5, 4, black, pawn_array);
 130     set_pawn(4, 5, black, pawn_array);
 131     set_pawn(4, 4, white, pawn_array);
 132     set_pawn(5, 5, white, pawn_array);
 133 }
 134
 135 unsigned int count_pawns_type(unsigned int pawn_array[board_size][board_size], unsigned int type) {
 136     unsigned int count = 0;
 137
 138     if (type > 2) {
 139         return 0;
 140     }
 141     for (int i = 1; i <= board_size; i++) {
 142         for (int j = 1; j <= board_size; j++) {
 143             if (is_box_type(i, j, pawn_array, type)) {
 144                 count++;
 145             }
 146         }
 147     }
 148     return count;
 149 }
 150
 151 static void direction_to_coordinates(unsigned int direction, int* start_y, int* start_x) {
 152
 153     if (direction == north) {
 154         *start_y = *start_y - 1;
 155     } else if (direction == north_east) {
 156         *start_y = *start_y - 1;
 157         *start_x = *start_x + 1;
 158     } else if (direction == east) {
 159         *start_x = *start_x + 1;
 160     } else if (direction == south_east) {
 161         *start_y = *start_y + 1;
 162         *start_x = *start_x + 1;
 163     } else if (direction == south) {
 164         *start_y = *start_y + 1;
 165     } else if (direction == south_west) {
 166         *start_y = *start_y + 1;
 167         *start_x = *start_x - 1;
 168     } else if (direction == west) {
 169         *start_x = *start_x - 1;
 170     } else if (direction == north_west) {
 171         *start_y = *start_y - 1;
 172         *start_x = *start_x - 1;
 173     }
 174 }
 175
 176 bool is_board_full(unsigned int pawn_array[board_size][board_size]) {
 177
 178     /* an alternate method is to test the round count vs. 60 */
 179     for (int i = 1; i <= board_size; i++) {
 180         for (int j = 1; j <= board_size; j++) {
 181             if (is_box_type(i, j, pawn_array , empty)) {
 182                 return false;
 183             }
 184         }
 185     }
 186     return true;
 187 }
 188
 189 unsigned int eval_winner(unsigned int nb_white, unsigned int nb_black) {
 190
 191     if (nb_white > nb_black) {
 192         return player_two;
 193     } else if (nb_white < nb_black) {
 194         return player_one;
 195     } else {
 196         return 0;
 197     }
 198 }
 199
 200 static unsigned int count_pawn_to_reverse_one_direction(int y, int x, int direction, unsigned int current_player, unsigned int pawn_array[board_size][board_size]) {
 201     unsigned int nb_pawns_reversed = 0;
 202     int moving_y = y, moving_x = x;
 203
 204     /* count the pawns to reverse in the chosen direction */
 205     direction_to_coordinates(direction, &moving_y, &moving_x);
 206     while (true) {
 207         if (!is_valid_coordinates(moving_y, moving_x) || is_box_type(moving_y, moving_x, pawn_array, empty)) {
 208             return 0;
 209         }
 210         if (is_box_type(moving_y, moving_x, pawn_array, current_player)) {
 211             break;
 212         }
 213         nb_pawns_reversed++;
 214         direction_to_coordinates(direction, &moving_y, &moving_x);
 215     }
 216     return nb_pawns_reversed;
 217 }
 218
 219 /* revert the pawns if needed in one direction */
 220 static unsigned int reverse_one_direction(int y, int x, int direction, unsigned int current_player, unsigned int pawn_array[board_size][board_size], bool dry_run) {
 221     unsigned int nb_pawns_reversed = 0;
 222     int moving_y = y, moving_x = x;
 223
 224     nb_pawns_reversed = count_pawn_to_reverse_one_direction(moving_y, moving_x, direction, current_player, pawn_array);
 225
 226     /* now reverse the needed pawns */
 227     if (nb_pawns_reversed > 0 && !dry_run) {
 228         moving_y = y, moving_x = x;
 229         direction_to_coordinates(direction, &moving_y, &moving_x);
 230         while (!is_box_type(moving_y, moving_x, pawn_array, current_player)) {
 231             reverse_pawn(moving_y, moving_x, pawn_array);
 232             direction_to_coordinates(direction, &moving_y, &moving_x);
 233         }
 234     }
 235     return nb_pawns_reversed;
 236 }
 237
 238 /* loop optimized version of valid_shot function changing nothing to the pawns 2D array */
 239 bool is_legal_shot(int y, int x, unsigned int current_player, unsigned int pawn_array[board_size][board_size]) {
 240     unsigned int nb_pawns_reversed = 0;
 241
 242     if (!is_valid_coordinates(y, x) || !is_box_type(y, x, pawn_array, empty)) {
 243         return false;
 244     }
 245
 246     for (unsigned int direction = north; direction <= north_west; direction++) {
 247         nb_pawns_reversed += reverse_one_direction(y, x, direction, current_player, pawn_array, true);
 248         if (nb_pawns_reversed > 0) {
 249             return true;
 250         }
 251     }
 252     return false;
 253 }
 254
 255 /* play the shot if legal and flip or reverse the necessary pawns */
 256 unsigned int valid_shot(int y, int x, unsigned int current_player, unsigned int pawn_array[board_size][board_size]) {
 257     unsigned int nb_pawns_reversed = 0;
 258
 259     if (!is_valid_coordinates(y, x) || !is_box_type(y, x, pawn_array, empty)) {
 260         return 0;
 261     }
 262
 263     for (unsigned int direction = north; direction <= north_west; direction++) {
 264         nb_pawns_reversed += reverse_one_direction(y, x, direction, current_player, pawn_array, false);
 265     }
 266
 267     if (nb_pawns_reversed == 0) {
 268         return nb_pawns_reversed;
 269     }
 270
 271     set_pawn(y, x, current_player, pawn_array);
 272     return nb_pawns_reversed;
 273 }
 274
 275 static void add_shots_list_cell(int y, int x, unsigned int type, struct shots_list_s* shots_list) {
 276     struct shots_list_s* list_cell = (struct shots_list_s*)malloc(sizeof(struct shots_list_s));
 277     if (!list_cell) {
 278         exit(EXIT_FAILURE);
 279     }
 280
 281     if (type > 0 && type < 5 && is_valid_coordinates(y, x)) {
 282         list_cell->y = y;
 283         list_cell->x = x;
 284         list_cell->type = type;
 285         list_add_tail(&(list_cell->list), &(shots_list->list));
 286     }
 287 }
 288
 289 void free_shots_list(struct shots_list_s* shots_list) {
 290     struct shots_list_s* list_counter;
 291
 292     while (!list_empty(&shots_list->list)) {
 293         list_counter = list_entry(shots_list->list.next, struct shots_list_s, list);
 294         list_del(&(list_counter->list));
 295         free(list_counter);
 296     }
 297
 298 }
 299
 300 void build_playable_shots_list(unsigned int current_player, struct shots_list_s* shots_list, unsigned int pawn_array[board_size][board_size]) {
 301
 302     for (unsigned int i = 0; i <= board_size; i++) {
 303         for (unsigned int j = 0; j <= board_size; j++) {
 304             if (is_legal_shot(i, j, current_player, pawn_array)) {
 305                 add_shots_list_cell(i, j, hint_allowed, shots_list);
 306             /* FIXME: a neighbourhood detection is needed
 307             } else if (is_box_type(i, j, pawn_array, empty)){
 308                 add_shots_list_cell(i, j, hint_forbidden, shots_list);
 309             */
 310             }
 311         }
 312     }
 313 }