Making Goblins Move: Breadth First Search Algorithim.


Welcome to Part Two of my Making Goblins move series. In the last article we talked about giving tiles values, and having
Goblin follow values as they increased or decreased. That works on a very base level, but it still kinda looks like our Goblin is
actually a cat that got into the garbage and ate some coffee Grinds. Its also rather debatable as to if its any better than generating
random directions and moving spaces. So just as our goblin friend has begun to crawl, were gonna chop his legs off
and start over, and fining a better way to get those goblins moving.
So what other ways can we make our goblin Move? Algorithms. Real world problems solved by math. And you cant talk about algorithims
without bringing up data structures, because there's no use applying the right algorithim to the wrong data structure
and sacraficing everything you would have gained. The data structure i use for the layout of game maps is a struct that looks like this:

Tile for a map:
        struct Point {
        int x, y;
        char sym;
        bool blocks;
        };
        


Take a bunch of those and throw them into a 2d array, and bang! game map. And i have a sneaking suspicion,
a lot of other peoples have something very similar. For an actual game, the attribute list grows longer when you
add properties like populated, color, etc. but for this exercise those are the attributes that matter,
  As you've probably have noticed, Point is exactly what it sounds like. A grouping of x and Y values representing a point on a map, which
in our case is a grid. And a point can also be a location on a graph.

Thats awfully convenient, for when it comes to graphs, their are plenty of algorithims that deal with graph traversal
or "going from one point on a graph, to another point on the graph."
Were also going to need to talk about distance, what it means, and how it can be represented. When your talking about distance,
most people instinctivly think of euclidean distance, a straight line from point to point, or "as the crow flies."
In the previous article, i talked about using euclidan distance to assign values to tiles, but somewhat skated over
the details, so heres a quick run down on the equation for telling the distance between two points in straight line:


That is, if you have the x/y points of two locations on the Map:

Point A is at 11/6
and

Point B is at 15/9
Following the above Equation we would:
x2 - x1 = 15 - 11 = 4
and
y2 - y1 = 9 - 6 = 3
squaring each then results in:
4^2 + 3^2
or
(4*4) + (3*3) = 16 + 9 = 25
and all thats left is to find the square root of 25: 5


So now that we now the math behind finding the distance between two points, lets look at a function in C++ program to calculate the answer?
Using the Point struct i mentioned earlier, the equivelant function for the above math would be:

=

Code for the above: euclidean.cpp


Types of distance

Other than the equation we just covered for euclidean distance which as we showed is fancy way of saying in a straight line, the two other types of distance
that are relevant to our pursuit, are "Manhattan Distance", named after my home town, and Absolute Distance, unfortunatly not named
after the vodka. Manhattan distance is what you use to tell someone your 8 blocks away, its derived by only using right angle turns, because
in manhttan, you cant walk diaganoly through a building to get where you need to go, you walk around the outside edge of the building.
This handy graphic, which i didn't make, sums it up nicely:


When talking about graphs and graphing algorithims, the word "edges" comes up alot, for our purposes, an "edge" is the connecting edge thats drawn between
two points. Counting edges from start to finish is one way of determining Manhattan distance. These arent the only kinds of distance used, theres distances for 3d planes (a z axis!), and other ways of deriving distance in a 2d plane, but these will do for what we need for now. So now that we know
what were dealing with lets get these slimey green Goblin's walking around the map. Do to that, were going to be using an algorithm called "Breadth First Search".


Path finding using the BFS algorithm,
represented by the orange * symbols. Manhanttan distance listed with the units being
"points" traversed

.

BFS, like other graph traversal algorithms, is used for searching for points on a graph, it's a "greedy" algorithim, because its used to
search an ENTIRE graph, unless you specifically tell it to stop, limit its range somehow. Once you start modifying it by introducing heuristics
you end up with Djikstra's Algorithm, or A* (both of which are also graph traversal algorithms). BFS's complexity is relative to the total amont of vetices + the total amount
of edges. One down side is that it has the potential to become "stuck", if your graph contains whats called "cycles"(think endless loop). But this can
be avoided through both careful implementation, and careful map planning, the latter of which isnt such a trivial task with randomly generated content
BFS as applied is broken down like this:


Breadth First Search Algorithm Process
  1. Have a starting point, start, and add it to a queue
  2. Take the first member of the queue, and pop it off, labeling it as current
  3. add this member to the visited list.
  4. push all Points adjacent to the current point that are not on the visited list to the queue
  5. go back to step two and repeat until you either reach your the point your looking for, or the queue is empty, meaning it has searched the whole map.

A queue, is a fancy word for a line of items that progresses by adding things to the back, and taking things from the front
If you're familiar with the stack programming such as in assembly, queues use the same terminology of pushing items onto the the queue, and poping
items off, though a queue works on the "First in, First out" principle of adding to the back and taking from the front.


  1. std::queue - A first in, first out container of values
  2. std::vector - An array of N or more contiguous values
  3. std::unordered_map - one of the key/value pair containers supported by the STL(another option would be to use std::set)

So right off the jump we know we need to include the <queue> header, <vector> header, and <unordered_map> headers in our include list.
We will also need the <algorithim> header. So we have our algorithim chosen, we have our containers picked out, and we have our data structure.
We're almost ready to get boogying. But first we need to add a couple operators to our Point struct to stop the compiler from whining. They also make our
life much easier so theres that.. By adding operator==, operator!=, and operator= to our Point we'll be able to compare and copy them that much easier.
the one operator which is absolutly necessary is the less than operator: operator< . We need this because unordered_map uses std::less for storing values.
Lets take a look at our new Point struct:

New & Improved Point
    struct Point {
        int x;
        int y;
        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;
        }
        bool operator < (const Point& other) const
        {
        return std::tie(x,y) < std::tie(other.x,other.y);
        }
      };


without adding the < operator, our code will not compile. We're also going to use a hash for our key in the unordered_map to make inserting
and retrieval easier, unordered_map uses a hashing function, but since were using our own type (Point) std::hash wont work out of the box which is the STL default,
so we'll use, the functio below to make a hash from our x/y pair, x is xor'd to y after y is shifted four bytes. to retrieve it you would just "N & 4".
the reason we shift y is because of the way xor works. if we relied on just using xor we'd run the risk of having keys that didnt map back to the proper value

   struct hashkey {
    std::size_t operator()(const Point pt) const {
      std::size_t x = std::hash()(pt.x);
      std::size_t y = std::hash()(pt.y >> 4);
    return x^y;
  }
};

With that all out of the way we can start putting a class together, as mentioned earlier, our class is going to need a queue, and
an unordered map, were also going to have an array containing coordinates for the directions a charachter can move in. We're going
to use four directions, up, down, left, and right, but if your game allows diagonal movement you need to add another four directions
for the diaganol moves. i defined an std::array in my class, and populated it in the constructor. We're also going to need to functions
for a way to check that were still on the map, and a way to determine if the tile were checking is available to be moved to(i.e not a wall, etc)
along with a function to perform the actual search. i also perform the adjacency check in its own function, but it doesnt need to be.
So with our functions and containers our class definition looks like this:

        bFirst::bFirst(World* map)
{
   this->map = map;
   Point N({0,-1,'^'});
   Point S({0,1,'v'});
   Point E({1,0,'>'});
   Point W({-1,0,'<'});
   cdir[0]=E; cdir[1]=N; cdir[2]=W; cdir[3]=S;
}

bool bFirst::inBounds(Point p)
{
     return 0 <= p.x && p.x < map->mapW && 0 <= p.y && p.y < map->mapH;
}

int bFirst::addNeighbors(Point current, Point target)
{
int addToQueue;
bool beenchecked = false;
for (auto dir : cdir)
{
   Point next;
   next = new Point({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.x == next.x && all.first.y == next.y)
         beenchecked = true;
      }
      if (beenchecked == false) {
         que.push(next);
       camefrom[next] = current;
    }
  beenchecked = false;
}
}
return addToQueue;
}

void bFirst::bFS(Point origin, Point target)
{
   reset();
   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);
   }
}

std::vector bFirst::getPath(Point start, Point target)
{
   std::vector path;
   bFS(start, target);
   Point current = target;
   while (current != start) {
      path.push_back(current);
      current = camefrom[current];
      std::cout<layout[current.x][current.y].s = '*';
   }
   std::reverse(path.begin(),path.end());
   path.push_back(start);
   return path;
}

void bFirst::reset()
{
 while(!que.empty())
 {
   que.pop();
 }
 camefrom.clear();
}
    



And there you have it, the breadth first search in all of its glory. The if (current == target) statement is
is whats called "Early Exit", meaning that once its found the target, the search is over, otherwise it will happily go on
exploring the entire map. As it stands, all of the Points that were scanned starting with the point specified have been saved
in the unordered_map, "camefrom", with its key being the hash of the Point that it came from. Using the data stored in camefrom
we need a way to arrange the data into a list of points which make a path from the origin point to the target
point. That function is the getPath function shown above looks like this:

    std::vector bFirst::getPath(Point start, Point target)
        {
           std::vector path;
           bFS(start, target);
           Point current = target;
           while (current != start) {
              path.push_back(current);
              current = camefrom[current];
              std::cout<layout[current.x][current.y].s = '*';
           }
           std::reverse(path.begin(),path.end());
           path.push_back(start);
           return path;
        }
 

Much Better. now we have a function that when given a start point and target point will conduct the search, and return a
a vector containing the coordinates of a path between the two points. Keep in mind that the path returned will be in reverse
Theres a few ways you can handle that, you could use vectors .rbegin & .rend with a reverse_iterator to move through the vector
or you can use std::reverse(path.begin(), path.end()) to reverse the order in which its stored. From here, its a rather trivial affair of using it to
to make goblins move. Assuming we're creating a game, and we have a class for goblins that contains a "move" function, like
this one:

        class Goblin {
            Point location;
            public:
            void moveTo(Point newLocation);
            };
            void Goblin::moveTo(Point newLocation)
            {
               this->location.x = newLocation.x;
               this->location.y = newLocation.y;
            }
    

We can now create a function that uses the getPath() function we made, to direct the goblins movement, it woud look something
like this:

    class Goblin {
        public:
        Point location;
        int stepstaken;
        std::vector trail;
        void moveTo(Point newLocation);
        bool automove(target);
        };
        bool Goblin::automove(Point target)
        {
        
        Point next;
        std::vector::iterator it;
        it = this->path.begin();
        std::advance(it, this->stepstaken);
        next = *it;
        if (next != target)
        {
        moveTo(next);
        return false;
        } else {
        moveTo(next);
        return true;
        }
        }
    

And there you have it, a way to move your goblins from any point to any other point on the map while avoiding obstacles!
Theres lots you can do with this, as the article just barely scratched the surface, be creative, have fun, and make those
goblins move!!!
All of the code present here with a complete working demonstration is available on my GitHub: http://github.com/maxgoren/goblins
The code is also available for download as a compressed tarball directly from my server: Here All code made available vie the MIT FOSSF License.


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