Orbital Obliterators

EXPAND . FIGHT . CONQUER

Creating an AI Decision System

Artificial intelligence is one of those things that I myself will tinker with forever, no matter how simple you make it, you’ll never quite be happy with an AI’s behavior… even if everyone else is. – Tom Day, 2015

For those that need reminding or those of whom who have just clicked onto this article, the contents below are relevant to the game “Orbital Obliterators“, and the process taken to make said game.


The AI Component

There is to be two different kinds of AI implemented into this game, at first, a simple ‘Barbarian’ AI, which has the following game limitations:

  • It cannot capture planets, thus cannot develop planets.
  • It cannot be bargained with and thus is a constant aggressive AI.

Therefore its running algorithm must only comply with the simple tasks which are: –

  • Move randomly about the map.
  • Attack any targets on the map, prioritizing ships over planets.

This above in effect makes it a relatively small AI. Furthermore the game will use values and statistics to define mostly all the states in game, the AI system can hook into this, and use the values in order to base its decisions. An application of fuzzy logic would seem to suffice for this application.

Fuzzy logic is an easy to read kind of AI logic, using vague sentences to justify its end goal and infinite ranges to define the overall bounds in question. Cox cited a conversation he had with a mathematician on the subject of fuzzy logic:

If you can’t explain fuzzy logic to me in one or two sentences, then it’s probably hogwash, and I’m not interested. (Cox, 1999)

This statement sums up the apparent simplicity that is fuzzy logic, in the sense that if the reading of the logic is complex, it isn’t suitable for use. The notion of this is appealing for a first time AI programmer as a simple AI system implementation, such as that of the ‘Barbarian’ AI needed. A summary of a basic fuzzy logic set for defining a new product price given by Cox below:

If the competition.price is not very high

Then our price should be near the competition price. (Cox, 1999).

This demonstrates the openness of fuzzy logic, the use of vague terms in this example will translate to varying figures in the sense of this game.

Scenario A: A barbarian’s ship targeting parameters:

If barbarian is close to player ship
Then attack player ship.

Scenario B: A barbarian’s ship chooses between targets prioritizing low health as a metric:

If barbarian is close to Player ship(s)
Then attack player ship where life is not very high.

In each example the game statistics such as ships current life and barbarian proximity in relation to player ships will all be recorded and thus plugged into these examples. This is the route that the AI will go down, with further complexity being added for the city-state AI, as a city-state will have to decide between which planets it upgrades as well as ship movements. Calling on more complex algorithms to be applied making use of weightings.

Scenario C: The planetary development decision for a city state: (extract)

If Weights.Playstyle is Aggressive
AND Aggressive TechTree has upgrade available
Then pick from Aggressive tree.
END

If Weights.Playstyle is NotAggressive
AND CityState is Under Attack
AND Aggressive TechTree has upgrade available
Then pick from Aggressive tree.
END

It is under this basis that the AI will be developed, using IF ELSE stacks to programmatically input the logic.The AI will hook into the player stats system and reputation systems to reflect on which player to prioritize and indeed, which ship.

The Problem of Path Finding

In several cases it will most likely be required within the programming to implement an AI algorithm to handle path finding, and also to use techniques to indicate which position the player objects are currently drawn and move them about the map. In this section the relevant mathematical techniques and algorithms will be reviewed.

Dijkstra’s Algorithm

Dijkstra’s algorithm, a path finding algorithm outlined by Dijkstra (Dijkstra, 1976) takes the core fundamentals of path finding, (an initial position, a target position) and sets the main metric of decision making as Cost.

What the algorithm uses is a predefined matrix of costs, associated with other factors predefined by the development and situation. Each path has a route and thus an associated cost with it. The algorithm looks at all costs and outputs a result.

With a world map grid in mind, this approach seems appropriate as each square would be assigned a cost. Obstacles may be present on the map, which would present higher costs to consider, and from this, a Dijkstra based algorithm would be most appropriate whilst remaining relatively simple.

Further to this, this algorithm can be used for the AI as well as the game mechanics for the player to help the AI make decisions on best routes to take to get to its target. Below  a small sketch depicts an example of route costs using Dijkstra’s Algorithm.

PathFinder

Getting the Surround of a Position.

Seeing as this world is a grid of that can extend for up to 3,000 squares, it is required as a first step to come up with a formulae that will allow the collection of all the surrounding nodes by a given radius as illustrated below if the AI’s position was that of (N). The diagram above shows the algorithm that is behind the system that gets an arbitrary amount of surrounding nodes from the specified node inputted. It works simply by drawing a virtual square around the node at the maximum height and length, worked out on line 2, further to this it works through each row in a nested for loop and selected a steadily increasing amount of nodes from the indent defined by the radius – the iteration. Once it reaches the middle row it’ll reverse the process. The addition of this piece of code allowed game mechanics that needed to manipulate radii around the selected node for example, a ships sight relative to itself and other nodes or a planets firing radius all come under the same algorithm.

aBarbarian Attack Decision

Now we have a way to ascertain which nodes are directly around us we can implement this process and apply some layered decision logic to define a basic defense strategy.

b

Above the process undertaken by a barbarian unit is displayed. This process defines what happened when a barbarian needs to decide whether or not to attack an enemy, and which enemy to attack if it has the choice. The circle labelled (R) is a barbarian refuge, the ‘mother-ship‘ that the barbarian must defend, in this instance, the barbarian overrides the usual choice of attacking the weakest Player (a) as Player (b) is closer to the barbarian refuge it needs to protect, if this wasn’t the case it would attack the weakest ship (a), and if no ships were present, attack the Node (N). If no targets are available it will orbit its Refuge (R).

City State Development Decision Tree

c1

The above shows the decision tree extract from a city states development choice factoring in if they are under attack. Industrialism is the Defensive strategy and Militarism is Offensive.

City State Deployment Decision Tree

d1The flow diagram above shows the decision tree implemented to decide whether or not to deploy a ship from one of the city-states planets. The core component to explore here is the use of a Dijkstra (Dijkstra, 1976) inspired cost algorithm to define whether or not the planet owned by the city-state is ‘at risk’… This is further illustrated in the equation below:

Cost =
    0 + 
    (All CityState Ships in Range - (2 * All Enemies in Range))
      + Friendly Ships in Range;
    if (Cost <= 0)
       {
          return Low Risk
       };
    if (Cost <= -4 AND >= -7)
       {
          return High Risk
       };
    else
       {
          return High Risk
       };

The Cost is used not only to assign the initial risk to the node, but referred to time and time again when calculating further choices. For example, whether or not to save money in the long run if the city-state feels threatened by the surrounding troops.

City State Attack Priority Implementing Risk.

Below displays the priority of attack that the city-state uses to decide which ship to engage when presented with a choice. This process too implements the planetary risk calculation outlined above to help a city-state ship decide whom to attack.

f1 (2)Once all of these factors have been implemented the end result is a well controlled AI system, which does still tend to surprise me in what it can get up to.


Further Reading

Contained in the ePortfolio on this site are multiple articles outlining how this project was made and some of the research techniques and planning that went into the project as a whole. Below are a few honorable mentions:

Picture1 Project Planning

The critical part of a project by far is never the coding although we all want it to be. Planning a project with a good methodology is the key when it comes to success. Read More…

Picture4Conducting Research

Conducting research whether it is market research or research into appropriate techniques is the cornerstone of any modern project and was not underestimated in this project. Read More…

Picture3Carrying out a Study

Its important to look into what kind of game you’re really making… That way you can insure that you’re putting in the right level of cool when developing. Read More…

Picture5Game Statistics System

To keep a player entertained when creating a game that will intentionally last a long time, you need a robust system of content to keep them enthralled right up to the moment. Read More…

Picture2Inside the World Engine

The universe is a vast empty space of unimaginable possibility, this games most defining moment has to be its attempt to capture a little of that magic with the World Engine. Read More…

Picture1332Building the Game Engine

Perhaps the most complex and challenging of the whole system, the main… system! The Game Engine forms the integral glue that holds and manages all the data. Read More…

<< Previous Article | Back | Next Article >>

References

Cox, E., 1999. The Fuzzy Systems Handbook. In: The Fuzzy Systems Handbook. 2nd ed. New York: AP Professional, pp. 1-43.

Dijkstra, E. W., 1976. A Discipline of Programming. 1 ed. Englewood Cliffs: Prentice Hall.