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.


Posted

in

, ,

by

Tags:

Comments

Leave a Reply

Your email address will not be published. Required fields are marked *