board.c (5117B)
1 #include "hexes.h" 2 3 #define NEIGHBOUR_COUNT 6 4 5 extern inline segment_relptr_t 6 segment_abs2rel(void const *restrict base, struct segment *restrict absptr); 7 8 extern inline struct segment * 9 segment_rel2abs(void const *base, segment_relptr_t relptr); 10 11 static s8 neighbour_dx[NEIGHBOUR_COUNT] = { -1, -1, 0, 0, +1, +1, }; 12 static s8 neighbour_dy[NEIGHBOUR_COUNT] = { 0, +1, -1, +1, -1, 0, }; 13 14 struct segment * 15 segment_root(struct segment *self) 16 { 17 assert(self); 18 19 struct segment *parent, *grandparent; 20 while ((parent = segment_rel2abs(self, self->parent))) { 21 if (!(grandparent = segment_rel2abs(parent, parent->parent))) 22 return parent; 23 24 self->parent = segment_abs2rel(self, grandparent); 25 26 self = grandparent; 27 } 28 29 return self; 30 } 31 32 bool 33 segment_merge(struct segment *self, struct segment *elem) 34 { 35 assert(self); 36 assert(elem); 37 38 struct segment *self_root = segment_root(self); 39 struct segment *elem_root = segment_root(elem); 40 41 if (self_root == elem_root) return false; 42 43 if (self_root->rank <= elem_root->rank) { 44 self_root->parent = segment_abs2rel(self_root, elem_root); 45 } else if (self_root->rank > elem_root->rank) { 46 elem_root->parent = segment_abs2rel(elem_root, self_root); 47 } 48 49 /* disambiguate between self and element ranks */ 50 if (self_root->rank == elem_root->rank) elem_root->rank++; 51 52 return true; 53 } 54 55 extern inline struct segment * 56 board_black_source(struct board *self); 57 58 extern inline struct segment * 59 board_black_sink(struct board *self); 60 61 extern inline struct segment * 62 board_white_source(struct board *self); 63 64 extern inline struct segment * 65 board_white_sink(struct board *self); 66 67 bool 68 board_init(struct board *self, u32 size) 69 { 70 assert(self); 71 72 self->size = size; 73 74 size_t segments = (size * size) + _BOARD_EDGE_COUNT; 75 if (!(self->segments = malloc(segments * sizeof *self->segments))) 76 return false; 77 78 for (size_t i = 0; i < segments; i++) { 79 struct segment *segment = &self->segments[i]; 80 81 segment->occupant = CELL_EMPTY; 82 segment->rank = 0; 83 segment->parent = RELPTR_NULL; 84 } 85 86 struct segment *black_source = board_black_source(self); 87 struct segment *black_sink = board_black_sink(self); 88 struct segment *white_source = board_white_source(self); 89 struct segment *white_sink = board_white_sink(self); 90 91 black_source->occupant = black_sink->occupant = CELL_BLACK; 92 white_source->occupant = white_sink->occupant = CELL_WHITE; 93 94 return true; 95 } 96 97 void 98 board_free(struct board *self) 99 { 100 assert(self); 101 102 free(self->segments); 103 } 104 105 void 106 board_copy(struct board const *restrict self, struct board *restrict other) 107 { 108 assert(self); 109 assert(other); 110 111 assert(self->size == other->size); 112 113 size_t segments = (self->size * self->size) + _BOARD_EDGE_COUNT; 114 memcpy(other->segments, self->segments, segments * sizeof *self->segments); 115 } 116 117 bool 118 board_play(struct board *self, enum hex_player player, u32 x, u32 y) 119 { 120 assert(self); 121 122 struct segment *segment = &self->segments[y * self->size + x]; 123 124 if (segment->occupant != CELL_EMPTY) return false; 125 126 segment->occupant = (enum cell) player; 127 128 /* handle connection to source/sink for given player at edge of board 129 */ 130 if (player == HEX_PLAYER_BLACK) { 131 if (x == 0) 132 segment_merge(board_black_source(self), segment); 133 else if (x == self->size - 1) 134 segment_merge(board_black_sink(self), segment); 135 } else if (player == HEX_PLAYER_WHITE) { 136 if (y == 0) 137 segment_merge(board_white_source(self), segment); 138 else if (y == self->size - 1) 139 segment_merge(board_white_sink(self), segment); 140 } 141 142 /* handle connecting to neighbouring segments with same occupant 143 */ 144 for (size_t i = 0; i < NEIGHBOUR_COUNT; i++) { 145 s64 px = x + neighbour_dx[i]; 146 s64 py = y + neighbour_dy[i]; 147 148 if (0 <= px && px < self->size && 0 <= py && py < self->size) { 149 struct segment *neighbour = &self->segments[py * self->size + px]; 150 151 if (segment->occupant == neighbour->occupant) 152 segment_merge(segment, neighbour); 153 } 154 } 155 156 return true; 157 } 158 159 void 160 board_swap(struct board *self) 161 { 162 assert(self); 163 164 for (u32 j = 0; j < self->size; j++) { 165 for (u32 i = 0; i < self->size; i++) { 166 struct segment *segment = &self->segments[j * self->size + i]; 167 168 switch (segment->occupant) { 169 case CELL_BLACK: 170 segment->occupant = CELL_EMPTY; 171 board_play(self, HEX_PLAYER_WHITE, i, j); 172 break; 173 174 case CELL_WHITE: 175 segment->occupant = CELL_EMPTY; 176 board_play(self, HEX_PLAYER_BLACK, i, j); 177 break; 178 179 default: break; 180 } 181 } 182 } 183 } 184 185 size_t 186 board_available_moves(struct board const *self, struct move *buf) 187 { 188 assert(self); 189 190 size_t idx = 0; 191 for (u32 j = 0; j < self->size; j++) { 192 for (u32 i = 0; i < self->size; i++) { 193 if (self->segments[j * self->size + i].occupant == CELL_EMPTY) { 194 if (buf) { 195 buf[idx].x = i; 196 buf[idx].y = j; 197 } 198 199 idx++; 200 } 201 } 202 } 203 204 return idx; 205 } 206 207 bool 208 board_winner(struct board *self, enum hex_player *out) 209 { 210 assert(self); 211 212 if (segment_root(board_black_source(self)) == segment_root(board_black_sink(self))) { 213 *out = HEX_PLAYER_BLACK; 214 return true; 215 } else if (segment_root(board_white_source(self)) == segment_root(board_white_sink(self))) { 216 *out = HEX_PLAYER_WHITE; 217 return true; 218 } 219 220 return false; 221 }