7DRL25 Postmortem Series: Distance Map Ideations

This will be a series of shorter posts on topics we found interesting in hindsight after this year's 7DRL. It might be all over the place.

Hello, Mika here! Today, the topic is distance maps, and how to use them for AI! Having read this great post about Dijkstra maps, which are so called only because they're a generalized cached version of Dijkstra's algorithm, I've decided to give them a run as a universal tool for both mapping and general mob AI. It was a joy, generally! I call these maps distance maps, or distance fields, as they are very similar (quite the same!) to the concepts used in signed distance fields. No need to bring in a weird name for something simple like that.

It's a map where every field tells you how far away from some goal feature you are. If the goal is the player, you get a map useful for enemies to be able to easily get to you. If the goal is walls, you get a map where every tile's value is the distance to the closest wall, etc. They can be used for many things, and they're additive, so having multiple can work together to produce more than linear combinatorial goodness!

While the idea is quite simple, along the way I've felt like my implementation could be loads better in several ways. Of course, it's 7DRL, so I didn't have the time to do that, but here we are!

First off – implement maps in a way that doesn't require a whole map to be allocated every time. If you can just keep a dictionary of tile indices mapping to distances (or, in Lua, a table indexed by the tile's position hashed in some way – we were using w * y + x – and mapping to the distances), that's great. In many cases, what you actually need is a radius around some point, so no need to do an abundance of allocations for it.

Secondly, keep the predicate of your distance map separated from the flooding algorithm itself. A distance map flood basically represents the following process:

1. In an empty map, add as many goals as you want. They have value 0, as they are at distance 0 from themselves. As you add them into the mapping, also add them to the work queue where potential candidates are kept. Initialize a visited set as well where we'll take care of cutting off unwanted exploration.
2. Dequeue one tile from the work queue. If it's not yet visited, do the following, else skip back to 2:
   1. Check if this tile is already in the mapping, and if it isn't take it's neighbors and get the minimum of all of their values. Once you get the minimum, set this tile's mapping to be that neighborhood minimum + 1. If the tile has no neighbors, then there's probably some weirdness going on and we don't want it anyway (it's either a goal, so the value is already there, or disconnected, so doesn't factor in).
   2. Go through all the neighbors (yeah, this can be a part of the loop above, but it's cleaner to keep it separate) and if they're not already in the mapping, and not visited, check them against your predicate for this distance map. If they pass the predicate, add them to the work queue.
3. Repeat until the work queue is empty!

So, what's this predicate? In example, if we're making a distance map from the player through walkable, empty fields, the predicate would be: is this field walkable and empty? If yes, add it in! I made the predicates functions that I add to the distance map when creating them, this worked out fine!

Thirdly, because distance maps are additive and float-multiplicative, and because we want to evaluate them point-wise ("I'm interested in what the value is on tile X, Y"), it's super useful to have an interface for combining them that lives outside the map itself. So... a distance map combinator library. For example, in some cool pseudocode:

local DM_fromPlayer = DistanceMap.new(...)
local DM_fromGold = DistanceMap.new(...)

local goblinPrios = DM.Add(DM_fromPlayer, DM_fromGold)
local greedyGoblinPrios = DM.Add(DM_fromPlayer, DM.Prio(DM_fromGold, 4))

In the example, DM.Add creates a view that behaves as if we took the sum of the two maps together (for example, if DM_fromPlayer returns 3 and DM_fromGold returns 2, goblinPrios returns 5 – this might seem weird, but it will be summed overall, so it will keep the shape of both maps). DM.Prio increases the value of the map in question by a certain factor, so in the same example from above, the greedyGoblinPrios would evaluate quite differently:

1. DM_fromPlayer still returns 3
2. DM_fromGold goes through a view in which it is reduced by 4 (reduced value means it's closer so that's good). If the value was 2 before, now it's -2.
3. Added together, the current sum of the two fields is -1, which tells us that the greedy goblins want to be on this spot more than the non-greedy ones, as it's close to a topic they care more about (gold!)

Make sure that the views have the same interface that distance maps have, and enable the combinators to do all sorts of fancy things, like multiplying with a value, adding them together, etc. Most importantly, as distance maps are created from already-existing maps on which we apply predicates away from some goals (the original maps don't need to be float maps or even integers!) we need to make sure that distance maps and their combinators can both be used as input maps to make new distance maps from! I don't have a nice combinator-like way of doing this, but I have time to think about it...

With just these tricks, changes in predicates, combinators and multiple map queries, we can get a lot of AI work! For example, aggressive creatures have the player's position as a goal – they're trying to get there and seem hellbent on doing so – while summoners try to keep the player at the edge of their sight, safely some distance away while summoning rats. How this works is as follows (assuming, say, that their sight is 5):

1. take a distance map with the player's position as a goal and empty, walkable tiles as the ones accepted by the predicate
2. find all the tiles at distance 5, see if they're in the monster's field of view, and use those as goals for a new distance map. This map now contains a gradient from the monster to these fields, that you can just roll-down through.

We actually use something even more simple than this and completely skip doing enemy field of view. I'd love to have made it that far, but we had to cut corners...

I want to explore distance maps a lot more. Right now, there's some arcane know-how around how to use them, there's some recipes for success, but I'd love to be able to play with them in a more arranged way. We need tooling for this kind of thing: something that can save state and let us rewind, apply limited filters (maybe this is a combinator which applies a change to the map only within some part of the 2D domain), blur them, focus them, bloom them, there's so many ideas! I also feel like we need to get the implementation down to the leanest and meanest, so that we never again have to fear whether we have too many distance maps. This is a whole large goal of its own, honestly...