In this post, I will mainly focus on the enemy AI development for Heart of Muriet.

Heart of Muriet is a single-player game; the AI is one of the most important features. I have put almost a full year of development, into making it better and easier to extend.

It's playing well and is already a challenge for beginner and mediocre players. To make sure veteran 4X players also face a challenge development will continue througout the whole EA phase and beyond.

Implemented a multi-threaded approach for building placement using a dozen different constraints, including clusters, border avoidance, influence radius considerations, and space requirements.

• Various building placement search functions: horizontal, vertical, circular outward and inward.

• Search function for placing within specific building type influence radii,

• Search function to optimise influence building placement for maximum building coverage.

• Optimised search functions with reduced boundary and height checks.

• Scoring for influence buildings favouring centred positions using border distance weighting (for buildings with an influence radius like Well, Mill, etc.)

• Scoring for influence buildings to minimise blocked grid cells within a radius (e.g., Forester Hut).

• Search functions include cluster scoring, which means that the closer a building is to a cluster of the same building type, the higher the scoring. The score is also affected if the building is in a radius, which has a positive influence.

  

• The screenshot shows the current placement algorithm in action. The AI automatically detects resource clusters and will place haul storage as close as possible.

• Defence buildings, like towers are placed at the outskirts, reserve buildings in the centre. The foresters require free space around them and won't be placed near resource nodes if possible.

• The forester was built first, the mining hub second. The mining hub ignores forester huts as they need to be placed close to a cluster; they are useless.

• Crop fields and residential buildings have a scoring for placing them parallel, which might save space.

• Buildings which are not used can also be destroyed and rebuilt in other provinces, like a mine that becomes useless when the resource nodes are depleted.

• There are still missing smaller features, like replacing buildings with better versions and removing buildings from hamlets to make provinces more beautiful.

One of the harder problems for an AI is to make good decisions on what to build, when to build it, and how many resources it can spend on certain areas in specific situations. For this reason, I developed a budget system. Every resource that is collected by workers and can be sold at the market pays into that system. E.g. if a worker collects 10 wood and wood is priced for 2 gold a piece, 20 gold is going into the budget and is distributed to the following areas:

• Economy

• Expansion

• Defence

• Research

Economy, Expansion and Defence also have sub-budgets for buildings and units. Over time, the areas collect more and more gold value, and once an area has enough of it the AI can make its first action like place a certain building, start a building upgrade or recruit a unit.

For each building, unit, or building upgrade, a gold value is calculated depending on the resource market prices. Each time an action is planned, the AI player checks first if it has enough budget.

If the check is successful, the action is only executed if there are enough resources available. This changes as soon as the player has a marketplace constructed. It can now trade any resource at the market, though prices change slowly with every buy and sell order, and a significant trading tax is applied.

There are exceptions where the budget is ignored, like a shortage of food, a hamlet revolt or an outside attack. The budget is recalculated and redistributed every now and then to reflect the correct market prices and due to rounding errors which occur over time. Example of a budget defined in the content editor:

The AI player can switch to different budgets, depending on their situation. E.g. he realises the player wants to destroy him with constant attacks and then switches to a defensive strategy. The budget is redistributed. Most of the resources are invested into the economy and defences to make sure it's not overrun by the player.

The following budgets are currently available:

• Economy

• Expansion

• Defense

• Research

• Weaken player

• Destroy player

Depending on the game state and the rank of the player, the main strategists (explained below) will decide which budget the player is switching to. Budget switches are rare events and will only happen if the player wants to change their overall strategy.

The ranking happens in different areas, so the AI player knows where it stands in terms of army size, economy, etc.

The AI system I am using is a Hierachical task network[en.wikipedia.org]. The framework is an open-source library called Fluid HTN[github.com] developed by Pål Trefall. Special shout-out to him for making this open source, and also his great support whenever I had questions.

Each strategist has a defined area that tries to fulfil a multitude of tasks, and it consists of the following parts:

• A sensor detects and tracks all the changes in the world. It indicates if actions are needed, like the requirement for more workers, resources, buildings or troops.

• The data context saves the world state as well as all information produced by the sensor, the operators, and the utility selects.

• The utility selects different actions and decides which of them should be planned. E.g. moving troops to a province or recruiting troops at another location.

• The operators execute the planned actions and write them back to the world state of the data context. This is where the AI actually places the buildings, moves troops, etc.

• The domain definition is the overall structure that inheriting utility selects, operators and effects. Below is an example of how this looks.

• Blackboards for sharing data between sensors.

  This is one of the simpler structures which decides what needs to be done in terms of spying and exploration, e.g. recruiting, moving to a staging province or starting spying/exploration and recalling the formation is close to being detected.

• 

• Plans and builds hamlets.

• Manages residential houses, crop fields, mills, and worker assignment.

• Identifies optimal provinces for hamlets and places necessary buildings.

• Tries to improve beauty and safety for hamlets and provinces which have the potential to get a new hamlet.

The HTN structure allows the AI to make proper planning possible. As an example, here are the steps for creating a hamlet:

• Find a good province which is not too close to other hamlets and, if possible, not too close to enemy borders.

• If it's already owned, great; if not, start a conquest plan.

• Build the first residential building so that people can live in the province.

• Save the resources for building a town hall.

• Place and build the town hall.

• Try to improve beauty for more immigration and happiness.

• Found the hamlet when enough population is available, and the happiness is good enough.

• Once the hamlet is established, check for happiness, beauty and adjust taxes and food rations regularly.

Planning actions like this can take several minutes in-game, and the AI needs to maintain the plan or throw it away and replan if certain steps aren't feasable anymore. Similar plans are made for conquering/raiding bases or destroying temples, with negative effects on one's own territory.

• Selects worker measures, like recruiting, moving, disbanding and updating their assignment

• Pick up the identity, disarm the ruins and loot.

• Resource output measures like:

  • Build a resource building/upgrades.

  • Build a marketplace.

  • Adds and removes haul storages/mines.

  • Planting or chopping trees.

• Profit measures like:

  • Sell resources at high prices, buy resources at low prices.

  • Convert mana/or to gold if required.

  • Buying resources from the marketplace when required.

• Oversees recruiting, buildings, scouting, and offensive troop training.

• Organise a troop for exploring and executing scouting.

• Complex province conquest planning.

• Retreat or send reinforcements to fight,

• Organising resources and military raids on enemy bases.

• Selects research priorities.

• Identifies suitable provinces,

• Manages research buildings and upgrades.

• Build defensive structures in vulnerable provinces.

• Destroy old and unnecessary defensive structures.

• Trains defensive and summons defensive units.

• Coordinates troop placement in vulnerable areas.

• Reacts to direct attacks of provinces and hamlet revolts.

• Retreat from lost fights, abandon provinces.

The most important strategist decides which overall strategy the AI player is going to follow in the next couple of cycles. The selection of the strategy is decided by a variety of factors.

• Rank of the Player e.g. Economy, Military, Provinces, etc.

• Any AI or human players directly nearby.

• Current defence strength of border provinces.

• Match of spells and units of the surrounding enemies.

• Happiness of the population.

• Morale of troops and workers.

• Exploration and spying information, and more.

Once the AI player has gathered all information via its sensors, it scores different strategies against each other and decides on one. Once the decision has been made, the AI will stick to it for a certain number of cycles to prevent switching back and force strategies.

Once the switch has happened, all resources are rebudgeted, and the AI player starts making different decisions. The main strategist can also be influenced by quests and certain lore and story events, or by a surprise attack by a human or AI player.

I have additional ideas to make the AI more interesting, e.g. by coupling an AI player's mood to influence the scoring, which will make the AI less predictable overall.

Debugging is an important part of the AI development cycle. I have to understand why the AI does make certain decision and why it doesn't. For this reason, I allocated some time to a nice debug window, which I can overlay while watching the AI play. This helped a lot to find problems and errors early on.

I have created a data structure to configure all AI parameters settings inside my content editor.

I can configure building orders, defense building priority, recruiting building priorities, exploration unit lists, the number of minimal workers and maximal worker saturation, the number of workers per building, which skills get levelled up first, a strategy bias e.g. towards expansion or defence, link a variety of budget configuration, how often it spys at foreign provinces, the minimum number of defense squads and so on.

I can also define different personality data for each of the wizards, and in the future, let players select certain settings when playing a skirmish mission.

This will help to develop AI players with certain specialities. interesting personalities and more depth and replayability to the game in the years to come.

Currently the AI is playing decently. Far from perfect, by any means. In certain situations, the player can easily defeat it; especially seasoned 4X players. There is still room for improvement, and it will always be a challenge to get ahead of the current player strategies.

To mitigate this, I plan to add a difficulty system where the AI's resources get multiplied depending on the selected difficulty setting. This is for players who want to test their skills against AI opponents with a bit more punch.

The above screenshot shows the south AI of the current playtest map. It has conquered 8 provinces in about 200 cycles, has two hamlets, decent defences and a bit underdeveloped army, due to a fast expansion. It has decent access to all important resources in the game, 30k gold and a marketplace to buy any missing resources if required. The population is a bit low with 160, probably had underestimated the required food when founding a new hamlet. With 87 workers, its economy is a bit understaffed, again due to the fast expansion.

The above screenshot shows the north AI of the current playtest map. It has conquered 5 provinces, one hamlets, decent defences and army, due to a slower expansion. It has access to all important resources, 20k gold and a marketplace to buy anything, which might be missing. The population of 200 is great, regarding the start at a mountain, as growing food is a lot harder. It has 88 workers, which is a bit over the top, but regarding the food problematic still a good decision.

The next update will focus on the newly added features to the game, which is almost a year worth of content. Stay tuned and thanks for reading. <3