1 /* Pioneers - Implementation of the excellent Settlers of Catan board game.
2 * Go buy a copy.
3 *
4 * Copyright (C) 1999 Dave Cole
5 *
6 * This program is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License as published by
8 * the Free Software Foundation; either version 2 of the License, or
9 * (at your option) any later version.
10 *
11 * This program is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU General Public License for more details.
15 *
16 * You should have received a copy of the GNU General Public License
17 * along with this program; if not, write to the Free Software
18 * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA
19 */
20
21 #include "config.h"
22 #include <math.h>
23 #include <ctype.h>
24
25 #include <glib.h>
26
27 #include "game.h"
28 #include "map.h"
29 #include "buildrec.h"
30
31 /* Local function prototypes. */
32 static gboolean buildrec_can_setup_edge(GList * list, const Edge * edge,
33 gboolean is_double);
34
35
buildrec_new(BuildType type,gint x,gint y,gint pos)36 BuildRec *buildrec_new(BuildType type, gint x, gint y, gint pos)
37 {
38 BuildRec *rec = g_malloc0(sizeof(*rec));
39 rec->type = type;
40 rec->x = x;
41 rec->y = y;
42 rec->pos = pos;
43 rec->special_points_id = -1;
44 return rec;
45 }
46
buildrec_free(GList * list)47 GList *buildrec_free(GList * list)
48 {
49 while (list != NULL) {
50 BuildRec *rec = list->data;
51 list = g_list_remove(list, rec);
52 g_free(rec);
53 }
54
55 return NULL;
56 }
57
buildrec_count_type(GList * list,BuildType type)58 gint buildrec_count_type(GList * list, BuildType type)
59 {
60 gint num = 0;
61
62 while (list != NULL) {
63 BuildRec *rec = list->data;
64 list = g_list_next(list);
65 if (rec->type == type)
66 num++;
67 }
68
69 return num;
70 }
71
buildrec_count_edges(GList * list)72 gint buildrec_count_edges(GList * list)
73 {
74 gint num = 0;
75
76 while (list != NULL) {
77 BuildRec *rec = list->data;
78 list = g_list_next(list);
79 if (rec->type == BUILD_ROAD
80 || rec->type == BUILD_SHIP
81 || rec->type == BUILD_BRIDGE)
82 num++;
83 }
84
85 return num;
86 }
87
buildrec_get(GList * list,BuildType type,gint idx)88 BuildRec *buildrec_get(GList * list, BuildType type, gint idx)
89 {
90
91 while (list != NULL) {
92 BuildRec *rec = list->data;
93 list = g_list_next(list);
94 if (rec->type == type && idx-- == 0)
95 return rec;
96 }
97
98 return NULL;
99 }
100
buildrec_get_edge(GList * list,gint idx)101 BuildRec *buildrec_get_edge(GList * list, gint idx)
102 {
103
104 while (list != NULL) {
105 BuildRec *rec = list->data;
106 list = g_list_next(list);
107 if ((rec->type == BUILD_ROAD
108 || rec->type == BUILD_SHIP
109 || rec->type == BUILD_BRIDGE) && idx-- == 0)
110 return rec;
111 }
112
113 return NULL;
114 }
115
buildrec_is_valid(GList * list,const Map * map,gint owner)116 gboolean buildrec_is_valid(GList * list, const Map * map, gint owner)
117 {
118 while (list != NULL) {
119 BuildRec *rec = list->data;
120 list = g_list_next(list);
121
122 switch (rec->type) {
123 case BUILD_NONE:
124 g_warning("BUILD_NONE in buildrec_is_valid");
125 continue;
126 case BUILD_ROAD:
127 /* Roads have to be adjacent to buildings / road
128 */
129 if (!map_road_connect_ok(map, owner,
130 rec->x, rec->y, rec->pos))
131 return FALSE;
132 continue;
133 case BUILD_BRIDGE:
134 /* Bridges have to be adjacent to buildings /
135 * road, and they have to be over water.
136 */
137 if (!map_bridge_connect_ok(map, owner,
138 rec->x, rec->y,
139 rec->pos))
140 return FALSE;
141 continue;
142 case BUILD_SHIP:
143 case BUILD_MOVE_SHIP:
144 /* ships have to be adjacent to buildings /
145 * ships, and they have to be over water /
146 * coast.
147 */
148 if (!map_ship_connect_ok(map, owner,
149 rec->x, rec->y, rec->pos))
150 return FALSE;
151 continue;
152 case BUILD_SETTLEMENT:
153 case BUILD_CITY:
154 case BUILD_CITY_WALL:
155 /* Buildings must be adjacent to a road
156 */
157 if (!map_building_connect_ok
158 (map, owner, rec->x, rec->y, rec->pos))
159 return FALSE;
160 continue;
161 }
162 }
163
164 return TRUE;
165 }
166
edge_has_place_for_settlement(const Edge * edge)167 static gboolean edge_has_place_for_settlement(const Edge * edge)
168 {
169 guint idx;
170
171 for (idx = 0; idx < G_N_ELEMENTS(edge->nodes); idx++) {
172 const Node *node = edge->nodes[idx];
173 if (node->type == BUILD_NONE && is_node_on_land(node)
174 && is_node_spacing_ok(node))
175 return TRUE;
176 }
177 return FALSE;
178 }
179
180 /* Check if we can place this edge with 0 existing settlements during setup
181 */
can_setup_edge_0(GList * list,const Edge * edge)182 static gboolean can_setup_edge_0(GList * list, const Edge * edge)
183 {
184 BuildRec *rec = buildrec_get_edge(list, 0);
185 const Edge *other_edge;
186 guint idx;
187
188 if (rec == NULL)
189 /* This is the only edge - it can only placed if one
190 * of its nodes is a legal location for a new
191 * settlement.
192 */
193 return edge_has_place_for_settlement(edge);
194
195 /* There is already one edge placed. We can only place this
196 * edge if it creates a second legal place for settlements.
197 * If I place a settlement on one of the edges, make sure
198 * there is still a place where the second settlement can be
199 * placed.
200 */
201 other_edge = map_edge(edge->map, rec->x, rec->y, rec->pos);
202 for (idx = 0; idx < G_N_ELEMENTS(edge->nodes); idx++) {
203 Node *node = edge->nodes[idx];
204
205 if (node->type == BUILD_NONE && is_node_spacing_ok(node)) {
206 gboolean ok;
207
208 node->type = BUILD_SETTLEMENT;
209 ok = edge_has_place_for_settlement(other_edge);
210 node->type = BUILD_NONE;
211
212 if (ok)
213 return TRUE;
214 }
215 }
216
217 return FALSE;
218 }
219
220 /* Check if we can place this edge with 1 existing settlement during setup
221 */
can_setup_edge_1(GList * list,const Edge * edge)222 static gboolean can_setup_edge_1(GList * list, const Edge * edge)
223 {
224 BuildRec *rec = buildrec_get(list, BUILD_SETTLEMENT, 0);
225 const Node *node =
226 map_node_const(edge->map, rec->x, rec->y, rec->pos);
227 const Edge *other_edge;
228
229 rec = buildrec_get_edge(list, 0);
230 if (rec == NULL)
231 /* No other edges placed yet, we can either place this
232 * edge next to the existing settlement, or somewhere
233 * which has a legal place for an additional
234 * settlement.
235 */
236 return is_edge_adjacent_to_node(edge, node)
237 || edge_has_place_for_settlement(edge);
238
239 /* This is the second edge, we must ensure that one of the
240 * edges is adjacent to the settlement, and the other has a
241 * place for the second settlement.
242 */
243 other_edge = map_edge_const(edge->map, rec->x, rec->y, rec->pos);
244 return (is_edge_adjacent_to_node(edge, node)
245 && edge_has_place_for_settlement(other_edge))
246 || (is_edge_adjacent_to_node(other_edge, node)
247 && edge_has_place_for_settlement(edge));
248 }
249
250 /* Check if we can place this edge with 2 existing settlements during setup
251 */
can_setup_edge_2(GList * list,const Edge * edge)252 static gboolean can_setup_edge_2(GList * list, const Edge * edge)
253 {
254 BuildRec *rec = buildrec_get(list, BUILD_SETTLEMENT, 0);
255 const Node *node =
256 map_node_const(edge->map, rec->x, rec->y, rec->pos);
257 const Node *other_node;
258 const Edge *other_edge;
259
260 rec = buildrec_get(list, BUILD_SETTLEMENT, 1);
261 other_node = map_node_const(edge->map, rec->x, rec->y, rec->pos);
262
263 rec = buildrec_get_edge(list, 0);
264 if (rec == NULL)
265 /* No other edges placed yet, we must place this edge
266 * next to either settlement.
267 */
268 return is_edge_adjacent_to_node(edge, node)
269 || is_edge_adjacent_to_node(edge, other_node);
270
271 /* Two settlements and one edge placed, we must make sure that
272 * we place this edge next to a settlement and both
273 * settlements then have an adjacent edge. If we have
274 * bridges, it is possible to have both settlements adjacent
275 * to a single bridge.
276 */
277 other_edge = map_edge_const(edge->map, rec->x, rec->y, rec->pos);
278 if (is_edge_adjacent_to_node(other_edge, node)
279 && is_edge_adjacent_to_node(other_edge, other_node))
280 /* other_edge is a bridge connecting both settlements
281 * -> edge can connect to either settlement.
282 */
283 return is_edge_adjacent_to_node(edge, node)
284 || is_edge_adjacent_to_node(edge, other_node);
285 if (is_edge_adjacent_to_node(edge, node)
286 && is_edge_adjacent_to_node(edge, other_node)
287 && !is_edge_on_land(edge))
288 /* This edge is a bridge connecting both settlements
289 */
290 return TRUE;
291 /* No bridges -> edge must be adjacent to the settlement which
292 * other_edge is not adjacent to.
293 */
294 if (is_edge_adjacent_to_node(other_edge, other_node))
295 return is_edge_adjacent_to_node(edge, node);
296 else
297 return is_edge_adjacent_to_node(edge, other_node);
298 }
299
buildrec_can_setup_edge(GList * list,const Edge * edge,gboolean is_double)300 static gboolean buildrec_can_setup_edge(GList * list, const Edge * edge,
301 gboolean is_double)
302 {
303 if (!is_double) {
304 BuildRec *rec = buildrec_get(list, BUILD_SETTLEMENT, 0);
305 if (rec != NULL) {
306 /* We have placed a settlement, the edge must
307 * be placed adjacent to that settlement.
308 */
309 const Node *node =
310 map_node(edge->map, rec->x, rec->y, rec->pos);
311 return is_edge_adjacent_to_node(edge, node);
312 }
313 /* We have not placed a settlement yet, the edge can
314 * only placed if one of its nodes is a legal location
315 * for a new settlement.
316 */
317 return edge_has_place_for_settlement(edge);
318 }
319
320 /* Double setup is more difficult - there are a lot more
321 * situations to be handled.
322 */
323 switch (buildrec_count_type(list, BUILD_SETTLEMENT)) {
324 case 0:
325 return can_setup_edge_0(list, edge);
326 case 1:
327 return can_setup_edge_1(list, edge);
328 case 2:
329 return can_setup_edge_2(list, edge);
330 }
331 g_warning("more than 2 settlements in setup!!!");
332 return FALSE;
333 }
334
buildrec_can_setup_road(GList * list,const Edge * edge,gboolean is_double)335 gboolean buildrec_can_setup_road(GList * list, const Edge * edge,
336 gboolean is_double)
337 {
338 if (!can_road_be_setup(edge))
339 return FALSE;
340
341 return buildrec_can_setup_edge(list, edge, is_double);
342 }
343
buildrec_can_setup_ship(GList * list,const Edge * edge,gboolean is_double)344 gboolean buildrec_can_setup_ship(GList * list, const Edge * edge,
345 gboolean is_double)
346 {
347 if (!can_ship_be_setup(edge))
348 return FALSE;
349
350 return buildrec_can_setup_edge(list, edge, is_double);
351 }
352
buildrec_can_setup_bridge(GList * list,const Edge * edge,gboolean is_double)353 gboolean buildrec_can_setup_bridge(GList * list, const Edge * edge,
354 gboolean is_double)
355 {
356 if (!can_bridge_be_setup(edge))
357 return FALSE;
358
359 return buildrec_can_setup_edge(list, edge, is_double);
360 }
361
362 /* Check if we can place this settlement with 0 existing edges during setup
363 */
can_setup_settlement_0(G_GNUC_UNUSED GList * list,G_GNUC_UNUSED const Node * node)364 static gboolean can_setup_settlement_0(G_GNUC_UNUSED GList * list,
365 G_GNUC_UNUSED const Node * node)
366 {
367 return TRUE;
368 }
369
370 /* Check if we can place this settlement with 1 existing edge during setup
371 */
can_setup_settlement_1(GList * list,const Node * node)372 static gboolean can_setup_settlement_1(GList * list, const Node * node)
373 {
374 BuildRec *rec = buildrec_get_edge(list, 0);
375 const Edge *edge =
376 map_edge_const(node->map, rec->x, rec->y, rec->pos);
377 const Node *other_node;
378
379 /* Make sure that we place one settlement next to the existing edge.
380 */
381 rec = buildrec_get(list, BUILD_SETTLEMENT, 0);
382 if (rec == NULL)
383 /* No other settlements placed yet.
384 */
385 return TRUE;
386
387 /* There is one edge and one settlement placed. One of the
388 * settlements must be placed next to the edge.
389 */
390 other_node = map_node_const(node->map, rec->x, rec->y, rec->pos);
391 return is_edge_adjacent_to_node(edge, node)
392 || is_edge_adjacent_to_node(edge, other_node);
393 }
394
395 /* Check if we can place this settlement with 2 existing edges during setup
396 */
can_setup_settlement_2(GList * list,const Node * node)397 static gboolean can_setup_settlement_2(GList * list, const Node * node)
398 {
399 BuildRec *rec = buildrec_get_edge(list, 0);
400 const Edge *edge =
401 map_edge_const(node->map, rec->x, rec->y, rec->pos);
402 const Edge *other_edge;
403 const Node *other_node;
404 Node *try_build_here;
405
406 rec = buildrec_get_edge(list, 1);
407 other_edge = map_edge_const(node->map, rec->x, rec->y, rec->pos);
408
409 /* Two edges placed, we must make sure that we place this
410 * settlement adjacent to an edge.
411 */
412 if (!is_edge_adjacent_to_node(edge, node)
413 && !is_edge_adjacent_to_node(other_edge, node))
414 return FALSE;
415
416 rec = buildrec_get(list, BUILD_SETTLEMENT, 0);
417 if (rec == NULL) {
418 /* No settlements placed yet, place the settlement and
419 * make sure that there is still a valid place for the
420 * second settlement.
421 */
422 gboolean is_ok = FALSE;
423
424 try_build_here = map_node(node->map, node->x, node->y, node->pos); /* Copy to non-const pointer */
425 try_build_here->type = BUILD_SETTLEMENT;
426 try_build_here->owner = edge->owner;
427 if (is_edge_adjacent_to_node(edge, node)) {
428 if (is_edge_adjacent_to_node(other_edge, node))
429 /* Node is adjacent to both edges -
430 * make sure there is still a valid
431 * location on either edge.
432 */
433 is_ok = edge_has_place_for_settlement(edge)
434 ||
435 edge_has_place_for_settlement
436 (other_edge);
437 else
438 /* Node is adjacent to edge, make sure
439 * other edge has location for
440 * settlement.
441 */
442 is_ok =
443 edge_has_place_for_settlement
444 (other_edge);
445 } else
446 /* Node is adjacent to other edge - make sure
447 * edge has location for settlement.
448 */
449 is_ok = edge_has_place_for_settlement(edge);
450 try_build_here->type = BUILD_NONE;
451 try_build_here->owner = -1;
452 return is_ok;
453 }
454
455 /* Two edges and one settlement placed, ensure that each edge
456 * is adjacent to at least one settlement.
457 */
458 other_node = map_node_const(node->map, rec->x, rec->y, rec->pos);
459 if (is_edge_adjacent_to_node(edge, other_node)) {
460 if (is_edge_adjacent_to_node(other_edge, other_node))
461 return TRUE;
462 else
463 return is_edge_adjacent_to_node(edge, other_node);
464 } else
465 return is_edge_adjacent_to_node(edge, node);
466 }
467
buildrec_can_setup_settlement(GList * list,const Node * node,gboolean is_double)468 gboolean buildrec_can_setup_settlement(GList * list, const Node * node,
469 gboolean is_double)
470 {
471 if (!can_settlement_be_setup(node))
472 return FALSE;
473
474 if (!is_double) {
475 BuildRec *rec = buildrec_get_edge(list, 0);
476 if (rec != NULL) {
477 /* We have placed an edge, the settlement must
478 * be placed adjacent to that edge.
479 */
480 const Edge *edge =
481 map_edge_const(node->map, rec->x, rec->y,
482 rec->pos);
483 return is_edge_adjacent_to_node(edge, node);
484 }
485 /* We have not placed an edge yet, the settlement is OK.
486 */
487 return TRUE;
488 }
489
490 /* Double setup is more difficult - there are a lot more
491 * situations to be handled.
492 */
493 switch (buildrec_count_edges(list)) {
494 case 0:
495 return can_setup_settlement_0(list, node);
496 case 1:
497 return can_setup_settlement_1(list, node);
498 case 2:
499 return can_setup_settlement_2(list, node);
500 }
501 g_warning("more than 2 settlements in setup!!!");
502 return FALSE;
503 }
504