💾 Archived View for thrig.me › blog › 2024 › 03 › 20 › scent-map.gmi captured on 2024-03-21 at 15:00:58. Gemini links have been rewritten to link to archived content
-=-=-=-=-=-=-
/blog/2024/03/11/code-smells.gmi
The prior effort to path creatures based on a flow map was quite primitive (though simple to implement) and ran into problems with twisty passages not spreading the scent very far. Another problem is that using the scent map to flee from a monster (the hero, really) can exhibit bad behavior; one might want the critter to flee past the hero to the door, and not get stuck in a corner. So improvements would be to use a better (more complicated) algorithm to fill the map with scent, and to construct a different map for getting away from the hero (monster).
A breadth first search (BFS) can fill a map, though in C requires that you have an integer matrix to store results in (not difficult, but do check that your laser bats cannot shoot down the entire process) and a queue to shift from and push potential points to (more difficult). A queue can be done with a linked list or an array; probably these two different approaches should be benchmarked to see if one is strictly worse than the other. If we ignore the details of the queue and seen matrix, a BFS does not require much code:
#define XX 0
#define YY 1
// borrowed from Brogue
const short dirs[8][2] = {{0, -1}, {0, 1}, {-1, 0}, {1, 0},
{-1, -1}, {-1, 1}, {1, -1}, {1, 1}};
// set this to 8 if you want 8-way motion
#define DIRECTIONS 4U
// mark the point "p" with the smell value and queue the point
void enqueue(vec_t *vec, int **seen, coord p, int value) {
vpush(vec, &p);
seen[p.yy][p.xx] = value;
}
...
enqueue(queue, smells->map, start_point, player_smell);
#define SMELL_UNSEEN -1
while (queue->length) {
coord position = vshift(queue);
int scent = smells->map[position.yy][position.xx] - 1;
if (scent < 0) continue;
for (size_t i = 0; i < DIRECTIONS; ++i) {
coord adjacent = position;
adjacent.yy += dirs[i][YY];
adjacent.xx += dirs[i][XX];
if (map_within(smells, &adjacent) &&
smells->map[adjacent.yy][adjacent.xx] == SMELL_UNSEEN)
enqueue(queue, smells->map, adjacent, scent);
}
}
A nice property here is that multiple points can be "enqueued" before the while loop; this sets multiple points that critters will path to. For example food might radiate scent; a critter using the food scent map will then path to the closest food, and the scent map need only be updated when the resource is consumed or spawns. With enough food, a different scent map could path a critter back to a suitable den…
A trick borrowed from Brogue is the "dirs" array that allows switching between 4-way or 8-way motion easily.
This implementation may not fill the entire map, depending on how large the map is and how strong (high) the "player_smell" value is. With a smaller, closed map (such as in Brogue) calculating the whole level probably makes sense; monsters can pretend not to notice the path when relevant. With a larger map a limited range scent map will avoid excessive CPU and memory use. The above code halts when the "player_small" zeros out after some distance. For example with a player_scent value of nine on a smell test map,
$ make smell && ./smell > nine
cc intmap.o vector-coord.o smell.c -o smell
$ heatmap nine
notice: range - 0 .. 9
$ mv out.png smell-nine.png
$ sed 's/ / /g;s/-2/#/g' nine
9 9
3 4 5 4 3 2 1 0 -1
2 # 6 # # # 0 # -1
1 # 7 8 7 # -1 # -1
0 # 8 9 8 # -1 # -1
-1 # 7 8 7 # -1 -1 -1
-1 # 6 7 6 # -1 -1 #
-1 # # # # # # -1 -1
-1 -1 -1 -1 # -1 # # -1
-1 # -1 # # -1 # -1 -1
The scent map only reaches a subset of the map; any point with "-1" has no information on where the scent is (or is a point not connected to the graph). If the player_scent is cranked up to 99, then the entire map is filled, or as far as that is possible; this map has an unconnected area.
$ sed 's/ / /g;s/-2/#/g' 99
9 9
93 94 95 94 93 92 91 90 89
92 # 96 # # # 90 # 88
91 # 97 98 97 # 89 # 87
90 # 98 99 98 # 88 # 86
89 # 97 98 97 # 87 86 85
88 # 96 97 96 # 86 85 #
87 # # # # # # 84 83
86 85 84 83 # -1 # # 82
85 # 83 # # -1 # 80 81
So with a BFS one can fill some amount of a map with distance values to or from a particular point (or multiple points, if one enqueues multiple starting points), and the BFS does not suffer from the "twisty passages" problem of the much simpler "spread values to adjacent open cells" code of the prior article (linked to, above).
The above graph or flow map is however not ideal for fleeing or getting away from the highest value;
3 4 5 4 3 2 1 | . . . . . . .
2 # 6 # # # 0 | . # + ##### .
1 # 7 8 7 # ? | . # . . . # .
0 # 8 9 8 # ? | . # . @ . # .
? # 7 8 7 # ? | . # . . . # .
? # 6 7 6 # ? | . # . . S # .
? # # # # # # | . ###########
? ? ? ? # ? # | . . . . # . #
? # ? # # ? # | . # . ### . #
if our "S" or Snek (or Salamander, Shark, Skeleton, etc.) wants to get to the monster (hero, "@") then that is not a problem; but to flee they are trapped in the corner; no adjacent value (7, or 8 with diagonal motion) is better than their current spot (6). Now this is probably fine for dumb and slow monsters like Snek, but one might imagine that those with more intelligence would want to make for the door ("+") even if they have to squeeze past their opponent. This necessitates a different map.
Obvious places to flee to would be cells with zero or no scent indication. Such points, however, may not exist. This may complicate the search for ideal spots to flee to. Their non-existence would be more typical on smaller, enclosed maps with higher scent values, as can be seen on the "99" map, where the best places to flee to have the values of 80 or 83. Seeding the reverse map will depend on the scent value, how you find the minimum point(s), whether the player's smell can change (is it an aura? Does a stronger aura trap monsters in corners?), or whether the scent system might punt the question and other means are used to move the critters around: what is visible to the player, and can we move out of visibility? Is there a room exit to route to? Etc. Another question is how far a monster needs to flee; with a stronger scent map and no ranged combat then looking for a value at least 10 points off the hero's value may suffice (89 or lower on the 99 map). With ranged combat you would likely need to keep them out of the player's field-of-view as well, which is a different system. That was a long way to say that there can be complications.
Anyways, one implementation of a flee map is to copy from the "seen" or visited map of scents, blocking off the player's position as if it were a wall, and using places "far enough" from the player as seed points to flee to. Cells with a known scent get reset as "unseen" so that the BFS fills them in. You could also search the "seen" map, find the minimum values, and use those to seed the map. This method just copies (possibly modifying) values over, then runs a BFS on that.
for (size_t r = 0; r < (size_t) smells->height; ++r) {
for (size_t c = 0; c < (size_t) smells->width; ++c) {
int value = smells->map[r][c];
if (value == player_smell) {
// do not flee through the worst of it
flees->map[r][c] = -2;
} else if (value > 0) {
flees->map[r][c] = SMELL_UNSEEN;
} else if (value == 0 or value == SMELL_UNSEEN) {
enqueue(queue, flees->map,
(coord){.yy = r, .xx = c},
player_smell * 2 - value);
} else {
// copy anything else. the walls, probably
flees->map[r][c] = value;
}
}
}
if (!queue->length)
fprintf(stderr, "warning: no flee map start points found\n");
while (queue->length) {
coord position = vshift(queue);
int scent = flees->map[position.yy][position.xx] - 1;
if (scent < 0) continue;
for (size_t i = 0; i < DIRECTIONS; ++i) {
coord adjacent = position;
adjacent.yy += dirs[i][YY];
adjacent.xx += dirs[i][XX];
if (map_within(flees, &adjacent) and
flees->map[adjacent.yy][adjacent.xx] ==
SMELL_UNSEEN)
enqueue(queue, flees->map, adjacent, scent);
}
}
Probably that "flush the queue" while loop should be a function, but I'm making this up as I go along, and don't know what I am or ain't gonna need here (YAGNI).
$ make smell && ./smell | perl -ple 's/-2/ #/g;s/ (\d)(?= )/ $1/g'
cc intmap.o vector-coord.o smell.c -o smell
9 9
15 14 13 14 15 16 17 18 19
16 # 12 # # # 18 # 19
17 # 11 10 9 # 19 # 19
18 # 10 # 8 # 19 # 19
19 # 9 8 7 # 19 19 19
19 # 8 7 6 # 19 19 #
19 # # # # # # 19 19
19 19 19 19 # 19 # # 19
19 # 19 # # 19 # 19 19
$ make smell && ./smell > flee
`smell' is up to date.
$ heatmap flee
notice: range - 6 .. 19
$ mv out.png flee.png
This shows that where the "@" is is a no-go "wall" cell, and that a critter trapped in the corner (value 6) can climb up this flow map to flee. They will have nowhere to go once they reach a value of 19, but either that will have taken them "enough" away from the player, or the flee map will update if the player chases them, granting new cells to flee to.
Dead ends could still be a problem, though a critter would need to "know" the map well enough that when fleeing and stressed out that one should not take that corridor. (There is a reason stairs leading down to the basement tend to have metal guards in front of them; this is to avoid a herd rush going the wrong direction when there's an emergency that starts a herd rush.)
(If a monster has a "den" or "lair" they might have a scent map for that instead of reversing the map of some opponent. Or if you have acid crabs that live in pools of acid, you could have them try to push or drag things into said pools. Fun for the whole family! Also a den or lair map probably does not need updates so could be done once when the map is generated. So dens or lairs are sounding better by the moment…)
https://www.redblobgames.com/pathfinding/tower-defense/
P.S. The "tower defense" page had a funny "Breath Based Search" typo.
