From 54f1c58cef6764fdd611eedc267e7491e777c09b Mon Sep 17 00:00:00 2001 From: =?utf8?q?J=C3=A9r=C3=B4me=20Benoit?= Date: Thu, 27 Apr 2017 22:03:30 +0200 Subject: [PATCH] Fix an off-by-one on the pawn 2D array indexes. MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit Signed-off-by: Jérôme Benoit --- analyse_descendante | 10 +- lib/constants.h | 1 - lib/debug.c | 26 +++++ lib/debug.h | 21 ++++ lib/list.h | 244 ++++++++++++++++++++++++++++++++++++++++++++ lib/othello.c | 56 ++++++++-- lib/othello.h | 9 +- lib/ui.c | 26 +++-- src/main.c | 23 +++-- 9 files changed, 386 insertions(+), 30 deletions(-) create mode 100644 lib/debug.c create mode 100644 lib/debug.h create mode 100644 lib/list.h diff --git a/analyse_descendante b/analyse_descendante index 4f00777..2baa9bc 100644 --- a/analyse_descendante +++ b/analyse_descendante @@ -38,10 +38,18 @@ JOUEUR_NOIR ? JOUEUR_BLANC ? --> Modules: +->Modules: main: othello.{c,h} ia: ia.{c,h} (MinMax, fcts d'évaluation, ...) IHM: ihm.{c,h} (affichage de l'othellier, saisie d'un coup, entrée au clavier, ...) coups: coups.{c.h} (coups jouables) regle: regle.{c,h} (implantation des règles du jeu) constantes: constantes.h (les constantes) + +->Exploration dans une direction (i, j): +Si hors_othellier ou case vide + alors Rien; +Sinon si case contient un pion adverse + alors continuer l'exploration dans la même direction; +Sinon si case contient pion du joueur + alors les pions adverses vus précédement doivent être retournés diff --git a/lib/constants.h b/lib/constants.h index aa6bc51..bc15fd1 100644 --- a/lib/constants.h +++ b/lib/constants.h @@ -29,7 +29,6 @@ extern const unsigned int black; /* 2 */ extern const unsigned int player_one; /* black */ extern const unsigned int player_two; /* white */ - extern const unsigned int hint_allowed; /* legal place for a pawn */ extern const unsigned int hint_forbidden; /* illegal place for a pawn */ diff --git a/lib/debug.c b/lib/debug.c new file mode 100644 index 0000000..e322990 --- /dev/null +++ b/lib/debug.c @@ -0,0 +1,26 @@ +/* + * ===================================================================================== + * + * Filename: debug.c + * + * Description: Debugging functions + * + * Version: 1.0 + * Created: 27/04/2017 12:58:37 + * Revision: none + * Compiler: gcc + * + * Author: Jerome Benoit (fraggle), jerome.benoit@piment-noir.org + * Organization: Piment Noir + * + * ===================================================================================== + */ + +#include + +#include "debug.h" + +void dbg_mvprintw(int base_y, int base_x, const char* fmt, va_list varglist) { + + mvprintw(base_y, base_x - strlen(fmt)/2, fmt, varglist); +} diff --git a/lib/debug.h b/lib/debug.h new file mode 100644 index 0000000..eb6c64e --- /dev/null +++ b/lib/debug.h @@ -0,0 +1,21 @@ +/* + * ===================================================================================== + * + * Filename: debug.h + * + * Description: Header for debugging functions + * + * Version: 1.0 + * Created: 27/04/2017 13:01:31 + * Revision: none + * Compiler: gcc + * + * Author: Jerome Benoit (fraggle), jerome.benoit@piment-noir.org + * Organization: Piment Noir + * + * ===================================================================================== + */ + +#include + +void dbg_mvprintw(int base_y, int base_x, const char* fmt, va_list varglist); diff --git a/lib/list.h b/lib/list.h new file mode 100644 index 0000000..3a76885 --- /dev/null +++ b/lib/list.h @@ -0,0 +1,244 @@ +#ifndef __LIST_H +#define __LIST_H + +/* This file is from Linux Kernel (include/linux/list.h) + * and modified by simply removing hardware prefetching of list items. + * Here by copyright, credits attributed to wherever they belong. + * Kulesh Shanmugasundaram (kulesh [squiggly] isis.poly.edu) + */ + +/* + * Simple doubly linked list implementation. + * + * Some of the internal functions ("__xxx") are useful when + * manipulating whole lists rather than single entries, as + * sometimes we already know the next/prev entries and we can + * generate better code by using them directly rather than + * using the generic single-entry routines. + */ + +struct list_head { + struct list_head *next, *prev; +}; + +#define LIST_HEAD_INIT(name) { &(name), &(name) } + +#define LIST_HEAD(name) \ + struct list_head name = LIST_HEAD_INIT(name) + +#define INIT_LIST_HEAD(ptr) do { \ + (ptr)->next = (ptr); (ptr)->prev = (ptr); \ +} while (0) + +/* + * Insert a new entry between two known consecutive entries. + * + * This is only for internal list manipulation where we know + * the prev/next entries already! + */ +static inline void __list_add(struct list_head *new, + struct list_head *prev, + struct list_head *next) +{ + next->prev = new; + new->next = next; + new->prev = prev; + prev->next = new; +} + +/** + * list_add - add a new entry + * @new: new entry to be added + * @head: list head to add it after + * + * Insert a new entry after the specified head. + * This is good for implementing stacks. + */ +static inline void list_add(struct list_head *new, struct list_head *head) +{ + __list_add(new, head, head->next); +} + +/** + * list_add_tail - add a new entry + * @new: new entry to be added + * @head: list head to add it before + * + * Insert a new entry before the specified head. + * This is useful for implementing queues. + */ +static inline void list_add_tail(struct list_head *new, struct list_head *head) +{ + __list_add(new, head->prev, head); +} + +/* + * Delete a list entry by making the prev/next entries + * point to each other. + * + * This is only for internal list manipulation where we know + * the prev/next entries already! + */ +static inline void __list_del(struct list_head *prev, struct list_head *next) +{ + next->prev = prev; + prev->next = next; +} + +/** + * list_del - deletes entry from list. + * @entry: the element to delete from the list. + * Note: list_empty on entry does not return true after this, the entry is in an undefined state. + */ +static inline void list_del(struct list_head *entry) +{ + __list_del(entry->prev, entry->next); + entry->next = (void *) 0; + entry->prev = (void *) 0; +} + +/** + * list_del_init - deletes entry from list and reinitialize it. + * @entry: the element to delete from the list. + */ +static inline void list_del_init(struct list_head *entry) +{ + __list_del(entry->prev, entry->next); + INIT_LIST_HEAD(entry); +} + +/** + * list_move - delete from one list and add as another's head + * @list: the entry to move + * @head: the head that will precede our entry + */ +static inline void list_move(struct list_head *list, struct list_head *head) +{ + __list_del(list->prev, list->next); + list_add(list, head); +} + +/** + * list_move_tail - delete from one list and add as another's tail + * @list: the entry to move + * @head: the head that will follow our entry + */ +static inline void list_move_tail(struct list_head *list, + struct list_head *head) +{ + __list_del(list->prev, list->next); + list_add_tail(list, head); +} + +/** + * list_empty - tests whether a list is empty + * @head: the list to test. + */ +static inline int list_empty(struct list_head *head) +{ + return head->next == head; +} + +static inline void __list_splice(struct list_head *list, + struct list_head *head) +{ + struct list_head *first = list->next; + struct list_head *last = list->prev; + struct list_head *at = head->next; + + first->prev = head; + head->next = first; + + last->next = at; + at->prev = last; +} + +/** + * list_splice - join two lists + * @list: the new list to add. + * @head: the place to add it in the first list. + */ +static inline void list_splice(struct list_head *list, struct list_head *head) +{ + if (!list_empty(list)) + __list_splice(list, head); +} + +/** + * list_splice_init - join two lists and reinitialise the emptied list. + * @list: the new list to add. + * @head: the place to add it in the first list. + * + * The list at @list is reinitialised + */ +static inline void list_splice_init(struct list_head *list, + struct list_head *head) +{ + if (!list_empty(list)) { + __list_splice(list, head); + INIT_LIST_HEAD(list); + } +} + +/** + * list_entry - get the struct for this entry + * @ptr: the &struct list_head pointer. + * @type: the type of the struct this is embedded in. + * @member: the name of the list_struct within the struct. + */ +#define list_entry(ptr, type, member) \ + ((type *)((char *)(ptr)-(unsigned long)(&((type *)0)->member))) + +/** + * list_for_each - iterate over a list + * @pos: the &struct list_head to use as a loop counter. + * @head: the head for your list. + */ +#define list_for_each(pos, head) \ + for (pos = (head)->next; pos != (head); \ + pos = pos->next) +/** + * list_for_each_prev - iterate over a list backwards + * @pos: the &struct list_head to use as a loop counter. + * @head: the head for your list. + */ +#define list_for_each_prev(pos, head) \ + for (pos = (head)->prev; pos != (head); \ + pos = pos->prev) + +/** + * list_for_each_safe - iterate over a list safe against removal of list entry + * @pos: the &struct list_head to use as a loop counter. + * @n: another &struct list_head to use as temporary storage + * @head: the head for your list. + */ +#define list_for_each_safe(pos, n, head) \ + for (pos = (head)->next, n = pos->next; pos != (head); \ + pos = n, n = pos->next) + +/** + * list_for_each_entry - iterate over list of given type + * @pos: the type * to use as a loop counter. + * @head: the head for your list. + * @member: the name of the list_struct within the struct. + */ +#define list_for_each_entry(pos, head, member) \ + for (pos = list_entry((head)->next, typeof(*pos), member); \ + &pos->member != (head); \ + pos = list_entry(pos->member.next, typeof(*pos), member)) + +/** + * list_for_each_entry_safe - iterate over list of given type safe against removal of list entry + * @pos: the type * to use as a loop counter. + * @n: another type * to use as temporary storage + * @head: the head for your list. + * @member: the name of the list_struct within the struct. + */ +#define list_for_each_entry_safe(pos, n, head, member) \ + for (pos = list_entry((head)->next, typeof(*pos), member), \ + n = list_entry(pos->member.next, typeof(*pos), member); \ + &pos->member != (head); \ + pos = n, n = list_entry(n->member.next, typeof(*n), member)) + + +#endif diff --git a/lib/othello.c b/lib/othello.c index 02eac9d..b576894 100644 --- a/lib/othello.c +++ b/lib/othello.c @@ -31,15 +31,16 @@ unsigned int current_player(unsigned int round_count) { } /* for consitency with ncurses, the board coordinates are in the following order: - * --x--> + * O-x--> * | * y * | - * v */ + * v + * The origin O has (1, 1) coordinates */ unsigned int get_box_value(int y, int x, unsigned int pawn_array[board_size][board_size]) { - return pawn_array[y][x]; + return pawn_array[y-1][x-1]; } bool is_box_type(int y, int x, unsigned int pawn_array[board_size][board_size], unsigned int type) { @@ -58,7 +59,7 @@ bool is_box_type(int y, int x, unsigned int pawn_array[board_size][board_size], int** set_pawn(int y, int x, unsigned int type, unsigned int pawn_array[board_size][board_size]) { if (is_box_type(y, x, pawn_array, empty)) { - pawn_array[y][x] = type; + pawn_array[y-1][x-1] = type; return pawn_array; } else { return NULL; @@ -66,8 +67,9 @@ int** set_pawn(int y, int x, unsigned int type, unsigned int pawn_array[board_si } static int** zero_pawns(unsigned int pawn_array[board_size][board_size]) { - for (unsigned int i = 0; i < board_size; i++) { - for (unsigned int j = 0; j < board_size; j++) { + + for (unsigned int i = 1; i <= board_size; i++) { + for (unsigned int j = 1; j <= board_size; j++) { pawn_array = set_pawn(i, j, empty, pawn_array); } } @@ -91,12 +93,48 @@ unsigned int count_pawn_type(unsigned int pawn_array[board_size][board_size], un if (type > 2) { return -1; } - for (unsigned int i = 0; i < board_size; i++) { - for (unsigned int j = 0; j < board_size; j++) { - if (pawn_array[i][j] == type) { + for (unsigned int i = 1; i <= board_size; i++) { + for (unsigned int j = 1; j <= board_size; j++) { + if (get_box_value(i, j, pawn_array) == type) { count++; } } } return count; } + +bool is_valid_input(int y, int x, unsigned int pawn_array[board_size][board_size]) { + + /* FIXME: separate the tests to permit to print explicit error messages */ + if ((y > 0 && y < board_size + 1) && \ + (x > 0 && x < board_size + 1) && \ + is_box_type(y, x, pawn_array, empty)) { + return true; + } else { + return false; + } +} + +bool is_board_full(unsigned int pawn_array[board_size][board_size]) { + + for (unsigned int i = 1; i <= board_size; i++) { + for (unsigned int j = 1; j <= board_size; j++) { + if (is_box_type(i, j, pawn_array , empty)) { + return false; + } + } + } + return true; +} + +void status_pawn(int y, int x, unsigned int pawn_array[board_size][board_size]) { + +} + +bool is_legal_box(int y, int x, int player, unsigned int pawn_array[board_size][board_size]) { + +} + +bool reverse_box(unsigned int pawn_array[board_size][board_size]) { + +} diff --git a/lib/othello.h b/lib/othello.h index 628f8e1..62fb04a 100644 --- a/lib/othello.h +++ b/lib/othello.h @@ -20,15 +20,20 @@ #define OTHELLO_H #include "constants.h" +#include "list.h" -/* FIXME: declare and initialize the array here */ -//unsigned int pawns[board_size][board_size]; +struct shots_list { + struct list_head list; + unsigned int*** pawn_array_member; +}; unsigned int current_player(unsigned int round_count); int** init_pawns(unsigned int pawn_array[board_size][board_size]); +bool is_valid_input(int y, int x, unsigned int pawn_array[board_size][board_size]); bool is_box_type(int y, int x, unsigned int pawn_array[board_size][board_size], unsigned int type); +bool is_board_full(unsigned int pawn_array[board_size][board_size]); unsigned int get_box_value(int y, int x, unsigned int pawn_array[board_size][board_size]); int** set_pawn(int y, int x, unsigned int type, unsigned int pawn_array[board_size][board_size]); diff --git a/lib/ui.c b/lib/ui.c index 2673dc9..c75e3b0 100644 --- a/lib/ui.c +++ b/lib/ui.c @@ -19,6 +19,8 @@ #include #include "ui.h" +#include "othello.h" +#include "debug.h" /* in all print routine, y and x are the coordinates of the first character of the shape * which can be a space ' ' */ @@ -94,27 +96,30 @@ static int remap_y(int y) { if (y == 1) { return 2; - } else if (y > 1 && y < board_size + 1) { + } else if (y > 1 && y <= board_size) { return (remap_y(y - 1) + 3); + } else { + return -1; } - return -1; } static int remap_x(int x) { if (x == 1) { return 3; - } else if (x > 1 && x < board_size + 1) { + } else if (x > 1 && x <= board_size) { return (remap_x(x - 1) + 5); + } else { + return -1; } - return -1; } void print_pawns(int base_y, int base_x, unsigned int pawn_array[board_size][board_size]) { - for (unsigned int i = 0; i < board_size; i++) { - for (unsigned int j = 0; j < board_size; j++) { - if (pawn_array[i][j] != empty) { - print_o(base_y + remap_y(i), base_x + remap_x(j), pawn_array[i][j]); + + for (unsigned int i = 1; i <= board_size; i++) { + for (unsigned int j = 1; j <= board_size; j++) { + if (!is_box_type(i, j, pawn_array, empty)) { + print_o(base_y + remap_y(i), base_x + remap_x(j), get_box_value(i, j, pawn_array)); } } } @@ -138,12 +143,13 @@ int map_col_letter_to_int(char c) { return 7; } else if (c == 'h' || c == 'H') { return 8; + } else { + return -1; } - return -1; } int prompt_values(WINDOW* windows, int base_y, int base_x, const char* msg, int* y, char* x) { mvwprintw(windows, base_y, base_x, "%s\n", msg); - int retVal = mvwscanw(windows, base_y + 1, base_x, "%d%c", y, x); + int retVal = mvwscanw(windows, base_y + 1, base_x + strlen(msg)/2, "%d%c", y, x); return (retVal == 1) ? 0 : 1; } diff --git a/src/main.c b/src/main.c index 195bdbe..4f5e61d 100644 --- a/src/main.c +++ b/src/main.c @@ -5,6 +5,7 @@ #include "ui.h" #include "othello.h" +#include "debug.h" int main() { int row = 0, col = 0; @@ -13,6 +14,8 @@ int main() { bool exit_condition = false; unsigned int nb_white = 0, nb_black = 0; + LIST_HEAD(shots_list); + char* player_msg; unsigned int pawns[board_size][board_size] = {{}}; @@ -26,6 +29,7 @@ int main() { } start_color(); getmaxyx(stdscr, row, col); + /* FIXME: fail if the screen size is too small */ //noecho(); echo(); curs_set(0); @@ -41,7 +45,7 @@ int main() { print_board(board_center_y, board_center_x); print_pawns(board_center_y, board_center_x, pawns); - char* title_msg = "Jeu othello"; + char* title_msg = "Jeu Othello"; mvprintw(center_y - 26/2 - 4, (center_x - strlen(title_msg)/2), title_msg); nb_white = count_pawn_type(pawns, white); @@ -67,21 +71,26 @@ int main() { do { y = 0; x = ""; - char* prompt_msg = "Prochain pion ? - ligne colonne (chiffre lettre):"; - prompt_values(stdscr, center_y + 26/2 + 1, center_x - strlen(prompt_msg)/2, prompt_msg, &y, &x); - /* FIXME: separate the tests to permit to print explicit error messages */ - if (((y > 0 && y < board_size + 1) || \ - (map_col_letter_to_int(x) > 0 && map_col_letter_to_int(x) < board_size + 1)) \ - && is_box_type(y, x, pawns, empty)) { + char* prompt_msg = "Prochain pion ? (ligne colonne - chiffre lettre):"; + int prmt_rt = prompt_values(stdscr, center_y + 26/2 + 1, center_x - strlen(prompt_msg)/2, prompt_msg, &y, &x); + if (is_valid_input(y, map_col_letter_to_int(x), pawns) && prmt_rt == 1) { input_ok = true; } } while (!input_ok); pawns[board_size][board_size] = set_pawn(y, map_col_letter_to_int(x), player, pawns); + struct shots_list shot_current; + shot_current.pawn_array_member = &pawns[y-1][x-1]; + //list_add(shot_current.list, shots_list.list); round++; /* increment the round count */ refresh(); + if (is_board_full(pawns) || round == 60) { + /* print the winnner and the restart possibility */ + exit_condition = true; + } + } while (!exit_condition); endwin(); -- 2.34.1