Vistulans - Game Dev Diary - Days 29-36 - Enemy AI + Playable Link
Tags: showdev, unity3d, csharp, gamedev
Published: 2020-04-11 19:03:01

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 😗 
{% github pilotpirxie/vistulans %} 

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.

```csharp
            // 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.

```csharp

    /// <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;
    }
```
```csharp
                // 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);
        }
    }
}
```

![Imgur](https://i.imgur.com/YveCMqD.png)

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.

```csharp
    /// <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.

```csharp
    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);
                }
            }
        }
    }
```

![Imgur](https://i.imgur.com/j3k9wJI.png)
![Imgur](https://i.imgur.com/xR5e4IQ.png)

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](https://smietanek.itch.io/vistulans)

⭐ Please star on GitHub if you like this project and want more 😗 
{% github pilotpirxie/vistulans %}