Daniel Petersen's Blog

Documenting my struggle to make a videogame, amongst other nonsense


Home Projects

Ai City Location Mapper

Posted on 2017-06-19

Today I’m going to try to implement an algorithm which picks city locations for the AI.

If you’ve ever played civilization, you should have a good idea on what this means, as it’s more or less the same problem from that game. Maps in my game are much larger than in Civilization, and my game ticks along at like 1 turn every 600 milliseconds, so performance is a pretty huge concern.

I’m still debating the exact city ring size, and I’m going off memory here but I think cities can currently grow to a maximum of 5x5 tiles. You can see the maximum growth of a city by the black outline around the center city this screen

I’ve come up with something that I think will work (high level code outline below), but I wouldn’t be surprised if there’s a much better way of going about it.

// Only one  object of this class will be instantiated, and each AI will talk to this object 
// in order to get a city location
class AI_City_Location_Mapper
{
private:
    // first dimension is number of continents on the map 
    // (where a continent is a group of connected land tiles)
    // second dimension is a vector of tile indexes where cities should be placed
    std::vector<std::vector<int>> CityLocationsByContinent

    // where the magic happens
    void calculateCityLocations(int ContinentIndex);

public:
    // city locations are calculated for each continent on map generation and
    // cached in the above array
    void onMapGeneration()
    {
        CityLocationsByContinent.resize(NUMBER_OF_CONTINENETS);
        for (int i = 0; i < NUMBER_OF_CONTINENETS; i++)
        {
            calculateCityLocations(i);
        }
    }

    // if the human player settles a city, the city locations for that
    // continent might need to be reworked to make more sense.
    void onCityCreation(int ContinentIndex)
    {
        calculateCityLocations(ContinentIndex);
    }

    // basically, the above two functions are the only time when city
    // locations are going to be updated.  

    // when the AI wants a location for a new city, it calls this function,
    // and passes the unit index for the settler in question. the game iterates
    // through each possible city location for the continent the city is on, and 
    // does a simple calculation based on distance and city desirability to determine
    // which city location to settle. -1 if no city available 
    int requestCityLocation(int UnitIndex);
};

For calculateCityLocations(), I’m thinking that I’m going to divide the map up into a larger grid, with each cell in this larger grid representing let’s say a 5x5 group of cells. Perhaps that size will be determined by the city ring size. I then think I’m going to assign a city location in the center tile of the actual grid for each cell in this large grid.

So essentially calculateCityLocations would be iterating over each city in this list and moving the city location over 1 tile for each loop iteration, based on the best location of its neighbors. If the initial city location happens to be on a water tile, I’ll have to do a check to make sure that doesn’t happen or fix it when it does. I already have a function which ranks how good any given city location is, but I’m going to need to expand that function to take into account tiles which are already owned by another city (obviously those tiles would be degraded in importance).

I’m aiming to do all of this today, but we’ll see how it goes.


Copyright © - Daniel J. Petersen