Adventurer archetypes: Level-up strategies

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”.

Spawn Adventurer From Archetype

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.

Athletics Body and mind SA Climbing, swimming, etc
Fortitude S Resilience to effects on the body, e.g. poison and disease
Reflexes A Avoidance of physical effects
Willpower P Resilience to effects on the mind, e.g. charm, sleep, hypnotize. Also used for morale checks in combat.
Concentration I Resistance to being interrupted while using powers and casting spells
Body building S Hit points bonus
Meditation I Mana points bonus
Weapon style [two-handed] Offense S Effective wielding of two-handed weapons + tactics
Weapon style [one-handed] SA Effective wielding of one-handed weapons, with or without shield + tactics
Weapon style [dual-wielding AS Effective wielding of two weapons simultaneously + tactics
Weapon style [ranged] AS Effective wielding of ranged weapons + tactics
Melee weapon mastery [blunt] SA Effective use of blunt weapons: stunning, etc
Melee weapon mastery [slashing] AS Effective use of swords and axes: bleeding, etc
Melee weapon mastery [daggers] A Effective use of daggers: backstab bonuses, critical, etc
Melee weapon mastery [polearms] SA Effective use of polearm weapons
Ranged weapon mastery [bows/crossbows]
AS Effective use of bows and crossbows
Ranged weapon mastery [slings/blowpipes]
A Effective use of slings and blowpipes (stunning for slings, criticals for both, etc)
Ranged weapon mastery [thrown] SA Effective use of thrown weapons (knockback effects when using heavy items, etc)
Armor [light] Defense A Effective use of light armor: focus on mobility and stealth
Armor AS Effective use of medium armor: tradeoff between protection and mobility/stealth
Armor [heavy] S Effective use of heavy armor: focus on protection
Shield mastery SA Effective use of shields: bucklers to tower shields
Sleight of hand Stealth A Pickpocketing creatures, burglary
Hide A Hide in shadows (opposite of Spot skill)
Lockpicking A Opening locked doors, chests and any containers that are mechanically locked
Move silently A Opposite of Listen skill
Item lore Lore PI Item identification and knowledge
Creature lore PI Creature knowledge
History and legends PI Knowledge about myths, legends, history and past world events
Dungeon lore PI Knowledge about dungeons (architecture, layouts, etc)
Arcane lore PI Knowledge about arcana
Literacy I Knowledge and ability to decipher dead languages, old scripts, etc
Detect traps Awareness P Ability to detect traps
Spot P Ability to spot difficult to see creatures, items and dungeon features
Listen P
Ability to listen to moving creatures in dungeons, other dungeon sounds (e.g. water running in secret room), enemy ambush in the wilderness, etc
Sixth sense P Ability to sense danger (ambush, powerful creatures, strong traps)
Disarm traps Crafts AP Ability to disarm traps
Repair SP Ability to repair items
Cooking IP Ability to cook nourishing meals
Make weapons SI Ability to make weapons. Skill in particular weapons is needed too
Make armor SI Ability to make armor. Skill in particular armor is needed too
Make accessories and utility AI Ability to make jewelry and general utility items
Enchant item Magic I Ability to enchant items
Alchemy I Ability to effectively mix potions
Wand mastery I Effective use of wands (single hand, with shield, dual-wielding)
Staff mastery I Effective use of staves as magic spell conduits
Magic school mastery [command] I Effective use of command magic spells (charms, curses)
Magic school mastery [alteration] I Effective use of alteration magic spells (buffs, debuffs)
Magic school mastery [divination] I Effective use of divination magic spells (magic mapping, detection)
Magic school mastery [creation] I Effective use of creation magic spells (heal, summon)
Magic school mastery [destruction] I Effective use of destruction magic spells ( elemental, damage)
Leadership Social C
Ease of recruiting and maintaining followers. Also, summoning strength/effectiveness, otherwise e.g. powerful summons can turn against you. Also affects party morale in combat
Persuasion C Extract information, convince, reduce relationship penalties
Haggling C Cheaper prices for everything
Renown C Effectiveness of adventuring feats and deeds in terms of renown
Perform C Musical instruments, dancing, acting
Scouting Adventure PI
Sight radius, more info on nearby overworld entities (e.g. creature groups and locations), ambush bonuses
Survival PI Effective camping and travelling in the wilderness, ambush bonuses, finding more food
Luck
Find more things, find less curse and more blessed items, maybe occasional reroll when getting gravely injured

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.

Pathfinding in the overworld, and moving away from HPA*

HPA* – bad decision?

1.5 years ago I wrote a post about my implementation of HPA*, and I was quite happy with it. At that time, I did make some assumptions about movement in the overworld:

  • Lots of units calculate pathfinding in the overworld
  • Movement mode is by land, water or air (walking/riding, swimming/sailing or flying)
  • Each unit can support multiple movement modes, each with their own speed
  • Each unit could have traits that affect the movecosts in a subset of biomes (pirates faster over sea, dwarves faster in mountains, etc)

The way the pathfinding system currently works is based on a unique “move cost map” ID, which is generated based on any movecost modifiers and movement modes. So, for the overworld map, we could have several IDs:

  • walking, no modifiers
  • walking, faster in coastal terrain
  • flying
  • flying, faster over sea
  • walking and flying, walking faster in forest
  • swimming, walking
  • ….

Each of those needs a unique pathfinder. Problem is, HPA*:

  • Needs quite a bit of storage
  • Needs a lot of precalculations
  • Works well when many units share the same HPA* data structure

Currently, I’m a bit closer into putting units (NPC parties) on the map, and I’ve made some horrifying realization, which one might notice from the above: The unbounded potential combinations will dwarf the benefits that HPA* will offer, as I can’t guarantee that many units will share the same data structures. So, that’s my research of an optimized pathfinder out of the window. Oh well.

Updated constraints/assumptions

So, my issue now is that I can have many movecost maps and many units per movecost map (although for the latter, I don’t know how many). Also, the map is going to be at least 512×512. So, how to deal with the issue of efficient pathfinding for the overworld? Constraints and assumptions. At the moment, I make the following assumptions:

  1. Lots of NPC parties moving in the world (say N, could be thousands)
  2. At worst case, each NPC party has its own movecost ID; a function to calculate the cost of a tile that has unique parameters for each party.
  3. When NPC parties travel great distances, it is logical to assume that they stop for supplies and a good night’s sleep to every city they can find
  4. When NPC parties travel across the sea, they possibly don’t carry their own boats, so they would go to a port, and board a ship to go to another port
  5. NPC parties would generally travel well-trodden roads, rather than going through the wilderness
  • From (1) and (2) I can conclude that caching movecost maps is prohibitive, due to 512x512xN storage requirements.
  • From (3), (4) and (5) I can conclude the the paths that NPCs will typically follow, are between cities, and that actually makes perfect sense.
  • From (4) I can conclude that a path between cities is either fully on land, or fully on water

Forming a new pathfinder

So, from the above, another pathfinding system slowly springs into existence, that is centered around city-state locations. I’ll be using grid A* and graph A* implementations. The grid A* calculates fine-granularity paths (a list of 2d integer points adjacent to each other) and the graph A* calculates coarse-granularity paths (a list of indices to the graph’s points)

  • Create a delaunay triangulation using the city-state locations
  • Create a graph from the triangulation results: nodes are city locations, edges are city-to-city connections
  • For each graph edge, run the grid A*
    • If the edge connects port cities in different landmasses, use a water-only move cost map, without modifiers
    • Otherwise, use a land-only move cost map, without modifiers
    • The results are paths between each pair of connected city points

When a unit needs to go from A to B, the following calculations take place:

  • Identify the closest city to A in the general direction of B: c0
  • Identify the closest city to B in the general direction of A: c1
  • Calculate a path A -> c0, using the grid A*
  • Calculate a path c1 -> B, using the grid A*
  • Calculate a path c0 -> c1, using the graph A*

From the above, we can walk along a fine-granularity path from A to B, using a large amount of precalculation.

But wait… still no unbounded movecost map handling?

If you’ve noticed from the above, I haven’t resolved one issue: the reason I rejected HPA* was because of the unbounded number of movecost maps. But, what do I do here? I just use basic movecost maps without modifiers (a land-based one and a water-based one)! So why is this any better? Well, this actually makes more sense, as

  • Well-trodden paths are generally preferred
  • Cities are always part of a long path, as it should be. HPA picked arbitrary points on cell edges.
  • Sailing routes are handled naturally.
  • The majority of units has average movement capabilities, and that means no modifiers
  • How fast units move can still be individually calculated, and that’s not expensive.

Conclusion for now

The above now has to be implemented, and I’ve also got some other thoughts for a data structure that will allow precalculation of all potential paths A->c0 and c1->B with just a little more storage, so that pathfinding in the overworld is always reduced in a graph search with a max of about 250 points and 750 edges.

City-state relations

There are lots of city states in the world, each with their own race composition, core values, guilds, and alignment among other things. As history has taught us, nations can like or dislike each other in varying degrees. In the game, I have the following simple scale: Hatred, Dislike, Annoyed, Neutral, Accept, Like, Love.  So, how do we set up relations between city states?

  • Alignment. Chaotic good and lawful evil cities are (almost) never going to be friendly. Similarly aligned cities are more likely to have positive bonds with each other. So, alignment is used to bias a relation towards love/hate.
  • Common core values. City-states with similar core values are more likely to be friendly, and vice versa. Since each city has an array of weights per core value, we can just treat the arrays as N-dimensional vectors and calculate the euclidean norm. As the major core value dictates the government, we can give a bit of extra weight in the major core values of each pair of cities.
  • Proximity. The farther two city-states are, the more unlikely they are to have (or have had) any significant connection. So, relations are dampened based on distance. I use a simple linear scale to do that.

So, the whole process can be described as follows:

  • Generate a random relation value
  • Add a bias based on alignment and common core values
  • Scale by a user-defined parameter, to control how “emotional” the relations between city-states are.
  • Dampen based on proximity
  • Add a user-defined bias, to control the general relation “direction” towards love/hate.

So it’s quite simple and generates some nice results I think. Here’s an example, varying the user-defined parameters. The purple territory is the city-state in question, shades of green represent accept/like/love while shades of red represent annoyed, dislike, hatred. Black is indifferent/neutral.

Scale = 1, bias = 0.0

Scale = 1, bias = 0.4

Scale = 2, bias = 0.4

 

What makes a city-state

Figure 1 Above, the territory of a selected city is highlighted with red (bottom left), while all other territories have a darker shade. On the right, city-state information is displayed.

Now that territories have been defined, we need to flesh out the city-states a bit more. The city-states will act as adventuring hubs, source for quests, target of other quests, and will also have a gameplay mind of their own. So, what makes a city-state?

Races

Each city has a race composition (out of about 10 currently), defined as percentages. The racial variety will depend on the level of the city. A small village will be composed of a single race, while a buzzing metropolis could have more than 5 races.

Alignment

Cities use the DnD alignment axes ( Lawful/Neutral/Chaotic and Good/Neutral/Evil) to represent what they stand for, and their goals. A chaotic neutral character would obviously prefer a similarly aligned city, as the interests would better match.

Statistics

Cities have 4 main statistics: Population, Influence, Wealth and Military. Influence directly affects the city-state territory, and the rest are self-explanatory. They will have gameplay effects, but not quite fleshed out yet.

Resources

Cities have food and basic material reserves. These resources depend on the biome tiles within a city’s territory. Rare resources (silver, gold, crystals and more) can also exist in a city’s territory, and they need to be mined to provide the prestigious resources. Such mines can be the target of sabotage, or places where disastrous events take place, and so on.

Core Values

Each city has a “score” (more like a weighted percentage) for each of several “core values”. These are Arcane Knowledge, Military Prowess, Prestige, Piety, Commerce, Prosperity and Technology. The score in each of these values would represent the strategies and interests of the city-state. E.g. a city-state interested in Arcane Knowledge would be looking for magical relics, while a Commerce-oriented one would be more interesting in setting up a complex trade network. Military city-states would be launching attacks on other city-states that they hate, or against any other invaders. In terms of future implementation, when trying to choose between behaviors classified with these core values, the weighting would affect the choices.

Guild chapters

In the game there will be several guilds, and each guild can have chapters in different cities.

Guilds can be of “class”, “lore” and “trade” type. Class guilds are fighters guild, clerics guild, rangers guild etc, so that the members can be adventuring classes. Lore guilds are explorers guild, historians guild, seekers guild, etc, that are interested in uncovering information about the world and long-forgotten relics. Trade guilds are blacksmiths, jewelers, alchemists etc, who unionize and typically sell things or services. Everybody gives quests, but PCs will possibly not be able to join trade guilds, as a player you don’t want to be in the shop all day serving customers, or reading books to do research.

Guilds have alignment, so that a chaotic evil guild will not exist in a good-aligned city (unless they’re operating secretly).

Guilds can have biome requirements, for example a pirates’ coven will only exist at a coastal city, or a druid enclave would exist only in a village or a town, near woods.

Some guilds are secret, for example a pirates’ guild, a necromancers’ guild, an assassins’ guild etc. To find those, certain conditions need to be met.

Guilds give quests, some might have initiation quests, and there will be quests (and rewards) for advancing in rank.

Some guilds might not like some other guilds. Due to them being competitors or have very different values. This would be reflected on how guild members treat each other.

Relations

City-states optionally have relations with other city-states. Generally, the closer a city-state is to another, the more likely the relationship to be more polarized (love or hate), compared to city-states that are very far from each other. The reasoning behind this is of course friction and interaction due to proximity. Additionally, like-mindedness in terms of alignment and core values would affect the relations, as a chaotic good city-state could never be friendly to a lawful evil one.

 

So that’s it for now, next time it’s going to be more on relations and also routes between cities and mines.

 

Figure 2 Another city-state territory and information, similar to Figure 1

Overworld Territories

City-States

City-states rule the world. For the whole overworld, using my current projections, there will be a maximum of about 250 cities. For a 512×512 overworld, this would be very roughly a city per 32×32 grid.  Given that a grid cell would represent about 10 sq km, this mean a very sparsely populated overworld, which doesn’t resemble the Middle Ages all that much. That’s fine though, as the alternative/realistic version would be a city/town/hamlet per grid tile, and that would make a quarter of a million such towns.

Borders and growth

City-states have areas of influence, which define their territory and borders.  The area of influence is directly related to how difficult is to cross the terrain. In that sense, sea and high mountains are in general more difficult than other terrains, and the difficulty only increases in temperature/humidity/vegetation extremes. With that in mind, we can create an “influence cost map”, which dictates how influence, generated by its sources (cities at the moment), is reduced while radiating outwards.

Borders between city states

Another interesting point is how to deal with borders between city-states. I found that the simple way of “whoever exerts greater influence on the tile, owns the tile” is unsatisfactory, as city-states with even slightly greater influence can quickly overcome the whole territory of another city state. For example, a city state gains 4% influence, and suddenly it wins over 60% of another city state’s total territory. To deal with that, I still compare the influences, but they are scaled by a factor related to the inverse squared distance of the grid cell in question to the city states: tiles close to city-states (and owned by them)  are much more difficult to be won over by some other city state, especially if it’s far away.

Algorithm

A couple of years ago I developed an algorithm for this, with “nations” in mind (a max of 16 of them). The algorithm was fast, a bit buggy and complicated. Also, code was messy. I tried to read and understand it, and realized I’d be better off writing something from scratch, and it had to be simple. As an attempt of documentation here’s the algorithm in all its glory.

Data format

First things first. For each tile, we store the source ID and the influence decay so far, from the source location until the tile. The decay will be the accumulation of decays along the “shortest” 8-connected path starting from the source.

Initialization

Create the influence decay map, that stores for each tile how much influence is reduced on crossing the tile horizontally or vertically (for diagonal crossing, it’s scaled by sqrt(2) )

Adding/Removing/Changing an influence source

All these cases are handled mostly in the same way, which important for simplicity.

-> Update local cache

We keep a very small per-source cache that stores the location and influence of each source — that’s it. We update the cache by adding/removing/modifying entries as needed

-> Calculate front

We calculate all the border tiles of a source in the following way. We start with the influence source location (the city), and we slowly expand outwards the 4 directions (left, right, top,bottom). We expand towards a direction if a point is within the influence of the source. Below is an image that represents this outwards expansion (the center of the concentric squares is the influence source). In the image, I mark the boundary points; these are the points that have at least one neighbour that is outside the source’s influence (they could belong to a different city, or they might be neutral). So, we slowly grow this axis aligned bounding box of the source’s points, while adding all the border points to a “to process” list.

 

-> Process queue

We have now a queue with a list of points to be processed. These are all the boundary points (For a newly created source, it’s location is the one and single boundary point). The queue is a  priority queue: we add points accompanied by weights, where the weights represent how important it is to process the points first. The reason why a priority queue is important is because we want to avoid traversing tiles multiple times. Imagine the following scenario:

  • Tile (32,45) needs to be processed. We figure out that it should belong to source S0, and it will have an influence of 50
  • Tile (32,45) needs to be processed again. Because we arrived here from a different path, we realize that it should actually belong to source S1, and it will have an influence of 62
  • Tile (32,45) needs to be processed again. We arrived from a different path again, but from the same source ( so effectively used a shortcut, e.g. around the mountains that cost much to pass through). So, while it will still belong to source S1, it will now have an influence of 65.

So, a tile can be unnecessarily processed several times, while we can avoid that if we process the last one first (S1, 65 influence), as the others simply have lesser influence and will not cause the tile to get re-processed. The above also hints on how the processing is done: as a form of floodfill. While on a tile, we figure out who the owner is, how much influence is there at the tile (source influence – influence decay till point), and which neighbouring tiles do we need to process. The queue processing algorithm can be summarized as follows:

  • Get the top point in the queue
  • Check if it’s obsolete. It would be obsolete if the stored weight is lower than the current weight (the weights are just the influence values). If it’s obsolete, repeat from above
  • Check the 8 neighbours and calculate the scores as if the neighbours owned the tile. So, we pretty much calculate if they should own it
  • If our influence is negative and there’s no better neighbour, the tile needs to be reclaimed by nature. If that’s the case, add to the queue all neighbours that are of the same source
  • If our influence is positive and there’s no better neighbour, we’re ok and we need to see if we need to expand this source id to neighbouring tiles. By comparing influences, we add potential candidates to the queue.
  • If there’s a better neighbour, we replace this tile. The new influence information can propagate further, so we check all neighbours to find out potential processing candidates and add them to the queue.

Video

Here’s a video that demonstrates border growth for 256 city states.

 

Nations, Races and Cities

One thing that has been bugging me for a while is the administrative aspect of the world’s population. Several races coexist in the world, sometimes not so peacefully. One of the important questions is, how to divide the population groups? This can answer questions such as who lives where, who likes whom, how does the player interact with each group, etc. The context is always important: this is a game where the player controls a single character over the course of maybe several in-game decades, in a persistent and procedural world, where there are lots of self-sufficient cities with guilds, shops etc.

Nation-based

One way of dividing them is DnD/Forgotten Realms style using nations. Each nation has different government type (plutocracy, magocracy, autocracy) and has citizens of potentially many races. This is a nice, “realistic” division, but comes with a number of complications for a type of game where you’re an adventurer going around in the world and doing stuff. Just a few issues below:

  • Nation conflicts and diplomacy. When there are several nations, it’s only natural that over the course of time conflicts arise. If relations were all nice among them, there’s no reason not to be unified. Modeling nation-wide war in a game where the player controls a single or a few characters can be problematic. What happens if nation A wages war on nation B? What does that mean for the player? Can the player not safely visit several cities of nation A or B anymore?
  • Nation-wide AI, city-wide AI, unit AI. With nations, there’s more AI to develop. What responsibilities does a nation have? What can it do? Found cities, wage wars, etc? We’re getting heavily into 4x game territory, and that becomes a bit much for solo development.
  • Nation identity.  When creating a number of fictional nations, effort must be put so that the nations are unique, individual, interesting. I’m personally very averse to fiction where the differences are superficial. For example picking a name from a generator list, roll a dice for government, roll a dice for alignment, etc and that’s it. That’s not enough. Forgotten realms for example has quite good depth for each nation, but that’s over tons of books and game supplements. Solo development can not afford such depth.

Race-based

Another way to split nations is by race, where the race would also be the nation. You have dwarves, elves, humans, etc. That’s nice and simple and at least addresses the “identity” issue above. There are still potential conflicts and AI to be modeled though, but they are nothing compared to the effort in creating a striking identity for a nation. The identity of the races still needs to be developed to escape the confines of the generic high fantasy elf/dwarf and other races, but that would be done for the nation-based division anyway, as a separate task. ( Create identity for dwarves, humans, orcs, etc, also create identity for nation of Whatever and Etcetera). Issues with race-based division:

  • Not sensible. It just doesn’t make much sense that, at least “good” nations would prohibit citizenship from other intelligent species, as long as they could all co-exist peacefully. Of course dwarves could be reserved against other races, or elves be haughty and racist, but having that at 100% everywhere makes the races one-dimensional and not so believable.
  • Player interaction limitation. In the game, several guilds exist that the player can join. If the player is from race A, do you get excluded from guilds in cities of race B? Otherwise, why would they be the special cases of allowing members of different race? It would take quite a bit of writing effort to make that sensible and believable. The game would force you to be part of a big group, where inadvertently you’d have situations of “us vs them” at a nation/race scale.

Multicultural city-states

Another way to divide the world is to ignore the nation-wide scale using city states (Elder Scrolls cities feel sort-of like that). Cities are self-sufficient, can contain guilds and various other buildings and people that a player can interact, and have the following advantages:

  • No need for full-out warfare. A nation gathering army and ganging up to attack a city is much easier than a city gathering army to attack another city. So all-out warfare between city-states is not something that one can expect to naturally happen. Subterfuge on the other hand is much more likely, and can create very interesting scenarios: for example a guild hires you to steal a relic from a rival guild of another city-state, or the government hires you to sabotage a mine operation that belongs to another city-state.
  • Multicultural. A city-state can optionally be multi-race, or single-race, or anything in-between. A fully dwarven city in the mountain is as plausible than a hillside settlement with hill dwarves and hill orcs, as long as the races can coexist peacefully.
  • No nation-wide simulation layer. Easier to develop as there’s no need for nation AI. Nations don’t need to found new cities, as the time scale of the game is not centuries (which would take for a city to start, grow and have some sort of history). There’s no resource management layer between cities and nations (does a mine’s ore go into nation coffers? Does a nation have resources, or they are per-city?)
  • Emergent identity. The city-state types are used as a prototype several times, but the simulated and played history can affect the development of individual city-states. A dwarven city in the mountains can start as poor, if surrounded by not-so-resourceful environment, but its fate might change if they discover a rare mineral nearby and mine it. A different dwarven city could have a completely different fate, for example it could be eradicated by Unknown Destructive Forces or sabotaged to oblivion. The basic identity (how does a dwarven city look like, how does it function, etc) is written for a limited number of prototypes, while the emergent identity via history generation and playing is what will make it rich.

 

The above are just some thoughts; not final, but representative of my current development mindset. While originally I started with the race-based approach, I’ll be using the city-state paradigm unless I can think of a blocker.