Making Goblins Move: a look at one method of Guiding NPC movement..


8/3/2020 NOTE: When i began work on this, i intended it to be a quick article on the topic of moving goblins around
It has since grown to become a multi-part series discussing the various ways and algorithims that are commonly employed
in the process of developing a Roguelike. Enjoy! -max


Hey, welcome to this little tutorial on implementing basic NPC movement in Roguelike and other tile/turnbased games.
I came across this method of NPC movement while searching for simple ways to handle how characters move and follow players.
one that is also commonly applied in roguelikes for pathfind. I did not name this method, and honestly its name does it a disservice.
Some people call these "value flow maps", "euclidean distance maps", "weighted value maps", and the list goes on. Dijstrka Maps is what they
were labeled when i came across them, and so thats the name i've used. This isnt the most complex or robust method for dealing with NPC's, but its simple
to implement, produces reasonable results, and isnt taxing on resources, which sounds like a decent combination to me, especially if you're first starting off in game development.
I'll be using C++ for this demonstration, but the concept can be adapted to any programming language without much headache.
All code was developed under MacOS using the GNU Compiler Collection, and should compile and run on
any system with a C++ compiler (Linux, BSD) I dont see why it shouldnt work with windows.

Before we get to the coding, lets take a look at the methodology of whats being implemented. The idea is based upon assigning value to
objects, obstacles, etc on our map. Every tile is assigned said value, based on its distance from an item. Because our maps are simple two dimensional grids, this
allows guided movement by following values in an ascending or descending order. In our scenario, instead of the NPC applying a path finding algorithm between it and a
set point to guide them towards the object, instead an objects value determines the value of the tiles surrounding it. At it's most basic it works by you placing an
object on a grid, and give a value to all of the spaces surrounding it, with their worth decreasing in concentric rings as you move furthur away from the object.
That, is what the Dijstrka map is. In practice, it looks like this:

Value maps around a player.


By assignin decrementing values, and programming the NPC to determine the value of the tile it is standing on, compared to the tiles surrounding it, and changing its
place to a tile of lower value, we are able to effect movement, as the NPC follows ever decreasing (or increading, depending on your implementation) tile values.


The map with the value of every walkable tile made visible


As you can see from the image above, if your standing on one side of a wall, and the NPC is on the other side of the wall, it will just stand against the wall closest do you
like the unintelligent computer generated goblin that is. but as you move, closer to it, it will follow along the oposite side of the wall, until an opening presents itself
through which it can travel, as you can see in this sequence:

I think ill just stare at this wall for a while..
do i hear something?..
Bingo!
Whats your name?
i'll follow you everywhere!

Why would we use this?

A common problem in when first beginning making roguelikes, or any game for that matter is dealing with NPC movement.
Either getting easily stuck at a wall/corner, or being out smarted by something as simple has having to negotiate a turn.
By weighting the tiles around the player, and having the map re-calculate the value of every tile every time the player moves positions
a fluid grid of values is formed. In the image above, ive made the values of the positions surrounding our player visible. If we were to place our
character in an area of the map with a turn, you can see that the values cascade downwards around the corner:

Values flowing around a corner

By setting the radius, you can control how soon an NPC takes note of your character and begins to move toward it. Conversly, you can
invert the values, if you wanted to implement a force field around your character that would push the NPC's away. You can also set up maps
around other objects, such as items on the map, or you could throw a weighted object that would draw the NPC's off so you can high tail it
in the opposite direction if things get dicey.

A goblin takes chase.

The two most important parts of using this concept is creating the map, and having the NPC analyze their surroundings in order to choose
the proper tiles. In the following two parts of this series, we will get fairly in depth so i won't get overly detailed now seeing, as this meant to merely introduce the types of problems we will encounter, however, Below are the main code snippets for these
two tasks . Full code of the demonstration is available via compressed tarball at
the bottom of the page as well as on my GitHub which is linked below.

Code for generating values around an object
(code to add color removed)
void World::setValue(Point* pPos)
{
 int x,y;
 int distance;
 int dx,dy;
 int limiter = 6; //changing this value changes how far out the Map goes around object. 
 for (x = 1; x < mapW - 1; x++)
 {
 for (y = 1; y < mapH - 1; y++)
  { 
  dx = x - pPos->x;
   dy = y - pPos->y;
   float dist = sqrtf(dx*dx+dy*dy);
   distance = (int)round(dist);
  if (distance < limiter)
  {
  this->layout[x][y].value = distance;
  this->layout[x][y].sym = std::to_string(distance);
  } else {
  this->layout[x][y].sym = " ";
  this->layout[x][y].value = 10;

  }
  }
}
}

Calling the above method at the end of every player movement will create and update the map every turn where the players position changes.


Code For having NPC's move according to Mapped values.
void ai::moveNPC(World* map, ent* g, Point* playerPos)
{
 int least, x , y;
 Point lowest;
 int centx = g->pos.x;
 int centy = g->pos.y;
 for (x = centx - 1; x < centx + 2; x++)
 {
 for (y = centy - 1; y < centy + 2; y++)
  {
   if (map->layout[x][y].value <= least && map->layout[x][y].blocks == false)
    {
     least = map->layout[x][y].value;
     lowest.x = x;
     lowest.y = y;
    }
  }
 }
 if (map->layout[lowest.x][lowest.y].blocks == false)
 {
map->layout[g->pos.x][g->pos.y].blocks = false;
g->pos.x = lowest.x;
g->pos.y = lowest.y; 
map->layout[g->pos.x][g->pos.y].blocks = true;
}
}

Now that we have an idea of one way to begin tackling this problem, in part two & three, we will discuss even better ways
to accomplish our goal of decently moving Goblins around. Stay Tuned!

Making Goblins Move Part Two - Intelligent Pathfinding using graph search algorithms.
Making Goblins Move Part Three - By combining the graph search algorithms from part two, with the flow fields presented here
we harness the powerful technique known as "Dijkstra Maps".

Full source of the demo is available as a compressed tarball: eucmap.tar.gz
The included binary of the BearLibTerminal Library is the MacOS version.BearLibTerminal for your operating
system can be obtained here: http://foo.wyrd.name/en:bearlibterminal
Code is also available on GitHub: http://github.com/maxgoren/djmaps
All code made available vie the MIT FOSSF License.


(c) 2020 Max Goren / MaxCodes.info
maxgoren@icloud.com