Pathfinding with smell maps

 Enemies in Axes, Armour & Ale find the player using various methods, from calculating a Bresenham line to the player, heading towards the players last seen location, or even just wandering aimlessly around the map.

One of the methods used is a smell, or distance, map. This is much easier to implement than A* star pathfinding or Dijkstra maps. It simply takes the players location as the starting coordinate and floodfills the walkable areas of the map with numbers that increment the further away that they get from the starting square. This is done using a Breadth First Search.

Take the simple map below, I've added point A and point B.

#  #  #  #  #  #  #  #  #  #  #  #  #  #  #  #  #  #  #  #  
#  .  .  .  .  .  .  .  .  .  .  .  #  .  .  .  .  #  #  #  
#  .  #  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  #  
#  .  .  #  .  .  #  .  #  #  .  #  #  .  .  .  .  #  .  #  
#  .  .  #  .  #  .  #  .  #  #  .  .  .  #  .  .  .  .  #  
#  #  #  .  #  A  .  .  .  .  .  .  #  .  .  #  #  #  .  #  
#  .  .  .  .  #  .  .  #  #  .  .  .  .  #  .  #  .  #  #  
#  .  #  #  .  .  .  .  .  .  .  .  .  .  #  #  #  .  .  #  
#  .  .  #  #  .  #  .  .  .  .  .  #  .  #  .  .  .  #  #  
#  .  #  .  .  .  #  .  .  #  #  #  .  .  .  #  .  .  .  #  
#  .  .  .  .  #  .  .  .  .  .  .  .  #  .  .  #  .  .  #  
#  .  .  #  #  .  .  .  .  #  .  .  .  .  .  .  .  .  .  #  
#  .  .  .  #  .  .  .  .  #  .  #  .  .  #  .  .  #  .  #  
#  .  .  .  .  #  .  .  .  .  .  .  .  .  .  .  .  .  .  #  
#  .  #  #  .  #  .  .  .  #  #  .  .  .  .  .  .  .  .  #  
#  .  #  .  #  .  .  .  .  .  #  .  #  .  B  .  .  .  #  #  
#  .  .  .  .  #  .  .  #  .  .  .  .  .  .  #  .  .  .  #  
#  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  #  
#  .  .  #  #  .  #  #  #  #  #  #  #  #  .  .  .  .  .  #  
#  #  #  #  #  #  #  #  #  #  #  #  #  #  #  #  #  #  #  #

Point A is the target, the player in this instance. 

The map is then filled like this:

99  99  99  99  99  99  99  99  99  99  99  99  99  99  99  99  99  99  99  99  
99  24  23  22  21  20  19  18  17  16  15  14  99  12  13  14  15  99  99  99  
99  25  99  21  20  19  18  17  16  15  14  13  12  11  12  13  14  15  16  99  
99  26  27  99  21  20  99  18  99  99  15  99  99  10  11  12  13  99  17  99  
99  27  28  99  22  99  2   99  4   99  99  7   8   9   99  13  14  15  16  99  
99  99  99  8   99  0   1   2   3   4   5   6   99  10  11  99  99  99  17  99  
99  9   8   7   6   99  2   3   99  99  6   7   8   9   99  99  99  23  99  99  
99  10  99  99  5   4   3   4   5   6   7   8   9   10  99  99  99  22  23  99  
99  11  12  99  99  5   99  5   6   7   8   9   99  11  99  23  22  21  99  99  
99  12  99  8   7   6   99  6   7   99  99  99  13  12  13  99  21  20  21  99  
99  11  10  9   8   99  8   7   8   9   10  11  12  99  14  15  99  19  20  99  
99  12  11  99  99  10  9   8   9   99  11  12  13  14  15  16  17  18  19  99  
99  13  12  13  99  11  10  9   10  99  12  99  14  15  99  17  18  99  20  99  
99  14  13  14  15  99  11  10  11  12  13  14  15  16  17  18  19  20  21  99  
99  15  99  99  16  99  12  11  12  99  99  15  16  17  18  19  20  21  22  99  
99  16  99  20  99  14  13  12  13  14  99  16  99  18  19  20  21  22  99  99  
99  17  18  19  18  99  14  13  99  15  16  17  18  19  20  99  22  23  24  99  
99  18  19  18  17  16  15  14  15  16  17  18  19  20  21  22  23  24  25  99  
99  19  20  99  99  17  99  99  99  99  99  99  99  99  22  23  24  25  26  99  
99  99  99  99  99  99  99  99  99  99  99  99  99  99  99  99  99  99  99  99

Using this, an enemy can track the player simply by looking at the number on their own square and moving to a square with a lower number.

#  #  #  #  #  #  #  #  #  #  #  #  #  #  #  #  #  #  #  #  
#  .  .  .  .  .  .  .  .  .  .  .  #  .  .  .  .  #  #  #  
#  .  #  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  #  
#  .  .  #  .  .  #  .  #  #  .  #  #  .  .  .  .  #  .  #  
#  .  .  #  .  #  .  #  .  #  #  .  .  .  #  .  .  .  .  #  
#  #  #  .  #  A  X  X  .  .  .  .  #  .  .  #  #  #  .  #  
#  .  .  .  .  #  .  X  #  #  .  .  .  .  #  .  #  .  #  #  
#  .  #  #  .  .  .  X  X  .  .  .  .  .  #  #  #  .  .  #  
#  .  .  #  #  .  #  .  X  .  .  .  #  .  #  .  .  .  #  #  
#  .  #  .  .  .  #  .  X  #  #  #  .  .  .  #  .  .  .  #  
#  .  .  .  .  #  .  .  X  X  X  X  X  #  .  .  #  .  .  #  
#  .  .  #  #  .  .  .  .  #  .  .  X  X  .  .  .  .  .  #  
#  .  .  .  #  .  .  .  .  #  .  #  .  X  #  .  .  #  .  #  
#  .  .  .  .  #  .  .  .  .  .  .  .  X  X  .  .  .  .  #  
#  .  #  #  .  #  .  .  .  #  #  .  .  .  X  .  .  .  .  #  
#  .  #  .  #  .  .  .  .  .  #  .  #  .  B  .  .  .  #  #  
#  .  .  .  .  #  .  .  #  .  .  .  .  .  .  #  .  .  .  #  
#  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  #  
#  .  .  #  #  .  #  #  #  #  #  #  #  #  .  .  .  .  .  #  
#  #  #  #  #  #  #  #  #  #  #  #  #  #  #  #  #  #  #  # 

This method of pathfinding is less CPU intensive than other methods, I also only update it every 3 turns. It can be used by all NPC's on the map but can only be used to find the player, not other NPC's. For the way that Axes works though, this is ideal.

Roguelikes, a very strange hobby

Disclaimer. This post assumes some familiarity with the idea of roguelike games, if not with the games themselves. This isn't a 'history of roguelikes' post, for that see here

Recently I was working on a graphical roguelike that I occasionally dust off and tinker with, Axes, Armour & Ale. It uses graphics in a very loose sense of the word, just small static tiles with no animation. I was trying to add stairs to the caves and dungeons to allow the player to go deeper and deeper into the dungeon and realised that I needed to do a lot of refactoring.

The original game just took place in a single dungeon, a la Rogue / Nethack etc, but then I decided that I wanted an overworld map as well, like ADOM.

I started pulling out bits of the code and sticking it in other places and found that I was writing lots of simple test programs in pure ASCII to try out features before committing to drawing graphical assets. In the end, I decided to do something that I had in mind when I first started Axes, write a back-to-basics, 80x25 terminal-based roguelike. With the option of later creating a GUI version from the same codebase.

With the constraints of writing a game that worked in both the Windows and Linux terminal, I found that I gained a lot more enthusiasm for the project. This was more like the games that got me into roguelikes in the first place. When I first fired up Nethack in 2002 and discovered what it was like to play a game that didn't give a damn whether you lived or died. Then I moved onto ADOM and found a game with a more cohesive story that took itself a little more seriously.

I don't play games as often as I used to now that I have kids, but a turn-based roguelike is easy to pick up and put down between episodes of Paw Patrol and visits to the local playground.

Once I was confronted with the text version of my unfinished game, it struck me that writing roguelikes is a damn strange hobby. Eschewing graphics, sound or really any advances made in game theory over the last few decades, to craft a form of entertainment that owes more to table-top role playing games and Choose Your Own Adventure books than a regular computer game. I regularly read peoples posts on r/roguelikedev  and see the vastly different approaches that people have to this genre. My approach is closer to the classic roguelikes already mentioned above.

After 2 previous attempts at writing a roguelike by following a tutorial (one in Java, and one using the Godot game engine) I'm winging it this time, with no tutorials to refer to. I've set myself some limitations, after writing one game using OOP and one using ECS, this one will be purely functional programming. I also want a native binary that doesn't require any external libraries in order to run.

I've decided to write it in the awesome Free Pascal, whilst totally ignoring its object-oriented features. Now that I write code for fun rather than for a living, I don't have to force every type of program into an OOP structure.

At the moment I've only gotten as far as organising the user interface and the units that I'll use to write to the terminal, so it's slow going and there isn't much to show yet. But I already have a scrolling map that scrolls a lot smoother than the graphical version does.