Cities & Villages – A* search
In this project I’ve gone through a problem inspired in Settlers of Catan, implement a A* search algorithm to solve it and analyzed the results.
The problem at hands (C&V, standing for Cities and Villages) consists on finding the best locations for cities and villages to explore an island. There are in total 5 islands. The space of each island is divided in hexagonal form, of Nx(2N), with an odd-q vertical layout. Each hexagon has a monthly production value, which is capitalized by the villages and cities in contact with the hexagon. Cities can capitalize on double output. Villages and cities are placed at the vertices of the hexagons, with the following restrictions:
• A village or town must have a minimum distance of two edges, for any other village or town;
• The total number of villages, plus the quadruple cities, cannot exceed twice the hexagons.
The A* search for C&V was coded in C++, on Dev-C++ IDE and run on an Asus Laptop Intel® Core™ i7-4510U CPU @ 2.00 GHz with 8 GB of RAM using Windows 10. Inside of Dev-C++ IDE, I went to the tab Tools > Compiler Options > Settings > Code Generation and changed the Optimization level to “high”. In the Table 1 the results are presented including the island number (IN), production value (PV), number of cities (NC), number of villages (NV), number of expansion (NG), number of generation (NE), number of evaluation (NEv) and execution time (ET).
