Pathfinding and AI in Unity

Following my experiments with procedural map generation, I wanted to see some action on the maps I generated. So, I decided to add agents to the scene to observe how they navigate through the map. And, in order to make it look more interesting, I wanted the agents to behave intelligently and perform certain tasks.

For navigation, I decided not to use Unity’s AI navigation package because I wanted to implement it myself. I specifically wanted to learn about the A* pathfinding algorithm and integrate it into my project. I found this amazing video series by Sebastian Lague to learn how to implement the algorithm. Since my terrain was created from point samples generated by Poisson Disk Sampling, it wasn’t a grid, so I needed to adapt the code in the tutorial to arbitrary graphs. The transformation seemed straightforward: the most noticeable difference between a grid, which is a special kind of graph, and the graph that represented my procedurally generated terrain was that the nodes in my graph can have arbitrary number of neighbors. However, it wasn’t going to be that simple, because the game’s poor performance in the case of many pathfinding requests would force me to parallelize pathfinding.

Running pathfinding tasks in parallel implied that I had to use Unity’s job system to enable multithreaded code execution. This meant that I had to convert my A* pathfinding implementation to a struct that implemented the IJob interface. In addition to this, I had to get rid of all the managed (≈ garbage collected) objects that the job used and switch to thread-safe types because the Burst compiler doesn’t support managed types.

The first change I made was to convert the managed node class that represented the vertices of my graph to a struct. Since the terrain is generated at the start of the game and it remains the same throughout runtime, the node positions could be made read-only. For pathfinding, I only needed to use the position on the xz-plane since the point samples were initially contained within a 2D disk on this plane and later assigned an elevation (y) value using Perlin Noise. I also needed the 3D positions of the nodes for placing objects at these locations. So, I decided to declare three fields (x, y and z) and define two properties (Pos2 and Pos3) that would return the 2D and 3D positions, respectively. In addition to the coordinates and positions, I also added an index field to facilitate the lookup of nodes. The GraphNode struct ended up looking like this:

public readonly struct GraphNode : IEquatable<GraphNode> {
  public readonly int index;
  public readonly float x;
  public readonly float y;
  public readonly float z;
  public readonly Vector2 Pos2 => new(x, z);
  public readonly Vector3 Pos3 => new(x, y, z);
  public readonly bool Equals (GraphNode other) => index == other.index;
  // ...
}

The A* pathfinding algorithm requires three values: g is the cost from the start node to the current node, h is the heuristic cost from the current node to the end node, and f is the sum of g and h. It begins by exploring the neighbors of the start node and stores them in the open list, sorted by their f values in an ascending order (lowest f cost first). A node whose every neighbor has been visited is moved to the closed list. Then, a new node is taken from the open list until the end node is added to the closed list. If the algorithm discovers a shorter path to any node in the open list during its execution, it updates the g cost of that node which results in an updated f cost. Hence, the open list should be able to efficiently reorder the nodes in the case of an update, which I will discuss later. For the algorithm to be able to trace the path backwards to construct the path after the end node has been reached, each node must point to the neighbor with the lowest g cost to indicate which step was taken; hence, another field (named parent) is required to store a reference to this neighboring node. Remember that this reference cannot be a pointer to a class instance since we’re not allowed to use managed types.

You may be wondering why I didn’t include the cost fields in the GraphNode struct. Notice that these costs are different for every pathfinding request that has a different start and end point, which means every job needs its own copy of the graph. Remember that the terrain, hence the node positions, is the same for each job. Storing both the positions and the costs in the same struct would result in unnecessary duplication of the coordinate values which did not change. So, it made more sense to define a separate struct to store the costs and other pathfinding related data that differed from job to job. The nodes that stored the positions could be shared between jobs (more on that later). With the addition of couple other fields that are implementation specific, the PathNode struct turned out like this:

public struct PathNode : IEquatable<PathNode>, IComparable<PathNode> {
  public readonly int index;
  public int parent;
  public bool isExplored;
  public bool isObstacle;
  public float g;
  public float h;
  public readonly float F => g + h;
  public readonly bool Equals (PathNode other) => index == other.index;
  public readonly int CompareTo (PathNode other) => other.F.CompareTo(value: F); // reverse the order so that lower F means higher priority
  // ...
}

The index value of a PathNode must be equal to the index of the corresponding GraphNode for convenience. The parent field is an integer that is the index of the neighboring node where a candidate path passes through. Even though I wanted to use a set to store the explored nodes (or indices), I opted to add a field called isEplored to indicate if a node has been explored, which I will explain later. I also added a field called isObstacle to indicate if the node is an obstacle because the map could contain trees. But the map was not supposed to change, hence the tree positions; so, why not include this field in the GraphNode struct? Because, tree positions are determined at a later stage after the nodes are constructed, and I thought I could add dynamic obstacles to the scene in the future. The CompareTo method of the IComparable interface for the float type in the expression a.CompareTo(b) returns greater than 0 if a is greater than b and vice versa; it returns 0 if they are equal. In my open list implementation, I sort items based on priority in a descending order (highest priority at the top). So, I implemented the CompareTo method in a way that returns greater than 0 when a has a lower f cost (higher priority) than b.

Now, it’s time to clear up the things I left unexplained in the preceding paragraphs. They are either related to the native container types that come with the Collections package or custom containers created by myself. These containers are thread-safe and can be used for data that is shared between a worker thread and the main thread.

Recall that the graph, which represents the terrain, is constant and can be shared between threads. NativeArray is the container I used to store GraphNode instances that constitute the terrain. This same array (graphNodes) is passed to the constructor of each PathfindingJob instance that is created. For this to work properly, and to receive appropriate warnings/errors when a job attempts to write to this container, it is required to add the ReadOnly attribute before the field declaration in the job definition that references this graph. The array itself is created by the main thread in a MonoBehaviour instance which is also responsible for disposing of it (by calling its Dispose method) once it’s no longer needed, to prevent memory leaks. This array is created using the Persistent allocator since its lifetime exceeds the four frame limit of the TempJob allocator. The edges of this graph are stored in a NativeParallelMultiHashMap of type <int, int> where the key is the index of a node and the value is a set that contains the indices of the node’s neighbors. This structure (graphEdges) is also created and handled the same way graphNodes is.

There can also be containers that are local to the job struct. These are allocated and deallocated by the job itself. Remember that the open list had to efficiently sort and store the PathNode instances. The pathfinding tutorial by Sebastian Lague also touches on this topic, and the data structure that is used for this job is a heap, specifically a max heap since higher priority nodes are at the top of the heap. However, the implementation in the tutorial could not be used in a job since it must be a native container. So, I had to convert that implementation to a NativeHeap by looking at the examples, and I was successful in doing so after some trial and error. The constructor of this custom native container looks like the following.

[NativeContainer]
[NativeContainerSupportsDeallocateOnJobCompletion]
public unsafe struct NativeHeap<T> : IDisposable where T : unmanaged, IEquatable<T>, IComparable<T> {
  public NativeHeap (int initialCapacity, Allocator allocator) {
#if ENABLE_UNITY_COLLECTIONS_CHECKS
    m_Safety = AtomicSafetyHandle.Create();
    AtomicSafetyHandle.SetStaticSafetyId(handle: ref m_Safety, staticSafetyId: s_staticSafetyId);
    AtomicSafetyHandle.SetBumpSecondaryVersionOnScheduleWrite(handle: m_Safety, value: true);
#endif
    capacity = initialCapacity;
    if (capacity <= 0)
      capacity = 16;
    m_Length = 0;
    m_AllocatorLabel = allocator;
    m_Buffer = (T*)UnsafeUtility.MallocTracked(size: capacity * UnsafeUtility.SizeOf<T>(), alignment: UnsafeUtility.AlignOf<T>(), allocator, callstacksToSkip: 1);
  }
  // ...
}

It is possible to add the DeallocateOnJobCompletion attribute before the declaration of the field of type NativeHeap in the job struct so that the job system automatically deallocates the container when the job is finished. For this to work, the custom container implementation must have the NativeContainerSupportsDeallocateOnJobCompletion attribute and comply with the requirements specified in the description page of this attribute. Recall that I had to add a field called isEplored to the PathNode struct because I could not use a NativeHashSet for the closed list. The reason is that this native container does not support the DeallocateOnJobCompletion attribute, and I did not want to manually dispose of it inside the Execute method of the job to keep it clean of code that is not directly related to the pathfinding algorithm itself. The fields of PathfindingJob are as follows:

public struct PathfindingJob : IJob {
  [DeallocateOnJobCompletion] NativeHeap<PathNode> queue;
  [ReadOnly] readonly NativeArray<GraphNode> graphNodes;
  [ReadOnly] readonly NativeParallelMultiHashMap<int, int> graphEdges;
  NativeArray<PathNode> pathNodes;
  NativeList<GraphNode> path;
  readonly PathEndpoints endpoints;
  // ...
}

The PathEndpoints struct is a pair of integers that specify the start and end node indices. The path is a NativeList created outside the job and filled in during its execution. It is not created in the job’s local scope so it can be accessed later, after calling Complete on the JobHandle. The queue is the open list, which is a priority queue implemented as a heap.

Before diving into how the pathfinding requests are handled, it is necessary to describe how they are created. These requests come from agents that display intelligent behaviour such as following other agents and destroying them, which brings us to artificial intelligence, but not in the form of a neural network. I wanted something simple since the behaviour I wanted to observe consisted of a few basic actions. I found behaviour trees to be more suitable in my case compared to state machines or goal oriented action planning. I’ve found this nice tutorial by Mina Pêcheux to learn about the basics and see how it’s implemented. My implementation looked more or less the same: I defined a LeafNode class and two composite node classes (SelectorNode and SequenceNode) that extend this class. To facilitate passing of data between the nodes of a behaviour tree, I implemented a basic Blackboard class and let all the nodes refer to a common instance. This class defines two dictionaries, one for the information that is being stored and one for the observers that will be notified when certain information is updated. I limited the number of observers for each key to one, which was enough for my purposes.

public sealed class Blackboard {
  readonly Dictionary<string, object> data = new();
  readonly Dictionary<string, Action> subs = new();
  public void Subscribe (string key, Action callback) {
    if (!subs.ContainsKey(key))
      subs[key] = null;
    subs[key] += callback;
  }
  public void Unsubscribe (string key, Action callback) {
    if (subs.ContainsKey(key))
      subs[key] -= callback;
  }
  // ...
}

The root node of an agent’s behaviour tree is a SequenceNode which has four children that define all the actions that an agent can perform. These actions are detecting a target, finding a path to the target, moving towards the target by following the path, and attacking the target. They are evaluated in sequence, and if any one of them does not succeed, the remaining nodes are skipped. These behaviours are all defined in separate classes that extend the LeafNode class. This tree is evaluated in the Update method of the agent’s MonoBehaviour class. The Start and Update methods of this class are given below.

public sealed class AgentBehaviour : MonoBehaviour {
  // ...
  void Start () {
    var detectTarget = new DetectTarget(blackboard, transform, getClosestEnemy: playerEvents.GetClosestEnemy, scanInterval: gameSettings.targetScanInterval);
    var findPath = new FindPath(blackboard, transform, requestPath: playerEvents.RequestPath);
    var followPath = new FollowPath(blackboard, transform, moveSpeed: gameSettings.unitMoveSpeed, attackRange: gameSettings.unitAttackRange);
    var attackTarget = new AttackTarget(blackboard, transform, attackRange: gameSettings.unitAttackRange, initiateAttack: playerEvents.InitiateAttack);
    behaviourTree = new SequenceNode(blackboard, detectTarget, findPath, followPath, attackTarget);
  }
  void Update () {
    behaviourTree.Evaluate();
  }
}

Here, gameSettings and playerEvents are ScriptableObject instances that store the game parameters and gameplay related actions, respectively. Agents need to trigger certain actions to perform some of their tasks that require collaboration from other scripts. For example, they do not know about each other by design; hence, they have to trigger an Action at a fixed interval (unless there is already a valid target) in order to get the Transform component of the enemy that is closest to them. As a result, these delegates are passed to any tree node that needs to trigger them. One such action is RequestPath of type Action<Vector2, Vector2, Action<GraphNode[]>> that is defined in PlayerEvents. Here is the FindPath node where these requests are made:

public sealed class FindPath : LeafNode {
  // ...
  public FindPath (Blackboard blackboard, Transform transform, Action<Vector2, Vector2, Action<GraphNode[]>> requestPath) : base(blackboard) {
    // ...
    blackboard.Subscribe(key: "Destination", callback: OnDestinationUpdated);
  }
  ~FindPath () {
    blackboard.Unsubscribe(key: "Destination", callback: OnDestinationUpdated);
  }
  void OnDestinationUpdated () {
    pathFound = false;
    findPath = true;
    destination = blackboard.GetData<Vector2>(key: "Destination");
    var pos2 = new Vector2(x: transform.position.x, y: transform.position.z);
    requestPath?.Invoke(pos2, destination, OnPathFound);
  }
  void OnPathFound (GraphNode[] path) {
    findPath = false;
    pathFound = true;
    blackboard.SetData(key: "Path", value: path);
  }
  public override NodeState Evaluate () {
    if (pathFound)
      return NodeState.Success;
    if (findPath)
      return NodeState.Busy;
    return NodeState.Failure;
  }
}

Now, let’s see how these requests are handled. The RequestPath invocation requires three arguments: agent position, target position and a delegate to the method that will process the returned path. At the receiving end of these requests, there is a queue that stores them. This is crucial because attempting to process all the requests as they arrive would cause poor performance when there are many such requests in the duration of one frame. Instead, they are processed in batches such that in each frame at most n requests are removed from the queue and n pathfinding jobs are run. The following code schedules jobs that will be executed in parallel by worker threads on multiple CPU cores. A copy of the pathNodes is created for each job since it contains information about the obstacles on the terrain. For the special case of batch size of one or a queue with only one item (not included in the code below), the Temp allocator is used over TempJob for faster allocation, and the job is directly executed (not scheduled).

var numJobs = Mathf.Min(a: gameSettings.pathfindBatchSize, b: pathRequestQueue.Count);
var jobData = new List<(JobHandle handle, NativeArray<PathNode> pathNodes, NativeList<GraphNode> path, Action<GraphNode[]> handler)>();
for (var i = 0; i < numJobs; i++) {
  var (endpoints, handler) = pathRequestQueue.Dequeue();
  var path = new NativeList<GraphNode>(allocator: Allocator.TempJob);
  var pathNodes = new NativeArray<PathNode>(length: this.pathNodes.Length, allocator: Allocator.TempJob);
  pathNodes.CopyFrom(array: this.pathNodes);
  var job = new PathfindingJob(graphNodes, graphEdges, pathNodes, endpoints, path, allocator: Allocator.TempJob);
  var handle = job.Schedule();
  jobData.Add(item: (handle, pathNodes, path, handler));
}
for (var i = 0; i < jobData.Count; i++) {
  var (handle, pathNodes, path, handler) = jobData[index: i];
  handle.Complete();
  pathNodes.Dispose();
  var pathArr = path.AsArray().Reverse().ToArray();
  path.Dispose();
  handler?.Invoke(obj: pathArr);
}

When the path is returned to the FindPath node that requested it, it is written to the blackboard which notifies the FollowPath node. Then, the agent is moved towards the position of the next GraphNode in the path at a constant speed, and this is repeated until it reaches the position of the last node in the array. Index 0 in the path array is the start node which points to the current position of the agent, so the next index should be set to 1 for each new path. If the target is also moving, which is the case here, the path will become invalid as the target starts to get farther away. There is a simple check to determine if the path the agent is currently following will lead to the enemy: calculate the distance from the final node in the path to the enemy and compare it to the distance from the agent’s current position to the enemy, if the final node is not closer to the enemy, request a new path. The Evaluate method of the FollowPath is given below with some parts omitted; attackRange is used as the epsilon value for distance comparisons.

public override NodeState Evaluate () {
  if (path == null)
    return NodeState.Failure;
  var pos3 = transform.position;
  var pos2 = new Vector2(x: pos3.x, y: pos3.z);
  if (target != null) {
    // check if the target is getting away, request a new path if that's the case
  }
  if (nodeIndex > lastIndex)
    return NodeState.Success;
  moveVector = (path[nodeIndex].Pos3 - pos3).normalized;
  transform.Translate(translation: moveSpeed * Time.deltaTime * moveVector);
  if (Vector2.Distance(a: pos2, b: path[nodeIndex].Pos2) < attackRange)
    nodeIndex++;
  return NodeState.Busy;
}

Battles between agents are simulated by one script that stores a dictionary whose keys are the Transform components of the agents in the scene, and values are AgentData instances that contain agent stats such as health points or attack power. When an agent gets close enough to its target, it can initiate an attack by triggering the InitiateAttack action which accepts the Transform components of the attacker and the defender, respectively. Unlike pathfinding requests, battles are not queueed or executed in batches since they are not computationally heavy. Each battle is started via StartCoroutine calls and executed over multiple frames. The attacker gets to hit first, then they take turns. The expression that calculates the damage dealt by the attacker can become very complex as the number of parameters (stats, items, powerups, etc.) increase. If the HP of one side drops to zero, the other side wins. The Fight method that is run as a coroutine is given below.

IEnumerator Fight (TransformPair pair) {
  var attacker = agents[key: pair.A];
  var defender = agents[key: pair.B];
  while (attacker.healthPoints > 0 && defender.healthPoints > 0) {
    var damage = Mathf.RoundToInt(f: attacker.attackPoints * (1f / (defender.defensePoints + 1)) + 1);
    defender.healthPoints -= damage;
    (attacker, defender) = (defender, attacker);
    yield return null;
  }
  battles.Remove(item: pair);
  agents[key: pair.A] = attacker;
  agents[key: pair.B] = defender;
  var loser = attacker.healthPoints > 0 ? pair.B : pair.A;
  // ...
}

The pairings are stored in a HashSet called battles to avoid duplicates. However, representing the fighting pairs as a Tuple would result in (a, b) and (b, a) being treated as different battles, where a and b are Transform instances. To prevent this, I defined a new type called TransformPair that produces the same hash code for the same pair regardless of the order. Once the loser is decided, its entry is removed from the dictionary agents, then it can be destroyed or returned to its pool if object pooling is employed (e.g., if there is re-spawn mechanic).

The agents in the scene are rendered via DrawMeshInstanced calls, similar to how I render the trees. I will skip this part since I explained the process in my previous post. To demonstrate the things I covered in this blog post, I spawned 48 agents at random positions and let them perform the actions defined by their behaviour trees. I rendered their active paths via Gizmos for better visualization. To make the scene prettier, I used tree models from the Low Poly Tree Pack package. The following is the recording of the legendary battles that took place in my procedurally generated map.

Procedurally Generated Maps for MOBAs

In recent months, I’ve been exploring procedural level generation techniques and algorithms to streamline the level design process for my future game projects so that I can spend more time on gameplay programming. While I haven’t delved into some of the more advanced stuff, I think I gained enough experience to quickly create levels suitable for various genres. In this post, I will talk about my progress in incorporating procedural map generation into a MOBA game I’ve been working on (in Unity).

When approaching the level design task, it would make sense to start with a conceptual design, do some sketching and use generative AI to create inspirational visuals before moving on to the actual implementation. However, I chose to skip this part knowing that once I decided on the strategies and assembled my toolkit, procedural generation would give me satisfactory results in no time, and instead of drawings I would have a 3D scene to work with and build upon. In the case of a MOBA, there are only a few special areas and structures which can easily be integrated into the level generation process without requiring human intervention.

The first thing my level needed was a terrain whose shape looked natural and organic. While Unity’s built-in terrain features allow us to create and update terrains at runtime, I wanted more control over the generation process, so I decided not to use those features. One of the reasons behind this decision was my desire to stay away from grid based implementations as grids are not that interesting. However, grids are easy to work with, and now I needed more advanced algorithms to create points in 3D space and connect (triangulate) them to form surfaces. I knew that Poisson Disk Sampling would create nicely distributed point samples and Delaunay Triangulation would be able to triangulate these samples, which would give me the required data to create a Mesh.

My initial idea was to implement both of these algorithms myself so I could better understand how they worked. And I was able to implement the sampling algorithm which worked well. When I attempted to implement the triangulation algorithm, I realized that it would take a long time to do it and it would probably contain lots of bugs in it. I had implemented the Ear Clipping algorithm before (which wasn’t useful in this case), but this was much more complex. So I started looking for a C# implementation of Delaunay Triangulation and found this nice repository by Patryk Grech which also contained an implementation of the Poisson Disk Sampling algorithm. The sample scene in the project allowed me to learn how to use the code and confirm that it worked as expected.

The following code generates point samples inside a circular region, triangulates the points and creates a mesh by providing the required data to the mesh constructor.

var radius = 48f;
var minDistance = 1f;
var sampler = UniformPoissonDiskSampler.SampleCircle(center: Vector2.zero, radius: radius, minimumDistance: minDistance);
var points = sampler.ToPoints();
var delaunator = new Delaunator(points);
var vertices = new Vector3[delaunator.Points.Length];
for (var i = 0; i < points.Length; i++) {
  var x = (float)points[i].X;
  var z = (float)points[i].Y;
  // assign a noise (elevation) value to the y coordinate
  vertices[i] = new Vector3(x, y, z);
}
var mesh = new Mesh {vertices = vertices, triangles = delaunator.Triangles};
meshFilter.mesh = mesh;

The part below is what’s missing in the code above, which is the elevation calculation that utilizes Mathf.PerlinNoise. Getting good results for the terrain heights is all about finding good value ranges for the frequency, amplitude, octaves, persistence, lacunarity and offset parameters.

var amplitude = 3f;
var frequency = .04f;
var lacunarity = 2f;
var persistence = .5f;
var octaves = 4;
var y = 0f;
for (var j = 0; j < octaves; j++) {
  y += Mathf.PerlinNoise(x: offset + x * frequency, y: offset + z * frequency) * amplitude;
  frequency *= lacunarity;
  amplitude *= persistence;
}

By combining these two code blocks, I was able to create a mesh shaped like a terrain. But a mesh alone doesn’t make a terrain; it needed colors to visually indicate the differences in elevation. I wanted to give the terrain a low-poly look; so, I applied flat shading to faces in Shader Graph as described in this article by Hextant Studios. I picked five shades of ground/soil color and assigned them to individual vertices of the mesh based on elevation levels (each vertex falls into one of five levels). The following is the resulting terrain when viewed from above.

It looks natural enough, so I’m satisfied with the result. However, a barren land like this isn’t particularly interesting, so I decided to introduce obstacles (trees) into the terrain. In nature, trees don’t usually stand alone, instead they create formations. For this purpose, I could have set a threshold value and decided whether to place a tree at any point in the mesh by comparing its y value with the threshold. This approach would have resulted in tree covered areas that are above or below a certain height, resulting in unrealistic tree distributions. Instead, I decided to generate a distinct noise value for each point by adjusting the offset provided to PerlinNoise and re-running the algorithm. I stored the tree locations in a HashSet for later.

To place trees on the terrain I needed a tree mesh. I found what I was looking for in this package by Broken Vector. I knew that spawning many tree objects in a scene would result in significant performance issues, and I only wanted to display the trees with no extra functionality. As a result, I decided to use GPU instancing, which reduces the number of draw calls between the CPU and GPU, and improves performance when many instances of a mesh are being drawn. Even though the mesh is the same, it is still possible to apply a different transformation to each instance, which creates variation. So, I chose a tree model and passed it as a prefab to the MapContainer class which contains all the code related to map generation. I also created a shader for the trees that utilized the color sheets provided with the tree models.

[SerializeField] GameObject treePrefab;
[SerializeField] Material treeMaterial;
void Awake() {
  treeMesh = treePrefab.GetComponent<MeshFilter>().sharedMesh;
  treeParams = new RenderParams(mat: treeMaterial) {
    shadowCastingMode = UnityEngine.Rendering.ShadowCastingMode.On
  };
}

treeParams in the code above is an instance of the RenderParams class, which provides various parameters for rendering functions. Notice that the shadowCastingMode is set to on, which is required for instances to cast shadows even though the Cast Shadows option is enabled in the tree shader. In addition to the render parameters and the mesh to be rendered, the Graphics.RenderMeshInstanced method requires an array of Matrix4x4 that specifies the scale, rotation, and translation amounts for each instance. For variation, I randomized the scale and rotation of each tree within reasonable limits. Randomization calls are omitted in the following code.

treeData = new Matrix4x4[trees.Count];
var k = 0;
foreach (var pos in trees) {
  var translate = Matrix4x4.Translate(vector: pos);
  var scale = Matrix4x4.Scale(vector: new Vector3(scaleX, scaleY, scaleZ));
  var rotate = Matrix4x4.Rotate(q: Quaternion.Euler(rotateX, rotateY, rotateZ));
  var transform = translate * rotate * scale;
  treeData[k++] = transform;
}

After creating all the necessary data, it was time to make the render calls within the Update method so it would be executed every frame. If a mesh has multiple submeshes, calling RenderMeshInstanced is necessary for each submesh which can have their own set of parameters.

void Update () {
  if (treeData != null)
    Graphics.RenderMeshInstanced(rparams: treeParams, mesh: treeMesh, submeshIndex: 0, instanceData: treeData);
}

With the addition of the trees, the map became more interesting and visually pleasing. However, it lacked a clear purpose since I hadn’t specified any regions of interest on the map. Now, it was time to introduce the first special regions into the map: the teams’ bases. Where to put the bases was obvious since the leading titles of the MOBA genre all follow the same rule: opposing ends of the diagonal from the bottom-left corner to the top-right corner. My terrain was centered around the xz-plane, so the first base would have negative x and z coordinates while the second one would be on the positive side of both axes. I had to decide on the base radius considering the distance between them and leave some margin from the borders of the terrain, as I wanted to cover the outer parts with trees to signify the boundaries of the map. Calculations of the center points of the bases are given below.

var sqrt2 = Mathf.Sqrt(f: 2);
var borderThickness = 4f;
var borderRadius = radius - borderThickness; // radius used in poisson disk sampling
var borderDistance = borderRadius / sqrt2; // divided by sqrt2 because of the angle (45 degrees) of the diagonal
var baseRadius = 2 * borderThickness;
var baseDistance = baseRadius / sqrt2;
var firstCenter = new Vector2(x: -borderDistance + baseDistance, y: -borderDistance + baseDistance);
var secondCenter = new Vector2(x: borderDistance - baseDistance, y: borderDistance - baseDistance);

When I ran the tree placement algorithm again with the same parameters multiple times while excluding the base areas, I occasionally obtained some decent maps but mostly, they were unplayable such as the following one.

As you can see, the second base is fully covered by trees while the first one has access to only a small part of the map. I thought maybe I could get a better tree distribution by adjusting the parameters of the noise function. By increasing the frequency from .04 to .1, I got the following result.

Even though there is a large enough connected walkable area, both bases are disconnected from it and there are many areas that cannot be reached. I figured that the tree density was too high to allow path formation between the bases. By changing the threshold value, which is compared against the noise value calculated at each vertex to determine whether to place a tree there, I started to see nice, almost fully-connected regions on the map. The only thing I did was to lower the tree density setting from .5 to .4, and I obtained the following map.

However, I still saw cases where the bases were disconnected when I re-ran the algorithm. It was clear that no amount of micro-adjustments would guarantee an acceptable output unless I was willing to limit tree density to very low values. I thought I needed to give up on Perlin noise and started looking for another algorithm that could accomplish the task. I wanted something simple enough to implement but capable of producing complex results. Cellular automaton was what I was looking for, but I didn’t know which model to simulate. Since I was dealing with trees, I searched for known models involving trees. Then, I came across the forest-fire model.

The forest-fire model in the link above was implemented for grids, but it was applicable to arbitrary graphs as well. The model has four rules:

• A burning tree dies (node becomes empty)
• A tree starts burning if any of its neighbors are burning
• A tree starts burning with some non-zero probability even if none of its neighbors are burning
• An empty node can grow a tree with some non-zero probability

I quickly implemented the algorithm for my graph with initial tree placements determined by Perlin noise (there was no escaping from it). I ran the algorithm using the same parameter values from the article (tree probability: .05, fire probability: .001) for 10 iterations and created an animated GIF of the simulation.

I then ran this model a couple iterations on a map generated using the parameter values that resulted in nice outputs in earlier trials. However, I used a much higher initial fire probability compared to the simulation above. See how it helps to connect the islands by breaking through the walls.

Still not satisfied with the results, I began to explore mazes…

Formal Syntax Scraping With ANTLR

A few years ago, I discovered ANTLR while trying to build a parser for a custom config file format. By defining a simple grammar, I was able to get my work done. Then, I discovered the grammars-v4 repository on GitHub and looked at the existing grammars of the languages I knew at the time. I immediately noticed that the SystemVerilog grammar was incomplete and the Verilog grammar had many commented-out rules for some reason. I decided to contribute by completing these two grammars, and started writing the grammar rules for SystemVerilog by copy-pasting sections from the specification document and manually(!) converting the BNF syntax to ANTLR’s grammar format.

After some serious work, I completed (or so I thought) the SystemVerilog grammar and created a pull request (PR). I received some feedback regarding formatting issues and fixed them all. Finally, my PR got merged into the main branch. Of course, the grammar was not free of bugs. Some of these issues could be attributed to my lack of experience with ANTLR. However, I kept discovering a particular issue even after fixing many instances of it, and it was due to an unforgivable mistake I had made: handwriting the grammar. It was the inconsistency between the grammar I wrote and the formal syntax of the language. Every time I opened them side by side, I noticed a rule that differed from the specification. At this point, I realized that the only way to do the conversion correctly was to automate this process. This is how Syntax Scraper came to life.

Since I was dealing with Verilog grammars, which are IEEE standards, I was only interested in the formal syntax described using Backus-Naur Form (BNF). In IEEE 1800-2017 (SystemVerilog standard), Annex A (formal syntax section), there is a list of conventions used in describing the formal syntax:

• Keywords and punctuation are in bold-red text.
• Syntactic categories are named in nonbold text.
• A vertical bar (|) separates alternatives.
• Square brackets ([ ]) enclose optional items.
• Braces ({ }) enclose items that can be repeated zero or more times.

To be able to distinguish between text that had different styling, I needed a tool that could extract this information from a PDF. After some research, I found pdfplumber, a Python package that does just what I wanted, which also meant that I was going to use Python to develop this tool. Due to some inconsistencies between different copies of the same standard document on the Internet, such as the use of different font families, I had to rely on one thing to detect bold text: the word bold appearing in the font name of the character.

After processing the PDF, I needed to parse its text to find the rule definitions. To accomplish this task, I decided to use an ANTLR-generated parser. However, there was an obvious issue: ANTLR cannot directly use font styling information, so I had to insert some special characters into the input text to help ANTLR differentiate between regular and bold text. Therefore, I decided to enclose bold text within single quotes ('). Since the input could also contain single quotes, which are literal delimiters in ANTLR syntax, I had to escape them with backslashes (\) to avoid syntax errors caused by unmatched single quotes. Similarly, backslashes in the input stream could cause issues, so I had to escape them as well. Below is the part of the BNF lexer grammar I created to handle these strings.

APOSTROPHE : "\'" -> skip, pushMode(STRING_MODE) ;
mode STRING_MODE;
STRING_TEXT : ~['\\]+ ;
STRING_ESC_SEQ : "\\' ( '\'' | '\\" ) -> type(STRING_TEXT) ;
STRING_APOSTROPHE : "\'" -> skip, popMode ;

The only difference between my BNF parser grammar and the original BNF syntax is the “fuzzy parsing” component. It means that the grammar is defined in such a way that only the necessary information is extracted from the input. The formal_syntax parser rule exemplifies this behavior. It detects sequences that conform to rule_definition and terminates the current match if a token violates the syntax. It then continues looking for the next ::= (is defined as) token. As a result, if a rule spans multiple pages, the words in the page footer (or in the next page’s header) will cause the rest of the rule to be skipped. Nevertheless, it is guaranteed that no ::= tokens are skipped, meaning that every ::= defines a rule.

formal_syntax : ( rule_definition | ~"::=" )*? EOF ;
rule_definition : rule_identifier "::=" rule_alternatives ;

After generating a parse tree, the next step was to convert the BNF rules to ANTLR rules. To accomplish this, I used the visitor generated by ANTLR. In the initialization phase, I created an empty string to store the grammar text and defined a variable to keep track of the current hierarchy level so that only the rule alternatives (separated by |) began on a new line. As I visited the nodes of the parse tree, I appended each symbol to the string while performing the following actions:

• Enclosed keyword and punctuation symbols, which corresponded to bold text in the input, in single quotes (').
• Appended a question mark (?) to optional items.
• Appended an asterisk (*) to repeated (zero or more times) items.
• Enclosed groups of items in parentheses (( )).

In addition to these, I had to override the default implementations of certain visitor functions, so they would return the text associated with each node:

def visitChildren(self, node):
  text = ""
  n = node.getChildCount()
  for i in range(n):
    if i > 0:
      text += " "
    c = node.getChild(i)
    result = c.accept(self)
    if result == None:
      result = ""
    text += result
  return text

def visitTerminal(self, node):
  return node.getText()

The ANTLR grammar generated by my tool is not free of syntax errors. The tool cannot distinguish between the title text, which is in bold, and bold text in rules. Furthermore, there are other text such as footnote references that have no clear styling information to indicate whether they are part of the rule text or not. However, I was able to identify and remove section references by the distinctive character called the section sign (§). Additionally, some rules may be incomplete, or even empty, due to their start and end being on different pages. All of these issues must be resolved manually by the user.

Although not perfect, this tool helped me eliminate all the inconsistencies between my grammar and the specification. With the ANTLR extension for Visual Studio Code, I was able to find and fix the syntax errors easily. Since submitting my first PR to the grammars repository, I have improved my grammar design skills and updated my grammars to a higher standard. I occasionally contribute new grammars to the repository and strive to assist other contributors and users.