A* algorithm on a 2D vector of enum

Question

here is the A* implementation:

#include <queue>
#include <stdexcept>
#include <unordered_map>

enum class TileType {
  DebugWall,
  Empty,
  Floor,
  Wall,
  Obstacle,
  Player,
  HealthPotion,
  ArmourPotion,
  HealthBoostPotion,
  ArmourBoostPotion,
  SpeedBoostPotion,
  FireRateBoostPotion
};

template<class T>
inline void hash_combine(size_t &seed, const T &v) {
  std::hash<T> hasher;
  seed ^= hasher(v) + 0x9e3779b9 + (seed << 6) + (seed >> 2);
}

struct Point {
  int x, y;

  inline bool operator==(const Point pnt) const {
    return x == pnt.x && y == pnt.y;
  }

  inline bool operator!=(const Point pnt) const {
    return x != pnt.x || y != pnt.y;
  }

  Point() = default;

  Point(int x_val, int y_val) {
    x = x_val;
    y = y_val;
  }

  std::pair<int, int> sum(Point &other) const {
    return std::make_pair(x + other.x, y + other.y);
  }

  std::pair<int, int> abs_diff(Point &other) const {
    return std::make_pair(abs(x - other.x), abs(y - other.y));
  }
};

template<>
struct std::hash<Point> {
  size_t operator()(const Point &pnt) const {
    size_t res = 0;
    hash_combine(res, pnt.x);
    hash_combine(res, pnt.y);
    return res;
  }
};

const std::vector<Point> INTERCARDINAL_OFFSETS = {
    {-1, -1}, {0, -1}, {1, -1}, {-1, 0}, {1, 0}, {-1, 1}, {0, 1}, {1, 1},
};

struct Neighbour {
  int cost;
  Point pair;

  inline bool operator<(const Neighbour nghbr) const {
    return cost >= nghbr.cost;
  }
};

std::vector<Point> grid_bfs(Point &target, int height, int width) {
  std::vector<Point> result;
  for (Point offset : INTERCARDINAL_OFFSETS) {
    int x = target.x + offset.x;
    int y = target.y + offset.y;
    if ((x >= 0 && x < width) && (y >= 0 && y < height)) {
      result.emplace_back(x, y);
    }
  }

  return result;
}

std::vector<Point>
calculate_astar_path(std::vector<std::vector<TileType>> &grid, Point &start,
                     Point &end) {
  std::vector<Point> result;
  std::priority_queue<Neighbour> queue;
  std::unordered_map<Point, Point> came_from = {{start, start}};
  std::unordered_map<Point, int> distances = {{start, 0}};
  int height = (int) grid.capacity();
  int width = (int) grid[0].capacity();
  queue.push({0, start});

  while (!queue.empty()) {
    Point current = queue.top().pair;
    queue.pop();

    if (current == end) {
      while (!(came_from[current] == current)) {
        result.emplace_back(current.x, current.y);
        current = came_from[current];
      }

      result.emplace_back(start.x, start.y);
      break;
    }

    for (Point neighbour : grid_bfs(current, height, width)) {
      if (grid[neighbour.y][neighbour.x] == TileType::Obstacle) {
        continue;
      }

      int distance = distances[current] + 1;
      if ((!came_from.contains(neighbour)) || distance < distances.at(neighbour)) {
        came_from[neighbour] = current;
        distances[neighbour] = distance;
        queue.push({distance + std::max(abs(end.x - neighbour.x), abs(end.y - neighbour.y)), neighbour});
      }
    }
  }

  return result;
}

The main problem I have right now is the order in which INTERCARDINAL_OFFSETS is iterated through. Since the bottom-right direction is last so it will always prefer going in the bottom-right direction since that node is added to the heap last. Is there a way I can improve this implementation?

Answer 1

Make better use of class Point

I see you created a class Point that represents a 2D coordinate, but you are not making very good use of it. Instead of the weird sum() member function that returns a std::pair<int, int> and which you don't even use, consider adding an operator+() member function that returns another Point:

Point operator+(const Point& other) const {
    return {x + other.x, y + other.y};
}

Then you can change grid_bfs() like so:

std::vector<Point> grid_bfs(Point target, …) {
    std::vector<Point> result;
    for (Point offset: INTERCARDINAL_OFFSETS) {
        Point grid_point = target + offset;
        if (…) {
            result.emplace_back(grid_point);
        }
    }

    return result;
}

Note that width and height together also form a 2D coordinate. Instead of passing those individually, pass them as a Point, and maybe name it grid_size or top_right (assuming the origin is bottom left). Then you could write:

bool is_in_range(Point point, Point max) {
    return point.x >= 0 && point.x < max.x && point.y >= 0 && point.y < max.y;
}

std::vector<Point> grid_bfs(Point target, Point grid_size) {
    …
    if (is_in_range(grid_point, grid_size) {
      result.emplace_back(grid_point);
    }
    …
}

Try to get rid of all occurences where you manually pass x and y or width and height separately, and replace them with calls to functions or operators that work on Points as a whole.

Pass by const reference where appropriate

If you pass something by reference or pointer, but you are not modifying the data that is passed in, make sure you make it a const reference or pointer. This will allow the compiler to generate more optimal code, and it will catch potential mistakes if you do accidentally write to it.

Alternatively, you can pass small things by value. For something like a Point, which only contains two ints, it might even be more efficient than passing by reference, although with optimizations enabled, the compiler will probably generate the exact same code.

Avoid unnecessary temporary variables

In this line of code:

for (Point neighbour : grid_bfs(current, height, width)) {

The call to grid_bfs() will return a temporary std::vector<Point>. That might seem innocent, but std::vector will do memory allocations behind the scenes. But you don't need need that. There are various ways around this:

1. Just manually inline grid_bfs() here:

   for (Point offset : INTERCARDINAL_OFFSETS) {
       Point neighbour = current + offset;
       if (!is_in_range(neighbour, grid_size)) {
           continue;
       }
   

2. Make grid_bfs a class that has begin() and end() member functions that return iterators that yield valid neighbour points.
3. Turn grid_bfs() into a coroutine that returns a std::generator<Point>. Made easy in C++23, but also possible in C++20 (see also Lewis Baker's CppCoro library).

Don't use at() unnecessarily

Using at() on a container will check if the element exists, and if not will throw an exception. This wastes CPU cycles if you already know the element is in the container. In this line:

if ((!came_from.contains(neighbour)) || distance < distances.at(neighbour)) {

The right hand side of || will only be evaluated if came_from.container(neighbour) is true, and since you always add items both to came_from and distances at the same time, you then know that distances will also contain neighbour.

Merge came_from and distances

You have two std::unordered_maps, but they always contain the same Points as keys. That just wastes memory and requires two lookups instead of one in most cases. You already have a struct Neighbour that holds a Point and an int, so I would replace the two maps with one std::unordered_map<Point, Neighbour> neighbours.

Answer 2

Since the bottom-right direction is last so it will always prefer going in the bottom-right direction since that node is added to the heap last.

You could add an explicit tie-breaker.

Finding shortcuts

Your implementation does check for distance < distances.at(neighbour), which is good (forgetting that part is a common mistake), but I'm not entirely convinced by the way that the new distance is subsequently handled. A new node is pushed on the heap, but an old node (with worse distance) may still exist. That could easily lead to the heap accumulating various useless nodes.

Initially I thought that would have the classic implications that usually come with that, but they are avoided, since came_from and distance are tracked outside the node that is pushed onto the heap. So whatever node is popped, will have the best-known came_from anyway, even if it wasn't the most recent version of the node.

It still has the consequence that, since there is no check to avoid double-expanding the same node, a node may be unnecessarily expanded several times. Allowing re-expansion is necessary in some unusual cases, but if you use a consistent heuristic (which you do) then you can "close" a node after it has been expanded once (having popped it off of the heap proves that it was reached via the shortest path).

An additional technique is looking up whether a node already exists in the heap and updating it in-place (moving it through the heap if necessary), but a std::priority_queue is not suitable for that (a heap that maintains a dictionary from coordinate to index in its internal vector can be used for this purpose).

capacity?

In this code:

  int height = (int) grid.capacity();
  int width = (int) grid[0].capacity();

I would expect size(), instead of capacity(). If the grid has additional capacity beyond the size, that means that space is not filled with real data, the search algorithm shouldn't be looking there.