board.c (24998B)
1 /* board.c - topologia del tablero (hexagonos, vertices, aristas, puertos) y 2 * generacion de tableros (principiante y aleatorio). */ 3 #include <string.h> 4 #include "catan.h" 5 6 #ifdef CATAN_SMALL 7 #define TOPO_SLOTS 1 /* la Pico: solo el clasico de siempre */ 8 #else 9 #define TOPO_SLOTS BOARD__COUNT 10 #endif 11 static Topo TT[TOPO_SLOTS]; 12 static bool T_ready[TOPO_SLOTS]; 13 14 /* Esquinas de un hexagono con punta arriba, en unidades enteras: N NE SE S SW NW */ 15 static const int8_t CX[6] = { 0, 1, 1, 0, -1, -1 }; 16 static const int8_t CY[6] = { -2, -1, 1, 2, 1, -1 }; 17 /* Vecinos en coordenadas axiales: E, SE, SW, W, NW, NE */ 18 static const int8_t DQ[6] = { 1, 0, -1, -1, 0, 1 }; 19 static const int8_t DR[6] = { 0, 1, 1, 0, -1, -1 }; 20 21 /* Cada tablero es un dibujo: una fila de texto por fila de hexagonos (las impares 22 * corridas medio hexagono a la derecha). 'L' tierra de arranque, 'I' isla (el primer 23 * pueblo en una isla donde no arrancaste da 2 puntos), 'D' desierto fijo, '~' mar, 'P' 24 * mar donde arranca el pirata, ' ' nada. Las tierras separadas por mar son regiones; 25 * las que tienen alguna 'L' son de arranque. Puertos: con port_pos, en esas posiciones 26 * de la costa; si no, repartidos parejo por la costa (con mar, por la orilla de las 27 * tierras de arranque). El clasico y el grande de siempre (mapa 0) dan exactamente los 28 * mismos indices de vertices y aristas que siempre (las partidas guardadas los usan). 29 * Los mapas sin mar de cada familia tienen la misma cantidad de hexagonos que el 0. 30 * Todos se juegan por bots en --sim/--duel antes de sumarlos (que ningun asiento gane 31 * de mas y que nadie quede encerrado). */ 32 typedef struct { 33 const char *name_es, *name_en; 34 const char *map[8]; 35 uint8_t nport, port_pos[NPORT]; 36 } Layout; 37 38 static const Layout LAYOUT[TOPO_SLOTS] = { 39 [BOARD_CLASSIC] = { "Oficial", "Official", { " LLL", "LLLL", "LLLLL", "LLLL", " LLL" }, 9, { 0, 3, 6, 10, 13, 16, 20, 23, 26 } }, 40 #ifndef CATAN_SMALL 41 [BOARD_CLASSIC + 1] = { "Lago", "Lake", { " LLLL", "LLLL", "LL LL", "LLLL", " LLL" }, 9, { 0 } }, 42 [BOARD_CLASSIC + 2] = { "Rectángulo", "Rectangle", { "LLLLL", "LLLLL", "LLLLL", "LLLL" }, 9, { 0 } }, 43 [BOARD_CLASSIC + 3] = { "Media luna", "Crescent", { " LLL", " LLLL", "LLL", "LLL ", " LLLL", " LL" }, 9, { 0 } }, 44 [BOARD_CLASSIC + 4] = { "Dos lóbulos", "Two lobes", { "LLL", "LLLL", "LLLLL", " LLLL", " LLL" }, 9, { 0 } }, 45 46 [BOARD_LARGE] = { "Oficial", "Official", { " LLL", " LLLL", " LLLLL", "LLLLLL", " LLLLL", " LLLL", " LLL" }, 11, 47 { 0, 3, 7, 10, 14, 17, 21, 24, 28, 31, 35 } }, 48 [BOARD_LARGE + 1] = { "Lago", "Lake", { " LLL", " LLLL", " LLLLL", "LLL LLL", " LL LL", " LLLLL", " LLL" }, 11, { 0 } }, 49 [BOARD_LARGE + 2] = { "Rectángulo", "Rectangle", { "LLLLLL", "LLLLLL", "LLLLLL", "LLLLLL", "LLLLLL" }, 11, { 0 } }, 50 [BOARD_LARGE + 3] = { "Media luna", "Crescent", { " LLLL", " LLLLL", " LLL", "LLL", "LLL", " LLL", " LLLLL", " LLLL" }, 11, { 0 } }, 51 [BOARD_LARGE + 4] = { "Dos lóbulos", "Two lobes", { " LLL", "LLLL", "LLLLL", "LLLLL ", " LLLLL", " LLLL", " LLLL" }, 11, { 0 } }, 52 53 /* Nuevas costas: isla grande de ~19 y islas chicas con oro */ 54 [BOARD_SEA1] = { "Islas al este", "Isles to the east", 55 { "~~~~~~~~~", "~LLL~~II~", "~LLLL~~I~", "~LLLLL~P~", "~LLLL~~I~", "~LLL~~II~", "~~~~~~~~~" }, 9, { 0 } }, 56 [BOARD_SEA1 + 1] = { "Islas al oeste", "Isles to the west", 57 { "~~~~~~~~~", "~II~~LLL~", "~I~~LLLL~", "~P~LLLLL~", "~I~~LLLL~", "~II~~LLL~", "~~~~~~~~~" }, 9, { 0 } }, 58 [BOARD_SEA1 + 2] = { "Costa larga", "Long coast", 59 { "~~~~~~~~~", "~LLLL~III", "~LLLL~~I~", "~LLLL~P~~", "~LLLL~~~~", "~LLL~~II~", "~~~~~~~~~" }, 9, { 0 } }, 60 [BOARD_SEA1 + 3] = { "Norte y sur", "North and south", 61 { "~II~~~II~", "~~~~~P~~~", "~LLLLLL~~", "~LLLLLLL~", "~LLLLLL~~", "~~~~~~~~~", "~II~~~~I~" }, 9, { 0 } }, 62 [BOARD_SEA1 + 4] = { "Bahía", "Bay", 63 { "~~~~~~~~~", "~LLLLL~I~", "~LLLL~~I~", "~LL~~I~P~", "~LLLL~~I~", "~LLLLL~I~", "~~~~~~~~~" }, 9, { 0 } }, 64 65 /* Cuatro islas: cada uno elige donde arrancar; las demas islas dan puntos */ 66 [BOARD_SEA1 + 5] = { "Esquinas", "Corners", 67 { "~~~~~~~~~", "~LLL~LLL~", "~LL~~~LL~", "~~~~D~P~~", "~LL~~~LL~", "~LLL~LLL~", "~~~~~~~~~" }, 8, { 0 } }, 68 [BOARD_SEA1 + 6] = { "Cruz", "Cross", 69 { "~~~LLL~~~", "~~~~LL~~~", "~LLL~~~LL", "~LL~D~LLL", "~~~~P~~~~", "~~~LLL~~~", "~~~LL~~~~" }, 8, { 0 } }, 70 [BOARD_SEA1 + 7] = { "Anillo", "Ring", 71 { "~~~~~~~~~", "~LL~~~LL~", "~LLL~~LLL", "~~~~I~~~~", "~LLL~D~LL", "~LL~P~LLL", "~~~~~~~~~" }, 8, { 0 } }, 72 [BOARD_SEA1 + 8] = { "Escalera", "Stairs", 73 { "~~~~~~~~~", "~LLL~~~~~", "~LL~~LLL~", "~~~~~~LL~", "~LLL~D~~~", "~~LL~~LLL", "~~~~P~LL~" }, 8, { 0 } }, 74 [BOARD_SEA1 + 9] = { "Estrechos", "Straits", 75 { " ~~~~~~~ ", "~LL~~~LL~", "~LLL~~LLL", "~~~~D~~~~", "~LLL~~LLL", "~LL~P~LL~", " ~~~~~~~ " }, 8, { 0 } }, 76 77 /* Archipielago: una tierra de arranque y muchas islitas */ 78 [BOARD_SEA1 + 10] = { "Islitas", "Islets", 79 { "~~~~~~~~~", "~I~~LLL~~", "~~~LLLL~I", "~I~~LLL~~", "~~~LLLL~~", "~I~~LLL~I", "~~~~~P~~~" }, 8, { 0 } }, 80 [BOARD_SEA1 + 11] = { "Costa norte", "North coast", 81 { "~~~~~~~~~", "~LLLLLLL~", "~LLLLLLL~", "~~LLL~~~~", "~~~~~~I~~", "~I~~I~~~I", "~~~P~~~~~" }, 8, { 0 } }, 82 [BOARD_SEA1 + 12] = { "Ele", "L-shape", 83 { "~~~~~~~~~", "~LLL~~~I~", "~LLL~I~~~", "~LLL~~~I~", "~LLLLLL~~", "~LLLLL~~I", "~~~~P~~~~" }, 8, { 0 } }, 84 [BOARD_SEA1 + 13] = { "Río", "River", 85 { "~~~~~~~~~", "~LLLLL~I~", "~LLLL~~~~", "~~~~~P~I~", "~LLLL~~~~", "~LLLLL~I~", "~~~~~~~~I" }, 8, { 0 } }, 86 [BOARD_SEA1 + 14] = { "Medialuna", "Half moon", 87 { "~~~~~~~~~", "~~~LLLLL~", "~~LLL~~~~", "~LLL~I~I~", "~~LLL~~~~", "~~~LLLL~~", "~I~~~~P~I" }, 8, { 0 } }, 88 #endif 89 }; 90 91 const char *board_name(int board) 92 { 93 if (board < 0 || board >= TOPO_SLOTS || !LAYOUT[board].map[0]) return ""; 94 return g_lang ? LAYOUT[board].name_en : LAYOUT[board].name_es; 95 } 96 97 static int find_hex(const Topo *T, int q, int r) 98 { 99 for (int h = 0; h < T->nhex; h++) 100 if (T->q[h] == q && T->r[h] == r) return h; 101 return -1; 102 } 103 104 static void push3(int16_t a[3], int v) 105 { 106 for (int i = 0; i < 3; i++) 107 if (a[i] < 0) { a[i] = (int16_t)v; return; } 108 } 109 110 static void push3b(int8_t a[3], int v) 111 { 112 for (int i = 0; i < 3; i++) 113 if (a[i] < 0) { a[i] = (int8_t)v; return; } 114 } 115 116 /* recorre en sentido horario las aristas que cumplen ok(), desde la primera */ 117 static int walk_edges(Topo *T, bool (*ok)(const Topo *, int), uint8_t *out, int max) 118 { 119 int start = -1, n = 0; 120 for (int e = 0; e < T->nedge && start < 0; e++) 121 if (ok(T, e)) start = e; 122 if (start < 0) return 0; 123 int e = start; 124 int v = T->vx[T->edge_v[e][0]] > T->vx[T->edge_v[e][1]] ? T->edge_v[e][0] : T->edge_v[e][1]; 125 do { 126 if (n < max) out[n] = (uint8_t)e; 127 n++; 128 int next = -1; 129 for (int k = 0; k < 3; k++) { 130 int f = T->vert_edge[v][k]; 131 if (f >= 0 && f != e && ok(T, f)) { next = f; break; } 132 } 133 if (next < 0) break; 134 e = next; 135 v = T->edge_v[e][0] == v ? T->edge_v[e][1] : T->edge_v[e][0]; 136 } while (e != start && n < 4 * NEDGE); 137 return n; 138 } 139 140 static bool is_coast(const Topo *T, int e) { return T->edge_hex[e][1] < 0; } 141 142 /* orilla de una region (la que se esta recorriendo): su tierra de un lado y mar del otro */ 143 static int shore_region; 144 static bool is_shore(const Topo *T, int e) 145 { 146 int a = T->edge_hex[e][0], b = T->edge_hex[e][1]; 147 if (a < 0 || b < 0) return false; 148 return (T->region[a] == shore_region && T->region[b] < 0) || (T->region[b] == shore_region && T->region[a] < 0); 149 } 150 151 /* n puertos parejos a lo largo de las aristas edges[0..ne), sin dos que compartan vertice 152 * (con los que ya hay desde first) */ 153 static int spread_ports(Topo *T, const uint8_t *edges, int ne, int n, int first) 154 { 155 int last = -100, used = first; 156 for (int i = 0; i < n; i++) { 157 int k = i * ne / n; 158 if (k <= last) k = last + 1; 159 while (k < ne && used > first) { 160 int e = edges[k], f = T->port_edge[used - 1]; 161 bool share = T->edge_v[e][0] == T->edge_v[f][0] || T->edge_v[e][0] == T->edge_v[f][1] || 162 T->edge_v[e][1] == T->edge_v[f][0] || T->edge_v[e][1] == T->edge_v[f][1]; 163 if (!share) break; 164 k++; 165 } 166 if (k >= ne) break; 167 T->port_edge[used++] = edges[k]; 168 last = k; 169 } 170 return used - first; 171 } 172 173 static void build(Topo *T, int board) 174 { 175 const char *const *map = LAYOUT[board].map; 176 int n = 0, sea = 0; 177 T->board = (uint8_t)board; 178 T->family = (uint8_t)(board / NMAPS); 179 T->sea_start = -1; 180 for (int row = 0; row < 8 && map[row]; row++) 181 for (int col = 0; map[row][col]; col++) { 182 char ch = map[row][col]; 183 if (ch == ' ') continue; 184 int q = col - (row - (row & 1)) / 2; 185 T->q[n] = (int8_t)q; T->r[n] = (int8_t)row; 186 T->hx[n] = (int16_t)(2 * col + (row & 1)); T->hy[n] = (int16_t)(3 * row); 187 bool water = ch == '~' || ch == 'P'; 188 T->region[n] = water ? -1 : 99; /* 99: tierra sin region todavia */ 189 T->kind[n] = water ? HK_SEA : ch == 'I' ? HK_ISLE : ch == 'D' ? HK_DESERT : HK_HOME; 190 if (water) sea = 1; 191 if (ch == 'P') T->sea_start = (int8_t)n; 192 n++; 193 } 194 T->nhex = (uint8_t)n; 195 T->sea = (uint8_t)sea; 196 197 /* vertices unicos, ordenados por (y, x) */ 198 int16_t px[NHEX * 6], py[NHEX * 6]; 199 int np = 0; 200 for (int h = 0; h < T->nhex; h++) 201 for (int k = 0; k < 6; k++) { 202 int x = T->hx[h] + CX[k], y = T->hy[h] + CY[k], dup = 0; 203 for (int i = 0; i < np; i++) 204 if (px[i] == x && py[i] == y) { dup = 1; break; } 205 if (!dup) { px[np] = (int16_t)x; py[np] = (int16_t)y; np++; } 206 } 207 for (int i = 1; i < np; i++) 208 for (int j = i; j > 0 && (py[j] < py[j-1] || (py[j] == py[j-1] && px[j] < px[j-1])); j--) { 209 int16_t t = px[j]; px[j] = px[j-1]; px[j-1] = t; 210 t = py[j]; py[j] = py[j-1]; py[j-1] = t; 211 } 212 T->nvert = (uint8_t)np; 213 for (int v = 0; v < T->nvert; v++) { 214 T->vx[v] = px[v]; T->vy[v] = py[v]; 215 for (int i = 0; i < 3; i++) { T->vert_hex[v][i] = -1; T->vert_edge[v][i] = T->vert_adj[v][i] = -1; } 216 } 217 for (int h = 0; h < T->nhex; h++) 218 for (int k = 0; k < 6; k++) { 219 int x = T->hx[h] + CX[k], y = T->hy[h] + CY[k]; 220 for (int v = 0; v < T->nvert; v++) 221 if (T->vx[v] == x && T->vy[v] == y) { T->hex_vert[h][k] = (uint8_t)v; push3b(T->vert_hex[v], h); break; } 222 } 223 224 /* aristas unicas, ordenadas por punto medio */ 225 uint8_t ea[NHEX * 6], eb[NHEX * 6]; 226 int ne = 0; 227 for (int h = 0; h < T->nhex; h++) 228 for (int k = 0; k < 6; k++) { 229 int a = T->hex_vert[h][k], b = T->hex_vert[h][(k + 1) % 6], dup = 0; 230 if (a > b) { int t = a; a = b; b = t; } 231 for (int i = 0; i < ne; i++) 232 if (ea[i] == a && eb[i] == b) { dup = 1; break; } 233 if (!dup) { ea[ne] = (uint8_t)a; eb[ne] = (uint8_t)b; ne++; } 234 } 235 for (int i = 1; i < ne; i++) 236 for (int j = i; j > 0; j--) { 237 int y1 = T->vy[ea[j]] + T->vy[eb[j]], x1 = T->vx[ea[j]] + T->vx[eb[j]]; 238 int y0 = T->vy[ea[j-1]] + T->vy[eb[j-1]], x0 = T->vx[ea[j-1]] + T->vx[eb[j-1]]; 239 if (y1 < y0 || (y1 == y0 && x1 < x0)) { 240 uint8_t t = ea[j]; ea[j] = ea[j-1]; ea[j-1] = t; 241 t = eb[j]; eb[j] = eb[j-1]; eb[j-1] = t; 242 } else break; 243 } 244 T->nedge = (uint8_t)ne; 245 for (int e = 0; e < T->nedge; e++) { 246 T->edge_v[e][0] = ea[e]; T->edge_v[e][1] = eb[e]; 247 T->edge_hex[e][0] = T->edge_hex[e][1] = -1; 248 push3(T->vert_edge[ea[e]], e); 249 push3(T->vert_edge[eb[e]], e); 250 push3(T->vert_adj[ea[e]], eb[e]); 251 push3(T->vert_adj[eb[e]], ea[e]); 252 } 253 for (int h = 0; h < T->nhex; h++) 254 for (int k = 0; k < 6; k++) { 255 int a = T->hex_vert[h][k], b = T->hex_vert[h][(k + 1) % 6]; 256 for (int e = 0; e < T->nedge; e++) 257 if ((T->edge_v[e][0] == a && T->edge_v[e][1] == b) || (T->edge_v[e][0] == b && T->edge_v[e][1] == a)) { 258 T->hex_edge[h][k] = (uint8_t)e; 259 if (T->edge_hex[e][0] < 0) T->edge_hex[e][0] = (int8_t)h; else T->edge_hex[e][1] = (int8_t)h; 260 break; 261 } 262 } 263 for (int h = 0; h < T->nhex; h++) 264 for (int d = 0; d < 6; d++) 265 T->hex_adj[h][d] = (int8_t)find_hex(T, T->q[h] + DQ[d], T->r[h] + DR[d]); 266 267 /* regiones: tierras conectadas (la primera que aparece es la principal) */ 268 int nreg = 0; 269 for (int h = 0; h < T->nhex; h++) { 270 if (T->region[h] != 99) continue; 271 int stack[NHEX], sp = 0; 272 stack[sp++] = h; 273 T->region[h] = (int8_t)nreg; 274 while (sp) { 275 int x = stack[--sp]; 276 for (int d = 0; d < 6; d++) { 277 int y = T->hex_adj[x][d]; 278 if (y >= 0 && T->region[y] == 99) { T->region[y] = (int8_t)nreg; stack[sp++] = y; } 279 } 280 } 281 nreg++; 282 } 283 T->nregion = (uint8_t)nreg; 284 T->home = 0; 285 for (int h = 0; h < T->nhex; h++) 286 if (T->kind[h] == HK_HOME && T->region[h] < 8) T->home |= (uint8_t)(1 << T->region[h]); 287 if (sea && T->sea_start < 0) 288 for (int h = 0; h < T->nhex && T->sea_start < 0; h++) if (T->region[h] < 0) T->sea_start = (int8_t)h; 289 290 for (int i = 0; i < T->nvert; i++) T->vert_port[i] = -1; 291 T->nport = LAYOUT[board].nport; 292 static uint8_t shore[4 * NEDGE]; 293 if (!sea) { /* costa del tablero: puertos en posiciones fijas o parejos */ 294 int nc = walk_edges(T, is_coast, shore, 4 * NEDGE); 295 T->ncoast = (uint8_t)(nc < NCOAST ? nc : NCOAST); 296 memcpy(T->coast, shore, T->ncoast); 297 if (LAYOUT[board].port_pos[1]) 298 for (int i = 0; i < T->nport; i++) T->port_edge[i] = shore[LAYOUT[board].port_pos[i]]; 299 else 300 T->nport = (uint8_t)spread_ports(T, shore, nc, T->nport, 0); 301 } else { /* parejos por la orilla de cada tierra de arranque, los mismos en cada una */ 302 int nh = 0, want = T->nport, used = 0, i = 0; 303 for (int r = 0; r < T->nregion && r < 8; r++) nh += (T->home >> r) & 1; 304 for (int r = 0; r < T->nregion && r < 8; r++) { 305 if (!((T->home >> r) & 1)) continue; 306 shore_region = r; 307 int ns = walk_edges(T, is_shore, shore, 4 * NEDGE); 308 if (ns > 4 * NEDGE) ns = 4 * NEDGE; 309 int n = want / nh + (i++ < want % nh); 310 used += spread_ports(T, shore, ns, n, used); 311 } 312 T->ncoast = 0; 313 T->nport = (uint8_t)used; 314 } 315 for (int i = 0; i < T->nport; i++) { 316 T->vert_port[T->edge_v[T->port_edge[i]][0]] = (int8_t)i; 317 T->vert_port[T->edge_v[T->port_edge[i]][1]] = (int8_t)i; 318 } 319 } 320 321 const Topo *topo_of(int board) 322 { 323 if (board < 0 || board >= TOPO_SLOTS || !LAYOUT[board].map[0]) board = BOARD_CLASSIC; 324 if (!T_ready[board]) { build(&TT[board], board); T_ready[board] = true; } 325 return &TT[board]; 326 } 327 328 /* Tablero de principiante del reglamento (filas de arriba hacia abajo). */ 329 void board_beginner(Game *g) 330 { 331 static const uint8_t TER[19] = { 332 T_MOUNTAINS, T_PASTURE, T_FOREST, 333 T_FIELDS, T_HILLS, T_PASTURE, T_HILLS, 334 T_FIELDS, T_FOREST, T_DESERT, T_FOREST, T_MOUNTAINS, 335 T_FOREST, T_MOUNTAINS, T_FIELDS, T_PASTURE, 336 T_HILLS, T_FIELDS, T_PASTURE }; 337 static const uint8_t NUM[19] = { 338 10, 2, 9, 12, 6, 4, 10, 9, 11, 0, 3, 8, 8, 3, 4, 5, 5, 6, 11 }; 339 static const uint8_t PORT[9] = { 340 PORT_ANY, WOOL, PORT_ANY, PORT_ANY, BRICK, LUMBER, PORT_ANY, GRAIN, ORE }; 341 for (int h = 0; h < 19; h++) { g->terrain[h] = TER[h]; g->num[h] = NUM[h]; } 342 for (int i = 0; i < 9; i++) g->port[i] = PORT[i]; 343 } 344 345 static bool red_adjacent(const Game *g, const Topo *t) 346 { 347 for (int h = 0; h < t->nhex; h++) { 348 if (g->num[h] != 6 && g->num[h] != 8) continue; 349 for (int d = 0; d < 6; d++) { 350 int n = t->hex_adj[h][d]; 351 if (n >= 0 && (g->num[n] == 6 || g->num[n] == 8)) return true; 352 } 353 } 354 return false; 355 } 356 357 static void shuffle(uint8_t *a, int n, Rng *rng) 358 { 359 for (int i = n - 1; i > 0; i--) { 360 int j = (int)rng_below(rng, (uint32_t)i + 1); 361 uint8_t t = a[i]; a[i] = a[j]; a[j] = t; 362 } 363 } 364 365 #ifndef CATAN_SMALL 366 /* reparte n entre los pesos w[0..k) (resto mayor; en empate, el primero) */ 367 static void apportion(int n, const uint8_t *w, int k, uint8_t *out) 368 { 369 int sum = 0, given = 0, rem[8]; 370 for (int i = 0; i < k; i++) sum += w[i]; 371 for (int i = 0; i < k; i++) { out[i] = (uint8_t)(n * w[i] / sum); rem[i] = n * w[i] % sum; given += out[i]; } 372 while (given < n) { 373 int b = 0; 374 for (int i = 1; i < k; i++) if (rem[i] > rem[b]) b = i; 375 out[b]++; rem[b] = -1; given++; 376 } 377 } 378 379 /* cada tierra de arranque con al menos 3 recursos distintos (o todos los que entran) */ 380 static bool home_varied(const Game *g, const Topo *t) 381 { 382 for (int r = 0; r < t->nregion && r < 8; r++) { 383 if (!((t->home >> r) & 1)) continue; 384 int seen = 0, n = 0; 385 for (int h = 0; h < t->nhex; h++) 386 if (t->region[h] == r) { n++; if (ter_res(g->terrain[h])) seen |= 1 << g->terrain[h]; } 387 int k = 0; 388 for (int i = 0; i < NRES; i++) k += (seen >> i) & 1; 389 if (k < (n < 3 ? n : 3)) return false; 390 } 391 return true; 392 } 393 394 /* produccion esperada (puntitos de las fichas) de cada tierra de arranque, por hexagono: 395 * que la mejor no le saque mas de un 15% a la peor */ 396 static bool home_pips_even(const Game *g, const Topo *t) 397 { 398 static const uint8_t PIP[13] = { 0, 0, 1, 2, 3, 4, 5, 0, 5, 4, 3, 2, 1 }; 399 int lo = 1 << 30, hi = 0; 400 for (int r = 0; r < t->nregion && r < 8; r++) { 401 if (!((t->home >> r) & 1)) continue; 402 int pips = 0, n = 0; 403 for (int h = 0; h < t->nhex; h++) 404 if (t->region[h] == r) { n++; pips += PIP[g->num[h]]; } 405 int per = n ? pips * 100 / n : 0; 406 if (per < lo) lo = per; 407 if (per > hi) hi = per; 408 } 409 return hi * 100 <= lo * 115; 410 } 411 412 static void sort_u8(uint8_t *a, int n) 413 { 414 for (int i = 1; i < n; i++) 415 for (int j = i; j > 0 && a[j] < a[j-1]; j--) { uint8_t t = a[j]; a[j] = a[j-1]; a[j-1] = t; } 416 } 417 418 /* Navegantes: la tierra de arranque con el reparto clasico (en proporcion: 4 bosque, 419 * pasto y campo, 3 cerro y montana, un desierto cada 19 si el mapa no trae uno fijo); 420 * las islas con oro (uno cada 4) y mas de lo escaso. Numeros: los de arranque salen de 421 * la bolsa clasica en un orden que la mantiene pareja si se corta antes; los de las 422 * islas, medianos. Sin 6 ni 8 juntos. Con "Nuevas costas" de siempre da el mismo tablero 423 * que daba antes de que hubiera varios mapas (las partidas guardadas lo regeneran). */ 424 static void board_sea(Game *g, const Topo *t, Rng *rng) 425 { 426 static const uint8_t HT[5] = { T_FOREST, T_PASTURE, T_FIELDS, T_HILLS, T_MOUNTAINS }, HW[5] = { 4, 4, 4, 3, 3 }; 427 static const uint8_t IT[5] = { T_HILLS, T_MOUNTAINS, T_PASTURE, T_FOREST, T_FIELDS }, IW[5] = { 3, 3, 2, 2, 2 }; 428 static const uint8_t BAL[18] = { 6, 8, 5, 9, 4, 10, 3, 11, 2, 12, 5, 9, 4, 10, 3, 11, 6, 8 }; 429 static const uint8_t ISL[10] = { 3, 11, 4, 10, 5, 9, 2, 12, 6, 8 }; 430 int nhome = 0, nisle = 0, fixed = 0; 431 for (int h = 0; h < t->nhex; h++) { 432 if (t->kind[h] == HK_DESERT) fixed++; 433 else if (t->region[h] >= 0 && ((t->home >> t->region[h]) & 1)) nhome++; 434 else if (t->region[h] >= 0) nisle++; 435 } 436 int ndes = fixed ? 0 : nhome < 19 ? 1 : (nhome + 9) / 19; 437 uint8_t home[NHEX], isle[NHEX], cnt[5]; 438 int kh = 0, ki = 0; 439 apportion(nhome - ndes, HW, 5, cnt); 440 for (int i = 0; i < 5; i++) for (int k = 0; k < cnt[i]; k++) home[kh++] = HT[i]; 441 for (int i = 0; i < ndes; i++) home[kh++] = T_DESERT; 442 int ngold = nisle >= 2 ? (nisle + 2) / 4 : nisle; 443 for (int i = 0; i < ngold; i++) isle[ki++] = T_GOLD; 444 apportion(nisle - ngold, IW, 5, cnt); 445 for (int i = 0; i < 5; i++) for (int k = 0; k < cnt[i]; k++) isle[ki++] = IT[i]; 446 int nhr = 0; /* con varias tierras de arranque, que sean parejas */ 447 for (int r = 0; r < t->nregion && r < 8; r++) nhr += (t->home >> r) & 1; 448 for (int tries = 0;; tries++) { 449 shuffle(home, kh, rng); 450 if (tries == 0) shuffle(isle, ki, rng); 451 int a = 0, b = 0; 452 for (int h = 0; h < t->nhex; h++) { 453 if (t->region[h] < 0) g->terrain[h] = T_SEA; 454 else if (t->kind[h] == HK_DESERT) g->terrain[h] = T_DESERT; 455 else if ((t->home >> t->region[h]) & 1) g->terrain[h] = a < kh ? home[a++] : T_DESERT; 456 else g->terrain[h] = b < ki ? isle[b++] : T_DESERT; 457 } 458 if (nhr < 2 || tries >= 300 || home_varied(g, t)) break; 459 } 460 uint8_t nums[NHEX]; 461 int nh = nhome - ndes, ni = nisle, nn = 0; 462 for (int i = 0; i < nh; i++) nums[nn++] = BAL[i % 18]; 463 sort_u8(nums, nn); 464 for (int i = 0; i < ni; i++) nums[nn + i] = ISL[i % 10]; 465 sort_u8(nums + nn, ni); 466 nn += ni; 467 uint8_t pool[NHEX]; 468 for (int tries = 0;; tries++) { 469 memcpy(pool, nums, (size_t)nn); 470 shuffle(pool, nn, rng); 471 for (int h = 0, k = 0; h < t->nhex; h++) 472 g->num[h] = (ter_res(g->terrain[h]) || g->terrain[h] == T_GOLD) && k < nn ? pool[k++] : 0; 473 if (red_adjacent(g, t)) continue; 474 if (nhr < 2 || tries >= 2000 || home_pips_even(g, t)) break; 475 } 476 /* puertos: uno 2:1 de cada recurso y el resto 3:1 */ 477 static const uint8_t P5[5] = { BRICK, LUMBER, WOOL, GRAIN, ORE }; 478 int np = t->nport, k = 0; 479 for (int i = 0; i < np - 5; i++) g->port[k++] = PORT_ANY; 480 for (int i = 0; i < 5 && k < np; i++) g->port[k++] = P5[i]; 481 shuffle(g->port, t->nport, rng); 482 } 483 #endif 484 485 /* Tablero al azar, sin 6 ni 8 juntos. Clasico: 4 bosque/pasto/campo, 3 cerro/montana, 486 * 1 desierto, 18 numeros, 9 puertos. Grande (5-6): 6/6/6, 5/5, 2 desiertos, 28 numeros 487 * (2 y 12 dos veces, el resto tres) y 11 puertos (5 de 3:1, 2 de lana, uno de cada otro). 488 * El clasico usa el azar exactamente como siempre: el servidor y las partidas guardadas 489 * regeneran el tablero desde la semilla. */ 490 void board_random(Game *g, int board, Rng *rng) 491 { 492 static const uint8_t TER0[19] = { 493 T_FOREST, T_FOREST, T_FOREST, T_FOREST, T_PASTURE, T_PASTURE, T_PASTURE, T_PASTURE, 494 T_FIELDS, T_FIELDS, T_FIELDS, T_FIELDS, T_HILLS, T_HILLS, T_HILLS, 495 T_MOUNTAINS, T_MOUNTAINS, T_MOUNTAINS, T_DESERT }; 496 static const uint8_t NUM0[18] = { 2, 3, 3, 4, 4, 5, 5, 6, 6, 8, 8, 9, 9, 10, 10, 11, 11, 12 }; 497 static const uint8_t PORT0[9] = { PORT_ANY, PORT_ANY, PORT_ANY, PORT_ANY, BRICK, LUMBER, WOOL, GRAIN, ORE }; 498 #ifndef CATAN_SMALL 499 static const uint8_t TER1[30] = { 500 T_FOREST, T_FOREST, T_FOREST, T_FOREST, T_FOREST, T_FOREST, 501 T_PASTURE, T_PASTURE, T_PASTURE, T_PASTURE, T_PASTURE, T_PASTURE, 502 T_FIELDS, T_FIELDS, T_FIELDS, T_FIELDS, T_FIELDS, T_FIELDS, 503 T_HILLS, T_HILLS, T_HILLS, T_HILLS, T_HILLS, 504 T_MOUNTAINS, T_MOUNTAINS, T_MOUNTAINS, T_MOUNTAINS, T_MOUNTAINS, T_DESERT, T_DESERT }; 505 static const uint8_t NUM1[28] = { 2, 2, 3, 3, 3, 4, 4, 4, 5, 5, 5, 6, 6, 6, 506 8, 8, 8, 9, 9, 9, 10, 10, 10, 11, 11, 11, 12, 12 }; 507 static const uint8_t PORT1[11] = { PORT_ANY, PORT_ANY, PORT_ANY, PORT_ANY, PORT_ANY, 508 BRICK, LUMBER, WOOL, WOOL, GRAIN, ORE }; 509 #endif 510 const Topo *t = topo_of(board); 511 #ifndef CATAN_SMALL 512 if (t->sea) { board_sea(g, t, rng); return; } 513 #endif 514 const uint8_t *TER = TER0, *NUM = NUM0, *PORT = PORT0; 515 #ifndef CATAN_SMALL 516 if (t->family == BF_LARGE) { TER = TER1; NUM = NUM1; PORT = PORT1; } 517 #endif 518 int nh = t->nhex, nn = nh - (t->family == BF_LARGE ? 2 : 1); 519 for (int h = 0; h < nh; h++) g->terrain[h] = TER[h]; 520 shuffle(g->terrain, nh, rng); 521 uint8_t nums[NHEX]; 522 do { 523 for (int i = 0; i < nn; i++) nums[i] = NUM[i]; 524 shuffle(nums, nn, rng); 525 for (int h = 0, k = 0; h < nh; h++) 526 g->num[h] = g->terrain[h] == T_DESERT ? 0 : nums[k++]; 527 } while (red_adjacent(g, t)); 528 for (int i = 0; i < t->nport; i++) g->port[i] = PORT[i]; 529 shuffle(g->port, t->nport, rng); 530 }