Welcome to my final year project blog !

I will be updating this blog and trying to show you my progress during the next few months.

What is my project about? It's about Artificial Intelligence in Real-Time Strategy Games.

It has been proved that real-time strategy games are one of the more thorny genres as far as AI is concerned, and a good architecture and planning is necessary to ensure success. 

One of the things that motivated me to start with this project was the next paragraph, found in AI Game Wisdom 1 book:

“Undertaking the development of an RTS AI takes guts. It is one of the hardest genres to develop AI for and will test your abilities to the limit”

Compared to other genres, the options and decisions that you are able to make in a RTS are much bigger. That is what makes the AI for RTS extremely complex and, at the same time, an interesting field to research as a game developer.

Great games such as Age of Empires, Star Craft and The Settlers 7 also inspired me to choose this subject.

This thesis will explore the possibilities for developing an efficient AI for a RTS, capable of making reasonable decisions during the progress of the game and represent a challenge to a human player. All this will be implement in a generic 3D game engine.

The final product will be an executable demo, were you will be able to observe the AI build a productive empire from scratch in a 3D environment. The idea is that every time you execute the demo, the AI will behave different as it can choose different paths to achieve its final strategy, but always taking into account the efficiency.


Facts:

- Dates of the posts have been modified so the order of reading is top-down instead of down-top. Ignore the posting dates as they are not real. It's not a smart solution but for the moment Blogspot doesn't offer any other.

-This is not supposed to be a tutorial and it won't be. I'm doing this blog so my tutor and other people can follow my progress through my project, and have a general idea of my work and the decisions I've been taking.

Choosing the right techniques

After some intensive research, I have come to what I think that are the best AI techniques to carry out such a complicated task. It hasn't been easy, as there are lots of options documented out there.

In this blog I will mention only the chosen techniques (in my thesis I refer to other techniques investigated).

The technique to implement is a Multi-agent system with a Goal-directed behaviour. With this we will create the "brain" (a non-physical entity) able to handle all the game information and act logically.

We will also have physical agents inside the world like soldiers and villagers/workers. For this agents I will be using the well known technique Finite State Machines, but I will talk about them in other publication.



Multi-agent system

A Multi-agent system, as it names says, is a system composed of multiple interacting intelligent agents within an environment, and it is used mostly to solve complex problems impossible or too difficult for a single agent.

This image shows the inner workings of an agent:

To sum up, the agent is an autonomous entity that has inputs (perception of the current state of the world) and outputs (actions). 

(more detailed information can be found here http://en.wikipedia.org/wiki/Intelligent_agent ).

Here is a list of the different agents that I am going to implement and a brief description of its tasks (following Bob Scott advices, AI developer for Empire Earth). Each agent will be independent from each other, but there will be a strong communication between them and a client/server relation.

Strategy Agent: This is the highest-level agent and it's responsible of the long term decisions. The main task of this agent will be decide the strategy to be carried out in this game (a fast attack with basic units, also known as rush, play defensive or play aggressive etc.). It also coordinates and set limits other agents (spending limits).  If the unit agent requests resources to train a unit, this agent may accept or reject the request, even if there are enough resources.

Unit Agent: Responsible of training units, keep track of them, prioritize the training in case there are several units requests and communicate with the building agent if a building is needed for a unit( for example, barracks to train soldiers).

Building Agent: Responsible for the placement of the structures and towns. Most of the work of this agent is to analyse/evaluate the terrain in search of the best places depending on the building. For example, if a lumberjack hut is requested, it will find the best place to ensure success gathering wood.

Resource Agent: Responsible for tasking the villagers/workers, expansion to new resources and attend request for other agents.

Research Agent: Responsible for researching new technologies based on their usefulness and cost.

Combat Agent: Responsible for directing the military units and requests units to the unit manager.

 (due to the amount of work involved in this project, which is basically create a RTS game and its AI from scratch, I am not sure if there will be implementing a combat system or not. The demo will be mostly focused on the resource management).

Goal-directed Behaviour

Each agent is an expert on his field, but knows very little about other's agents tasks. For example, the Unit agent will have no idea of how/where to place a building if it needs one, instead it will just ask the Building agent for it.

The Building agent on the other side, will have no idea of why that building was requested, it will just try to find the best possible place for that concrete building and place it as soon as possible. This is the client/server relation I commented above.

The agents behaviour is driven by their own goals, and each agent has its own personal goals. Those goals can be treated as "sub-goals" of the Strategy agent goal.

Only if all the agents work and collaborate properly with each other, the strategy agent will be able to carry its "major" or main goal, which is defeat the opponent.

Terrain & Pathfinding

As mentioned before, the implementation and demonstration of my AI will take place in a 3D environment inside a Game Engine.

The engine I'm going to be using is Unity 3D, mostly because I have 2 years of experience with this engine and I love every part of it. Also, working with a known game engine will save me a lot of time.

Some of the graphics assets are part of a Pack I bought on the Unity Asset Store, and some of them are mine (I use Blender for modelling and unwraping and photoshop for texturing).


Map

I have been setting the environment where the acction will take place. The map consists of a limited field, and distributed resources. I have done the map for two players because it will be great to watch two AI competing against each other for the resources.

One of the starting areas has more resources around it than the other one (more gold and stone). This will give a significant advantage to one of the AI players, and it will show how the AI adapts to different situations.

The resources are food, wood, stone and gold ore. In this image we can see all of them except food, which will be manufactured in farms.

The resources and the game itself will be explained in the next publication.

A* Pathfinding

Although I have implemented my own A* pathfinding for a 2D game in C++, adapting it to the 3D environment and C# could take a lot of time and it's not the main objective of my project. For this reason, I will be using Aron's Granberg A* Pathdinfing to move all my units.

I have already implemented and tested it inside Unity, and I couldn't be happier with the results. Here is a image of some units avoiding obstacles (stone in this case).

The small red cubes at the bottom of the stone are non-walkable nodes, and they are avoided by the units.

Game Design

In this publication I'm going to do a brief explanation of the design for my RTS game.

We have four key elements in our game design: Resources, Units, Buildings and Upgrades. It's obvious that I'm not going to create a complete and balanced RTS game, with all the option that this kind of game usually have (that could take me months), but at the same time I need enough variety to explore and play with the AI to see interesting results.

For example, it would be boring and "easy" to create an AI for a RTS game with only one kind of resource (gold), only two units (villager and soldier) and one building (barracks). Why? because the game would be so linear;

Produce villagers -> get gold -> build barracks -> produce soldiers -> "win".

Instead, we want the AI to have different paths to achieve its goals, different possible strategies. In the game I have designed we have four different resources, four kinds of units, nine buildings and six different upgrades.

I have also defined the amount of resources needed for everything, the times of construction for buildings and training for units, and the time it takes to gather each resource.

Here is a outline of the game design (some  of the tables are minimized so they could fit in a single image). Upgrades also consume resources and take time to research, although it is not shown in the image.

(click on the image to enlarge)

I think that with this design there is enough variety to plan different strategys.

For example, we have a University that you need if you want to do research, like double bit axe (gather wood 20% faster), or improved pickaxe (gather ores 20% faster). We also have a weak soldier (pikeman) and a strong soldier (Knight) which is more expensive but is stronger.

If it's planning a fast rush of basic units (pikemen), is it worth to build a university as soon as possible and invest on some research to gather wood and food faster? or just focus on getting pikemen and forgetting about everything else?

How many workers is it going to allocate to each resource?

In the early game is it going to focus only in improving its economy (tons of villagers for tons of resources), or is it sacrificing some resources for training soldier and have some defenses?

I want to have different options in every phase of the game. That will allow me to create different AI "profiles", and try to make the AI as unpredictable as possible.

Villagers Finite State Machine

As mentioned in one of the first publications, we have two kinds of agents. Here is a quote for those who don't remember it:

"The technique to implement is a Multi-agent system with a Goal-directed behaviour. With this we will create the "brain" (a non-physical entity) able to handle all the game information and act logically.

We will also have physical agents inside the world like soldiers and villagers/workers. For this agents I will be using the well known technique Finite State Machines, but I will talk about them in other publication."

In this publication I'm going to talk about the Finite State Machine I have designed for the Villagers, the agents responsible for gathering resources to rise the empire.

Here is the Diagram of the FMS:

Villagers are in the IDLE state by default until someone orders them something to do. Right now there are four functions to task the Villagers, and the only thing you need is to have the correct building in a good position (for example, if you want to gather wood you will need a Lumber camp in a good spot with lots of trees):

AssignLumberCamp(GameObject lumbercamp_building);
AssignStoneCamp(GameObject stonecamp_building);
AssignGoldCamp(GameObject goldcamp_building);
AssignBarn(GameObject barn_building);

So, by calling the next line of code, Villager.AssignLumberCamp(GameObject lumbercamp), it will automatically start working and it won't stop until it can't find more trees (assuming that there is a Lumber camp placed and it's in a good position near trees) or someone tells him to stop.

Here is a brief description of the states:

Idle: It does nothing.

Search resource: Try to find the nearest resource to the given building within a certain limited radius and selects it.

Go to resource: Moves to the selected resource (uses A*).

Gather resource: Gathers resources from the selected resource (It takes 12 seconds to gather 10 resource units more or less, although it depends on the resource). It stays in this state until the max resource capacity has been reached (10 units) or until the selected resource is finished.

Deliver resource: Moves to the assigned building to deliver the resources (uses A*).

I have used the green colour in the FSM diagram to mark the "natural flow" of the villager if everything goes fine, which is:

Search resource -> Go to resource - > Gather resource-> Deliver resource -> Go to resource - > Gather resource -> Deliver resource etc.

There are 3 "special cases" that interrupts the natural flow of the FSM. They are the white arrows with text in them:

Search resource -> Idle: The Villager was unable to find any resources so it returns to the Idle state. This is because the building has been placed incorrectly or the resources around have been already gathered.

Gather resource -> Search resource: The villager finished the selected resource but hasn't reached its max. resource capacity. It searches for another resource near him before going to deliver it. So if it has 7/10 of wood, and the selected tree has been completely chopped, it will try to find another tree to reach 10/10 before travelling to deliver it.

Deliver resource -> Search resource: It can be the case that, during the travel to deliver the resources, your selected resource (a tree for example) was chopped by other villager. In that case, the villager will try to find another resource to keep working. Otherwise, it would travel to an empty resource, being a waste of time.

After hundreds and hundreds of lines of code and lots of hours invested, I am happy to show you the first video of my demo:

In this video we can see a bunch of Villagers in the map (they are white capsules for the moment) and how I assign them to gather different resources. The buildings for the resources gathering have been placed by hand.

As I have mentioned, the Villagers depend on the correct placement of the building to gather resources efficiently.  Who is the responsible of placing the buildings? The Building Agent, which is the first non-physical agent that I am going to implement in the next days.

The Building agent will requite a lot of work, because it needs to analyse the terrain and find the best spots for each resource, and each building has its very own requirements.

Building Agent - Generic Buildings

The main function of the Building Agent is to attend requests for placing buildings. Some buildings require a very specific location to operate correctly, and some others not.

So we could divide the buildings in two types depending on its requirements, resource buildings and generic buildings.

Resources buildings like Lumberjack Hut, Stone mining camp and Gold mining camp, require a very specific location, whereas other buildings like Barn, Barracks, Monastery or University don't have those requirements.

In this post I am going to explain the Generic building placement. The only requirement of these buildings is to find a spot with enough space to place it around the Bastion (the main building). There are different approaches to solve this problem,  but this is the way I have solved the problem.

First of all, I have implemented some kind of grid system into the building agent. This system has 2 variables, BuildNodes_Iterations and BuildNodes_Space and allows the Building agent to create a grid of nodes around the selected building (in this case the Bastion), and use those nodes to find free spots for the generic buildings.

In this Image we can see the BuildNodes that it has generated around the Bastion with BuildNodes_Iterations = 4 (yellow numbers/lines ) and BuildNodes_Space = 25 (red numbers/lines ).

Basically, iterations is the amount of  node "squares" around the selected area, and Space is the space between nodes. 

Each BuildNode is a potential spot for a Generic Building.

Here other grid configurations:


BuildNodes_Iterations = 2, BuildNodes_Space = 50

Not enough BuildNodes

BuildNodes_Iterations = 6, BuildNodes_Space = 15

Too many BuildNodes




As you can see with this system I can easily modify the amount of BuildNodes around the selected area, and adapt it to my needs. Depending on the game, the number of different buildings, the size of the buildings etc. one configuration will be better than the other.

For my needs I think that BuildNodes_Iterations = 3 and BuildNodes_Space = 40 will do. I need enough nodes to have some diversity and randomness when placing the buildings, but not too many BuildNodes to avoid unnecessary and redundant calculations.

Once we have the BuildNodes grid, it "randomly" (some simple hints are given for each building) selects one and try to place the building there. If there are no obstacles within a certain radius (each building has its own radius), it places the building there, otherwise, it keeps looking for a valid BuildNode with enough free space around it. If no BuildNode satisfies the space requirements, the order is cancelled.

Here is a video where I order the Building Agent to place some buildings, and see how well this system works.

The solution is quite simplistic, and further development of this system would be probably required in order to have a well-organised city/empire. But for the moments it works pretty well, and it fits my needs for the project.

In the next post I will talk about Resource Buildings, which are more complex because they don't only need a free spot, but also the right or the best spot to operate correctly.

Building Agent - Resource Buildings

As mentioned in the last post, resource buildings require not only a free spot to place the structure but also a good place so the villagers can gather resources efficiently.

Resource buildings for food, gold and stone were fairly simple. Barns could be considered almost like a generic building, as it doesn't need a specific location to perform properly, as long as there's enough room in its surroundings to place farms. Because of that, the Barn is the only Resource Building that uses the Building Agent's BuildNode system.

Lumberjack hut and minings camps are placed using a more accurate system that ensures the building is close enough to the resource.

Gold/stone mining camps were also quite easy. All the stone and gold nodes contain the same amount of resources, so in this case we only need to find the nearest node, and place our structure there.

As for the Lumberjack hut, things were a little bit more complicated than expected, and ended up in a quite complex algorithm. My first approach was obviously find for the nearest trees to the bastion, and see how many trees were around those trees, and then, repeat that search 4 or 5 times (for the 4-5 nearest trees). The tree with the higher number of surroundings trees would be the best spot to place the hut.

I quickly realized that it wasn't going to work, and I didn't even try to implement it. Lets see the next example:

Yellow spots are the ones that I consider the best to place the Lumberjack hut and red ones are the ones that the Building Agent will consider using the mentioned technique. As you can see, looking for the nearest trees to the bastion X times is not the solution, as there are a hundred ways this method could fail depending on the map and the trees distribution. Using a brute-force technique and doing 100 iterations ( X= 100) is not a solution for me, as it could work, but it would be awful in terms of optimization.

To solve this problem, I realised that a whole analysis of your surroundings should be done. I'm not going to explain the whole process here, but after several hours, I had it working.

In this image we can see the the same situation but with my new system. For debugging purposes, I have done that all the analysed trees grow x2 in size, and the best tree grows x3 in size (anyway I've coloured them so they are more visible in the image).

By the distribution of the analysed trees (red ones) you can see that it did pretty well searching equally on the Bastion surroundings for not missing any potential tree spot. The proof is that it successfully found the best spot (with 108 surrounding trees) with only 14 iterations, and placed the hut there.

So we have a system that detects the best spots for our resource buildings.

Once we have a tree or a gold/stone node selected as the best one, we need to place the building there. The thing is that it's not a trivial task, because you need to place the building  as close as possible but avoid all kind of obstacles.

What happens if the best selected tree is a little bit deep in the forest? You can't place the Lumberjack hut in the middle of the trees ignoring all the collisions. Same can happens with gold/stone nodes, they can have trees/mushrooms or other blocking elements in its surroundings. With our human eyes, we can easily solve that problem, but take in mind that our Building Agent doesn't have such an extraordinary system, so we could consider it's blind.

To solve this problem, I have designed an accurate Obstacle Avoidance system that it's used for this purpose. In this video we can see some kind of "fight" between me and the Building Agent. He is trying to place a Gold mining camp and I'm trying to block every free place he finds:

                                                             



So it seems that we have everything we need to place resource buildings around the map. Lets see what happens:

                                                               

Remember that video where I showed the Villagers gathering resources? in that video I had to place the buildings by hand. Now there's no need for that any more !

We have smart villagers that gathers resources as long as they have the appropriate building in the appropriate spot, and we have a building agent able to satisfy that need. So plenty of resources for our empire are 100% guaranteed !!

We are slowly removing the "human" interaction. In this video, I was the one giving the order to build things. Next step is that those orders are all given by the AI itself.

Now I need to do a Protocol/Communication system between the agents so they can communicate properly in that client/server relation.

Final goal is to remove all human interaction, so you can just execute the demo and enjoy the show while you realx.

Resource Agent

This agent is responsible for creating an economic system to support and achieve the strategy with help from the other agents. This agent has a strong communication with the Unit Agent and also Building Agent.

It starts by calculating the total resource requirements of the strategy. For example, if the strategy agent asks for five knights and five clerics, it will calculate the cost of these ten units and also the additional cost of their dependences (in this case Barracks and Monastery). If the initial amount of resources is not enough to satisfy this strategy, it also adds the cost of the resource buildings and workers needed to fulfill the missing resources.

                                                                 

Once it knows the total resources needed , it makes a calculation of how many workers are needed. After that, it distributes them among the different resources by calculating percentages. The percentage of  needed wood over the total needed resources is the percentage of workers assigned to get wood over the total needed workers. With this we ensure that if we need three times more wood than any other resource, it is going to spend three times more workers to gather it compared to other resources.

All the mentioned parts above relay on mathematical formulas that unfortunately I can't show because this blog doesn't allow Mathematical Symbols and showing them picture by picture would be really tedious. Nevertheless, I mention and show them in my thesis paper.

Although the developed formulas can be used in pretty much every RTS, some parameters should be modified and adapted depending on the gathering speed for each resource and so on, as every RTS game is different in that aspect.

As for the order of the resources assignation when training new workers, it is done with certain randomness by assigning weight at the resources. For instance, food has the biggest weight because it is the main resource needed to produce more workers and avoid stalling. Therefore, the first workers will mostly get assigned to gather food and wood. 

Percentages for resources assignment are:

-          Food  34%

-          Wood  28%

-          Stone  22%

-          Gold  16%

Gold is a resource needed for advanced combat units, therefore it has the lowest weight at the beginning to have a better boost on the other resources.

If one resource has all its workers already assigned and a worker rolls for that resource, it rolls again.

This system is probably less accurate than if we scripted the resource order by code depending on the required strategy, but would be less adaptive and we also gain a bit of randomness, which is good to avoid the exact game over and over again. 

After some tests giving the AI the same amount of resources and the same amount of units to train, I realised that changing the order of a single worker in the first minute of the game, can lead into "major" differences in minutes 7-10, which is great because although the overall strategy and the final result is pretty much the same, the paths it follows to achieve it are slightly different, giving always new experiences to the player.

The firsts test results of this agent were really positive.