💾 Archived View for thrig.me › blog › 2024 › 03 › 11 › code-smells.gmi captured on 2024-03-21 at 15:02:45. Gemini links have been rewritten to link to archived content
-=-=-=-=-=-=-
So theoretically one has a critter, a Snek, perhaps, and you want to get that critter over to some other location... how to do this?
0123456789
0.........
1.........
2..S......
3.........
4.........
5.........
6.....@...
7.........
8.........
9
Another question is can we make the Snek instead move away from that other location. Or what happens if there are a lot of critters who need to move towards or away from a point, and one does not want to calculate a go-towards or move-away path for each and every critter? Or could we make the Snek circle the target?
One could code smells, where the target location has some value, and then increasingly adjacent cells have increasingly lower values. Some random tips:
A first attempt might look something like:
// smolpath - small example of bespoke pathfinding
#include <stdint.h>
#include <stdio.h>
#define MAP_LINES 15
#define MAP_COLS 9
#define MAX(a, b) (((a) > (b)) ? (a) : (b))
typedef struct {
int xx; // "xx" is easier to find and less common than just "x"
int yy;
} point;
// this should be allocated, but that's more complicated
static int smell[MAP_LINES][MAP_COLS];
// presumably the smell goes away over time
inline static void smell_decrease(void) {
for (size_t y = 0; y < MAP_LINES; ++y)
for (size_t x = 0; x < MAP_COLS; ++x)
smell[y][x] = MAX(smell[y][x] - 1, 0);
}
// make adjacent smells one less than the current cell, if not higher
inline static void tweak_adjacent(size_t y, size_t x) {
const int value = MAX(smell[y][x] - 1, 0);
size_t newy, newx = x;
newy = y - 1;
if (newy < SIZE_MAX && smell[newy][newx] < value)
smell[newy][newx] = value;
newy = y + 1;
if (newy < MAP_LINES && smell[newy][newx] < value)
smell[newy][newx] = value;
newy = y;
newx = x - 1;
if (newx < SIZE_MAX && smell[newy][newx] < value)
smell[newy][newx] = value;
newx = x + 1;
if (newx < MAP_COLS && smell[newy][newx] < value)
smell[newy][newx] = value;
}
// spread it around...
inline static void smell_spread(void) {
for (size_t y = 0; y < MAP_LINES; ++y)
for (size_t x = 0; x < MAP_COLS; ++x)
tweak_adjacent(y, x);
// and let any weak spots fade out
smell_decrease();
}
// put a smell somewhere
void smell_mark(point *origin, int amount) {
smell[origin->yy][origin->xx] = amount;
smell_spread();
}
void smell_show(void) {
for (size_t y = 0; y < MAP_LINES; ++y) {
for (size_t x = 0; x < MAP_COLS; ++x) {
printf("% 3d", smell[y][x]);
}
putchar('\n');
}
}
int main(void) {
smell_mark(&(point){.xx = MAP_COLS / 2, .yy = MAP_LINES / 2}, 9);
smell_show();
}
The above is in error; it only spreads the smell towards the Southeast, if we arbitrarily assume that North goes out the top of the terminal, and West to the left. Having good ways to observe the scent map will be really handy, especially if the map gets larger. Make a colored heatmap, perhaps?
$ make smolpath && ./smolpath
cc -O2 -pipe -o smolpath smolpath.c
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 7 6 5 4 3
0 0 0 7 8 7 6 5 4
0 0 0 6 7 6 5 4 3
0 0 0 5 6 5 4 3 2
0 0 0 4 5 4 3 2 1
0 0 0 3 4 3 2 1 0
0 0 0 2 3 2 1 0 0
0 0 0 1 2 1 0 0 0
0 0 0 0 1 0 0 0 0
This is easy to fix; simply make another pass over the map going in the other direction,
inline static void smell_spread(void) {
for (size_t y = 0; y < MAP_LINES; ++y)
for (size_t x = 0; x < MAP_COLS; ++x)
tweak_adjacent(y, x);
// whoops, also need a reverse pass
for (size_t y = MAP_LINES - 1; y < SIZE_MAX; --y)
for (size_t x = MAP_COLS - 1; x < SIZE_MAX; --x)
tweak_adjacent(y, x);
// and let any weak spots fade out
smell_decrease();
}
and now the target cell is surrounded by a field of lower values. To approach the target, find adjacent points that have the highest value and pick one of them. To flee, find the lowest values and pick one. A random pick here is probably necessary as otherwise the flee would be predictable. The good news is that there aren't many choices to consider; there would be more if diagonal motions were allowed, or worse if the map has three or more dimensions. Yes, this cellular pathfinding works with an arbitrary numbers of dimensions (which I have code for in Common LISP, but that doesn't help me for a game in C).
$ make smolpath2 && ./smolpath2
cc -O2 -pipe -o smolpath2 smolpath2.c
0 0 0 0 1 0 0 0 0
0 0 0 1 2 1 0 0 0
0 0 1 2 3 2 1 0 0
0 1 2 3 4 3 2 1 0
1 2 3 4 5 4 3 2 1
2 3 4 5 6 5 4 3 2
3 4 5 6 7 6 5 4 3
4 5 6 7 8 7 6 5 4
3 4 5 6 7 6 5 4 3
2 3 4 5 6 5 4 3 2
1 2 3 4 5 4 3 2 1
0 1 2 3 4 3 2 1 0
0 0 1 2 3 2 1 0 0
0 0 0 1 2 1 0 0 0
0 0 0 0 1 0 0 0 0
Any cell with a zero in it has no information on where the target is. These can be used to place objects far away from the smell, though one could also use a "low enough" smell value for that, especially if the smell is high enough to fill the entire map.
Another probably necessary complication is to mark certain cells as impermeable; that is, cells that the smell must not pass through. Walls, lava pits, that sort of thing. Unless you do want your critters walking into walls or lava pits, which may be suitable behavior for, I don't know, zombies. For impermeability one could assign, say, -1 as "this value blocks the smell" and skip marking or adjusting those cells.
Even more complicated would be to assign permeability values to each cell, so that a window would pass the gas less quickly than a corridor or open door would. But that's more work.
One can also find regions of the map that are blocked off; these will be areas of high scent next to low or no scent. Various means could be used to detect such and if need be carve doors or passages to connect up isolated areas on the map.
The above code performs very poorly in twisty, narrow passages. These would require increased map passes to spread the smell as expected, though at that point you would likely be better off with a more complicated floodfill algorithm. Still, if the map is mostly open or if you don't mind the smell taking longer to move through narrow twisty passages, this code may get the job done.
Here's what a twisty passage scent stopper looks like:
// here we "box" the target in
static int smell[MAP_LINES][MAP_COLS] = {
{ 0, 0, 0, 0,-1, 0, 0, 0, 0 },
{ 0,-1,-1, 0,-1, 0, 0, 0, 0 },
{ 0, 0,-1, 0,-1, 0, 0, 0, 0 },
{-1, 0,-1, 0,-1,-1,-1,-1, 0 },
{ 0, 0,-1, 0, 0, 0, 0, 0, 0 },
{ 0,-1,-1, 0,-1,-1,-1,-1, 0 },
{ 0, 0,-1, 0, 0, 0,-1, 0, 0 },
{-1, 0,-1, 0, 0, 0,-1, 0, 0 },
{ 0, 0,-1, 0, 0, 0,-1, 0, 0 },
{ 0,-1,-1,-1,-1,-1,-1, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{-1,-1,-1,-1,-1,-1,-1,-1, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0 },
};
This "boxing in" limits the simple spread, a lot (the following is from a version of the code with an error!)
$ make smolpath3 && ./smolpath3
cc -O2 -pipe -o smolpath3 smolpath3.c
9 10 11 12 0 0 0 0 0
8 0 0 13 0 0 0 0 0
0 0 0 14 0 0 0 0 0
0 0 0 15 0 0 0 0 0
0 0 0 16 15 0 0 0 0
0 0 0 17 0 0 0 0 0
0 0 0 18 19 18 0 0 0
0 0 0 19 20 19 0 0 0
0 0 0 18 19 18 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0
though if the target moves around the smell should reach out more:
$ make smolpath3 && ./smolpath3 | sed 's/-1/ #/g' | tail -16
cc -O2 -pipe -o smolpath3 smolpath3.c
15 16 17 18 # 6 7 8 9
14 # # 19 # 7 8 9 10
11 10 # 20 # 8 9 10 11
# 9 # 19 # # # # 12
7 8 # 18 17 16 15 14 13
6 # # 17 # # # # 12
3 2 # 16 15 14 # 10 11
# 1 # 15 14 13 # 9 10
0 0 # 14 13 12 # 8 9
0 # # # # # # 7 8
0 0 1 2 3 4 5 6 7
# # # # # # # # 6
0 0 0 0 1 2 3 4 5
0 0 0 0 0 1 2 3 4
0 0 0 0 0 0 1 2 3
That's a bit hard to visualize, though?
Luckily, someone just so happened to write a script that makes visualizing the smell map a bit easier, as the terminal is pretty limited in resolution and is not square.
Sure would have been nice to have this before going into a limited time programming challenge. Maybe for the next one… and probably after I write a smol library for scent-mapping with all sorts of features and bloat.
I did try randomizing the scent decrease (skip the decrease on a roll of 1 on a 1d-something); this produced local hotspots that critters would get stuck on, but will confuse "intelligent" monsters just as well as the dumb ones. Randomization might help in some other context, like maybe all the monsters are dumb, or you do want them stuck sometimes. Maybe if you combined scent map randomization with field-of-view, so the player both has to manage their scent and keep out of visual contact?
inline static void smell_decrease(void) {
for (size_t y = 0; y < MAP_LINES; ++y) {
for (size_t x = 0; x < MAP_COLS; ++x) {
if (smell[y][x] < LOW_SMELL) continue;
if (rand() % 6 == 0) continue; // add noise
smell[y][x] = MAX(smell[y][x] - 1, LOW_SMELL);
}
}
}
Here 1d6 adds a fair amount of noise (to make it easier to see for the humans); a game might require much less noise for monsters to latch onto a hotspot, e.g. maybe a 1d20.
Anyways, there are plenty of other ideas to play with here (wind that blows the scent in a direction, for example), so this is probably a good place to stop. For now.
wherein path.c the above is adapted from
heatmap and manual page for such
https://roguebasin.com/index.php/Dijkstra_Maps_Visualized
P.S. Do not use rand(3) as it is terrible, unless you want something quick and somewhat portable. Also be sure to seed it properly on one of those not-OpenBSD operating systems.
