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