Various Features

About the project

This project, while not exactly a game, is something I've been working on during my spare time. Occasionally I'll think of something, like an algorithm I'd like to learn more about, and try to teach myself how to it works. So far the project has three main features I've made simply for the fun of it. I've tried to keep them nice and modular, so the individual features can be packaged and used in other projects if I so choose.

A* Pathfinding

The first feature I worked on is A* pathfinding. It's something I've wanted to look into for a long time. The main source I used for my implementation was this pseudo code. A* Code Sample

Maze Generation

During my stay at Excamedia we had a short lecture about procedural generation. One of the topics was maze generation algorithms. Of all the algorithms shown, I liked the look of the recursive backtracking algorithm mazes the most, so I decided to create my own. Maze Generation Code Sample

Try the demo here.


Mecanim Dialogue Tree

Finally, there's the Mecanim dialogue tree. While I was thinking about creating a 2D RPG, my thoughts went into the dialogue system. If you want branching dialogues, storing it all in a simple .xml file or in the Unity inspector can result in a long list of texts that are hard to keep track of. I decided I'd rather look for a solution in which the branching dialogue paths would be easily visible. Beforehand, I had worked on a Finite State Machine that makes use of Mecanim (see my Just Another Space Shooter page), so I wondered if I could apply Mecanim to this as well.
What I ended up with is a dialogue tree system that makes use of the Mecanim animator. By creating a Mecanim state (which we'll call "nodes" from now on), we can attach one of four scripts to our newly created node; the DialogueRoot script, the DialogueNode script, the DecisionNode script and the EventNode script.

The DialogueRoot script is best placed on the "Start" node (automatically created in Mecanim), it keeps track of which node is currently active (as there's no way I know of to get this information directly from the Animator) and stores the default dialogue window prefab (which is used for all dialogue nodes that don't have their own dialogue window prefab set). Only one DialogueRoot node is allowed per tree.
The DialogueNode simply stores the text shown in the dialogue window (optionally you can also set a dialogue window prefab to this node). When this node is active, it passes itself to the DialogueRoot, so the DialogueRoot can keep track of which node is active. The dialogue window containing this node's text is shown in the game.
The DecisionNode is a little more complicated. It stores both the dialogue text and a list of decisions. These decisions each have an integer ID and the text to be shown in-game. Like the DialogueNode, it passes itself to the DialogueRoot and can have its own dialogue window prefab.
Lastly, there's the EventNode, which only stores an integer ID. This ID is later used to call an event (if for example, we want to teleport the player) when that node is activated. Like the DialogueNode, it passes itself to the DialogueRoot.

The real meat of the dialogue tree system is contained in the DialogueController script. This script is placed on an object with an Animator component. This Animator is used to store our dialogue tree. When the dialogue starts, or the next dialogue node should be activated, the script sends the "ProceedDialogue" trigger to the animator. This causes the next node to activate. The DialogueController then retrieves the currently active node from the DialogueRoot. Depending on the type of node, the DialogueController opens the correct dialogue window prefab (or none, if it's an EventNode). Lastly, the DialogueController passes the dialogue texts and decisions to the appropriate UI scripts to make sure everything is displayed properly.
The DialogueController also stores a list of UnityEvents (along with corresponding integer IDs). When an EventNode is activated, the UnityEvent with the appropriate ID is found and the function of that UnityEvent is called.
One of the perks of using Mecanim is its ability to store variables. This means we can use these EventNodes to insert variables into Mecanim, which can be used as extra conditions in a dialogue tree. Let's say we want a character to say something else when it is spoken to a certain amount of times. We can simply increase an integer value each time it is spoken to and create a transition from the start node to the first dialogue node with the variable's expected value as a condition. DialogueController Code Sample

public List<GridNode> FindPath(GridNode[,] grid, Vector2 start, Vector2 destination)
{
    //check if start and destination coordinates are out of bounds
    if (!IsWithinBounds(start, grid) || !IsWithinBounds(destination, grid))
    {
        return null;
    }

    //List of gridnodes to be evaluated
    List<GridNode> openList = new List<GridNode>();
    //List of gridnodes that have already been evaluated
    List<GridNode> closedList = new List<GridNode>(); 

    GridNode startnode = grid[(int)start.x, (int)start.y];
    //We start here, so it doesn't take any steps to reach it, therefore cost = 0
    startnode.Cost = 0;
    //Estimated distance to the destination node * weight
    startnode.Score = (int)Mathf.Abs(Mathf.Abs(startnode.Coordinates.x - destination.x) + Mathf.Abs(startnode.Coordinates.y - destination.y)) * weight; 
    openList.Add(startnode);

    GridNode destinationNode = grid[(int)destination.x, (int)destination.y];

    //Exit loop when there are no more gridnodes to be evaluated (no path found)
    while (openList.Count > 0)
    {
        GridNode currentNode = GetLowestCost(openList); //get the gridnode with the smallest score + cost value

        if (currentNode == destinationNode)
        {
            return ReconstructPath(currentNode); //path found
        }

        //node should no longer be evaluated
        openList.Remove(currentNode); 
        closedList.Add(currentNode); 

        //Check neighbors of this node
        foreach (GridNode neighbor in GetNeighbors(grid, currentNode.Coordinates))
        {
            //Skip this neighbor if it is null
            if (neighbor == null)
            {
                continue;
            }

            //Skip this neighbor if it is obstructed by an obstacle
            if (neighbor.Obstacle)
            {
                continue;
            }

            //Skip this neighbor if it was already evaluated
            if (closedList.Contains(neighbor))
            {
                continue;
            }

            //Skip this neighbor if it is already in the open list and the amount of steps needed to reach it from the current node is higher
            if (openList.Contains(neighbor))
            {
                if (neighbor.Cost <= currentNode.Cost + 1) 
                {
                    continue;
                }
            }
                
            //Cost of this neighbor's node is incremented by 1 (takes 1 more step to get to this neighbor from the current node)
            neighbor.Cost = currentNode.Cost + 1;
            //Set score to the estimated distance between the neighbor and the destination * weight
            neighbor.Score = (int)Mathf.Abs(Mathf.Abs(neighbor.Coordinates.x - destination.x) + Mathf.Abs(neighbor.Coordinates.y - destination.y)) * weight; 
            neighbor.CameFrom = currentNode;

            //Insert the neighbor into the open list
            openList.Insert(0, neighbor);
        }
    }
        
    Debug.Log("No path found!");
    return null;
}
private void GenerateMaze()
{
    List<Tile> checkedTiles = new List<Tile>();
    Tile currentTile = tiles[1, 1];
    checkedTiles.Add(currentTile);
    currentTile.SetVisited(true);

    //infinite loop, breaks out when there are no more tiles left to check
    while (true)
    {
        Tile lastTile = currentTile;
        currentTile = GetUnvisitedTile(currentTile);
            
        if (currentTile == null)
        {
            //no unvisited or viable neighbors found
            //are there any tiles left that could have viable neighbors?
            if (checkedTiles.Count == 0)
            {
                break//we're done
            }
            //go back and re-check the last tile
            currentTile = checkedTiles[checkedTiles.Count - 1];
            checkedTiles.RemoveAt(checkedTiles.Count - 1);
        }
        else
        {
            //neighbor found! mark it as visited and set the wall between the tiles to true
            if (currentTile.GetXCoord() < lastTile.GetXCoord())
            {
                verticalWalls[currentTile.GetXCoord(), currentTile.GetYCoord()] = true;
            }
            else if (currentTile.GetXCoord() > lastTile.GetXCoord())
            {
                verticalWalls[lastTile.GetXCoord(), lastTile.GetYCoord()] = true;
            }
            else if (currentTile.GetYCoord() < lastTile.GetYCoord())
            {
                horizontalWalls[currentTile.GetXCoord(), currentTile.GetYCoord()] = true;
            }
            else if (currentTile.GetYCoord() > lastTile.GetYCoord())
            {
                horizontalWalls[lastTile.GetXCoord(), lastTile.GetYCoord()] = true;
            }

            currentTile.SetVisited(true);
            checkedTiles.Add(currentTile);
        }
    }

    SpawnMaze();
}

private Tile GetUnvisitedTile(Tile currentTile)
{
    List<Tile> neighborTiles = new List<Tile>(); //list of unvisited neighbor tiles
    int tileX = currentTile.GetXCoord();
    int tileY = currentTile.GetYCoord();

    //detect out of bounds
    if (tileX > 0)
    {
        if (!tiles[tileX - 1, tileY].GetVisited())
        {
            neighborTiles.Add(tiles[tileX - 1, tileY]);
        }
    }
    if (tileX < tiles.GetLength(0) - 1)
    {
        if (!tiles[tileX + 1, tileY].GetVisited())
        {
            neighborTiles.Add(tiles[tileX + 1, tileY]);
        }
    }
    if (tileY > 0)
    {
        if (!tiles[tileX, tileY - 1].GetVisited())
        {
            neighborTiles.Add(tiles[tileX, tileY - 1]);
        }
    }
    if (tileY < tiles.GetLength(1) - 1)
    {
        if (!tiles[tileX, tileY + 1].GetVisited())
        {
            neighborTiles.Add(tiles[tileX, tileY + 1]);
        } 
    }

    if (neighborTiles.Count == 0)
    {
        return null;
    }

    //return a random unvisited tile
    int randomDirection = Random.Range(0, neighborTiles.Count);
    return neighborTiles[randomDirection];
}
public void UpdateDialogue()
{
    DialogueTreeNode treeNode = dialogueRoot.GetNode();

    //is this a dialogue node?
    if (treeNode.GetType() == typeof(DialogueNode))
    {
        DialogueNode node = (DialogueNode)treeNode;
        OpenDialogue(node);
    }

    //is this a decision node?
    if (treeNode.GetType() == typeof(DecisionNode))
    {
        DecisionNode node = (DecisionNode)treeNode;
        OpenDecision(node);
    }

    //is this an event node?
    if (treeNode.GetType() == typeof(EventNode))
    {
        EventNode eventNode = (EventNode)treeNode;
        for (int i = 0; i < events.Count; i++)
        {
            if (eventNode.eventId == events[i].eventId)
            {
                events[i].uEvent.Invoke();
                break;
            }
        }
        ProceedDialogue();
    }
}