Roses & Thorns
Project Lead & Lead Programmer
Mar 2020 - Mar 2021
Unity, C#
Probably my most ambitious project to date,
Tactical Tools
This project was a learning process for me. It first came about after I built a map editor prototype in one of my other classes. Roses & Thorns was build off of that foundation, but a faulty foundation it was. Many things I didn't consider, whether because of my own bias, lack of forward thinking, or limited knowledge of Unity and C#, came back to cause problems as we started working.
- The map maker only worked during runtime, and displayed no visuals in the editor otherwise. Saving map layouts requires complicated work-arounds that made it frustrating to work with.
- Being the one who built it, I was the only one who really understood how to use it. Despite my efforts to make it user friendly, the interface was stark and had one too many quirks.
- The structure of the map maker had put a severe limit on our artists. Not only did all the assets have to fit the blocky mold, but artists could not hand place the assets themselves, instead having to use the map maker.
And the final nail in the coffin was code dependency. At the time I had made the tool, I had limited experience with interfaces, events, and tools. Every script was a monster of code, checking for every individual interactions and exceptions, even despite my attempts to optimize. We eventually cheesed the results, layering the grid over nicely designed environments and did our best to approximate certain features that the grid offered. But this was an utter failure on my part.
Starting From Scratch
We were lucky in that our schedules gave us a two month break between classes. This gave me the much needed opportunity to fix the mistakes I made. I took the time to learn about Unity Editor Tools, Unity Events, and game programming patterns (like the finite state machine and commands) that would massively improve my code.
The new map maker in question has the following features:
- It can be used in editor, using handles to adjust the width and height of the grid.
- It can conform the position of the nodes to the ground under them, allowing for more varied terrain.
- Obstacles and special terrain types can be determined via trigger colliders with the environment, allowing a synthesis of art and level design previously undoable.
- The grid can be "baked" into the scene, like a nav-mesh, removing the expensive processes used to determine unchanging variables and easily saving the result to the scene.
- State Machines are used to keep track of things such as game state and units' state, an improvement from the previous enum-based system.
- Most interactions are handled using Unity Event "Listeners" and Scriptable Objects, making more readable and workable code.
I can think of even more improvements I would like to have made if I had the time, and may do in the future. Decoupling logic from visuals was something I strived for but ended up dropping. Baking the grid also seems bad in retrospect, as it removed the possibility of shifting or altering environments and terrain height. Events probably could have solved the issue of the expensive processes before baking, and even allow for changing environments. And many times I had used ScriptableObjects where I really shouldn't have, especially for abilities, where rather than create a Monobehavior that takes the data of the ScriptableObject, the SO enacts the functionality itself. I've since learned better.
Expand
//excerpt from Node Map Creater.cs
public int MapSizeX => ((anchor[1].x - anchor[3].x)/spread)+1;
public int MapSizeZ => ((anchor[0].z - anchor[2].z)/spread)+1;
public void BakeNodeMap()
{
if (!Application.isPlaying && NodesNotEmpty)
{
NodeMap nodeMap = nodeFactory.GetNodeMap();
nodeMap.InitializeNodeMap(editableNodes, MapSizeX, MapSizeZ, nodesBlanket? fallPoint : Center, anchor, spread, cliffHeight, edgeOfMapIsWallOrCliff);
DestroyImmediate(gameObject);
}
}
public void InitializeNodeMapCreator(Vector3Int[] mapAnchors)
{
anchor = mapAnchors;
UpdateNodeList();
}
public void UpdateNodeList()
{
if (transform.hasChanged)
transform.position = SnapExt.Y(Center, Center, 1);
transform.position = Center;
if (nodesBlanket)
{
RaycastHit hit;
if (Physics.SphereCast(transform.position, SpreadHalfExtent, Vector3.down, out hit, 100, Layer(NodeType.Floor)))
fallPoint = hit.point + (Vector3.up * blanketHeight);
}
if (NodesNotEmpty)
{
editableNodes.Clear();
editableNodes.TrimExcess();
}
editableNodes = new List<EditableNode>();
if (MapSizeX > 0 && MapSizeZ > 0)
{
for (int x = 0; x < MapSizeX; x++)
{
for (int z = 0; z < MapSizeZ; z++)
{
EditableNode tempNode = new EditableNode(FromBottomLeft(x, z), x, z, this);
editableNodes.Add(tempNode);
}
}
}
}
Pathfinding
Something I know I wanted to include in this prototype was circular radiuses. In typical tactical games, movement is handled with a diamond shape as it is the most simplest to use on a grid, outside of squares. With circles however, I hoped to circumvent the frustration of not being able to reach a tile just barely outside of your range. Through an email correspondence with Amit Patel (you should check out his blog at Red Blob Games), we were able to conceive of a grid-based pathfinding system that uses circles rather than the usual diamonds. My original attempts were process-intensive recursions and checks that slowed down Unity whenever I wanted to see a character's movement range. The new algorithm we landed on was based on a combination of Dijkstra's Algorithm and Breadth-First Search, using a priority queue, and has shown little-to-no signs of slowing down even at the largest of radius sizes.
Normally, each cell in a grid would have a horizontal and vertical movement cost of 1 (which I will call the Rook Cost in my code, in reference to chess), making all diagonal movement effectively cost 2 (the Bishop Cost). However, what if diagonal movement had a different cost, more than 1, but less than 2? With a cheaper Bishop Cost, you can fill in the corners of the diamond, adjusting the ratio to round it out more or less. In my experience, while 1:1.5 (or 2:3) may seem like the obvious choice for Rook:Bishop costs, I found that experimenting with different ratios gave better results in creating an aesthetically pleasing circle on a grid. For Roses & Thorns I landed on a 3:5 ratio.
Now the algorithm. Breadth-First Search is able to find all the potential paths quickly up to your movement cost limit, and Dijkstra's Algorithm is able to organize them by cost effectiveness. This algorithm is also able to organically work around obstacles, having a more natural quality in shrinking the maximum distance, and works perfectly for games where you can move in 8 directions. One thing to note is that when adjusting the ratio away from 1:2, the movement cost limit (by that I mean, the most the character can spend to move in one go) becomes a little harder to figure out. You have to figure out what is the farthest distance of cells you can travel to in order to reach a corner
I hope to find time to work on a generic version of this algorithm for broader use in future projects.
Expand
//Excerpt from PathfindingExt.cs
public static HashSet<Node> DijkstraBFSCircle(this HashSet<Node> nodes, Node start, int radius, bool fill = true)
{
HashSet<Node> boundary = new HashSet<Node>().ReachNodes(start, NodeShape.Square, radius);
IPriorityQueue<Node, int> queue = new SimplePriorityQueue<Node, int>();
IDictionary<Node, int> distance = new Dictionary<Node, int>();
nodes = new HashSet<Node>();
queue.Enqueue(start, 0);
distance.Add(start, 0);
while (queue.Count > 0)
{
Node currentNode = queue.Dequeue();
for (int i = 0; i < 8; i++)
{
Dir dir = i.ToDir(false);
if (currentNode.CanTravelToNeighbor(dir))
{
Node neighbor = currentNode.GetNeighbor(dir);
int dist = distance[currentNode];
int nodeCost = i < 4 ? RookCost : BishopCost;
if (neighbor.data.Type == NodeType.DifficultTerrain)
nodeCost = (int)(nodeCost * 2f);
dist += nodeCost;
if (dist <= MaxMoveStep(radius) && boundary.Contains(neighbor))
{
if (!distance.ContainsKey(neighbor))
{
distance.Add(neighbor, dist);
nodes.Add(neighbor);
queue.Enqueue(neighbor, dist);
}
else if (dist < distance[neighbor])
{
distance[neighbor] = dist;
queue.Enqueue(neighbor, dist);
}
}
}
}
}
}
public static List<NodeCost> Pathfind(Node start, Node end, int radius, HashSet<Node> alreadyOnPath = null, int startCost = 0)
{
if (alreadyOnPath == null)
alreadyOnPath = new HashSet<Node>();
HashSet<Node> boundary = new HashSet<Node>().ReachNodes(start, NodeShape.Square, radius);
HashSet<Node> exploredNodes = new HashSet<Node>();
IPriorityQueue<Node, int> unexploredNodes = new SimplePriorityQueue<Node, int>();
unexploredNodes.Enqueue(start, 0);
Dictionary<Node, Node> nodeSequence = new Dictionary<Node, Node>();
//gScore, the cost to move from neighbor to neighbor
Dictionary<Node, int> distance = new Dictionary<Node, int>();
distance.Add(start, startCost);
while (unexploredNodes.Count > 0)
{
Node currentNode = unexploredNodes.Dequeue();
if (currentNode == end)
{
return ReconstructPath(nodeSequence, distance, currentNode, start, radius, startCost);
}
exploredNodes.Add(currentNode);
for (int i = 0; i < 8; i++)
{
Dir dir = i.ToDir(false);
if (currentNode.CanTravelToNeighbor(dir))
{
Node neighbor = currentNode.GetNeighbor(dir);
if (!alreadyOnPath.Contains(neighbor))
{
if (boundary.Contains(neighbor))
{
if (exploredNodes.Contains(neighbor))
continue;
int dist = distance.ContainsKey(currentNode) ? distance[currentNode] : MaxMoveStep(radius);
dist += i < 4 ? RookCost : BishopCost;
if (!unexploredNodes.Contains(neighbor))
unexploredNodes.Enqueue(neighbor, dist);
else if (dist >= (distance.ContainsKey(neighbor) ? distance[neighbor] : MaxMoveStep(radius)))
continue;
distance[neighbor] = dist;
nodeSequence[neighbor] = currentNode;
}
}
}
}
}
return null;
}
Abilities
A short tidbit, I think some of our abilities look
