# Logging

Up to now I’ve been using spdlog for logging. I had decided that I would have a logger per system, plus a general logger for core library code, plus a general logger for game library code, plus a logger for json loading. Each logger from spdlog supports multiple sinks (outputs). One can quickly imagine that things get convoluted/complicated.

I like the idea of log “channels” (ie categories). That was the reason for the existence of loggers per system, etc. I realized that my approach was bloated.

I decided to ditch spdlog for a simple approach, that only uses fmtlib:

• We have log levels as usual: trace, debug, info, warn, error, fatal, off
• There are 2 outputs: file and gui. Both are configurable
• File output is parameterized on filename and most verbose log level
• Gui output is parameterized on history size (max line num) and default log level
• File output stores all logs, gui output shows only the selected channels (one or many), which helps wading through the logs
• Start with a fixed channel list (frequently used), but allow extensions. E.g. core library channels:
• app: application init/update related logs
• gfx: graphics subsystem
• gui: gui subsystem
• core: everything else
• Allow runtime channel creation & use

Here’s an example view of the gui console log, using imgui as usual:

# Time for Action: Time and Action Management + Fast-Forward

Handling time is coupled with handling actions: The whole point of time management is handling the order of actions. I’ve done some … pre-work in the past here, so many of the concepts still apply. So:

### Actions and commands

• A EntityCommand is the basic “unit” of actions: it’s an instruction for an entity to do something, e.g. “move left in a dungeon”, “teleport there”, “Do damage to X entity”, “move north in overworld”
• Commands happen instantly, they do not know anything about time/duration.
• Implementation-wise, commands are stateless functors, that take a bunch of parameters and do some work. In the future, the implementation could be moved into Lua to avoid recompiles and have dynamically editable behavior
• Commands have two functions: Execute() and OnInterrupt(). If a command that is scheduled to play gets interrupted, we call OnInterrupt instead.
• An EntityActionConfig stores a handle to a command plus timing and interrupt information: execution/recovery durations and interrupt strength/difficulty class
• An action happens like this:
• Wait for execution duration (during this stage, the action can be interrupted)
• Execute EntityCommand immediately
• Wait for recovery duration
• An action can interrupt another action if the interruption strength is greater than the interruption difficulty class. In this case, the execution stage of the target is cancelled and replaced with an “interrupt recovery” duration, which at the moment is half the execution duration, starting from the time of interruption.
• EntityActionConfigs are set up in json, and are constant throughout the application.
• An EntityActionData structure stores a handle to an EntityActionConfig plus parameters for the command to be executed.

### Time system

At this point, we move onto the TimeSystem, which handles execution of actions. The TimeSystem stores a set of actions, ordered by execution time. The set data contains:

• The entity whose turn it is
• The time that the entity plays
• The stage of the entity’s action (just started, execution, recovery, interrupt recovery)
• An EntityActionData structure, storing what needs to be done with what parameters
• A reference to the previous entry in the set, of the same entity (e.g. a “recovery” entry would store the “execute” entry)

When an AI entity plays its turn, there are two different things that can happen:

• We don’t have an action scheduled yet, so we run AI to figure out what to do next. The AI system is responsible for filling out the EntityActionData structure (what action to execute, and which parameters). A player character, using GUI/keys would cause this structure to be filled in the same way. When we fill in the data, we schedule the execution stage which will happen after the “execute duration” if it’s not interrupted
• We have an action scheduled, so we just execute the command and scheduled the next turn to be after the “recovery duration”. If the command fails (e.g. try to hit an entity that is now not there) we should not pay the normal recovery duration. At the moment the cost is half the recovery duration, but maybe for a failed command the cost should be zero. This is still work in progress and needs real examples (e.g. player tries to move to a wall, etc)

### Fast-Forward

Fast-forward refers to coarse simulation that happens for entities that are in a different level to the player (or whatever we deem as “active” level). Fast forward will not be used for overworld entities, as the time intervals in the overworld are much larger compared to dungeons, so we won’t have performance issues simulating 1000 entities where one action takes 1 day, whereas in a dungeon a move could be several seconds.

After a lot of thought and a few test implementations, I’ve decided to keep a single list in the time system for all the game’s entities that are active. A reasonable question is “what happens to creatures in a level when a player leaves the level”? We clearly can’t afford to be simulating all levels generated ever. On the other hand, it’s not nice to just “freeze” or “reset” the level (could be fine for other games). At this point, I’ve thought (and designed the code to be supportive of) the following process: When an AI entity plays its turn and it is on an inactive level (but not the overworld), it will plan a “fast forward” action. Such actions are coarse simulation like “wander around the level”, “go pick up a fight”, “sleep”, “sentry”: these actions would take hours each. So, all the entities would always play, but the frequency of play would be drastically lower for entities in overworld or inactive dungeon levels. Maybe we can have even coarser level simulations that each lasts days or months, using the same principles.

What’s important is what happens when a level with fast-forward action-taking entities gets activated. In this case, we interrupt the entities actions and execute the OnInterrupt() command, which could place the entity randomly, run the same simulation but with a different duration (e.g. a “normal day cycle” action for 3 months that gets interrupted 1 month in, gets executed for 1 month).

Several aspects of the fast-forward system will be tested pretty soon, as the simulation will happen in the overworld and the NPC AI will be delving in dungeons. As they will enter the dungeons, the active level will be the overworld and the NPCs will be in inactive levels, therefore playing fast-forward actions like “Clear dungeon level”, “Delve to next level” and “Flee dungeon”.

### Next steps

Next time will be AI revamp in addition to spawning of world events and implementing/writing some EntityCommands and EntityActionConfigs.

# Towards NPC simulation

So, now that simulations now run acceptably, we need to move on from simulations to (well, simulated) reality. There’s a still big list of todos:

• Implement turn system (I have an older implementation, so it’s not completely from scratch, maybe)
• World occasionally generates adventure locations (dungeons)
• Basic city-related AI
• City occasionally spawns quests (think town hall bulletin, paid work)
• Factions occasionally spawn quests (guild advancement)
• Inns occasionally spawn rumours (quests with great rewards that might or might not be true – still thinking about this)
• Basic NPC AI
• Actions in a city…
• [?] Rest/heal. But maybe that will be automatic
• Check city/faction/inn quests.
• Meet up people at an inn and form parties
• Actions in a dungeon…
• Progress with an encounter
• Flee
• Actions in the wilderness…
• Move towards destination (be it a city, a dungeon or an NPC/party)
• (hmm maybe I need to consider party vs party fight simulation)
• Actions anywhere…
• Set destination (dungeon, city, party, etc)
• Decision making
• Estimate quest difficulty (expected survival. Also try to see what skills are required and compare to own skills)
• Estimate quest importance (based on personality and goals. Rogues like gold, Paladins like righteous stuff, etc)
• Estimate if enough rations for a quest can be purchased
• Ability to track particular NPCs/parties (in terms of location in world map and logging)

The turn/time system will be the first in the list, as actions and AI all utilize the concept of time

# NPC Party Dungeon Delving and Wilderness Encounter Simulation

As a reasonable follow-up to single NPC dungeon delving simulation, now we test parties of adventurers.

### Strength in Unity, Complementary

Parties are stronger than individual NPC, but without being overpowered. The increase in power is not linear: 5 heroes working together are not 5x more effective than a single hero, but general survival rate is greatly improved. So, here are a few similarities/differences between a single NPC and a party, with regards to mechanics in the coarse simulation layer that I’m currently developing:

• Healing is applied to all members equally
• Damage is reduced based on the number (N) of party members by: $\frac{N-1}{2N}$
• N=1: 0%, N=2: 25%, N=3: 33%, etc.
• XP are divided among party members
• For skill checks: use the max value among members
• For skill category checks: for each member calculate the average of the category’s skills, and use the max among members

With these in mind, it’s clear that it’s beneficial to have parties with complementary skills.

### Single-Delve Tests Revisited

Here are a few examples that show survival rate in a few party size configurations (1,2,6) when we put a party (of any level) against a dungeon of a similar level.

Here are a few examples that show survival rate when we put a lvl 1 party against a series of dungeons of a similar level to the party (dungeons progressively get stronger as party levels up). CR mod is difference of character level to dungeon level, so a crmod of -5 means a level 25 party will tackle a level 20 dungeon.

### Wilderness Encounters

Adventurers start their adventures typically at cities. They travel, and travel, following well-established routes as much as possible and crossing through other cities, until finally they enter full-on wilderness to get to a dungeon to clear. So, with some quick and not-too-inaccurate math we can figure out that if $X$ is the total distance to the dungeon and $Y$ is the average city-to-city distance, then the distance off roads will be $\text{min}(Y/2,X)$. The split to off-road and on-route is important, as threat on route is significantly smaller.

The tests assume a +-20% in challenge rating compare to the character level, and they utilize the dungeon delving simulation code from the previous post, but with 1-3 encounters only.

These examples show the benefits of being in a party, and they also demonstrate that survival chances drop with larger distances (but the drop decays sharply), and they also drop with higher character levels, as more dangerous encounters get spawned.

### Side-effect plot viewer

The generated graphs use several parameter sets, e.g. party size, retreat threshold, etc. It becomes difficult to navigate through the graphs when you want to flip between two arbitrary parameter values. So, instead of researching it further, I wrote a dead simple script that allows “interactive” graph rendering in the cheatiest way: it parses special parameter-encoding filenames, e.g. “wildernesssurvival_retreat2_party5.png”, and listens to keypresses. When e.g. ‘r’ is pressed, I load the file ‘wildernesssurvival_retreat3_party5.png’, while now if ‘p’ is pressed, I load ‘wildernesssurvival_retreat3_party6.png’. This is actually a lifesaver! And works with all graphs. Here’s the code in all its glory:

import glob
import sys
import os
import numpy as np
import matplotlib.pyplot as plt
import matplotlib.image as mpimg

def run(img_format, params):

param_ranges = [] # for each param, a list of values
param_cur_indices = []
ax = None
fig = None

def press(event):
sys.stdout.flush()
for k in range(len(params)):
if event.key.lower() == params[k]:
off = 1 if event.key == params[k] else len(param_ranges[k])-1
param_cur_indices[k] = (param_cur_indices[k]+off) % len(param_ranges[k])
param_cur_values = [ param_ranges[i][param_cur_indices[i]] for i in range(len(params))]
ax.imshow(img)
fig.canvas.draw()

all_files = glob.glob(img_format.replace("{}","*"))
img_format_const_parts = img_format.split('{}')
for i in range(len(params)):
"""
To extract number for i-th param, locate the end of the string before and the start of the string after
"""
values = []
for j in range(len(all_files)):
fname = all_files[j].replace('\\','/')
idx_start = fname.find(img_format_const_parts[i]) + len(img_format_const_parts[i])
idx_end = fname.find(img_format_const_parts[i+1])
values.append( int(fname[idx_start:idx_end]))
values = sorted(list(set(values)))
param_ranges.append(values)

param_cur_indices = [0] * len(params)
param_cur_values = [ param_ranges[i][param_cur_indices[i]] for i in range(len(params))]

plt.close('all')
plt.ioff()

fig, ax = plt.subplots()
plt.axis('off')
fig.canvas.mpl_connect('key_press_event', press)
ax.imshow(img)
plt.show(block=True)

if __name__ == '__main__':
#params = ['c','e','r']

#params = ['c','e','r','p']

img_format = 'C:/Users/Babis/Documents/repos/aot/build/apps/aot_v0/wildernesssurvival_retreat{}_party{}.png'
params = ['r','p']
run(img_format, params)

# Single NPC Dungeon Delving Simulation

Previous week was simulation of level progression of NPC adventurers. The logical continuation is to pit such generated characters against dungeons, and run simulations for the outcome.

### Dungeons: A Series of Challenges

The Tomb Of Horrors.

The Haunted Graveyard.

The Forgotten Crypt.

The Lair of the Werewolf King.

All these are locations where adventures take place, and typically adventurers slay lots of monsters and acquire treasure and artifacts. Since we’re still at a high level of abstraction, instead of creating dungeons and placing monsters, we can simulate the outcome in a simpler way, as a series of challenges:

Adventurer walks in, faces a skill test (e.g. how good is the two-handed skill) or a skill category test (e.g. how good are the combat skills on average), takes damage based on the test result (which is a scalar rather than a bool) and heals a bit. If the test passes, adventurer gains XP and proceeds to next challenge.

A dungeon is configured for a such coarse simulations as follows:

• Number of challenges: How many challenges should adventurers succeed in to complete the dungeon.
• Challenge rating:  The difficulty of the dungeon, in terms of character level.
• Skill Challenge Pool: The skills that can be tested against, if the challenge is skill-based.
• Skill Category Challenge Pool: The skill categories that can be tested against, if the challenge is category-based.
• Skill Challenge Chance: The chance of encountering a skill-based challenge rather than a category-based one.

The two challenge pools (skill and skill category) contain subsets of skills/categories, each with a specified DC (difficulty class) modifier as compared to the average for the CR (challenge rating) of the dungeon.  So for example a dungeon could have particularly hard lockpicking tests, or very easy combat.

Adventurers can have their personal “retreat threshold” (aka bravery), so some will flee if their health is below 20%, others when it’s below 5%, others never.

The simulation goes as follows in pseudocode:

for each encounter:
calculate challenge rating # progressively harder
calculate test mastery level base

test_type = weighted select skill or category
if test_type == category:
sample category # from the list of categories that we can test for this dungeon
run skill check against adventurer's average skill level
calculate success and apply damage
elif test_type == skill:
sample skill # from the list of skills that we can test for this dungeon
run skill check against adventurer's skill level
calculate success and apply damage

return status::Death
else:
if success:
else:
flag encounter for retry

return status::Retreat

return status::Success

For simulation purposes, mana acts as a “mana shield”; when mana is available it can be utilized to block off damage at half effectiveness, e.g. at 100 damage, 48 mana left => 24 damage absorbed, mana goes to zero, adventurer takes 76 damage.

I developed two tests to see the simulation in action, single-delve and lifetime-delve

### Single-delve tests

These tests take single adventurers and put them against a single dungeon. Run enough tests at all potential character levels, and we can get an idea of survivability rates at different levels. All characters are generated using the level-up strategies from the previous post.  Below are a few graphs that show the success/retreat/death per adventurer level by varying the general cautiousness of adventurers (CR mod), the number of challenges of the dungeon and their retreat threshold.

Here is a GIF with all graphs, to avoid flooding the page, as there are many many combinations (first retreat value varies, then challenges, then CR mod):

These tests take single adventurers, starting from level 1 and put them continuously against dungeons until they die or reach level 30. The adventurers pick a dungeon level compared to their level, using a CR modifier (-5 is easier dungeons, up to 0, as above is suicide given the previous graphs). Here is a GIF again with all graphs, much less data this time, so easier to follow: ( retreat varies first, then challenges)

### Next time, party time

Clearly the survivability rates are not great, especially at higher levels. So, as it is natural, parties can and will form, as there is strength in unity. The party simulation will not be too complicated, and should give a reasonable boost to survivability esp. at higher levels.

Finally there’s another wild idea. These simulation results can be exported to JSON, so that when AI has to make choices about which dungeons to tackle, it will use the graph results. The more the AI knows about a dungeon (CR, encounter num, etc), the more accurate the survivability percentage it will be, utilizing rumors, dungeon lore skills, etc. So, it can make a more informed decision.

Another fun idea is to try to use something like tracery (or a home-brewed adaptation) to generate “adventure stories”.

After writing down the extensive catalog of attributes and skills, it’s only natural that we have to create several characters to test things out. Characters (adventurers in this case) can be grouped in terms of their general capabilities and function; in many RPG games this would be a character class. In Age of Transcendence, there are no character classes; NPCs and players develop their skills as they see fit. In this model, “classes” are just suggestions on how a character may develop. Below, I call the classes “archetypes” and the development suggestions “level up strategies”.

An archetype is a configuration to build an infinite set of similar (in some aspects) adventurers. The parameters at the moment are:

• Race list
• Age range
• Alignment list
• Starting level range
• Level-up strategy list

When creating a character from an archetype, we choose a race from the race list, sample an age from the range, sample alignment from the list, sample a level from the range and choose a level up strategy. The interesting and complicated bit is the level-up strategy.

Level-Up Strategy

The level-up strategy is the configuration that the game logic uses to develop characters differently through the levels. For example, a level-up strategy for a fighter would focus on mostly improving strength, and focusing on skills such as body-building, heavy armor and weapon masteries, while one for a thief would focus on agility, daggers and/or bows and stealth skills.

The approach that I’m using is a mix of coarse and fine granularity weights, and it consists of:

• Attribute improvement weights: a weight value per attribute, so that when we want to allocate attribute points, we do weighted sampling.
• Well-rounded-ness: This is a scalar specifying how balanced a character will be. A balanced character will improve many attributes and skills, while an unbalanced will be more of a savant type, focusing heavily on a few skills, ignoring most others.
• Skill focus: A list of tuples (skill name, target mastery level, allow surpassing target mastery level).
• Skill category weights: A list of weights, one per skill category.

When we level up, we first allocate the unspent attribute points based on their respective weights.

Immediately after, we allocate a percentage of the unallocated skill points (based on wellroundedness: savants use more) to improve skills in the focus list, until we reach a target mastery level. When we reach the mastery level, we either never touch the skill again, or if we allow surpassing the target mastery level, we still consider it for advancement as explained below.

After we allocate focus skills, we have a remainder of skill points. These will be allocated to the rest of the skills, excluding the focus skills that have reached the target mastery and can’t improve. The weight for each of these remainder skills is the product of a) the skill’s category weight, b) the number of skills in the category and c) the distance of the skill’s value to the required skill value of the maximum mastery we can achieve with the current attributes. (note: (b) looks odd but it’s useful, as if we say that Offence (with about 10 skills) is as important as Adventuring (3 skills), it’s 3 times more likely that a skill in Adventuring gets a point)

There’s an extra important consideration. Some skills form subcategories, such as all “Weapon style”skills forming the “Weapon Style” subcategory, all “Melee weapon mastery” ones, etc. In these cases it’s more typical that a character develops one or two more than others, rather than equally developing the whole selection. For this reason, I

Finally, well-roundedness is used every time we do weighted sampling by replacing the weights with “w = pow(w,2-well_roundedness)”. It’s also used for the skill subcategories in the same way.

Below are some example level-up progression results using matplotlib. Title shows some info (Yes, some is bonkers, like neutral paladins). Y axis is the skill value, with grid lines at mastery levels (30 is Master, 50 is Grandmaster). X axis shows attributes (first 5) and skills. Darker colors show values at earlier levels, while lighter colors show values at later levels, as explained in the legend. The images are large, so you might need to open them in a separate window, or zoom.

Still here? Well, there are videos of these progressions too 🙂

Here still? Here’s my spreadsheet with the draft level-up strategy configuration. Well-roundedness seems to have an inverse effect, so I’d say that the graphs were helpful in noticing that 🙂

 Archetype Name FighterX FighterS Fighter Thief Mage Bard Ranger Paladin STR 4 4 4 1 1 1 2 3 AGI 2.5 2.5 2.5 3 1.5 2 3 1 INT 1 1 1 2 4 2 2 1 PER 1.5 1.5 1.5 3 2.5 2 2 2 CHA 1 1 1 1 1 3 1 3 [total] 10 10 10 10 10 10 10 10 Body/Mind 5 5 5 5 5 5 5 5 Offense 6 6 6 3 1 2 3 5 Defense 6 6 6 2 3 2 3 5 Stealth 0 0 0 5 0 2 3 0 Lore 2 2 2 2 5 5 3 1 Perception 1 1 1 4 1 2 3 3 Crafts 2 2 2 0 3 0 1 1 Magic 0 0 0 0 5 1 0 2 Social 1 1 1 2 1 5 1 2 Adventure 2 2 2 2 1 1 3 1 [total] 25 25 25 25 25 25 25 25 Well rounded 0 1 0.5 0.5 0.5 0.5 0.5 0.5 Athletics Expert+ Expert+ Expert+ Fortitude Expert+ Expert+ Expert+ Adept+ Reflexes Expert+ Adept+ Willpower Expert+ Concentration Expert+ Body building Expert+ Expert+ Expert+ Adept+ Meditation Novice Novice Novice Expert+ Weapon style [two-handed] Grandmaster Master Master Weapon style [one-handed] Grandmaster Weapon style [dual-wielding Expert+ Weapon style [ranged] Master Melee weapon mastery [blunt] Melee weapon mastery [slashing] Master Melee weapon mastery [daggers] Master Melee weapon mastery [polearms] Expert+ Ranged weapon mastery [bows/crossbows] Master Ranged weapon mastery [slings/blowpipes] Ranged weapon mastery [thrown] Armor [light] Master Expert Armor Armor [heavy] Master Master Master Master Shield mastery Master Sleight of hand Expert+ Hide Master Lockpicking Grandmaster Move silently Master Item lore Expert+ Creature lore Expert+ Expert History and legends Expert+ Adept Dungeon lore Expert+ Adept Arcane lore Expert+ Literacy Expert+ Adept Detect traps Expert Spot Expert Listen Expert Sixth sense Disarm traps Expert Repair Cooking Make weapons Make armor Make accessories and utility Enchant item Expert+ Alchemy Expert+ Wand mastery Expert+ Staff mastery Expert+ Magic school mastery [command] Magic school mastery [alteration] Magic school mastery [divination] Magic school mastery [creation] Magic school mastery [destruction] Master Leadership Expert Master Persuasion Master Master Haggling Renown Master Perform Grandmaster Scouting Master Survival Grandmaster Luck

(Formatting (bold, colors) is not copied over unfortunately, I’ll update this if I find out how)

# Attributes, skills and masteries

My intention for this first draft of attributes and skills is to use a mix of systems that I like: Dungeons and Dragons, Might & Magic and Elder Scrolls. Needless to say, this is a draft and several things will change.

The system is classless: characters are free to develop as they like, mixing and matching from a large pool of skills, where standard archetypes (fighter/wizard/rogue) are implemented as strategies for attribute and skill allocation.

### Attributes

Attributes define the potential of a character for performing/using skills. They change infrequently, so they act as a skeleton for builds. They affect skills by providing bonuses (or penalties) and restricting skill mastery. I’m going with the typical DnD attributes except constitution.

• STRENGTH: Physical power and resilience. Affects hitpoints.
• AGILITY: Motor skills.
• INTELLIGENCE: Intellect, reasoning. Affects spellcasting.
• PERCEPTION: Intuition, awareness, insight.
• CHARISMA: Influence on others

For starters, I’ll use the DnD scale where a value of 10 is average. Similarly, characters gain a point every 3 levels.

### Skills

Skills are areas of expertise and training. They are split into multiple categories: Body and mind, offense, defense, stealth, lore, perception, crafts, magic, social and adventure. The categories are just a way of grouping related skills, so that players do not see a massive flat list of skills.

Skills can be used in a variety of scenarios, when a character is attempting certain actions (swim in the river/climb mountains: use Athletics. Attack with a greatsword: use “two handed style”. Talk to a guild member, use “persuasion” or “renown”. etc).

Skills start at 0 can be trained up to 50. Characters will earn 5 skill points each level to distribute. A skill value cannot be higher than 2x character level. So, a skill can be maxed at lvl 25. For reference, the soft cap for character level would be around 30, reached at about 20h of playtime.

Skills have optional associated major and minor attributes (in the below table, in column 3, if only one initial appears, it’s a major attribute). Major and minor attribute affect skill advancement as explained in the masteries section below.

Again, the above is still work in progress and several things are prone to change. What’s missing at the moment are active abilities, but that’s for another time and out of the scope of this post.

### Skill mastery levels

For each skill, there are several mastery levels / tiers. Everybody starts at the Novice level. When the character has allocated a certain number of points to a skill and fulfills certain attribute requirements (see Major/Minor attributes in previous section and column 3 in previous table), the character is eligible for advancing the mastery level, typically using a guild/trainer (for grandmaster level and maybe more, quests would be involved, as in Might and Magic games). Advancing a mastery level will give fixed bonuses and affect interactions with the character in the game world, unlocking quests, affecting relations, etc. For requirement purposes, the game will use natural values, not counting effects from spells/items/etc.

 Skill mastery level names Skill Req Maj Attr Req Min Attr Req Novice 0 0 0 Apprentice 1 4 2 Adept 5 8 5 Expert 15 12 8 Master 30 16 11 Grandmaster 50 20 14

If a character does not fulfill the attribute requirements for a skill, they cannot allocate points any further. For example, a fighter character with STR=17, DEX=13 and INT=10 can achieve:

• Master in Heavy Armor ( STR > 16)
• Master in Shield ( STR > 16, DEX > 11)
• Expert in Make Weapons ( STR > 12, INT > 8)

### HP/MP

The game will use standard cRPG values for life and spellcasting.

Max hitpoints for a level can be calculated from level, Strength attribute and Body building skill. Max spell points are similarly calculated from level, Intelligence attribute and Meditation skill. The formula draft at the moment (which will change with 99.9% certainty) is:

Level x ((Attribute-10) x 1.5 + Skill x 0.5 + 10)

### Testing things out

At the moment I have a character generator based on predefined archetypes (fighter/wizard/mage/etc), so the next step is to design “challenges” for characters, their cost in terms of HP/MP and their value in terms of experience.

# Overworld adventuring: Parties, quests, locations, levels, stats and skills

So, at the moment the serialization works and the game starts in debug in a few seconds, loading lots of stuff from disk. Territories, routes, cities, etc are all pre-created and serialized in. What’s next? The overworld-level play, in the beginning played at a coarse-simulation level by NPCs. This should be fun. So, it goes as follows:

• Generate every so often adventure locations (uncovered tombs, unearthed creatures in mines, dungeons, bandit camps, you name it)
• Cities and guilds occasionally give quests
• Heroes can accept quests and travel to locations, and succeed or die trying.
• Overworld travel applies some coarse simulation based on level, skills, biome, chances of ambush, etc
• Dungeon clearing applies some coarse simulation based on level, skills and dungeon traits
• Heroes can join other heroes and form parties
• I can watch them play and die, eating popcorn
• Filter the logs to track individual heroes and parties

What becomes apparent from the above is the need for everything in the title: parties, quests, adventure locations, levels, stats and skills. This is fun stuff, and very very prone to change, but we need to start from somewhere. For quests and adventure locations I have a few books full of good ideas (Tome of Adventure Design, Ultimate Toolbox, Sly Flourish’s Fantastic Locations), so they will be utilized. For stats and skills, I like DnD but I also like some cRPG systems, like Might and Magic series (especially the skill mastery levels and how you need to find trainers to advance a tier). Further posts will target and expand on these subjects

# Cerealization

This is a good point for actually using a first form of save state, as the initialization is now computationally intensive. So far, the following things take place:

• Load configuration files to create/initialize systems
• Load/initialize resources: textures, texture atlases, shaders, renderers, framebuffers, widgets, application states, etc etc
• Create world
• Generate (or use cached) a biome map
• Generate (or use cached) autotiling data
• Generate (or use cached) a resource map
• Generate cities, territory map, factions, mines, relationships, etc
• Generate (or use cached) pathfinding routes

In the above, ‘or use cached’ implies an adhoc piece of code that looks for a cache file with the results of the process and uses that, or runs the calculations and dumps the results in the end. It exists only in certain parts, when the outputs are very contained, e.g. a 2D array of data.

At this point, I need to serialize the entire “Create world” process, but now the generated results are not simple anymore:

• Some new resources
• Completely new state of several systems
• State of existing resources (initialized now, not initialized before)

I’ve already prepared for that, and I’m using the library cereal for serialization. Currently the process is mostly complete, so the whole “Create world” process takes very little time, as it just serializes data from a 6MB file.

Currently I need to “standardize” serialization of GPU resources (textures, buffer objects), which is a bit trickier but doable. The way it’s getting implemented is as follows:

• JSON configuration initializes a config structure, specific to the GPU object, e.g. cTextureConfig has ( dims, target, format, iformat, dtype, miplevels, data, etc)
• The config structure is used to initialize the object
• A member function can update the config structure from the current state of the GPU resource (this is mainly for textures/buffers that have been updated)
• cereal out: update the config structure from current state, then serialize out the config structure
• cereal in: load from disk to the config structure, then call Init()
• json in: load from the json file to the config structure, then call Init()

I can also implement GPU resource cloning using this config update mechanism

# City-based pathfinding in the overworld

So, this follows straight from the last post about the change of heart regarding HPA*.  The new system is slightly different, but generally simpler. Below, I’m going to describe how it works.

### Prerequisites

The basic input of this system is a move cost map (a value per pixel) as well as the city locations. To implement this system, we need A* for graphs and grids, as well as a function to calculate a delaunay triangulation as well as a dijkstra map.

### Part 1: Connectivity

First calculate a delaunay triangulation of the cities. This looks something like the below (ignore the red edges)

From the triangulation we make a graph. For each graph edge (which is a city-to-city path), we run A*-grid at max quality settings. This calculates a nice path of least-resistance, it’s the “road” if you wish. The path results look like the first image of the post. For 250 cities, we get about 750 paths. For each of those paths, we also calculate and store the traversal cost.

### Part 2: Arbitrary point-to-city support

When we need to go from A to B, where the distance between A and B is great, we naturally want to stop at cities to restock etc. So, the final path will look like A -> city0 -> city1 -> … -> cityN -> B. This step precalculates infromation for fast calculation of A -> city0 and cityN -> B.

For each of the eight directions, we calculate a dijkstra map using a slightly customized move cost function: movement towards the direction has less cost, therefore is preferred. The targets of each dijkstra map are all the city locations.

After we calculate all dijkstra maps, we now need to calculate, for each point in the map and for each of the eight directions/maps, the direction towards the least cost. The direction needs 4 bits to store (eight directions plus 1 bit to mark if it’s a no-direction), so direction maps for 8 directions will then cost 32 bits per pixel, which is not bad.  And we won’t need the dijkstra maps any more; these direction maps can provide us with a best path to a city given a main, general direction.

This concludes the precalculations, and it will hopefully make sense in the next part.

### Part 3: Runtime pathfinding

We have points A and B. From point A, we calculate which of the 8 directions leads more towards B. We pick the dijkstra direction map computed in part 2 above and traverse it till we reach a node, also recording the path while we’re at it. We apply the same process with point B, but we use the inverse direction. So now, we have 2 nodes in the graph, and we run A*-graph to calculate the best path between them. The cost function uses the precalculated traversal costs from part 1.  So now, we have: 1) fine path from A to closest city c0 2) fine path from B to closest city cN 3) coarse path between cities c0 and cN. This is all we need to calculate a continuous path from A to B. Some examples below — Red is A -> city0, Black is cityN -> B and magenta is the concatenation of precalculated city-to-city paths. If you zoom in, white points along the path are the cities.

### Notes, failure cases and future work

On average, using a Ryzen desktop processor, at max A* quality, it takes 0.22ms per path in Release configuration, or  3.37ms in Debug. For future reference. The cached memory needed for the entire pathfinder (graphs, precalculated paths and direction maps) is about 1.5 MB.

Path coalescing. When calculating the fine paths, every time we calculate one, we can reduce the cost of traversing those tiles just by a little bit. This is akin to making a natural forest path. The first path it’s traversed, it’s wild and kinda tough to get through. Make 1000 people walk on the path, and it’s now a bit easier. Make 1000000 walk the path and it should now be very distinct compared to its surroundings.  By reducing the cost a little bit, the path network looks a bit “neater”.  Following are images of non-coalesced, slightly coalesced and heavily coalesced. More is not always better.

Embarking/disembarking at random locations. If I want to go to Hawaii, I don’t take the road to the nearest beach and drop a ship and sail. I’d go to a port. So, when calculating movecosts, we can add an additional embark/disembark costs if we’re about to make a change from a water tile to a land tile and vice-versa, unless one of the two tiles is a city. This beautifully controls the movement via the cost multiplier. Set it to infinity, and we’re just not allowed to change to water/land unless via a port. Set it very high, and embarking at any other point is only when absolutely necessary. The good part is that we can identify those points and make them simple ports in the game, as apparently they are naturally exactly that!

Redundancy on short paths. Sometimes, to go from A to B we end up with the following:

This happens as we’re forced to find city nodes, and we pick nodes based on the general direction that we’re heading. Thankfully, we can just add a simple length check like:

2|AB| < (|Ac0| + |c0c1| + |c1B|)

to identify if the coarse path is unnecessary. In those cases, we run an A*-grid to calculate the path between A and B.

Backtracking. Sometimes we get the following sort of backtracking:

If you look at the black path, it goes backwards. Sometimes I can explain it as before we embark on a long trip, we make sure to go to a nearby city to restock, even if it takes us off-route. There are of course other ways to solve it, and they are easy but still need a bit of work, so this is marked as not-important.

More nodes. If the number of graph nodes is deemed too low, and I’m not happy with the large distance between cities, we can always add more nodes. The “optimal” way (not in terms of performance, but of results) of doing it is using a simple loop:

1. Calculate the dijkstra map
2. Find largest score (point furthest away from anything)
3. Add the scoring point into the feature list
4. Go to 1, until a desired max score is reached

This step should happen before the delaunay triangulation.