Code Smells

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:

Start with a tiny map; they're easier to debug than something that already fills the whole screen or terminal.

Make the map non-square so that if you screw up the [x,y] versus [y,x] you probably will get an error, or things will display the "wrong way". This may not be a problem for some environments, but ncurses operates by [rows,cols] which usually translates to [y,x].

Diagramming what you think should happen on graph paper may also help. The odds of everything being wrong in the same way is lower if you've got your brain model, a paper model, and code.

You will need to handle 8-way motion if diagonal moves are allowed. The examples below only calculates for non-diagonal moves. A smell map may need to match the movement system, or have a flag for 4- versus 8- way motion.

A limited time programming challenge is not the best time to work this out. However, the pathfinding library I was using developed mysterious memory issues, so had to be tossed out.

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();
    }

smolpath.c

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.

Scent stoppers

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.

A maze of twisty passages

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:

smolpath3.c

    // 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?

Heatmap

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.

heatmap.pl

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.

twisty-smells.png

sbal-heatmap.png

More random things

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.

big-noise.png

That's all, folks!