Building a Die-Roll Parser with C# and Irony

9 09 2015

Introduction

As part of a recent project to build a system for online, play-by-post RPGs, I have been working on a system to handle rolling various amounts and types of dice. The rolling itself is relatively simple, as I’m just using the built in Random class. However, I also needed the system to pull the details of what to roll from a string provided by the user. Moreover, the user could optionally employ a variety of basic mathematical operations.

To do this I needed to develop a lexer/parser that could handle basic math as well as a custom operator, D, to signify rolling dice. The D operator would take the first operand as the number of dice and the second as the number of sides on each die.

A few examples:

  1D6         →  1-6
  2D7         →  2-14
  5+1D6       →  6-11
  (1+2)D(3*4) →  3D12 
                →  3-36

Installing Irony via NuGet

While I could have built the lexer/parser from scratch, I figured I would save some time by not reinventing the wheel. I settled on the excellent Irony library to build my “language” with. The Irony library is available through Microsoft’s NuGet package manager so I installed it using the tools built into my IDE (Visual Studio 2015). You can do this by executing the following command in the NuGet Package Manager console.

PM> Install-Package Irony

Building the Language Grammar

Note: This is an incredibly “dumbed down” overview of the incredibly complex area of language definition; for more details I suggest reading up on BNF, or Backus-Naur Form.

Irony makes setting up the grammar for a language quite easy. The elements that make up the language are split into two categories, terminals and non-terminals. These pieces are used to break the expression into a tree structure. Terminals are the pieces which can be found at the ends of branches, while everything else is non-terminal.

For example, 1 + 2 – 3 * 4 / 5 becomes:

       -
   +       /
  1 2    5   *
            3 4

As you can see from the above example, the only terminal we have is constant numerical values. Setting up number literals is particularly easy in Irony:

public class ExpressionGrammar : Grammar {
    public ExpressionGrammar() : base(caseSensitive: false) {
        var number = new NumberLiteral("number");
        number.DefaultIntTypes = new TypeCode[] { TypeCode.Int32 };
        number.Options = NumberOptions.AllowSign | NumberOptions.AllowLetterAfter;

        var rollOperatorTerminal = ToTerm("d");
        rollOperatorTerminal.AllowAlphaAfterKeyword = true;

Here I tell Irony we have a number literal, I want to call it “number,” it will be internally represented as a 32 bit integer value and can have preceding sign and be followed by a letter. The following letter becomes important later, when we implement the die roll operator. the roll operator terminal is just used later for the roll operator so it can figure out where to break things apart.

We have rather more non-terminals. The top level is an expression, which is either a term, binary expression, or roll expression. A term is either a number literal or a parenthetical epression. Binary, roll, and parenthetical expressions are all exactly what they sound like.

        var expression = new NonTerminal("Expression");
        var term = new NonTerminal("Term");
        var parentheticalExpression = 
            new NonTerminal("ParentheticalExpression");
        var binaryExpression =
            new NonTerminal("BinaryExpression", typeof(BinaryOperationNode));
        var binaryOperator = new NonTerminal("BinaryOperator", "operator");
        var rollExpression =
            new NonTerminal("RollExpression", typeof(RollOperationNode));
        var rollOperator = new NonTerminal("RollOperator", "operator");

You may have noticed that the binary and roll expressions have a type specified. This type is used to evaluate those nodes in the tree when we get to that portion of the process.

Once we’ve defined what all the non-terminals are we need to define what they look like. We do this using the | and + operators, which have been overloaded by Irony to simplify this process. The | operator is used for OR, as in either of the terms provided can be matched, while the + operator is used for concatination, as in the first term followed by the second matches.

        expression.Rule = term | binaryExpression | rollExpression;
        term.Rule = number | parentheticalExpression;
        parentheticalExpression.Rule = "(" + expression + ")";
        binaryExpression.Rule = expression + binaryOperator + expression;
        binaryOperator.Rule = ToTerm("+") | "-" | "*" | "/";
        rollExpression.Rule = expression + rollOperator + expression;
        rollOperator.Rule = rollOperatorTerminal;
    
        Root = expression;

The first block of code here sets the pattern matching for each non-terminal. The last line tells the system what the root term should be when the abstract syntax tree (AST) is built. Normally you have multiple expressions/commands in a language, but I only need to handle one expression at a time.

Next we need to do some cleanup. I start by setting the order of operations. For the most part this is the same as basic arithmetic. However I also have a new operator for rolling. For this I decided to give it the highest precedent. 3D6 * 2 usually means roll 3, six-sided dice, and multiply the total by 2, not roll three, twelve-sided dice.

        RegisterOperators(1, "+", "-");
        RegisterOperators(2, "*", "/");
        RegisterOperators(3, "d");

Finally, there are some characters which need to be treated in a unique way. In particular, parenthesis are punctuation, and need to match up. (1+2)-(3 shouldn’t work. Also, when we build the tree we don’t need all the nodes. The nodes we can skip are called “transient.” This is not strictly necessary, but it makes navigating the tree easier when a branch is just the operator with the values as children, rather than the expression with the operator as a child, which in turn has several term nodes with the actual values even deeper in the tree. I also enable AST generation here.

        MarkPunctuation("(", ")");
        RegisterBracePair("(", ")");
        MarkTransient(term, expression, binaryOperator, parentheticalExpression, rollOperator);

        LanguageFlags = LanguageFlags.CreateAst;
    }
}

Building the Custom AST Node

In the previous section we told the system to use a custom AST node class for evaluating the roll operator. The class we need to provide here has to be based on the AstNode class, and override a few methods therein. First, we need an empty constructor, and an initialization method.

public class RollOperationNode : AstNode {
    public AstNode Left, Right;
    public int LastRoll;

    public RollOperationNode() { }
    
    public override void Init(AstContext context, ParseTreeNode treeNode) { 
        base.Init(context, treeNode);
        var nodes = treeNode.GetMappedChildNodes();
        Left = AddChild("Arg", nodes[0]);
        Right = AddChild("Arg", nodes[2]);
        var operatorToken = nodes[1].FindToken();
        ErrorAnchor = operatorToken.Location;
    }

This is mostly boilerplate code. We trigger the base init first, then pull in the node data. We store the children for later evaluation, and find the operator so that, in the event of an error, the parser can tell the user where the problem originated.

Next we need to tell the system how to evaluate these rolls. This is a relatively simple process, as I have factored the actual rolling logic into a utility class we can take a look at later. First I evaluate the child nodes (can’t roll the dice until I know how many and what kind to roll). Next I get the random result, store it in case I need it later, and return the result. The thread changes are for Irony.

    protected override object DoEvaluate(ScriptThread thread) {
        thread.CurrentNode = this;
        var leftValue = (int)Left.Evaluate(thread);
        var rightValue = (int)Right.Evaluate(thread);
        var result = new Dice().Roll(leftValue, rightValue);
        thread.CurrentNode = Parent;
        LastRoll = result;
        return result;
    }
}

Building the Utility Classes

Finally, we need a few utility classes to fill in some blanks and make using the parser a bit easier. We will start with the Dice class I just used in the operator evaluation logic. It is definitely not good practice to be initializing the Random instance each time, and there are far better alternatives, but this will suffice for testing.

public class Dice {
    private Random random;

    public Dice() {
        random = new Random();
    }

    public int Roll(int numberOfDice, int sidesPerDie) {
        int total = 0;
        for(int i=0; i<numberOfDice; ++i) {
            total += random.Next(1, sidesPerDie + 1);
        }
        return total;
    }
}

Pretty simple. We need to add a couple easy methods to the grammar class as well. First we need to override the BuildAst method so that the tree will build properly, and spit out errors if it fails. Obviously it would be better here to spit out more useful errors, but it will work for now. We also add a method to retrieve the runtime, which lets us shorten the next bit of code.

    public override void BuildAst(LanguageData language, ParseTree parseTree) {
        var opHandler = new OperatorHandler(language.Grammar.CaseSensitive);
        Util.Check(!parseTree.HasErrors(), "ParseTree has errors, cannot build AST.");
        var astContext = new InterpreterAstContext(language, opHandler);
        var astBuilder = new AstBuilder(astContext);
        astBuilder.BuildAst(parseTree);
    }

    public LanguageRuntime CreateRuntime(LanguageData language) {
        return new LanguageRuntime(language);
    }

Finally we need a class to help with triggering the roll. This is again mostly boilerplate code, so we don’t want to be re-typing it every time we evaluate an expression.

public class RollHelper {
    public void Roll(string expression) {
        var grammar = new ExpressionGrammar();
        LanguageData language = new LanguageData(grammar);
        Parser parser = new Parser(language);
        ParseTree parseTree = parser.Parse(expression);

        grammar.BuildAst(language, parseTree);
        ParseTreeNode root = parseTree.Root;
        var astNode = root.AstNode as AstNode;

        var runtime = grammar.CreateRuntime(language);
        var scriptApp = new ScriptApp(runtime);
        var thread = new ScriptThread(scriptApp);
        var value = astNode.Evaluate(thread);
    }
}

Summary

With all this we should be able to evaluate the expressions I used as examples at the beginning of this post. I hope to later expand this system to allow for basic variable evaluation so users could embed character stats, weapon/armor specs and so on into their rolls, but that will be a challenge for another time.





Code Snippet: Map Generation

28 04 2015

Overview

My capstone project, a dual-stick shooter called “Endless Swarm,” employed procedurally generated levels. To improve the appearance of these levels I developed a system which would select appropriate tiles to piece together a 3D level from a 2D character array. The system is contained in a single MonoBehavior script which accepts as inputs the aforementioned character array and a positional offset at which to create the map.

The generator works by looping through each character in the array and counting the number of each type of tile found adjacent to the current one. E.G. A tile might have one wall tile next to it, and three floor tiles. Tiles diagonal to the origin are not considered. This, combined with the type of tile the algorithm is currently considering, is enough to determine which object or objects need to be placed in 3D space.

The code is organized into two core methods and a number of helper methods. The first, Build() is the publicly exposed method, and is responsible for loading the array, and making the call to ConvertMap(), a method which converts the character array to an array of a TileType enumeration. Then it loops through all the tiles; if a floor is found it calculates the location and creates the floor. Otherwise, if it sees a wall, it calls into the second key method, BuildWallPiece().

public void Build(char[,] input, float xOffset = 0.0f, float yOffset = 0.0f) {
    TileType[,] map = ConvertMap(input);
    int mapWidth = map.GetLength(0);
    int mapHeight = map.GetLength(1);
    for(int x=0; x<mapWidth; ++x) {
        for(int y=0; y<mapHeight; ++y) {
            TileType type = GetTileType(map, x, y);
            if(type == TileType.Floor) {
                Vector3 position = new Vector3((-x - xOffset) * TileSize, 0, (y + yOffset) * TileSize);
                CreateFloor(position);
                floorPositions.Add (position);  //add floor tile positions to a series of lists...
                spawnPositions.Add (position);
                enemyPositions.Add (position);
            } else if (type == TileType.Wall) {
                BuildWallPiece(map, x, y, xOffset, yOffset);
            }
        }
    }
}
private TileType[,] ConvertMap(char[,] input) {
    TileType[,] map = new MapBuilder.TileType[input.GetLength(1), input.GetLength(0)];
    for(int x=0; x<input.GetLength(1); ++x) {
        for(int y=0; y<input.GetLength(0); ++y) {
            var type = MapBuilder.TileType.Void;
            if(input[y,x]=='F') type = MapBuilder.TileType.Floor;
            if(input[y,x]=='W') type = MapBuilder.TileType.Wall;
            int xPos = input.GetLength(1) - (1 + x);
            map[xPos, y] = type;
        }
    }
    return map;
}

BuildWallPiece() takes a similar set of arguments, as well as the coordinates of the tile it is to consider. The method is responsible for counting the adjacent peices and determining which objects to place. Helper methods are used to place the objects into the world.

public void BuildWallPiece(TileType[,] map, int x, int y, float xOffset, float yOffset) {
    Vector3 position = new Vector3((-x - xOffset) * TileSize, 0, (y + yOffset) * TileSize);
    
    TileType north, south, east, west;
    north = GetTileType(map, x, y - 1);
    south = GetTileType(map, x, y + 1);
    east = GetTileType(map, x + 1, y);
    west = GetTileType(map, x - 1, y);
    
    int numWalls = 0, numFloors = 0;
    if(north == TileType.Wall) ++numWalls;
    else if(north == TileType.Floor) ++numFloors;
    if(south == TileType.Wall) ++numWalls;
    else if(south == TileType.Floor) ++numFloors;
    if(east == TileType.Wall) ++numWalls;
    else if(east == TileType.Floor) ++numFloors;
    if(west == TileType.Wall) ++numWalls;
    else if(west == TileType.Floor) ++numFloors;
    
    if(numFloors == 1) {
        float angle = 0;
        if(north == TileType.Floor) angle = 90;
        else if(east == TileType.Floor) angle = 180;
        else if(south == TileType.Floor) angle = 270;
        
        CreateWall1(angle, position);
    } else if(numFloors == 2) {
        if(north == TileType.Floor && south == TileType.Floor) {
            CreateWall1(90, position);
            CreateWall1(270, position);
        } else if (east == TileType.Floor && west  == TileType.Floor) {
            CreateWall1(0, position); 
            CreateWall1(180, position);
        } else if(north == TileType.Floor && west == TileType.Floor) {
            CreateWall2(0, position);
        } else if(north == TileType.Floor && east == TileType.Floor) {
            CreateWall2(90, position);
        } else if(south == TileType.Floor && east == TileType.Floor) {
            CreateWall2(180, position);
        } else if(south == TileType.Floor && west == TileType.Floor) {
            CreateWall2(270, position);
        }
    } else if(numFloors == 3) {
        if(north != TileType.Floor) {
            CreateWall3(0, position);
        } else if(east != TileType.Floor) {
            CreateWall3(90, position);
        } else if(south != TileType.Floor) {
            CreateWall3(180, position);
        } else if(west != TileType.Floor) {
            CreateWall3(270, position);
        }
    } else if(numFloors == 4) {
        CreateWall4(position);
    }
    
    if(numWalls > 1) {
        if(south == TileType.Wall && west == TileType.Wall) {
            CreateWall5(0, position);
        }
        if(north == TileType.Wall && west == TileType.Wall) {
            CreateWall5(90, position);
        }
        if(north == TileType.Wall && east == TileType.Wall) {
            CreateWall5(180, position);
        }
        if(south == TileType.Wall && east == TileType.Wall) {
            CreateWall5(270, position);
        }
    }
}

Complete Source

using UnityEngine;
using System.Collections;
using System.Collections.Generic;

public class MapBuilder : MonoBehaviour {
    public Transform Floor, Wall1, Wall2, Wall3, Wall4, Wall5;
    public float TileSize = 5.0f;
    public List<Vector3> floorPositions = new List<Vector3> ();
    public List<Vector3> spawnPositions = new List<Vector3> ();
    public List<Vector3> enemyPositions = new List<Vector3> ();
    
    public enum TileType { Floor, Wall, Void };
    
    public void Build(char[,] input, float xOffset = 0.0f, float yOffset = 0.0f) {
        TileType[,] map = ConvertMap(input);
        int mapWidth = map.GetLength(0);
        int mapHeight = map.GetLength(1);
        for(int x=0; x<mapWidth; ++x) {
            for(int y=0; y<mapHeight; ++y) {
                TileType type = GetTileType(map, x, y);
                if(type == TileType.Floor) {
                    Vector3 position = new Vector3((-x - xOffset) * TileSize, 0, (y + yOffset) * TileSize);
                    CreateFloor(position);
                    floorPositions.Add (position);  //add floor tile positions to a series of lists...
                    spawnPositions.Add (position);
                    enemyPositions.Add (position);
                } else if (type == TileType.Wall) {
                    BuildWallPiece(map, x, y, xOffset, yOffset);
                }
            }
        }
    }
    
    public void BuildWallPiece(TileType[,] map, int x, int y, float xOffset, float yOffset) {
        Vector3 position = new Vector3((-x - xOffset) * TileSize, 0, (y + yOffset) * TileSize);
        
        TileType north, south, east, west;
        north = GetTileType(map, x, y - 1);
        south = GetTileType(map, x, y + 1);
        east = GetTileType(map, x + 1, y);
        west = GetTileType(map, x - 1, y);
        
        int numWalls = 0, numFloors = 0;
        if(north == TileType.Wall) ++numWalls;
        else if(north == TileType.Floor) ++numFloors;
        if(south == TileType.Wall) ++numWalls;
        else if(south == TileType.Floor) ++numFloors;
        if(east == TileType.Wall) ++numWalls;
        else if(east == TileType.Floor) ++numFloors;
        if(west == TileType.Wall) ++numWalls;
        else if(west == TileType.Floor) ++numFloors;
        
        if(numFloors == 1) {
            float angle = 0;
            if(north == TileType.Floor) angle = 90;
            else if(east == TileType.Floor) angle = 180;
            else if(south == TileType.Floor) angle = 270;
            
            CreateWall1(angle, position);
        } else if(numFloors == 2) {
            if(north == TileType.Floor && south == TileType.Floor) {
                CreateWall1(90, position);
                CreateWall1(270, position);
            } else if (east == TileType.Floor && west  == TileType.Floor) {
                CreateWall1(0, position); 
                CreateWall1(180, position);
            } else if(north == TileType.Floor && west == TileType.Floor) {
                CreateWall2(0, position);
            } else if(north == TileType.Floor && east == TileType.Floor) {
                CreateWall2(90, position);
            } else if(south == TileType.Floor && east == TileType.Floor) {
                CreateWall2(180, position);
            } else if(south == TileType.Floor && west == TileType.Floor) {
                CreateWall2(270, position);
            }
        } else if(numFloors == 3) {
            if(north != TileType.Floor) {
                CreateWall3(0, position);
            } else if(east != TileType.Floor) {
                CreateWall3(90, position);
            } else if(south != TileType.Floor) {
                CreateWall3(180, position);
            } else if(west != TileType.Floor) {
                CreateWall3(270, position);
            }
        } else if(numFloors == 4) {
            CreateWall4(position);
        }
        
        if(numWalls > 1) {
            if(south == TileType.Wall && west == TileType.Wall) {
                CreateWall5(0, position);
            }
            if(north == TileType.Wall && west == TileType.Wall) {
                CreateWall5(90, position);
            }
            if(north == TileType.Wall && east == TileType.Wall) {
                CreateWall5(180, position);
            }
            if(south == TileType.Wall && east == TileType.Wall) {
                CreateWall5(270, position);
            }
        }
    }
    
    public TileType GetTileType(TileType[,] map, int x, int y) {
        if(x < 0 || x >= map.GetLength(0) || y < 0 || y >= map.GetLength(1)) {
            return TileType.Void;
        } else {
            return map[x, y];
        }
    }
    
    private TileType[,] ConvertMap(char[,] input) {
        TileType[,] map = new MapBuilder.TileType[input.GetLength(1), input.GetLength(0)];
        for(int x=0; x<input.GetLength(1); ++x) {
            for(int y=0; y<input.GetLength(0); ++y) {
                var type = MapBuilder.TileType.Void;
                if(input[y,x]=='F') type = MapBuilder.TileType.Floor;
                if(input[y,x]=='W') type = MapBuilder.TileType.Wall;
                int xPos = input.GetLength(1) - (1 + x);
                map[xPos, y] = type;
            }
        }
        return map;
    }
    
    private void CreateFloor(Vector3 position) {
        Quaternion rotation = Quaternion.AngleAxis(0, Vector3.up);
        var piece = GameObject.Instantiate(Floor, position, rotation) as Transform;
        piece.parent = transform;
    }
    private void CreateWall1(float angle, Vector3 position) {
        Quaternion rotation = Quaternion.AngleAxis(angle, Vector3.up);
        var piece = GameObject.Instantiate(Wall1, position, rotation) as Transform;
        piece.parent = transform;
    }
    private void CreateWall2(float angle, Vector3 position) {
        Quaternion rotation = Quaternion.AngleAxis(angle, Vector3.up);
        var piece = GameObject.Instantiate(Wall2, position, rotation) as Transform;
        piece.parent = transform;
    }
    private void CreateWall3(float angle, Vector3 position) {
        Quaternion rotation = Quaternion.AngleAxis(angle, Vector3.up);
        var piece = GameObject.Instantiate(Wall3, position, rotation) as Transform;
        piece.parent = transform;
    }
    private void CreateWall4(Vector3 position) {
        Quaternion rotation = Quaternion.AngleAxis(0, Vector3.up);
        var piece = GameObject.Instantiate(Wall4, position, rotation) as Transform;
        piece.parent = transform;
    }
    private void CreateWall5(float angle, Vector3 position) {
        Quaternion rotation = Quaternion.AngleAxis(angle, Vector3.up);
        var piece = GameObject.Instantiate(Wall5, position, rotation) as Transform;
        piece.parent = transform;
    }
}




Code Snippet: Hive-Mind

28 04 2015

Overview

While working with my team on Endless Swarm, a dual-stick shooter built as a capstone project, we determined that we would need a way to manage both the rate at which enemies spawned, and keep those enemies balanced by type. E.G. The number of low-level enemies should be greater than the number of high-level, boss-like enemies.

To this end I designed an AI system called the Hive-Mind intended to manage our enemy entities on three fronts: balancing and purchasing, spawning, and commanding. Unfortunately, due to time restraints, only the balancing and purchasing, and spawning systems were ever completed.

Purchasing/Balancing

This section of the AI is responsible for selecting which types of alien units will eventually enter play, and how many of each should be added. It uses a point-buy system similar to what is found in most Table-Top Wargames. The AI gains points at a rate determined by the current difficulty level and the number and types of currently existing enemies. Each type of enemy is assigned a point value, and the AI expends points to “purchase” units. Purchased units are added to a pool to be spawned at a later time. Which unit is purchased is dependent on the numbers and types of currently existing enemies.

The points gain system is simple enough, a PointsPerSecond value is kept in the Hive-Mind component, and adjusted by difficulty. Before points are added each frame they are multiplied by the time which has passed and a multiplier based on the number of existing enemies:

private float PointsPerSecond = 5.0f;
private float pointsMultiplier {
    get {
        return Mathf.Max(0, 40 - currentRatio.Total) / 20.0f;
    }
}
void Update() {
    points += PointsPerSecond * pointsMultiplier * Time.deltaTime;
    // If we have enough points, purchase the next enemy to spawn.
}

In contrast to the simple point-buy system, the balancing is somewhat more complex. The system is built on a “ratio” class I developed for this purpose. The class stores an arbitrary number of values which are converted to proportions by dividing each value by the sum of the values. E.G. Given a ratio of [3:1] the proportions would be [0.75:0.25].

public Ratio(params float[] values) {
    this.Values = values;
    this.total = values.Sum();
    this.proportions = new float[values.Length];
    CalculateProportions();
}
private void CalculateProportions() {
    if(total > 0) {
        for(int i=0; i<Values.Length; ++i) {
            proportions[i] = Values[i] / total;
        }
    }
}

Two ratios are stored by the Hive-Mind AI system. One represents the desired ratio for all spawned enemies, the other contains the actual counts of each enemy type as its values. The meat of the ratio class is in the GreatestDeficiencyIndex() method, which compares two ratios and determines which value to increase (I.E. Which enemy to spawn) to bring the two ratios as close to each other as possible.

public int GetGreatestDeficiencyIndex(Ratio target) {
    if(target.proportions.Length != proportions.Length) return -1;
    float maxDeficiency = 0.0f;
    int maxDeficiencyIndex = -1;
    for(int i=0; i < proportions.Length; ++i) {
        float deficiency = target.proportions[i] - proportions[i];
        if(deficiency > maxDeficiency) {
            maxDeficiency = deficiency;
            maxDeficiencyIndex = i;
        }
    }
    return maxDeficiencyIndex;
}

If the proportion values of both ratios are identical the method returns a -1; otherwise it returns the index of the proportional values which differ by the greatest degree. In the case of a -1, the Hive-Mind defaults to spawning the weakest enemy, which unbalances the ratios again.

Finally, once enough enemies have been added to the spawn pool (determined by a points cap on the pool) they are all instantiated into the world at a randomly chosen spawn point.

public void SpawnGroup() {
    int numSpawned = 0;
    var spawnPoints = GameObject.FindGameObjectsWithTag("EnemySpawnPoint");
    var spawnPoint = spawnPoints[Random.Range (0, spawnPoints.Length-1)];
    for(int i=0; i<spawnGroup.Values.Length; ++i) {
        for(int j=0; j<spawnGroup.Values[i]; ++j) {
            var offset = numSpawned == 0 ? 0f : spawnOffset * (((numSpawned-1) / 8) + 1);
            var rotation = Quaternion.AngleAxis((float)numSpawned * 45f, Vector3.up);
            var spawnPos = spawnPoint.transform.position + (rotation * (Vector3.right * offset));
            spawnEnemy(spawnPos, (EnemyType)j);
            ++numSpawned;
        }
    }
    spawnGroup = new Ratio(TargetRatio.Values.Length);
}

Complete Source

HiveMindController.cs

using UnityEngine;
using System.Linq;
using System.Collections;

public class HiveMindController : MonoBehaviour {
    public EnemySpawnScript enemySpawnScript;
    public PlayerController playerScript;

    public Ratio TargetRatio = new Ratio(20, 7, 5, 2);
    public float PointsPerSecond = 5.0f;
    public int MinPointsToSpawn = 50; 

    private Ratio currentRatio, spawnGroup;
    private float points, nextCost;
    private EnemyType nextSpawn;
    private readonly float spawnOffset = 3f;
    
    private float pointsMultiplier {
        get {
            return Mathf.Max(0, 40 - currentRatio.Total) / 20f;
        }
    }
    
    void Start() {
        currentRatio = new Ratio(TargetRatio.Values.Length);
        spawnGroup = new Ratio(TargetRatio.Values.Length);
        nextSpawn = EnemyType.Swarm;
        points = 0;
    }
    
    void Update() {
        points += PointsPerSecond * pointsMultiplier * Time.deltaTime;
        if(points >= nextCost) {
            points -= nextCost;
            addCreature(nextSpawn);
            if(getTotalCost(spawnGroup) > MinPointsToSpawn) {
                SpawnGroup();
            }
        }
    }
    
    private void determineNextSpawn() {
        int nextSpawnId = currentRatio.GetGreatestDeficiencyIndex(TargetRatio);
        if(nextSpawnId == -1) nextSpawnId = 0;
        nextSpawn = EnemyTypeHelper.GetById(nextSpawnId);
        nextCost = nextSpawn.GetPointCost();
    }
    
    private void addCreature(EnemyType type) {
        currentRatio.Values[type.GetIndex()] += 1;
        spawnGroup.Values[type.GetIndex()] += 1;     
        determineNextSpawn();
    }
    
    /*public void RemoveCreature(EnemyType type) {
        int newValue = (int)Mathf.Max(0, currentRatio.Values[type.GetIndex()] - 1);
        currentRatio.Values[type.GetIndex()] = newValue;
        determineNextSpawn();
    }*/
    
    public void SpawnGroup() {
        int numSpawned = 0;
        var spawnPoints = GameObject.FindGameObjectsWithTag("EnemySpawnPoint");
        var spawnPoint = spawnPoints[Random.Range (0, spawnPoints.Length-1)];
        for(int i=0; i<spawnGroup.Values.Length; ++i) {
            for(int j=0; j<spawnGroup.Values[i]; ++j) {
                var offset = numSpawned == 0 ? 0f : spawnOffset * (((numSpawned-1) / 8) + 1);
                var rotation = Quaternion.AngleAxis((float)numSpawned * 45f, Vector3.up);
                var spawnPos = spawnPoint.transform.position + (rotation * (Vector3.right * offset));
                spawnEnemy(spawnPos, (EnemyType)j);
                ++numSpawned;
            }
        }
        spawnGroup = new Ratio(TargetRatio.Values.Length);
    }
    
    private void spawnEnemy(Vector3 position, EnemyType type) {
        switch (type.GetIndex ()) {
        case 0:
            enemySpawnScript.CreateEnemy1(position);
            break;
        case 1:
            enemySpawnScript.CreateEnemy2(position);
            break;
        case 2:
            enemySpawnScript.CreateEnemy3(position);
            break;
        case 3:
            enemySpawnScript.CreateEnemy4(position);
            break;
        }
    }
    
    private int getTotalCost(Ratio ratio) {
        int total = 0;
        for(int i=0; i<spawnGroup.Values.Length; ++i) {
            EnemyType type = (EnemyType)i;
            total += (int)(type.GetPointCost() * spawnGroup.Values[i]);
        }
        return total;
    }
}

Ratio.cs

using System;
using System.Linq;

[Serializable]
public class Ratio {
    public float[] Values;
    public float[] Proportions { get { return proportions; } }
    public float Total { get { return total; } }
    
    private float[] proportions;
    private float total;    
    
    public Ratio(int numValues) {
        this.Values = new float[numValues];
        for(int i=0; i<numValues; ++i) {
            this.Values[i] = 0.0f;
        }
        this.total = 0.0f;
        this.proportions = new float[Values.Length];
        CalculateProportions();
    }
    
    public Ratio(params float[] values) {
        this.Values = values;
        this.total = values.Sum();
        this.proportions = new float[values.Length];
        CalculateProportions();
    }
    
    public int GetGreatestDeficiencyIndex(Ratio target) {
        CalculateProportions ();
        target.CalculateProportions ();
        if(target.proportions.Length != proportions.Length) return -1;
        float maxDeficiency = 0.0f;
        int maxDeficiencyIndex = -1;
        for(int i=0; i<proportions.Length; ++i) {
            float deficiency = target.proportions[i] - proportions[i];
            if(deficiency > maxDeficiency) {
                maxDeficiency = deficiency;
                maxDeficiencyIndex = i;
            }
        }
        return maxDeficiencyIndex;
    }
    
    public void CalculateProportions() {
        total = Values.Sum();
        if(total > 0) {
            for(int i=0; i<Values.Length; ++i) {
                proportions[i] = Values[i] / total;
            }
        }
    }
}




Custom Field-Of-View

27 03 2015

While working on a rogue-like project I’m not quite ready to announce, the need arose for a customized grid-based FoV solution. In particular, one that would permit fractional opacity values. In this blog post I aim to outline the solution I found, and open it up for discussion.

First, some requirements. The FoV would be used for an overworld map with a height-map element and varried terrain types. While this means there will be few if any elements that totally block the player’s view, there are some I want to obscure it. For example, the player should be able to see farther over an open plain or the ocean than they can into a dense forest or over rolling hills.

Representation

I intend to codify the information for this feature in two numbers, opacity, and visibility. Both will fall between zero (0) and one (1).

Opacity will be set once at startup on a per-tile (or per-tile-type) basis, and will determine how badly the tile obscures the player’s vision. It will be based on factors such as height (possibly relative height in a later iteration, adding the necessity to recalculate these values), and the type of terrain. A dense forest might use 0.4 while an open plain might have a zero (0).

Visibility is calculated each frame, and is defined as one (1) minus the sum of the opacity values of all tiles between it and the player. An opacity of one (1) means the tile is completely blocked. A visibility of zero (0) means the tile is completely obscured from where the player is standing, while a visibility of one (1) means the tile is perfectly visible. A factor of the distance between the player and the tile is also be subtracted to simulate fog.

The Algorithm

While considering how best to design my own solution I realized each tile only needed to consider the closest tile in a direct line from the tile in question to the player. If it was aware of the visibility and opacity of that tile, it could calculate its own visibility from that information. For such a system to work the algorithm would have to consider the tiles closer to the player first, and then work its way outward. As such, the algorithm I’ve designed first considers the eight (8) tiles surrounding the player, then the tiles surrounding those, and expands outwards from there.


Diagram 1 – Order in which tiles are checked. Zero (0) represents the player.
Tiles labeled with a one (1) are checked first, then two (2), and so on.

When considering a given tile, and assuming the tiles between it and the player have already been considered, the next step is to determine which tile would be next in a line drawn from it to the player. In my current iteration I’m using Atan2() to give me an angle, and checking which of the eight (8) forty-five (45) degree wedges that angle falls into. Something based on the slope would likely be faster, as it wouldn’t involve calling a trigonometric function.

Once I know what that inner tile is, the visibility of this tile is set to be the visibility of the inner tile minus the opacity of the inner tile. This is done instead of using the opacity of the current tile to allow tiles with an opacity of one (1) to still be visible. When considering a tile diagonally, the opacity to add is multiplied by 1.4f, a rough approximation of the square root of two (2), to give the effect of a more circular view.

The Code

The project I’m building makes use of the Libtcod library for input and rendering, as well as a few other features. In this particular section of the code base you will see me reference a TCODConsole class, and call methods on it which place characters and strings onto a console. I also adjust the foreground colors using the TCODColor class and an Interpolate method which blends them. Finally, there is a hand-written Vector2 class used to track positions.

At the moment I’m building the system in a test scene; the scene interface in this project contains methods explaining how to update each tick, how to render, and how to respond to input. Here I’m specifying a location for the player, a list of locations for the walls, and a temporary location for use later in the algorithm, pre-allocated for performance. Angle is also being pre-allocated for later. Range determines how far out the FoV algorithm will look, and fog is as explained earlier. Visibility and opacity are 2D float arrays used to store the values defined earlier.

public class TestScene  : IScene {
    private Vector2 player, temp;
    private float angle
    private int range = 100;
    private float fog;
    private float[,] visibility;
    private float[,] opacity;
    private List<Vector2> walls;
}

The constructor is fairly self-explanatory. I’m setting the player’s position and creating the arrays, and setting the opacity based on the presence of the walls I define.

public TestScene() {
    player = new Vector2(20, 20);
    fog = 0.1f;
    visibility = new float[Game.Settings.ScreenWidth, Game.Settings.ScreenHeight];
    opacity = new float[Game.Settings.ScreenWidth, Game.Settings.ScreenHeight];
    walls = new List<Vector2>();
    walls.Add(new Vector2(10, 10));
    walls.Add(new Vector2(11, 10));
    walls.Add(new Vector2(11, 11));

    for (int x = 0; x < Game.Settings.ScreenWidth; ++x) {
        for (int y = 0; y < Game.Settings.ScreenHeight; ++y) {
            opacity[x, y] = 0.0f;
            if (walls.Any(w => (int)w.X == x && (int)w.Y == y)) {
                opacity[x, y] = 1.0f;
            }
        }
    }
}

Inside the update method I clear the visibility array with zeros (0), save at the player’s location, which starts at one (1) so that the player can always see where they’re standing.

public void Update(float deltaTime) {
    for (int x = 0; x < Game.Settings.ScreenWidth; ++x) {
        for (int y = 0; y < Game.Settings.ScreenHeight; ++y) {
            visibility[x, y] = 0;
            if (x == (int)player.X && y == (int)player.Y) {
                visibility[x, y] = 1;
            }
        }
    }
}

The render method draws the FoV at increasing ranges, then layers the player and walls over them. I’m doing this because the visibility is rendered as arrows pointing at the square they came from, with a color based on visibility. Ideally the system wouldn’t “render” the FoV at all, but would instead simply darken less visible tiles.

public void Render(TCODConsole console) {
    for (int i = 1; i <= range; ++i) {
        RenderFovAtRange(console, player, i);
    }
    foreach (var wall in walls) {
        console.putChar((int)wall.X, (int)wall.Y, "#");
    }
    console.putChar((int)player.X, (int)player.Y, "X");
}

After this I have some code in place to handle input and allow the player to move around and adjust the range of the FoV algorithm. I’m testing it in a 50×50 area, so the range of 100 is more than enough to cover all of it.

The next block of code, RenderFovAtRange(), loops through all the tiles in a square at the defined distance from a center point. The corners are handled afterwards at the end, as they would otherwise be calculated twice. This isn’t problematic in the current version, but if I were to later add multiple sources for theFoV (as might happen to simulate lights) the addition would cause problems.

private void RenderFovAtRange(TCODConsole console, Vector2 source, int range) {
    Vector2 coords = new Vector2();
    for (int x = -range + 1; x <= range - 1; ++x) {
        coords.X = (int)source.X + x;
        coords.Y = (int)source.Y - range;
        PutFovArrow(console, source, coords);
        coords.Y = (int)source.Y + range;
        PutFovArrow(console, source, coords);
    }
    for (int y = -range + 1; y <= range - 1; ++y) {
        coords.X = (int)source.X - range;
        coords.Y = (int)source.Y + y;
        PutFovArrow(console, source, coords);
        coords.X = (int)source.X + range;
        PutFovArrow(console, source, coords);
    }
    coords.X = (int)source.X - range; coords.Y = (int)source.Y - range;
    PutFovArrow(console, source, coords);
    coords.Y = (int)source.Y + range;
    PutFovArrow(console, source, coords);
    coords.X = (int)source.X + range; coords.Y = (int)source.Y - range;
    PutFovArrow(console, source, coords);
    coords.Y = (int)source.Y + range;
    PutFovArrow(console, source, coords);
}

Finally, for each tile it considers the above method calls PutFovArrow(). Each call to this method considers where the tile is in respect to the source, determines the next closest tile, calculates the visibility, and draws an arrow pointing at the tile it referenced with a color based on the visibility it calculated. In final form it will likely do no drawing at all, instead just filling the visibility array for later use when rendering.

private void PutFovArrow(TCODConsole console, Vector2 source, Vector2 pos) {
    // No point checking if we're outside the bounds of the map anyways.
    if(pos.X < 0 || pos.X >= Game.Settings.ScreenWidth ||
        pos.Y < 0 || pos.Y >= Game.Settings.ScreenHeight) {
            return;
    }

    temp = source - pos;
    temp.Normalize();
    angle = 180.0f + (float)(Math.Atan2(temp.Y, temp.X) * (180.0 / Math.PI));
    if (angle >= 360.0f) angle -= 360.0f;

    char c = '?';
    float op = 0.0f,
            vis = 0.0f;
    if (angle != float.NaN) {
        if (angle > 337.5f || angle <= 22.5f) {
            op = 1.0f * (fog + opacity[(int)pos.X - 1, (int)pos.Y]);
            vis = Math.Max(0.0f, visibility[(int)pos.X - 1, (int)pos.Y] - op);
            c = (char)TCODSpecialCharacter.ArrowWest;
        } else if (angle > 22.5f && angle <= 67.5f) {
            op = 1.4f * (fog + opacity[(int)pos.X - 1, (int)pos.Y - 1]);
            vis = Math.Max(0.0f, visibility[(int)pos.X - 1, (int)pos.Y - 1] - op);
            c = (char)TCODSpecialCharacter.NW;
        } else if (angle > 67.5f && angle <= 112.5f) {
            op = 1.0f * (fog + opacity[(int)pos.X, (int)pos.Y - 1]);
            vis = Math.Max(0.0f, visibility[(int)pos.X, (int)pos.Y - 1] - op);
            c = (char)TCODSpecialCharacter.ArrowNorth;
        } else if (angle > 112.5f && angle <= 157.5f) {
            op = 1.4f * (fog + opacity[(int)pos.X + 1, (int)pos.Y - 1]);
            vis = Math.Max(0.0f, visibility[(int)pos.X + 1, (int)pos.Y - 1] - op);
            c = (char)TCODSpecialCharacter.NE;
        } else if (angle > 157.5f && angle <= 202.5f) {
            op = 1.0f * (fog + opacity[(int)pos.X + 1, (int)pos.Y]);
            vis = Math.Max(0.0f, visibility[(int)pos.X + 1, (int)pos.Y] - op);
            c = (char)TCODSpecialCharacter.ArrowEast;
        } else if (angle > 202.5f && angle <= 247.5f) {
            op = 1.4f * (fog + opacity[(int)pos.X + 1, (int)pos.Y + 1]);
            vis = Math.Max(0.0f, visibility[(int)pos.X + 1, (int)pos.Y + 1] - op);
            c = (char)TCODSpecialCharacter.SE;
        } else if (angle > 247.5f && angle <= 292.5f) {
            op = 1.0f * (fog + opacity[(int)pos.X, (int)pos.Y + 1]);
            vis = Math.Max(0.0f, visibility[(int)pos.X, (int)pos.Y + 1] - op);
            c = (char)TCODSpecialCharacter.ArrowSouth;
        } else if (angle > 292.5f && angle <= 337.5f) {
            op = 1.4f * (fog + opacity[(int)pos.X - 1, (int)pos.Y + 1]);
            vis = Math.Max(0.0f, visibility[(int)pos.X - 1, (int)pos.Y + 1] - op);
            c = (char)TCODSpecialCharacter.SW;
        }
    }
    visibility[(int)pos.X, (int)pos.Y] = vis;
    console.setForegroundColor(TCODColor.Interpolate(TCODColor.black, TCODColor.white, vis));
    console.putChar((int)pos.X, (int)pos.Y, c);
    console.setForegroundColor(TCODColor.white);
}

The Result

When I walk next to the walls I get a view like this:


Diagram 2 – View with wall opacity of one (1)

If I go into the code and alter the walls to have an opacity of 0.3 instead of one (1) I get:


Diagram 3 – View with wall opacity of 0.3