Map generation version 2 continued to evolve this week, primarily through incorporation of features from the original map generator. These features include caverns, circular rooms, theme correction, and dungeon stocking.
Generator in action:
Looping didn’t make it in yet. I got hung up on partitioning the map into sections, which ties into how the looping will work.
The above examples use the version 1 stocking logic, which randomly populates each room using a weighted randomizer based on room type rarity. The need for more intelligent dungeon stocking is what triggered creating a second version of the map generator. As with looping, sections are key. The plan is to partition the map into several sections and apply content based on the section type.
Also, map graphs got some minor improvements – corridors have been de-emphasized by removing the node labels and making the nodes smaller. This makes it easier to understand the map structure. Here’s an example:
Next week, I’ll figure out map sectioning and looping.
The few hours available this week went to improving map generation. Adding dead-end removal and some rules for connecting corridors to other rooms and corridors has immensely improved map layouts. Here are a couple of examples:
Next week, I’ll add looping to reduce linearity and backtracking, and make some minor refinements such as removing redundant doors.
The algorithm for determining available space is fully working. I really struggled with it. I expected needing a few days to complete it but those days turned into weeks. The algorithm design itself was sound; it was the calculations that drove me nuts. Ample debug statements and code comments helped get the job done. Another useful technique for troubleshooting procedural generation issues is to temporarily increase simplicity, predictability, and repeatability. To debug the algorithm, I disabled the random starting point and instead set the starting point to 10, 10 and the initial feature size to 5×5, simplifying the math. By using fixed values, I knew what the expected values were (I didn’t have to calculate these in my head every time because the starting point and feature size changed each run). Using the same fixed values for every run made it easy to tweak the algorithm until the desired result was achieved.
Here are a few examples employing the new available space algorithm. Note that these aren’t playable maps; they simply demonstrate the algorithm at work.
Other accomplishments this week:
Room and corridor fine-tuning. The ratio of rooms to corridors was adjusted, along with the sizes. In both cases, I compiled data from multiple hand-drawn dungeon maps and calculated min, max, median, and mean values. The median and mean values were similar when I removed extraordinarily large rooms from the data set.
Smarter corridors. Corridors now only connect to other corridors and rooms from specific points, based on the orientation and direction of the corridor. This helps corridors connect to other features in a more logical fashion.
Level graphs working again and improved. Level graphs required a few modifications to function with the new map partitioner. While I was in the code, I made some improvements. The new partitioner treats both rooms and corridors as graph nodes (previously only rooms were nodes), so I gave room and corridor nodes different shapes and sizes to better distinguish them.
New automated tests. I rarely use test-driven development, but there were some situations this week where it made sense. The calculation-heavy utility methods for determining available space were easier to develop and test independently rather than when integrated into the full map generator.
Next week I’ll continue refining the new dungeon layout. The goal of putting out a demo by year-end is almost certainly unattainable at this point due to the unplanned procedural generation work. But, I am taking a lot of time off in December and may be able to pull it off.
I continued working on the new dungeon layout algorithm. I grossly underestimated how long it would take to finish. It’s making me miss BSP.
The grid logic eats massive amounts of time. It’s just little things like mapping local coordinates to global, making sure I’m adding and subtracting 1’s as needed when working with rectangles, remembering that the y value decreases when going north and increases when going south in the coordinate system but the order is reversed when displayed on screen. My graph paper tablet is indispensable for this type of work. I have ten full pages of sketches of rooms and corridors that I used to work out algorithms, calculations, and measurements. Debugging is time-intensive too. Tracing through the code line-by-line to check values, in conjunction with running the map generation visualizer one step at a time, has been effective.
The maps are better than last week, but still basic. The generation is much more robust than last week. Except in some rare cases, there’s no more problematic behavior like orphaned connection points and overlapping rooms. I haven’t re-enabled the processors that run after the basic level structure is created, so the map is unpopulated. There aren’t even any doors. Here are some examples of where the level generation stands:
Next week is all about fine-tuning the generator to improve the map layout. I expect this to be time-consuming because it’s a trial-and-error process.
The entire week was spent on a new dungeon layout algorithm. Binary space partitioning (BSP) has been replaced by what I’m calling dynamic space partitioning. Dungeon generation now occurs by adjoining new rooms to existing rooms. It’s similar, at a high level, to the Dungeon-Building Algorithm from Mike Anderson. A key difference is that before generating and placing a new room, the maximum amount of free space available from a connection point on the edge of an existing room is calculated, thus creating a new partition. When the new room is placed, the partition is resized to match the size of the new room, releasing the unused space from the original partition. This approach yields a more rational dungeon layout (if a dungeon layout can ever be considered rational), prevents overlapping rooms, and is more efficient than similar approaches that randomly generate new rooms until finding a room that fits.
I had hoped to have some amazing example maps to share by the end of the week. The core algorithm has been implemented, but it produces terrible maps in its current state. The sizes of rooms and corridors are completely random (within their bounding boxes), as is distribution and number of connection points per feature. More logic is required to generate playable, sensible maps, but I’m not certain of how much more yet. My plan is to identify common patterns in the many hand-drawn dungeon maps I’ve collected and generate rules from those patterns. I do miss some of the benefits of BSP – filling the entire map space is guaranteed, creating corridors between sibling nodes is simple and clean, and using different themes for different sections of the dungeon was easy.
Next week, I’ll continue to focus on the new dungeon layout generator. My plan for a playable demo by the end of 2022 is still possible (I’m not replacing the entire map generator, just the first step that places rooms and corridors), but less likely with the increased scope.
As with the previous week, I have some real life issues impacting my availability. It doesn’t take long for the codebase to begin feeling unfamiliar after a stretch of not working with it. The issue has been exacerbated by spending most of the time I’ve had outside of the code editor, studying hand-drawn dungeon maps. Maps in Legend are currently a random, incohesive collection of rooms. This is common in roguelikes, but one of my main goals for the game is maps that look and play like they were created by a person. It’s an ambitious goal, but one that is very important to me, so important that it needs to be in the initial release. Last week I designed a solution for matching structural patterns in the map to content. This week I designed a new solution for arranging map areas such as rooms and corridors. This solution will replace the current BSP-based map area generator. Next week, I will implement the new map area generator.
I was short on time this week due to a family health issue.
Acquired gold and kill tracking. The amount of gold the player acquires and the number of enemies the player kills is now tracked. These stats are displayed when the run ends.
Tester player class. It’s been a few weeks since I’ve run the automated tests. When I ran them this week, every one of them failed. Yikes! Most of the tests failed because of the recent changes I made to the starting classes, specifically removing items and abilities that the classes shouldn’t have at the start of the game. The automated tests assumed these items and abilities were available. I added a new player class (Tester) that has all abilities, and made that the class used by the automated tests. For obvious reasons, the Tester won’t be available to the player.
Bug fixes. Resuming automated testing exposed some issues. Fortunately, none of the issues were caused by code defects; they were caused by objects that weren’t properly configured after the Stat Modifier enhancements implemented a few weeks ago.
Contextual map generation brainstorming. I put a lot of thought into how to arrange map rooms and elements in a more logical fashion. I already have many pages of notes on this topic. I’ve worked through a variety of concepts including procedural history generation, rules for the types of rooms that can be placed next to each other, tying stories to structure, and story hierarchies that span the entire dungeon. A concrete implementation is slowly being pieced together. It’s been helpful to list examples of dungeon levels that the generation would ideally be able to produce, such as a level divided into two sections occupied by opposing factions.
Next week, an initial, though likely rudimentary, contextual map generation implementation is the main goal. I can’t spend much more time on this if I want to complete the demo release by year-end. I also need to complete combat / progression balancing, which is a dependency for finalizing actor and item stats.
Play-testing at the beginning of the week produced a long list of improvements and bugs to work through. There is no better method for prioritizing work than playing your game (or better yet having others play it too).
Finalized the Death Screen. Consisting of a text message and “Try Again” button, the death screen is basic, but will suffice for the demo release. It looks simple but took some effort to hide and disable things – stat meters, status icons, enemy health bars, hotbar, player input.
Finalized the Won Game Screen.
Separated actions that entities can perform and actions that can be performed on entities. A few times throughout Legend’s development I’ve unintentionally used an object for multiple purposes. This was the case with the entity ActionTypes collection. Originally this object was used to store the types of actions that can be performed on an entity, e.g. the Drink action for a Fountain, the Open action for a Door. Later, I started using it to also store the actions that an Actor could perform. I’m not sure what I was thinking at the time, but I clearly wasn’t thinking enough, especially considering how simple the solution was – two separate collections.
New Map Elements
Portal. The Portal appears on the last level. When players step into the portal, they exit the dungeon and win the game.
Debris Pile. This replaces the Grass Map Element, which didn’t fit into the dungeon setting. The Debris Pile blocks movement and sight and is destroyed in one hit.
Turns remaining added to status effect tooltip.
Magic bar is hidden for player classes that don’t use magic.
When an actor is healed, the floating text showing the number of HP is now green instead of red.
The Inspect Panel doesn’t work. Recent changes broke it.
Torch light doesn’t appear when the game starts. When I removed all the starting items from all player classes (many of which were added for testing purposes) and re-added them, I forgot to give each class a torch.
Torch light doesn’t disappear when a torch is unequipped. I discovered that the torch game object was being added to the player twice. The torch was being added twice because two different events added torches. Two different events exist because one event is triggered by equipping a torch (needed on level 1, when starting items are automatically equipped) and the other is triggered by setting the quick switch slot (needed on level 2 and after because the torch light has to be re-instantiated and the equip event will not fire because the torch is already equipped). I modified the second event to check for the existence of a torch light game object before instantiating a new one.
Inspecting cells with multiple entities of the same type doesn’t work.
Finite status effects have one extra turn. I had no idea this was happening; adding the turns remaining to status effect tooltips exposed this.
Flames show damage floating text when they burn out.
Player is able to open doors that aren’t adjacent.
Next week will look similar to this week. AI isn’t being properly saved/restored across levels or saved games. This will be a pain to fix but is necessary. There’s some interesting map generation work to do too, though I’ll need to be careful to avoid getting carried away with it.
Between unexpected issues at work and a lot of thinking and spreadsheeting rather than coding, it didn’t feel like I got much done this week. My brain is getting fried working out how various numbers will change over the course of a run – HP, damage, damage reduction, stat ratios between no/light/medium/heavy armor, net stats from different equipment combinations (this has especially been a headache; I’m tempted to have a single equipment slot for armor rather than body/head/hands/feet), early vs. late game ratios (to control difficulty), etc. It’s been challenging figuring out where to start because there are so many relationships between stats. My starting point is determining what should be the typical number of hits to kill the player according to their armor category and working backwards from these numbers to determine the stat values. It’s also been helpful to write out different combat scenarios like “how many hits should it take a bandit with a short sword to kill a player wearing light armor.” The model is coming together, but there are still many numbers to plug in. After the model is finished, I’ll create a simple simulator to efficiently test it, and do play testing.
Aside from all the fun with spreadsheets, I completed a couple of items on the 2022 goal list: finalizing the Select Class Screen and Passive Abilities.
Updated Select Class Screen. Locked classes are now shown as a silhouette of the sprite, with a lock icon (I’d prefer a padlock but grabbed the closest thing I had, which was from the Oryx sprites). Class attributes are now shown in a grid view with the attribute names.
Passive Abilities. Passive Abilities were previously 25% completed. They could be assigned to classes in the designer, but didn’t appear on the Abilities Panel, didn’t have sprites, and didn’t have any effect in the game. These items have now been implemented. Passive Abilities are currently only used to dictate the weapons and armor that a class can use. Passive Abilities that provide other types of benefits will be added in the future.
Finalized the starting classes. Three classes will be unlocked when the game is installed: Knight, Ranger, and Wizard. Just this week I replaced the Rogue with the Ranger. I wanted the starting classes to be the most straightforward classes to play, representing the core combat styles of melee, ranged, and magic. Additionally, the Rogue’s abilities, and map features to use those abilities, won’t be ready by year-end.
Common Ability Group. I decided that all classes should have the Run ability. I added a new ability group called “Common” to contain abilities that are available to all classes. I don’t have any other abilities in mind currently that fit into this category, but I expect there will be some in the future.
Q4 plan. I set goals for the remaining weeks of the year. I don’t usually get this granular with planning, but it is necessary to keep me on track and reach my goal of a playable version by the end of 2022. I’ve set goals by month as well, which are:
October: remaining functionality
November: remaining content
December. testing and polish
Next week, I must finish the initial progression/balancing model. I also plan to finalize the item, ability, and enemy list for the demo release. I’ll also review all of the systems and identify the major improvements/fixes that are needed for the demo release.
Kill Touch and Charm Animals. Kill Touch instantly kills an adjacent target. I need to put some limits on this, such as resistance for stronger enemies. Charm Animals charms all animals in a 5×5 square
Warding Glyph. Places a glyph on the ground, visible only to the caster, that harms the first actor to walk on it.
Destroy Undead. Destroys all undead enemies in a 5×5 square.
Cure. Cures poison.
New Item: Poison Arrow. Poison Arrows inflict poison on their target.
New Map Element: Poisoned Fountain. The water in this fountain is poisoned, giving it a green hue. Drinking from the fountain causes a Poisoned status effect. The fountain will have additional future uses (when the functionality is built): pouring a Cure Poison potion into the fountain purifies the fountain, an empty vial can be dipped into the fountain to create a Poison Potion, and a weapon can be dipped into the fountain to give it a temporary Poison effect.
New sound effects. Cauldron bubbling, fountain trickling, egg cracking and hatching
Particle effect for conjuration. It’s a slightly modified version of one of the particle effects from the Pixel Arsenal particle effects package.
Enemies can open doors. Gone are the days in which the player could flee from enemies simply by passing through a doorway. Enemies can now open doors to continue their pursuit. Whether a particular enemy can open a door is governed by the actions it can perform. Some enemies, such as giant rats, are too unintelligent and/or physically incapable of opening doors.
Combat balancing. Several hours went into fine-tuning the damage formula and damage progression in a spreadsheet. My naive original damage formula was [Damage caused by the attacker] – [Damage reduced by the defender]. I liked the simplicity and intuitiveness of this calculation but it didn’t work in practice. I did a bit of research on damage formulas used in RPG’s (in hindsight, something I should have done before any spreadsheet work or coding, because designers have already figured this stuff out) and found some alternative formulas. A common formula is [Damage] = [Attack] * C / ([Defense] + C), where Attack is the damage caused by an attack before applying damage reduction, Defense is a C is a Constant, usually 100, and Damage is the resulting damage after damage is applied.
Assumptions and constraints:
Max HP never changes.
Max HP only slightly varies between different classes.
Each class fits into one of the following armor categories: none, light, medium, heavy.
Each armor category has a target number of hits before dying (none:2, light:3, medium:7, heavy: 12). The damage formula and item stats are all designed around these numbers.
Tooltips for stats. Tooltips are now displayed when hovering over player stats.
New automated tests. Cell area utilities.
Fixed AI bugs.
Actors don’t track the player’s last seen location in some scenarios
Actors sometimes choose to respond to the wrong observation because observation weighting isn’t taking player regard (friendly or hostile) into consideration
Player allies sometimes follow the player instead of attacking enemies of the player
Fixed other bugs.
Inanimate objects, such as stairs, barrels, and doors, are subject to charming. It doesn’t make sense for entities without brains (and some with brains) to be charmed, so they’re now excluded. That said, this bug may inspire a future spell where inanimate objects are brought to life.
The Run ability allows the player to run past an enemy.
Changing levels and saving/loading working again. The reinstantiation of a previously visited level breaks more often than any other functionality in the game. So many changes break it. Most recently, adding theme-specific sprites for certain objects caused it to fail.
With the last quarter of 2022 starting this weekend, I’m putting together a plan to get the first playable version done by year-end. Next week’s goals will be determined by that plan.