This week was a grind. Every time I fixed a bug in the history generator, a new bug appeared on the next run. When I found the source of a bug, I made quick and direct fixes without regard to code quality or architecture, resulting in some ugly branching and repetition. I had my reasons for using this approach. I’ve struggled to fully devise the conceptual and architectural solutions for history generation. Producing working code for various history generation examples allowed me to identify patterns that I could apply to the architecture. I have code rework to do now, but that’s better than being stalled out in abstract design.
It wasn’t until yesterday that I got a clean history generation test run. The current test run generates 20 events randomly selected from 10 different event types. Most of the event types are generic – add a new section, add a new actor, add a new faction, etc. There are a couple of event types to test triggers – a faction leader dies, the faction leader’s son becomes leader of the faction. There’s also one event type that advances the history era. This event type ages world state entities according to the time difference between the current and next era. The current implementation of the aging event type is very simple; if the amount of time that has elapsed exceeds the lifespan of the entity, the entity dies. I will expand the implementation in the near future to do more interesting things such as decomposition.
Despite the limited number and generic nature of the current event types, interesting events are being produced: a giant rat is appointed leader of a faction of dark elves, the giant rat’s daughter is a gelatinous cube, the son of a wizard is a thief, troglodytes and knights settle in the same cavern section. I want to maximize the possibility space, but avoid generating histories that are highly random and implausible. This can be accomplished through constraints in the event type definition. For example, only an actor type associated with a faction can become the leader of that faction.
The impact of history generation on overall game progress remains a big concern. I don’t know how long this detour will take. It’s a far greater effort than I envisioned it being, and there is far more work to do. I planned on winding down the effort by the end of March. While I have succeeded in developing a functioning framework, there is so much more content to create, and undoubtedly as new content is created more bugs and functionality holes will be exposed. Next week, I’ll continue working on history generation exclusively to close out March. My plans for April aren’t solidified yet, but a key goal will be expanding the variety of history event types.
History generation improvements continued at a good pace this week.
- History Event Triggers. History events can now trigger future events to produce more logical event sequences. World state entity updates, such as placing an entity in a new location, now emit triggers that get added to a queue. When a new history event is being selected, the trigger queue will be examined first. If the queue is non-empty, the next trigger will be dequeued. The event selector will then find all of the event types that can respond to the trigger, and randomly select one of those. This allows multiple outcomes for an event.
- History Event Parameters. To support History Event Triggers, there needed to be a mechanism for passing an event’s entities to triggered events. This was accomplished by mapping trigger parameters to event entity placeholders. This was a difficult feature to implement because of how extensively indirection is used in history generation. Many of the values in the history event type definitions are expressed as entities (e.g. “ActorA”) or entity attributes referencing other entities (e.g. “ActorA.Section”). Those values are parsed to find the matching entity in the world state. The history event parameters add another layer of indirection by referencing parameter names in the trigger and placeholder names in the triggered events. This approach provides great ease of use and flexibility for designing events at the cost of under-the-hood complexity.
- History Event Significance. The main purpose of history events is to construct the world state. As such, some events aren’t significant enough to convey to the user or record in a history timeline. I added a significance attribute to prevent insignificant events from being presented to the player.
- On-Demand Entity Creation in History Events. Previously, history events could either create an entity or select an existing entity from the world state. Now, events can be configured to attempt to find an existing entity first, and create a new entity if an existing entity isn’t found. This ensures that existing entities are used as much as possible, which makes the timeline more interesting, and that there is a wide variety of event types to choose from (events that require existing entities can only be generated if those entities exist).
Now that there’s a way to link cause and effect history events, next week I’ll resume work on stocking the dungeon from the generated history. The system is working but more content (i.e. event types) is needed. Creating new event types in and of itself is simple; it can be done entirely in the Unity inspector. However, I need to code more varieties of the building blocks that define history events, for example the criteria that determines the types of entities that can be bound to an event.
I’m ahead of schedule for a change. The dungeon is now being populated by the world state produced from history generation. The way it works is: 1) sections are created (e.g. caverns, temple, catacombs) 2) world state entities (e.g. rooms, actors, items) are placed 3) the remaining unused portions of the map are filled in with randomly selected content associated with the section. It doesn’t have much bearing on gameplay yet, because only a handful of test events have been created. Nonetheless, it’s satisfying to walk through a temple and know (as the game developer) that it’s there because it was created by dark elves long ago, and that the remains in the crypt belong to the first leader of the dark elves, and that the magic sword the leader was entombed with is now in the possession of a thief hiding out in the nearby caverns. The history generation places map elements in a more logical fashion, which was the main goal, but I also need to reveal the history to the player in bits and pieces, through inscriptions, journals, NPC interactions, etc.
Next week, I’ll add support for more advanced generation from the world state, such as adding objects to preexisting containers on the map (e.g. chests, actor inventory). I’ll also start work on cause and effect relationships for history events, which will enable more logical event sequences.
Having several large, distraction-free blocks of time was a huge productivity boost this week. I haven’t had that over the past month. History generation progress continued to accelerate. The current capabilities are:
- History event types, created using the Unity Inspector.
- Logical sequencing of events via preconditions: conditions that must be satisfied for the event to be used
- Event type text templates: the event type expressed in a human-readable statement, with placeholders for world state entities that can be bound to the event
- Event placeholder to world state entity binding, with entity selection criteria
- Support for the following world state entity types: map sections, map elements (rooms, decor), factions, actors, objects, and items
- World state generation from events
What’s still needed:
- Map population from world state
- World state entity injection into map elements
- Additional world state entity attributes
Next week, the “What’s still needed” bullets are the goal.
I’m finally getting some traction on the history generation implementation, which is a big relief. I was starting to feel like the pursuit of procedurally generated history was leading me into a dark abyss. I attribute the recent progress to a deliberate shift from highly analytical solution design to brute force coding. I could no longer advance by thinking about the solution and writing it out in design docs. I had to build things, see how they worked, and either refine or discard them. By doing so, it became easier to see what worked and what didn’t. And, I didn’t have to hold the entire solution in my working memory; I could build pieces that did work, forget about their details because I knew they worked, and concentrate on what was missing and what needed to be revised.
Next week, with February coming to an end, I’m pushing to complete the history event generation (code only; content comes after). My March goal is to populate the dungeon from the history generator’s output, the world state. I expect this to be less complicated than history generation. It will iterate through each entity in the world state, find a matching concrete object (a room, actor, item, etc.), and locate an area on the map to place the object.
Progress has slowed to a crawl in recent weeks. I’ve had limited free time lately and the procedural history generation has grown increasingly complex, almost to the point where I need to rethink it or scrap it. I coded the barebones implementation last week but hit a wall when I added more historical event types. I’ve also spent a disproportionate amount of time optimizing the editing of history generation ScriptableObjects in the Unity Inspector. I originally conceived a solution that was heavily text-based, using dot notation to reference different attributes of entities in the history state. Thinking that this was too error-prone and user-unfriendly, I built (most of) an Inspector UI to edit the objects. I’m not sure at this point which approach is preferable; they have equal pros and cons. Relating historical events is another area that is proving to be far more difficult than anticipated, and where I’ve likely gone overboard. Increasingly, the original idea of loosely connected, randomly generated events seems like it won’t work. Initial testing revealed that the sample histories I created by hand in the design doc had many implicit connections and assumptions I didn’t factor into the procedural generation. Finally, transforming the world state produced by the history generator into concrete objects in the dungeon has exposed a limitation in how dungeon stocking currently works. Map Elements, the objects used to stock the dungeon, can be overlaid but can’t communicate with each other. For example, if a king dies and is to be buried in a crypt, the king can be placed in the crypt, but cannot be placed specifically in the sarcophagus in the crypt. There are fairly simple solutions for this particular case, but a general solution is more complicated.
The key achievement this week was deciding to have history events use the Command pattern to interact with the world state. I tested this idea using the hand-created timelines and it works well (the measure of how well it works being applicability across all of the timeline events). This solution is advantageous from an editing standpoint too; it works well in the Unity Inspector. I’m a little concerned that I’m giving editability too much weight in my solution selection, but it is an important factor because I need to be able to rapidly create many event types.
Next week, I’ll implement the initial set of world state commands. These include placing entities in locations, killing entities, adding items to entities, and aging entities. Also, I’ll try to solve the historical event relationship problem. My goal is to finalize the history generation design in February and implement the Map Element transformation in March, entering Q2 with a working history generator.
Barebones history generation is working. The key classes, methods, and process steps have been built and integrated. There’s still a lot of functionality to fill in. For example, the event sequence is entirely random; there are no relationships between events yet.
The history generation is driven by predefined event types. Event types contain text describing the event (e.g. “[Who] arrives at [Where]”), selection criteria for the entities involved in the events, the entity attribute changes caused by the event, and potential follow-on events. Event types inherit from ScriptableObject and, as such, can be created and edited in the Unity inspector. Due to the complexity of event types, I relied heavily on Odin Inspector to make the objects easier to view and edit.
Next week, the history generation implementation continues.
Architecture and code design for history procedural generation is 75% complete. History generation is turning out to be a feature that seemed simple at an abstract level but has proven to be very difficult at a concrete level. It wasn’t part of the original vision, but I had considered it early on and chosen to exclude it because I didn’t think it was necessary. My opinion only recently changed, when I realized that dungeon stocking needed to be more contextual. Now history generation is a must-have, though I’m still uncertain about how well it will work in practice.
Next week, I’ll start history generation coding.
- Map generation optimization. Map generation was further optimized this week, bringing memory allocation to ~50 MB (from 5.5 GB originally). Optimization is taking longer now. The low-hanging fruit has been picked; the remaining inefficiencies are more spread out and smaller percentages of the whole. Good gains came from removing some logging calls, which are expensive in Unity. Another boost came from reworking the graph shortest path algorithm, which gets called for every unique pair of rooms. When I optimize, I focus first on memory allocation and second on duration. Memory is in good shape, but it is still taking 5-6 seconds to generate a map (the 3-5 seconds I reported last week was incorrect; I wasn’t looking at the actual duration data). My goal is under 3 seconds, so there’s still some optimization work to be done. I’m targeting code that is frequently executed. The worst case is slightly over 1,000,000 executions.
- History procedural generation design. The conceptual design is done. The next step is software architecture/code design.
Next week, I’ll focus on the history generation implementation.
- Map generation optimization. I knew as I wrote Map Generator 2.0 that some of the code was horribly slow and wasteful and would need to be optimized later. Map generation had ballooned to 10-15 seconds and .5 GB of memory. It’s now down to 3-5 seconds and 200 MB of memory, and there’s much more room for improvement. The optimization techniques were converting LINQ statements to for loops and reducing use of temporary lists. One optimization example involved how connections between rooms are stored. I started with one list that stored all original connections between rooms. Then I created a new list for connections that constructed loops and another new list for connections that joined sections. I used separate lists instead of the original list because I needed to do different things with the items in these lists, and it was more expedient to create new lists (though a little voice inside my head was telling me to slow down and do it the right way). I added a fourth list when I realized I needed to track each connection in each room that used the connection (as opposed to only the room that originated the connection). Because it was sometimes necessary to get all of the connections, I created a property that combined all four lists into one new list. Yikes. The allocations… The solution was to combine the lists into one and add an attribute indicating the type of connection. This caused way more rework, and troubleshooting issues caused by the rework, than I anticipated. At least the rework made the code simpler and easier to understand, which is always beneficial.
- Movement optimization. Enabling actor actions to be displayed simultaneously exposed a problem: the movement code took a long time to run, causing actors to instantly move to the next cell rather than moving incrementally over multiple frames. Linear interpolation is used to calculate how far an actor moves each frame, with the actor’s movement speed and elapsed time since the last update as inputs. I ran the Unity profiler and identified the main causes: dynamic lighting and excessive Unity log calls. The log calls are easy enough to deal with; they won’t be in production releases. Dynamic lighting, which uses the Smart Lighting 2D asset, is a dilemma. I want to keep it in the game but I’m not sure how much I can optimize it. Temporarily disabling the lighting and logging fixed movement between two cells, but there was still an issue when moving across multiple cells. Actors momentarily stopped at each new cell before moving again. I had seen this before and knew the source: the state logic in the Update method caused some frames to skip movement. For example, an Update call would determine that all actions had finished in the previous Update and it would update the turn state. Movement wouldn’t resume until the next Update. With nested state logic (there are turn phases, actions phases, and action step phases), several frames passed before movement resumed. This was resolved by modifying the state logic to process state changes in the same update when applicable. For example, when an action step finishes, the logic will start the next action step in the same update.
- Displaying actor actions simultaneously. I reverted the changes I made last week to present actor actions simultaneously. It became clear that an enormous amount of rework was needed to separate action logic and presentation. Fortunately, a much simpler solution had been right in front of me the whole time: asynchronous actions. Instead of waiting for each action to finish being presented, I’d simply start off each action at the same time. I didn’t consider this initially because one actor’s actions can affect another; I believed that all actors’ actions had to be resolved before any of them could be presented. For example, if the player hits an enemy, and that enemy dies, the enemy shouldn’t be able to move. I still had to make some modifications to get this working, such as checking that an actor is still alive, and tracking cells that actors are moving to before they reach the cell (so that other actors don’t attempt to move into the same cell).
- Pathfinding improvement. Over time, I’ve changed my mind on how actors interact with other actors and objects that are diagonally adjacent. I may change my mind again, but what’s certain is that there needs to be a way to allow interactions with adjacent objects in ordinal or cardinal directions, depending on the object. Currently, a melee attack can be performed from an adjacent diagonal cell, but opening a door cannot. Until this week, the latter was not possible because of a limitation in the pathfinding code – since actors can move diagonally, and the pathfinding code finds the shortest route, paths end at a cell diagonal to the cell containing the object being interacted with. The fix for this was to change the path destination based on the interaction range of the object. An object with a range of 1 can only be interacted with if the actor is adjacent to the object in a cardinal direction.
- Better debugging statements. It just occurred to me that I’ve written a lot of bad debugging statements. I typically add debugging statements while troubleshooting a particular issue. They make sense when working within the context of an issue, but not on their own. Without context, they do more harm than good because they increase cognitive load, which is already high from being in troubleshooting mode. I improved these statements by adding more relevant state information to them. I also rearranged the statement in some cases so that the subject of the statement (actor, item, etc.) was at the beginning of the statement. This made it easier to skim through the debug log.
- Inspector improvements for ScriptableObjects using Odin. To reap the full benefit of Odin, I added Odin attributes to all classes inheriting from ScriptableObject. These objects are now easier to view and edit in the Unity Inspector.
- Duplicate door bug fix. Doors recently stopped opening when they were clicked. Actually, most doors didn’t open but a few did. I reviewed the pertinent code but couldn’t find a problem. I started a game and right-clicked on a door to open the Inspect Panel, which shows everything in the cell. Nothing appeared to be out of the ordinary, and the door opened when I clicked it. Then I clicked another door. This one didn’t open. I opened the Inspect Panel and found the problem: there were two doors on the cell. It turns out that the recent change to track connections between rooms in both rooms caused most doors to be added twice. The fix was trivial; I just had to exclude door creation on the duplicate connections.
Next week, I’ll further optimize map generation. Possibly, I’ll start coding the procedural history generation, which I’ve been slowly designing over the past month.