vistulans
Vistulans - graph-based strategy game about west slavic tribes with myths, legends and fantasy stories
Vistulans - Game Dev Diary - Days 29-36 - Enemy AI + Playable Link
Meat Boy
Posted on April 11, 2020
At the end of the journey with the development of my game, I had been working on something that pretends to be an enemy artificial intelligence. In this case, AI is a set of algorithms which allows making a decision against the player.
To briefly remind what the project is about:
Game Vistulans is named from Vistula (Latin name of Wisลa - large and long river in Europe and historical Slavic tribes near) is inspired by Slavic mythology and graph-based strategy games. The game is written in C# with Unity Engine.
โญ Please star on GitHub if you like this project and want more ๐
pilotpirxie
/
vistulans
๐ฎ Vistulans - graph-based strategy game about west slavic tribes with myths, legends and fantasy stories
AI in Vistulans is separated into four different topics:
- Finite-State-Machine for managing different states of vertices
- Dijkstra-like greedy algorithm for offensive decisions
- Breadth-First-Search algorithm for defensive decisions
- Decision Tree for resources management and casting spells
Vertex States
Every vertex can be at one of a few states. May be owned by the player, one of the enemy bots or by the wild tribe (inactive). When I was writing game, I tried to make possible to add unlimited enemies, fighting with each other, as long as the player has enough strong device to run it. Furthermore, each vertex can be at a different level, so the value of the vertex is different and is basing on army number staying at the vertex, vertex owner, vertex type and vertex level. That information is used to run one of the pathfinding algorithms.
Attack
For each enemy vertex is checked if neighbours are owned by other owner and have less army power than current vertex * 1.3. Thanks to this little overcalculation it seems the enemy is waiting to be not only strong enough to capture new vertex but also to defend the current one.
// Check if current vertex isn't player or wild
if (vertex.Owner != OwnerType.Player && vertex.Owner != OwnerType.Wild)
{
// Check if vertex has neighbour,
// if not then switch to second state
List<VertexController> enemyNeighbours = new List<VertexController>();
foreach (GameObject connection in vertex.Connections)
{
VertexController connectedVertex = connection.GetComponent<VertexController>();
if (vertex.Owner != connectedVertex.Owner)
{
// First state, use Dijkstra to
enemyNeighbours.Add(connectedVertex);
}
}
// Sort list of enemy vertices to find vertex with lowest army power (weight)
List<VertexController> sortedEnemyNeighbours = enemyNeighbours.OrderBy(o => o.ArmyPower).ToList();
if (enemyNeighbours.Count > 0)
{
foreach (VertexController enemyVertex in sortedEnemyNeighbours)
{
// Check if vertex has sufficient amount of army power to move
if (vertex.ArmyPower > enemyVertex.ArmyPower * 1.3f)
{
vertex.SendArmy(enemyVertex.Id, (int)(enemyVertex.ArmyPower * 1.3f));
}
}
}
If the vertex doesn't have enemy neighbours and all connected vertices are owned by the same owner, then different algorithm search further on the graph for vertices which have enemy neighbours and army power will be more useful. Thanks to this, some enemy vertices gather resources and other fights with the player. The breadth-First-Search algorithm in this case, is used to determine if an army traversing between two vertices is possible and which vertex will be next to traverse.
Those unconnected with the enemy are gathering army power and sending to vertices connected with vertices owned by someone else. To make it looks nice, destination vertex is picked based on which one has less army power and more needs help from another vertex. This is how games like this are played.
/// <summary>
/// Get shortest path from start
/// </summary>
/// <typeparam name="T"></typeparam>
/// <param name="graph"></param>
/// <param name="start"></param>
/// <returns></returns>
static Func<T, IEnumerable<T>> ShortestPath<T>(Graph<T> graph, T start)
{
// Contains previous vertex neighbours
Dictionary<T, T> previousVertex = new Dictionary<T, T>();
Queue<T> queue = new Queue<T>();
queue.Enqueue(start);
// Perform until traverse all vertices (empty queue)
// and in every step add neighbours of current vertex
while (queue.Count > 0)
{
// Get first vertex in the queue to scan for neighbours
var vertex = queue.Dequeue();
// For each connected neighbour in adjacency list
foreach (var neighbour in graph.AdjacencyList[vertex])
{
if (previousVertex.ContainsKey(neighbour))
{
continue;
}
previousVertex[neighbour] = vertex;
// Add every neighbour to que
queue.Enqueue(neighbour);
}
}
// Prepare path of jumps to selected vertex
IEnumerable<T> ShortestPath(T end)
{
List<T> pathOfJumps = new List<T>();
// Set current to current
var currentVertex = end;
// Traverse backward until reach start vertex
while (!currentVertex.Equals(start))
{
// Add current vertex to jump list
pathOfJumps.Add(currentVertex);
currentVertex = previousVertex[currentVertex];
}
// Add jump at the end
pathOfJumps.Add(start);
// Reverse list to order from start to end
pathOfJumps.Reverse();
return pathOfJumps;
}
return ShortestPath;
}
// Second state, use Breadth-first search algorithm to determine where to move units
if (enemyNeighbours.Count == 0)
{
List<VertexController> verticesWithEnemyNeighbours = new List<VertexController>();
// Search for all vertices of current vertex
foreach (VertexController tempVertex in _gameplayController.VertexList)
{
if (tempVertex.Owner == vertex.Owner)
{
bool hasEnemyNeighbours = false;
foreach(GameObject connectedToEnemyVertex in tempVertex.Connections)
{
if (connectedToEnemyVertex.GetComponent<VertexController>().Owner != tempVertex.Owner)
{
hasEnemyNeighbours = true;
}
}
if (hasEnemyNeighbours)
{
verticesWithEnemyNeighbours.Add(tempVertex);
}
}
}
// Function, which returns shortes path between this vertex and picked
Func<int, IEnumerable<int>> shortestPath = ShortestPath(_graph, vertex.Id);
int indexOfVertexToTraverse = -1;
int armyPowerOfVertexToTraverse = int.MaxValue;
int jumpDistanceToNearestMatchingVertex = int.MaxValue;
foreach(VertexController tempVertex in verticesWithEnemyNeighbours)
{
// Shortest path to tempVertex
List<int> pathJumps = shortestPath(tempVertex.Id).ToList();
if (pathJumps.Count < jumpDistanceToNearestMatchingVertex)
{
jumpDistanceToNearestMatchingVertex = pathJumps.Count;
indexOfVertexToTraverse = pathJumps[1];
armyPowerOfVertexToTraverse = tempVertex.ArmyPower;
}
else if (pathJumps.Count == jumpDistanceToNearestMatchingVertex && armyPowerOfVertexToTraverse > tempVertex.ArmyPower)
{
jumpDistanceToNearestMatchingVertex = pathJumps.Count;
indexOfVertexToTraverse = pathJumps[1];
armyPowerOfVertexToTraverse = tempVertex.ArmyPower;
}
}
// If found vertex to traverse, then send army
if (indexOfVertexToTraverse != -1)
{
// Print result
Debug.Log($"From {vertex.Id} to {indexOfVertexToTraverse}");
if (vertex.ArmyPower > 1)
{
vertex.SendArmy(indexOfVertexToTraverse, vertex.ArmyPower - 1);
}
}
/// <summary>
/// Represent graph vertices and connections
/// </summary>
/// <typeparam name="T"></typeparam>
public class Graph<T>
{
/// <summary>
/// Instantiate new graph
/// </summary>
/// <param name="vertices">Vertices</param>
/// <param name="edges">Edges</param>
public Graph(IEnumerable<T> vertices, IEnumerable<Tuple<T, T>> edges)
{
// Add every vertex to adjacency list
foreach (var vertex in vertices)
{
AddVertex(vertex);
}
// Add every vertex to adjacency list
foreach (var edge in edges)
{
AddEdge(edge);
}
}
// Adjacency list, represents vertices and connections between them
public Dictionary<T, HashSet<T>> AdjacencyList { get; } = new Dictionary<T, HashSet<T>>();
/// <summary>
/// Add vertex to adjacency list
/// </summary>
/// <param name="vertex"></param>
private void AddVertex(T vertex)
{
AdjacencyList[vertex] = new HashSet<T>();
}
/// <summary>
/// Add edge to adjacency list
/// </summary>
/// <param name="edge"></param>
private void AddEdge(Tuple<T, T> edge)
{
if (AdjacencyList.ContainsKey(edge.Item1) && AdjacencyList.ContainsKey(edge.Item2))
{
AdjacencyList[edge.Item1].Add(edge.Item2);
AdjacencyList[edge.Item2].Add(edge.Item1);
}
}
}
The last part was the possibility to upgrade vertices and cast spells. This is a very simple decision tree made of conditional statements and calculation of resources. If an enemy has a greater increase of mana it should wait and cast a more powerful spell than when it has a lower increase. Of course, it should have enough resource at the moment to cast a spell.
/// <summary>
/// Based of current increment of mana, cast spells
/// </summary>
void CastSpellsAI()
{
int[] totalManaIncrease = { 0, 0, 0, 0, 0 };
// Count mana increase per owner
foreach (VertexController vertex in _gameplayController.VertexList)
{
if (vertex.Type == VertexType.Shrine)
{
totalManaIncrease[(int)vertex.Owner] += vertex.Level;
}
}
foreach (VertexController vertex in _gameplayController.VertexList)
{
// For each enemy player
if (vertex.Owner != OwnerType.Player && vertex.Owner != OwnerType.Wild)
{
// Decide if cast spells
if (_gameplayController.Mana[(int)vertex.Owner] >= 100 && totalManaIncrease[(int)vertex.Owner] <= 2)
{
foreach (VertexController tempVertex in _gameplayController.VertexList)
{
if (tempVertex.Owner != vertex.Owner && tempVertex.Owner != OwnerType.Wild)
{
_gameplayController.Mana[(int)vertex.Owner] -= 100;
_gameplayController.CastOffensiveSpell(tempVertex);
break;
}
}
}
else if (_gameplayController.Mana[(int)vertex.Owner] >= 300 && totalManaIncrease[(int)vertex.Owner] >= 3 && totalManaIncrease[(int)vertex.Owner] <= 4)
{
foreach (VertexController tempVertex in _gameplayController.VertexList)
{
if (tempVertex.Owner != vertex.Owner && tempVertex.Owner != OwnerType.Wild)
{
_gameplayController.Mana[(int)vertex.Owner] -= 300;
_gameplayController.CastEarthquakeSpell(tempVertex);
break;
}
}
}
else if (_gameplayController.Mana[(int)vertex.Owner] >= 500 && totalManaIncrease[(int)vertex.Owner] >= 4)
{
// Search for vertex with highest armypower to takeover
int vertexIdWithHighestArmy = -1;
int vertexArmyPower = int.MinValue;
foreach (VertexController tempVertex in _gameplayController.VertexList)
{
if (tempVertex.Owner != vertex.Owner && tempVertex.Owner != OwnerType.Wild)
{
if (vertexArmyPower < tempVertex.ArmyPower)
{
vertexIdWithHighestArmy = tempVertex.Id;
}
}
}
if (vertexIdWithHighestArmy != -1)
{
_gameplayController.Mana[(int)vertex.Owner] -= 500;
_gameplayController.CastTakeoverCast(GameObject.Find($"vertex{vertexIdWithHighestArmy}").GetComponent<VertexController>(), vertex.Owner);
break;
}
}
}
}
}
Similarly, I made enemy upgrades. I am calculating the total increase of honey which is used as a resource for upgrading vertices. At this moment I had an idea of sorting vertices based on how many enemy neighbours it has. However, it was somewhere in the night, probably about 5 AM and in a few hours I was going to the university, where I was presenting my game so it was good enough for me at this moment.
void UpgradeAI()
{
foreach (VertexController vertex in _gameplayController.VertexList)
{
// For each enemy player
if (vertex.Owner != OwnerType.Player && vertex.Owner != OwnerType.Wild)
{
if (vertex.Type == VertexType.Apiary && _gameplayController.Honey[(int)vertex.Owner] >= vertex.Level * 25)
{
_gameplayController.UpgradeVertex(vertex);
}
}
}
foreach (VertexController vertex in _gameplayController.VertexList)
{
// For each enemy player
if (vertex.Owner != OwnerType.Player && vertex.Owner != OwnerType.Wild)
{
if (vertex.Type == VertexType.Village && _gameplayController.Honey[(int)vertex.Owner] >= vertex.Level * 25)
{
_gameplayController.UpgradeVertex(vertex);
}
}
}
foreach (VertexController vertex in _gameplayController.VertexList)
{
// For each enemy player
if (vertex.Owner != OwnerType.Player && vertex.Owner != OwnerType.Wild)
{
if (vertex.Type == VertexType.Shrine && _gameplayController.Honey[(int)vertex.Owner] >= vertex.Level * 25)
{
_gameplayController.UpgradeVertex(vertex);
}
}
}
}
This approach results in enemy AI which is pretty hard IMO and few of my friends lose with them. This is the last article for the Vistulans Dev Diary. Thanks for being with me for so long ๐ The game is playable in browser: Play Vistulans
โญ Please star on GitHub if you like this project and want more ๐
pilotpirxie
/
vistulans
๐ฎ Vistulans - graph-based strategy game about west slavic tribes with myths, legends and fantasy stories
vistulans
Vistulans - graph-based strategy game about west slavic tribes with myths, legends and fantasy stories
๐ ๐ช ๐
๐ฉ
Meat Boy
Posted on April 11, 2020
Join Our Newsletter. No Spam, Only the good stuff.
Sign up to receive the latest update from our blog.
Related