Part 3: More than one way to move a Goblin


       Hello and welcome to part 3 of my Making Goblins Move series. In part one i focused on euclidean
distance and showed how to make a rudimentary flow map based on such. In part two I introduced the
the concept of Manhattan Distance as well as implementing the Breadth First Search algorithm. In this article i will cover 2 more
main stays in the Roguelike development world for pathfinding: Dijkstras Algorithm, and A*. I will also demonstrate how to combine
Breadh First Search, with the flow map concept to make a superior influence map than one based on euclidean distance, which is commonly
called a "Dijkstra Map" in the Roguelike dev world, and an influence map everywhere else. You may want to re-read Part two for a refresher
on Breadth First Search before continuing.



Algorithms, Algorithms, Algorithms


       Apart from sorting and searching, graph/tree traversal is probably on of the most studied areas of algorithims and computer science
due in large part to its myriad "real world" applications. From network routing, to GPS directions, Google Maps, to circuit board design,
train scheduling and dispatch to a million other uses, knowing how to get from Point A to Point B (litterally and figurativly) is an
important ability, especially if you need to get from Point A to Point D, while avoiding Point C, etc, etc. The two most commonly
encountered techniques are the aformentioned Breadth First Search(BFS), and the Depth First Search(DFS), and countless variations of both
for countless different criteria. As can be inferred from the names, BFS explores nodes and edges laterally before continuing to the next level
while DFS goes down as far as it can before moving to the next lateral node. Most graph traversal algorithims are based on one or the other
of these two methods.


       Of the various adaptations of BFS, the two most commonly used in Roguelike development are Dijkstra's Algorithm(DA) and A*
DA differs from the simple BFS by taking into account the varrying "cost" of movement. A basic example of this is: if there are two
Paths leading from Point A to Point D and both are the same distance, how ever one path is through knee deep mud and the other is
paved asphalt, taking the paved route wont "cost" as much. By keeping track of both distance AND cost, DA returns the "cheaper" i.e.
the better of the two paths. It's implemntation is remarkably similar to Breadth First Search because it is in fact a variant of it.
By utilizing a Priority Queue instead of a regular Queue we have what we need to implement DA. I am going to show the code
for DA alongside BFS as to emphasize both their similarities and differences.

Common Pathfinding Algorithims Explained

       It should be noted that the algorithims as they are applied to roguelike dev are not "pure" applications of the algorithims,
meaning theyre modified to better meet the needs of the roll in which they serve. One example of this is the "early exit"
implementation of BFS. If supplied with a target, an early exit implementation will stop the search ones the target is encountered,
where BFS in its pure form explores the entire graph. Another example would be when using Dijkstras Algorithm to start with a specific
node and search out from there. Once again Dijkstras Algorithm is meant to be started by loading ALL points into an array or list and
assigning them an initial value. For the purposes that it used in an RL, this is cumbersome and wasteful, and unnecessary. The purpose
of doing this is so that nodes wont be analyzed more than once, the reality is that a node being visited twice or multiple times is not
a major hinderance to performance.
Lets take a look at DA and BFS(note: The algorithims shown below both incorporate "early exit"):

Dijkstras Algorithim Breadth First Search
void dijk::dijkSearch(Point origin, Point target)
{
   Point start;
   Point current;
   int level = 0;
   start = origin;
   pque.emplace(start, start.t_cost);
   camefrom[start] = start;
   effort[start] = 0;
   while (!pque.empty())
   {
      current = pque.top().value;
      pque.pop();
      if (current == target)
          break;
      addDijkNeighbors(current, target, level);
   }
}

void dijk::addDijkNeighbors(Point current, Point target, int level)
{
  Point next;
int thiscost = 0;
for (auto dir : cdir)
{
   next = {current.x + dir.x, current.y + dir.y, dir.s};
   next.costm = map->layout[next.x][next.y].costm;
   if (inBounds(next) && map->layout[next.x][next.y].blocks == false)
   {
     for (auto all : effort)
     {
        thiscost = effort_now(next) + effort[current]; 
        if (effort.find(next) == effort.end() || thiscost < effort[next]) 
        {
            effort[next] = thiscost;
            camefrom[next] = current;
            pque.emplace(next, thiscost);
         }  
        }
      }
     }
}
            
void bFirst::bFS(Point origin, Point target)
{
   Point start;
   Point current;
   start = origin;
   que.push(start);
   camefrom[start] = start;
   while (!que.empty())
   {
      current = que.front();
      que.pop();
      if (current == target)
          break;
      addNeighbors(current, target);
   }
}

void bFirst::addNeighbors(Point current)
{
  Point next;
  bool beenchecked = false;
  for (auto dir : cdir)
  {
   next = {current.x + dir.x, current.y + dir.y, dir.s};
   if (inBounds(next) && map->layout[next.x][next.y].blocks == false)
   {
     for (auto all : camefrom)
     {
       if (all.first == next)
         beenchecked = true;
      }
      if (beenchecked == false) {
         que.push(next);
       camefrom[next] = current;
    }
      beenchecked = false;
   }
  }
}
            

It should be noted that both of those algorithims are set up to scan a grid in the form of a 2D Array of the following

    struct Point {
        int x;
        int y;
        int costm;
        int level;
        char s;
        bool blocks;
        color_t color;
        bool operator==(const Point& other) const {
            return x == other.x && y == other.y;
        }
        bool operator!=(const Point& other) const {
            return x != other.x || y != other.y;
        }
        Point operator=(Point other) {
            x = other.x;
            y = other.y;
            s = other.s;
            return other;
        }
        Point operator=(Point* other) {
            x = other->x;
            y = other->y;
            s = other->s;
            return *other;
        }
                
        bool operator < (const Point& other) const
        {
            return std::tie(x,y) < std::tie(other.x,other.y);
        }
        
        bool operator >(const Point& other) const{
            return std::tie(x,y) > std::tie(other.x,other.y);
        }
                    
        Point(int x, int y, char s, int cost) : x(x), y(y), s(s),costm(cost) { }
        Point(int x, int y, int cost) : x(x), y(y), costm(cost) { }
        Point(int x, int y, char s) : x(x), y(y), s(s), costm(1) { }
        Point()
        {
                
        }
};             
            

       As you can see both algorithims are executed in a very similar manner. The only difference in the Search functions of
both algorithims, is that in Dijkstras Alorithim, as stated earlier, the Queue has been replaced by a Priority Queue, and a
second Map has been added: effort[] which logs the cost of moving to the corresponding Point. Now, i may have downplayed
The importance of changing the Queue to a Priority Queue, Because this is one of two ways (the other will be discussed below)
That the ordering of nodes visited is changed. This change in order is the reason that even on graphs which DONT have an associated
cost of movement that Dijkstra's Algorithim produces a different path than Breadth First Search.
       The add neighbors function is where the other difference arises (note: this section of code CAN be included in the previous function,
i seperate it into two functions because i believe it is clearer to read). In the Breadth First version, it simply checks if
a node has been visited, and if it has not, marks it as visited and records what previous node was visited before it. The Dijkstra
version works much the same way, with one important caveat: it checks if it has been visited OR if the cost of visiting it is lower
than the cost of a previous node that visited it. This makes a significant impact on what nodes make it to the Queue and which don't. If we are applying Dijkstra's algorithim to a graph where the cost of movement is all the same: either you can move, or you cant, it will
produce similar, all be it perhaps a slightly straighter path. The following pictures succintly display the different outcomes of applying
Both algorithims to the same graph:

Breadth First Search Algorithim:
Dijkstra's Algorithim
Both Algorithims:

       As you can see in picture one, The path produced by BFS is comprised of straight paths, turning only when encountering
a "hard obstacle", meaning one which it can not step to at all, where as the path produced by Dijkstra's algorithim winds its way
down to the tunnel, and then weaves through blue spikes before heading up to the Goal, where BFS plowed right through them. this is
whats meant by choosing a path by "cost" or "effort", is it worth it for the path to ignore an obstacle or go through it? At the
Blue spikes, the cost difference was worth weaving around them, where as the cost of avoiding the yellow lines just before the goal
was such that it was "cheaper" to go straight through them then weave a path around. Another interesting difference between the two, is
when each deemed when to turn in the tunnel, with Dijkstra going down at the first drop, and back up at the first opportunity, where
BFS did not turn down, nor back up until otherwise forced.


        The other common path finding algorithim that is frequently encountered is the A* algorithim.
A* is based on Dijkstras algorithim, but incorporates a heuristic. A heuristic is essentially making a guess of what might be the best outcome
based on an assumption that may, or may not be correct. I'm not going to go heavily into the topic, as it is beyond the scope of this article.
for now lets suffices to say that when applied, a heuristic must be "admissable", meaning it must not overestimate. With A* we are once again dealing
with cost, but we are now adding the additional step of trying to ascertain which next move would be the most efficient, thus limiting the number of
of nodes visited. Because of their similarities, i'm only going to show the addNeighbors and heuristic function for A*, as the rest is exactly
the same as shown above for Dijkstra's algorithim.


    int heuristic(Point A, Point B)
    {
        return std::abs(A.x - B.x) + std::abs(A.y - B.y);
    }
    
        void dijk::addDijkNeighbors(Point current, Point target, int level)
        {
        Point next;
        int thiscost = 0;
        for (auto dir : cdir)
        {
           next = {current.x + dir.x, current.y + dir.y, dir.s};
           next.costm = current.costm;
           if (inBounds(next) && map->layout[next.x][next.y].blocks == false)
           {
             for (auto all : effort)
             {
                thiscost = effort_now(next) + effort[current]; 
                if (effort.find(next) == effort.end() || thiscost < effort[next]) 
                {
                    effort[next] = thiscost;
                    camefrom[next] = current;
                    pque.emplace(next, thiscost + heuristic(next, target)); // <----A*
                 }  
                }
              }
             }
        }    
    

       When run on the same map as BFS and Dijkstra, A* comes up with yet a different path, and depending on point of origin the difference
of even on tile produces a vastly different, allbeit valid path to get from start to the first tunnel. This is because when presented with a map
that contains the same cost of movement for any of the tiles, it selects one pretty much at random. I wont go through displaying it all here
but its a fun exercise to do yourself, Full code for BFS, Dijkstra, and A* is available at the bottom of this page via Github, or directly as
a compressed tarball. In the meantime, lets see what A* cooked up, for at least one try:


       When you compare the Three, A* comes up withsomething somewhat in the middle of the BFS and Dijkstra. The reasoning behind it is thus(not my words):
"If the heuristic function is admissible, meaning that it never overestimates the actual cost to get to the goal, A* is guaranteed to return a least-cost path from start to goal."

       Now armed with the various algorithims, when applied properly Your Goblins can find there way in the dark, one method for doing so that
will work any of the three is shown in Part Two of this series.

But seeing as this Part 3 of Making Goblins Move, how no fear: There is yet another way!


Influence Maps, AKA "Dijkstra Maps"

       Influence maps are fantastic way to deal with moving your Goblins around in a Roguelike. The concept
is simple, and with a little creativity rather easy to implement. The basic idea is that you have a position of value, a main point of fixation if you will. In our case, thats the player.
by noting the distance of every point on the map from said position, and assigning the distance as a value to the tiles, we essentially form
concentric rings around the position consisting of values in ascending order. Kind of like ripples forming on a pond when you throw a rock in it. Then, as our stinky evil hearted goblin moves through his odious dungeon of decay, he(or she, its an equal opportunity odious dungeon of decay afterall) is scanning his surroundings and
stepping to the tile that has the lowst value in relation to the one he is standing on*.
Does that sound familiar? It should after studying the pathfinding algorithms above.
I will admit, at first i was wondering where the HELL the name "Dijkstra Map" came from, because you would think from the name that it is a map
that is generated using Dijkstra's Algorithm. But that's not where the name comes from. The name is derived from how our snivelling little tomb raiding goblin process the map in order to move across it.
Our Goblin, bless his little goblin heart, is using Dijkstra's algorithm: "scanning his surroundings, and stepping to the tile with the most appropriate value"
i.e. weighing the cost of his immediatly adacent points and choosing the one which fits his priority.
Mystery solved.

The end result? The goblin "Rolling down" the values towards The designated position, and aint no stupid corners or barriers gonna stop him.
. There are two very good articles on the subject on Rogue Basin, both of which refer to it as "Dijkstra Maps"(googling "influence maps" will yield even more information):

       In Part One of this series, I introduced the concept of Influence Maps using nothing but Euclidian
distance. This works, to an extent but it has inherent problems of: Not taking into account obstacles that are in its way. And unless there is unobstructed line of site
to the target the goblin will not be able to reach it. I.e. corners, and especially something like an S curve is pretty much a deal breaker for our Euclidian Goblin.
In essence, hes following a path, but hes not pathfinding, and the path may be wrong.
The following method fixes that by replacing the way we assign step. values to each tile. Instead of using Euclidian distance as we did in Part One we are going to use Breadth First to assign value
to every node as it iterates through the Array of tiles. The effect of this is that unlike assigning values line-of-site distance
obstacles will be taken into consideration resulting in a path around the obstacle instead of our Goblin being obstructed.


The implementation of this requires several changes to how we use BFS:

  • We will be plotting the whole map..
  • We need a way to track the distance of every tile from the starting point
  • we need a way from that information to be available to the Goblins for movement
  • the map must be updated if the player moves.


First things first, lets make the necessary changes to the algorithim, and then ill explain how i implemented it for moving Goblins
To the search function we add an integer to record the "level", i.e. how far we've gone from the starting point. We then need a way to know
When to increment that value. Theres many ways to do this, but the simplest way, is to just the value of 'next' to 'current + 1' By repeatedly doing this we are left with concentric rings of values that stretch around obstacles that the Goblins
can follow.
Lets take a look at our new Search Function:

void bfMapper::setMapValue(Point start, int cut)
{
   Point current, next;
   std::vector<std::vector<bool>> seen;
   seen.resize(mapW,std::vector<bool>(mapH));//nodes we've already checked
   start.level = 0;      //distance from current
   que.push(start);   //add our position to the queue
   seen[start.x][start.y] = true; //mark it as visited
   while (!que.empty())
   {
     current = que.front(); que.pop();    //take first node off the queue
      if (level == cut)     //for making "sub maps" around items, etc.
        break;
      for (auto dir : cdir) //cdir is an array of {-1,0}{1,0}{0,-1}{0,1} etc.
      {
        next = {current.x + dir.x, current.y + dir.y, dir.s}; //apply cdir values to current
        next.level = current.level + 1; //were tile out from current, so value increases
        if (inBounds(next) && map->layout[next.x][next.y].blocks == false) //check were still on the map
        {
          if (!seen[next.x][next.y]) //have we already assigned a value?
          {
            que.push(next);         //add to queue for processing neighbors
            seen[next.x][next.y] = true;    //mark as visited
	          map->layout[next.x][next.y].level = next.level; //assign the map tile its distance from start;
          }
        }
      }
   }
   que.clear();
   start.level = 0;
}
    

As you can see, were derriving the value of 'next' from 'current' to get the proper level. I use the term level because under the hood, the nodes are being
traversed like a graph/tree, which is original purpose of BFS. Lets take a look at the changes to the addNeighbors function:
Oh look at that, we've merged the two functions together. As i've said previously, the addneighbors function doesnt NEED to be it's
own function, its just easier to read code wise, a little less cluttered in my opinion. But since we'll be calling this mapping function
EVERY TIME the player moves, having one less function call to process helps in the performance department. It's also important to node that we're using
a pointer to the map not the map object itself, as repeatedly passing the map back and forth would quickly drain performance(the fully populated map is around 14MB).

Were also now setting the value of each tile directly on the map grid instead of using a key/value container to mark where we came from. The resulting map looks like this(Color and numbers/letters added for clarity):


As you can see, the values of the tile increment in a way so that it can curve around barriers. This allows our Goblin to move to the player
without bouncing repeatedly against a wall or getting stucking in a corner:


not the best gif ever made, but you get the idea.

Making the Goblin move


       Allright, i know ive thrown alot of information at you in this one, and your probably wondering if i'm ever
going to get to the damn point and show you how to make the damn Goblin get to stepping. So without further ado, lets get to it. In the previous section
We saw how the our modified BFS kept track of levels, and changed our addNeighbors function to plot that on the map as an incrementing value. So now, in order
to get our goblin truckin' all we have to is create a function for goblin movement that:
  • Using the goblins current position check the cooresponding tile/point on the map and note the value of its position
  • Scan the tiles that immediatly adacent to its position that are open for being stepped to and compare their values to the value of the current tile, as well as to each other
  • Step to the tile with the lowest value relative to their current position.

This is a fairly straight forward process. In fact, its VERY similar to the adjacency matrix implementation of Dijkstra's Algorithm, using distance as the weight. And seeing as "scanning the immediatly adjacent tiles" is exactly what the addNeighbors function does, we have a good starting point
for what we're about to do. The following code is how i implemented this:

void moveEnt(ent* g, World* map)
{
  int bestValue = 1000; //dummy value arbitrarilly high to gaurentee first comparison sets a proper value.
  Point best;   //the point chosen to move to.
  Point checking; //the point being analyzed
  Point cdir[4] = { {-1, 0}, {1, 0}, {0, -1}, {0, 1}  }; //values to apply to g->pos to get current.
  for (auto dir : cdir)
  {                                 //loop through checking all the directions
    checking.x = g->pos.x + dir.x;
    checking.y = g->pos.y + dir.y;
    checking.level = map->layout[checking.x][checking.y].level;
    if (checking.level < cost && map->layout[checking.x][checking.y].blocks == false 
    && map->layout[checking.x][checking.y].populated == false)
    {                                   //If the value being checked is lower than the current lowest &&
      bestValue = checking.level;       // the point is one that can be walked on && theres not another 
      best = checking;                  //goblin/NPC already occupying the tile.
    }
  }
  map->layout[g->pos.x][g->pos.y].blocks = false;       //set the currently occupied point to
  map->layout[g->pos.x][g->pos.y].populated = false;    // make it unoccupied
  g->pos = best;                                        //set the goblins position as the one we chose as best
  map->layout[g->pos.x][g->pos.y].blocks = true;        //set the newly occupied current point to occupied. 
  map->layout[g->pos.x][g->pos.y].populated = true;
}
    

how to make those goblins move

So now we have an influence map created, and a way for the goblin to move around by using it. awesome but theres more. What is we want our
Goblins to have more varied behaviour than to just head to one Point? What if our Goblin has other jobs to do than just head to/attack the player?
lets take the example of the goblin seeking out the player, but ALSO seeking out items that are scattered through out the dungeon. The influence map created
around the player is what we'll call the "alpha influence map", this map is updated every time our player changes his position so that the goblin is
always heading to the right spot. BUT, if we implement the idea of the "early exit" from the algorithims i talked about above. we can make smaller influence
maps, "beta influences" if you will with smaller fields of attraction than the alpha map, we then merge the alpha an beta maps to create a map with areas
that can "distract" the goblin from its primary mission. To better visualize this, ill show you an influence map applied to one of the dungeons from my
rogelikedev code-along 20/20 project:



behold!

As you can see in the image, the alpha influence map is created focusing around the player "@"'s position. The items however, which are representd by the "&" symbol each have their own beta maps, or "spheres of influence" surrounding them. This functions to draw the goblins off the main path and towards the item
once the item is collected, the beta map is erased and the alpha maps influence values replace it.


Just as we've used the concept for attraction, we can also use it to repel: If we keep everything the same, except that we designate the starting
level as say, 100, and decrement the values as you get farther from the origin, the goblins will flee AWAY from that point instead of towards it.
Combined with "early exit" so the inversed field only goes out say levels, you can have a pretty neat "force field" effect.

    void bfMapper::setInverseValue(Point start, int cut)
    {
       Point current, next;
       std::vector<std::vector<bool>> seen;
       seen.resize(mapW,std::vector<bool>(mapH));
       start.level = 100;      //distance from current now starts at 100 instead of 0
       que.push(start);   
       seen[start.x][start.y] = true; 
       while (!que.empty())
       {
         current = que.front(); que.pop();    //take first node off the queue
          if (level == cut)     //for making "sub maps" around items, etc.
            break;
          for (auto dir : cdir) 
          {
            next = {current.x + dir.x, current.y + dir.y, dir.s}; 
            next.level = current.level - 1; //now we're lowering the value instead of increasing
            if (inBounds(next) && map->layout[next.x][next.y].blocks == false) 
            {
              if (!seen[next.x][next.y]) 
              {
                que.push(next);         
                seen[next.x][next.y] = true;    
                map->layout[next.x][next.y].level = next.level; //assign the map tile its distance from start;
              }
            }
          }
       }
       que.clear();
       start.level = 0;
    }
  

There's much more you can do with influence maps and the article i linked to above, The Incredible Power of Dijkstra Maps covers them in great detail.

Thats All for this installment of Making Goblins Move. Its my sincere hope that you found the information presented both clear and usefull. As always, all the code
presented and discussed here is available under the MIT license and can be downloaded from my GitHub: http://github.com/maxgoren/goblins


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