Monthly Archives: January 2015

You are browsing the site archives by month.

AI in Imperium

Overview of the AI

The AI system in Imperium has been coming for a long time, it can be measured in years by now. I’m very bad at doing AI, and it seems so is everyone else. There are a lot of nice ideas out there, but very few good “design patterns” to really help you on your way. Things like genetic algorithms and fuzzy logic does not go too well with a game played in real time on an iPad. Things like minimax works well for board games where you have turns and well defined game states, but not at all for my use case. So I had to come up with something own.

The most useful article I’ve found on the Internet that has helped me is http://www.armchairgeneral.com/unity-of-command-a-look-behind-its-challenging-artificial-intelligence.htm which discusses how Unity of Command has done their AI. UoC is a turn based and hex based game on a strategic scale in a modern environment, so it is actually very far from Imperium, but the ideas seem to be quite applicable to Imperium too. The AI in UoC uses a form of pattern matching to decide what to do. It looks at the game state and tries to identify certain patterns and when found performs a given action. With lots of patterns it can react to what is happening in the game and do sane moves. So I thought about using the same ideas, partially because it’s all quite simple to implement and easy to debug.

Strategic planner

First a strategic planner will look at the scenario as a whole and decide what to do. If the AI is supposed to be attacking then it will check objectives and allocate organizations to try and take the objectives. If the AI should defend it will mostly just just set an overall flag “hold at all costs”. The strategic planner does not really handle individual units at all, it will only do the big decisions. The strategic planner is updated at the beginning of the scenario and periodically after that.

Tactical planner

The tactical planner looks at individual units and organizations and decides what to really do. If the strategic planner has decided that an organization should take an objective it will try to do so. To do these real unit actions a rule engine is used, as in UoC. The rule engine operates on lots of conditions that are various snippets of state.

Conditions

Conditions are one of the foundation pillars of the AI in Imperium. Conditions are basically boolean or numeric values that are updated based on game state. there are three different forms of conditions: global conditionsorganization specific conditions and unit specific conditions. The conditions are updated at regular intervals and form the knowledge base that the rule engine then uses to determine what to do.

Global conditions

The global conditions are related to the overall game type and how the game has progressed. There are conditions like:

  • is this a game where the AI defends?
  • are all the objectives held by the AI?
  • are we playing the first minutes of the scenario?

The global conditions rarely change and are not too frequently updated.

Organization specific conditions

All units belong to organizations in Imperium. The basic ones are the battalions, brigades etc that have been defined in the scenario editor. In general all units should be given a battalion or similar and “free” units should be avoided. The free units will each be given an own organization by the game, but one that the player does not see. Examples of conditions related to organizations are:

  • should this organization take an objective?
  • should the organization advance?
  • should the organization hold?
  • is the headquarter unit for the organization alive?

The organization specific conditions are on a much lower level than the global ones, but they do not contain information about individual units.

Unit specific conditions

This group contains most of the conditions and contain state about units. Each unit has an own set of all these conditions. Examples of these conditions are:

  • does the unit see enemies?
  • does the unit have enemies in its field of fire?
  • is the unit in column or formation mode?
  • is the unit a support unit?
  • is the unit under fire?
  • does the unit have a target?
  • does the unit have a current mission?

There are a lot more than these. These conditions are updated most frequently of all conditions, as the state can change very quickly. There are quite a lot of these conditions as each AI unit has an own set of them. A big chunk of the AI time is spent updating these conditions.

Rule engine

The conditions in themselves don’t really do anything and the strategic planner only draw up high level orders. The real action takes place in the tactical planner which uses a rule engine to do the low level giving of orders. The tactical planner mostly uses a simple rule engine to decide what to actually do. The engine contains a set of rules which based on conditions decide what to do. Each rule is checked against each unit and a matching rule is executed. All rules have a priority that define the order in which the rules are checked and the first rule to match for a unit is the one that gets executed and the rest are skipped. The rule engine is executed every few seconds for each unit.

The rules look at the global, organization specific and unit specific conditions and use basic boolean logic to see if they apply. A simple rule that advances units at the beginning of an attack scenario would look at these conditions:

  1. the scenario must be an attack scenario from the AI’s point of view (isDefendScenarioCondition == false)

  2. the scenario has just started (isBeginningOfGameCondition == true)

  3. the unit must not have a current mission, e.g. be moving or firing (hasMission == false)

  4. the unit must not have enemies in range (hasEnemiesInRange == false)

  5. the unit must not be under fire (isUnderFire == false)

If all these holds then the rule matches and it will be executed for the unit. A different rule for advancing on an objective could add that the organization should have been tasked with taking an objective (shouldTakeObjective == true). The advancing rule above would when it matches find a suitable place for the unit to move to in the general direction of “forward toward the front”. It would check some semi random positions using the path finder to find one which can be reached easily. This helps to avoid a unit going a long way around some impassable obstacle like a river or woods.

The actual “do stuff” thus takes place in the execution part of each rule and that part is just as important as finding the right rule.

Challenges and future work

A number of challenges still remain before the AI player does anything sane at all. The conditions need to be accurate and updated often enough for them to be useful. This is currently in a fairly good shape and there are conditions for a lot of different things and new ones are easy to add as needed.

Identifying fronts and enemy concentrations

The current rules just more or less assume that the enemy is towards the left on the map, as all scenarios so far have the human player start at the left and the AI at the right. Obviously this is not enough and the AI needs to be able to identify where the threats are and move intelligently towards front lines. So far this issue is not too big as the AI is not very mobile at all, especially after the scenario has started up a bit. To recognize front lines and where the enemy really is the influence maps can be used. These are already calculated but just not used anywhere. Using them in any way turned out to be immensely hard. From the influence maps a front line map is also calculated. It basically checks where the influence map changes sign and the influence “switches player”. This gives a simple matrix where the front line will have a different value. This map could be used to find the closest front for any unit by just tracing some rays in the matrix from a unit toward expected front line until the map value changes. Could also be done directly with the influence map of course.

Using terrain effectively

Understanding terrain is also not trivial. The scenarios do not have any elevation changes at all which makes things easier. Some terrain types however are impassable for some units and it can be beneficial to place units in some other terrain. Artillery for instance can not move through woods, but woods provides some cover form infantry units. The path finder allows units to navigate the map and find the fastest paths so that artillery never tries to move through woods and gets stuck. Nothing however tries to find optimal or even good positions for units so that they are in proper cover but have good field of fire etc. For this, I have no idea what to do.

Handling assaults and identifying good targets

The AI should be able to identify good targets to fire at. This is already more or less done and uses the same code as the the human player. All units will automatically try to pick a target that is in range if they have no other mission. Targets are given a value based on the range, if they are in the attackers field of fire or not and if they are advancing, assaulting or retreating. The target with the highest value will be picked. The AI does however currently not identify targets that it could successfully assault and does not do any kinds of coordinated attacks. This is perhaps something that the strategic level planner needs to do?

Future work

More rules will be added, the current ones will be tested and there will be a lot of tweaks to everything. Giving the AI a better situation awareness and mobility will be important as well as having it avoid totally dumb moves. There’s a lot to do… 🙂

 

Still not dead :)

It’s been half a year since I posted anything here. I’ve been working on and off on Imperium and actually made some good progress. There should be a beta version out hopefully this year.

The whole game is fairly complex and it takes a lot of time to get things right. In retrospect, I should have started with something way simpler and only later added to it, but that’s not how it works for me. So, there’s still a fair deal of things to get done until I can put out a 1.0 release, but nothing that is really big. The hardest bit is still the AI. I do have a solution that I think will work fairly ok. The framework for it is more or less done and I need to add in the rules that form the actual intelligence part. That is not trivial, but it’q quite doable and to some extent fairly mechanic. The AI does not have to be perfect, but it should do something that looks somewhat intelligent, especially as I’ve decided to disable the online multiplayer for the 1.0 version. I’ll add it in later once the single player experience works ok, probably for a 1.x or a 2.x version.

I have some new graphics too. Mostly it’s for the setup parts and does not affect the gameplay in any way, but it looks brilliant. Got in touch with a very talented artist that’s drawn a new splash screen and a new logo. I’m very happy with the new stuff and now I’m thinking of having him redo some other parts of the graphics too. We’ll see how much I can afford.

From now on I’ll try to write some more regular updates about what’s going on (if anything).