About

Demo project made for the Videogame Design and Development degree subject Artificial Intelligence.  The goal was to make a a tactical role-playing game (1 vs. 1) in which a player and an AI fight for dominance in an area. Players must deploy troops, capture neutral objectives, and advance across the map to destroy the enemy base.

Project Guidelines

• You cannot use Unity's NavMeshAgent class, you must implement the AI techniques yourself.
• The environment must be extended, reusing elements from the game or creating new ones.
• You need to add more instances of the units to the expanded environment, and start the game with a randomised layout.

NPCs

We can define our IA into two classes, static and dynamic.

Dynamic agents:

• Scout: The Scout is the most basic unit and the one you will start the game with.

• Grenadier: The Grenadier it’s an upgraded Scout that can throw Grenades. Grenades damage all units in a given radius, including allies (this piece of information is relevant for the influence map of the Throw Grenade action.

• Engineer: The Engineer  it’s an upgraded Scout that can build up to two turrets. Turrets are static units that can shoot once per turn. Turrets have long range but low damage output.

• Berserker: The Berserker it’s the fastest unit, and can perform powerful melee attacks that defeat most enemies in one hit.

• Juggernaut: The Juggernaut it’s a beefier Scout. Has the highest health, range and damage output.

	SCOUT	GRENADIER	ENGINEER	BERSERKER	JUGGERNAUT
HEALTH	100	100	100	100	200
SHOOT RANGE	5	5	5	5	6
DAMAGE	40	40	40	40	80
MOVEMENT	3	3	4	5	3
COST	300	700	1200	1500	2500
SPECIAL ACTION	NONE	THROW GRENADE (Distance: 4)	BUILD STRUCTURE (Deploy 1-2)	MELEE ATTACK (Distance: 1)	NONE

Static agents:

• Turrets: Engineers can build this unit. It has 7 of range and 40 damage. Only two turrets can be placed simultaneously.
• Territory Flag: Flags are capture points found in neutral areas. Units can interact with them to reclaim the area. The base can spawn new dynamic agents in all claimed areas.
• Base: The base is the most important unit. The game ends when either player destroys the other player’s base. Only the base can spawn dynamic agents. It has 500 health.

AI Implementation

As a requirement in the course, we were told that the AI must meet the three levels of any AI in a video game: movement, decision making and strategy.

For the movement level, we considered different solutions, such as recreating Unity's NavMesh class by ourselves. However, the complexity of the project itself forced us to reuse the A* algorithm we used in the first project to provide more complexity to the AI in the other levels of operation.

As this project is a turn-based RPG, it is assumed that only one action can be performed at a time, so all the optimizations made for the previous project are not necessary. So we kept the grid, and the heap so that the algorithm was optimal enough to not slow down the game, but we eliminated the use of path following because we didn't consider it necessary. We also kept the pathfinding calculation in a separate thread so it wouldn't interfere with other movement calculations.

Additionally, the grid updates the walkable and non-walkable nodes dynamically. This way, when map obstacles are created, the grid is automatically updated. Furthermore, when an obstacle is destroyed, the grid is also updated. 

For the decision-making level, as with the movement level, we considered different options. The first was to implement an AI with machine learning, but we had neither the knowledge nor the time to do it, as it is a subject that is studied at the end of the course. 

On the other hand, we tried to implement an ID3, so we represented an analog game board and tried to play as if it were a multiplayer game to see which actions were the most correct and what reasoning led us to it. Then we created a table with all the possible variables and which action we would trigger at each turn. Once we got to this point, we didn't know how to implement the ID3 algorithm or how to continue with the development, so we decided to discard this option as well.

Finally, having the whole structure of a behaviour tree already built, we decided to continue with this branch and finish developing it completely without ID3. This way, even if the behaviour tree was not fully optimised, we would have a functional behaviour tree that did what we needed.

We implemented two behaviour trees, one for the units, and one for the main base. The reason for using only one behaviour tree for all the units in the game is that the code is structured according to the actions and not according to the units, so the units depend on the actions and not the other way around.

However, each action has different nodes within the mesh where it can be performed. To calculate which is the best node where to act, we decided to develop an influence map that, depending on which action the behaviour tree selects, calculates its attached influence map with its points of interest and danger points. So, for example, the action of throwing a grenade creates points of interest where enemies are located, and points of danger where allies are located, thus calculating the best position in the grid where to throw a grenade.

Generic Unit behaviour tree:

Base behaviour tree:

Some actions influence map:

AI Communication

For the communication of the different units and their general behaviour, as well as at the decision-making level, we think about making communication and behaviour using machine learning. This, again, was infeasible due to the ignorance of this type of AIs, increased even more by the development time we had left.

Taking advantage of the fact that we had the territory flags, we decided to build a Finite State Machine conditioned on the territory flags that the AI possessed. So we found four states: ultra-defensive, defensive, neutral and offensive.

On the one hand, we have the general states that are defensive, neutral, and offensive. Each state is determined by who owns the territory flags on the map. This means that as the game evolves the units move towards the taking of the territory flags and finally towards the player's base.

Regardless, as soon as a player's unit is deemed to be close enough to the base to pose a danger, the AI goes into the ultra-defensive mode, causing troops to retreat to the base to protect it.

Technical features

• Custom pathfinding is made with a grid mesh and nodes with variable sizes
• A* algorithm for the NPCs' movement. 
• The open nodes are stored in a heap, and all pathfinding is calculated in a separate thread.
• Use of steering behaviours to follow calculated paths.

GAMEPLAY

Summary

Turn-based 1v1 tactical RPG in which one player and one AI will compete for domination of territory. Deploy troops, capture neutral objectives, and advance across the map to destroy the enemy's base.

Features

• The player can deploy troops using action points and a custom money system
• There's a cover system in with, the agents become untargetable by enemy attacks.
• Fog of War limitates player's visual.