A* algorithm on a 2D vector | Together C & C++ | Page 1

long jewel Mar 6, 2023, 4:16 PM

Hi, here is the A* implementation:

#include <queue>
#include <stdexcept>
#include <unordered_map>
#include "primitives.hpp"

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;
}

And primitives.hpp:

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;
  }
};

Is there any way I could improve the A* implementation?

#A* algorithm on a 2D vector