10 Kobolds pathing for the price of one with hierarchical pathfinding

It’s been a while and I apologize for not updating the blog lately. Lair of the Kobolds is still progressing however and I have been busy on the game even while the blog’s been quiet.

Out of curiosity one day I sent 200 kobolds walking around a large map. They were using A* pathfinding like most games of this type do, and some are notorious for slowing down with a lot of creatures walking around.  Lair of the kobolds was no exception. Most of the kobolds stood around waiting for their turn in the pathing queue while only a select lucky few could get where they were going.

The problem with normal A* is it will flood the map searching, especially if there is no route to the target location or it’s a got a very roundabout path.  I researched a bit and stumbled upon HPA* which is a variation of A* that uses hierarchical clusters in order to narrow down the path before doing the normal square by square A*. HPA* Gets around the flooding problem by only flooding the clusters that are transitioned through, and there are far fewer of them. This paper is a good reference for how it works.

The Basic Algorithm

The way the algorithm works is you break the world into clusters of cubes, and then find all transitions between the clusters. Once you have the transitions you run A* on each pair of transitions within a cluster to get connectivity and distance between the two transitions. Then you can  do another A* search on just the transition nodes to get an abstract path which is just the links between transitions. To get the real path from the abstract path you then run A* between the transitions in each cluster that the abstract path uses.

Once the transitions through the clusters are found, normal A* is run to walk between the clusters. Below is the visualization of a single kobold’s path. Red is the path through transitions, yellow is the actual path he follows. It’s not an optimal path but it can be made prettier by implementing path smoothing.

PathfindingPath

Selecting Transitions in 3D

Getting it to work in 3D was a little more involved than the 2D example in the paper. I started out by designating clusters as 3d cubes rather than 2d squares, which then gave the problem of the “edges” now turning into 2d squares themselves. The X and Z directions could be simplified by scanning them in slices that are only 1 cube high, but I found that pathfinding was faster if the clusters had a height of 1 anyway because kobolds walk on the ground and there was a lot of failed transition searching through the floors and ceilings of dungeons. Below is a view of the clusters on a small map. Each 1 block high cluster is surrounded by a square, and all the transitions between clusters are small cubes.

PathfindingDebug

Finding transitions between Y levels was a bit harder, since there’s no easy scanline way that results in good transitions. What I ended up doing was floodfilling both the current level and the level above to find individual “islands”, then grouping together the ramps that had the same two islands on either side and picking from those.

Below is an example of how this works. We are trying to find the transitions between the upper and lower levels which are separated by the dark pit in the center. The ramps are signified as arrows leading from the upper level to the lower. Something simple like finding all the ramps and choosing one won’t work, because the two parts of the upper level and two parts of the lower level aren’t connected.

RampTransitions

 

Next, we floodfill each section of the top layer, then each section of the bottom, with any ramps getting tagged with both end’s fills. This separates our ramps into distinct groups: red/blue, red/green, yellow/blue, yellow/green.

TransitionFloodColors

We know that all ramps in each group can get us from the same lower section to the same upper section, so we can feel free to choose one. I simply picked the one most central to each set.

TransitionPicks

Dealing with Geometry Changes

Kobolds mine (and will soon build) so the pathing information for a cluster occasionally needs to be reprocessed. If the changed block is in the middle of a cluster, all that needs to be done is recalculate the distances and connectivity of the transitions within that cluster. But if the changed block is on the edge of the cluster, the transitions between the changed cluster and the neighbor it shares an edge with need to be re-found. The neighbor only needs to calculate transition distances for any new transitions it gets from the changed cluster, because no internals changed. Since my clusters are only one block high, transitions with the upper and lower neighbors need to be re-found every time

 

The Verdict

Now how well did it do to speed things up? I ran a test with kobolds pathing to random surface points on some large maps, all paths going through both HPA* and A* to compare.

On a hilly map the average time for A* was 14.7 milliseconds. With HPA* it went down to 2.5 milliseconds.

On a flattish map the average time for A* was 9.5 milliseconds. With HPA* it went down to 0.9 milliseconds.

Not too shabby. Now about 6-10 times more kobolds can path around than before this was implemented.

And now… 200 kobolds walking around a large map:

200KoboldPaths

Posted in AI, Lair Of The Kobolds | 2 Comments

Coloring the World

Most of the materials used in Lair of the Kobolds are greyscale in texture. For instance, here is the world with no coloring applied

Screenshot of lair of the kobolds with no color applied

World with no color

Here is a screenshot of the same type of area with coloring

Screenshot with color applied

World with color

This is done by applying the color to the object in the shader based on the color of the texture.

Coloring the Terrain

The simplest one is the terrain textures. Two colors are applied to it, one color to the dark pixels, a different color to the light pixels, and a blend of those colors in between. In the screenshot above you can see that the grass goes from a green to a yellowish green as those are the two colors applied. The formula for this kind of coloring in a cg shader is: outColor.rgb = texture.rgb * lerp(primaryColor, secondaryColor, readtex.r).

This allows just a few variations in tiles to create vastly different environments. Below is a savanna area created by recoloring the grass and dirt textures.

Savanna map

Savanna map created by recoloring textures

 

Coloring the Kobold

The kobold is colored slightly differently. He uses each of his color channels as a map to each of three input colors. The eye is mostly red, meaning that  the first color input will have most influence on it. The chest and ears are green which is mapped to the second color, and the rest of the body is mostly blue which maps to a third color. The formula for the kobold’s color in a cg shader is:  outColor = texture.r*color1+texture.g*color2+texture.b*color3.

Kobold with unmodified texture colors

By changing the colors I can get many different kobold variations, as well as create effects such as a chameleon skill that will color the kobold the same as the ground he stands on.

Kobolds with a chameleon effect

 

 

Posted in Lair Of The Kobolds | Leave a comment

Cavern Painters

Last Week I showed how the skeletons for the dungeons in Lair of the Kobolds are formed. This week I worked on painters to make these dungeons more varied, and the rules that govern the painters. There are currently three kinds of painters: a painter that makes a rectangular room like the basic rooms shown in the last post, a painter that carves a windy cavern corridor between a room’s connections, and a painter that carves a blobby cavern in the room.

A dungeon using room painters

A dungeon using room painters

The dungeon creator figures out which painter to use based on rules. The main route between the entrance and the exit (stairs down in this case) has to be a cavern corridor or cavern room. Any rooms off the main path may get a cavern or rectangle. To create complexes of carved out rectangular rooms like someone lives there, the rectangles can only connect to other rectangles.

Other rules govern the system too, for instance, a dead end may only be a rectangular or cavern room, not a corridor (though some really small dead end rooms right now look like a corridor just ends.)

Eventually the room painters will also do things like insert monsters and objects into the rooms, but these simple painters will do for now.

Posted in Dungeons, Lair Of The Kobolds | Leave a comment

Dungeons!

Last week I implemented dungeons, or at least their skeletons. Right now just big rectangular rooms are being dug out, but the dungeons go all the way down to the bottom layer connected by ramps. It doesn’t look too exciting right now, but eventually, each of these skeleton rooms will get a special room painter to dig out a cavern or a troll den or a dwarven bedroom or other interesting things for the kobolds to explore.

Dungeon Skeleton

The skeleton of a dungeon in a mountainous region

 

This skeleton is generated using the subdivision method, which takes the whole area and repeadedly slices it in two until the desired room size is reached.

Diagram of dungeon subdivision

Next, a start and end room are selected. Preferably they are very far apart. An A* path is used to link the rooms together between start and end. After that, all other rooms are linked to these rooms

Link rooms together

Now you can stop here if you want boxy square dungeons. If you don’t, some of these rooms need to be pruned. The next part is hard to show with such small diagrams. Basically calculate all the room “tendrils” that grow from the main path. In the diagram below, the main path is yellow. We want to keep that. The tendrils are orange. Start pruning these tendrils from the ends until the desired number of rooms is reached.

Prune dead ends

The result of this is a basic dungeon shape that can now be decorated any way you like.


Posted in Dungeons, Lair Of The Kobolds | 1 Comment

What is Lair of the Kobolds?

What’s the first thing you think of when you hear about a kobold? Cannon fodder?  Little nuggets of exp? Quest monsters for noobs? Well the kobolds have had enough of that stereotype. Sure they start out as cannon fodder, but under your guidance perhaps they can survive long enough to flourish and maybe even prove themselves.

The idea for the game started out with the 48 hour game programming contest, Ludum Dare. The theme for Ludum Dare 15  was caverns, and what lives in caverns? Goblins! Goblins who could perhaps set traps to kill any invading adventurers as well as clearing the caverns of trolls. The result of the 48 hours wasn’t exactly a work of art, but the seed of the idea was there.

Work continued on the game. Where I implemented mining, smelting, and the gathering of food. Unfortunately, I didn’t have much time to work on it and pushed it aside.

Recently I’ve started it up again, coding it with a full 3D Voxel engine. Also I’ve changed the monster of choice to kobolds, since they have some interesting gameplay elements and they don’t get enough recognition. I will be posting more information on the game here as it is implemented.

Posted in Lair Of The Kobolds | Leave a comment