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).

Privacy Settings
We use cookies to enhance your experience while using our website. If you are using our Services via a browser you can restrict, block or remove cookies through your web browser settings. We also use content and scripts from third parties that may use tracking technologies. You can selectively provide your consent below to allow such third party embeds. For complete information about the cookies we use, data we collect and how we process them, please check our Privacy Policy
Consent to display content from - Youtube
Consent to display content from - Vimeo
Google Maps
Consent to display content from - Google