So I've been trying to convert this Python module to a C++ module and I've finished the logic, however, I've encountered some segmentation faults. The module is meant to create a binary space partition to generate the rooms, then it will use a minimum spanning tree and the A* algorithm to draw the hallways.
The map.cpp file:
// Custom includes
#include "astar.h"
#include "bsp.h"
// External includes
#include <unordered_set>
// ----- STRUCTURES ------------------------------
struct LevelConstants {
int level, width, height;
};
struct Edge {
int cost;
Rect source, destination;
inline bool operator<(const Edge edg) const {
// The priority_queue data structure gets the maximum priority, so we need to
// override that functionality to get the minimum priority
return cost > edg.cost;
}
inline bool operator==(const Edge edg) const {
return cost == edg.cost && source == edg.source && destination == edg.destination;
}
};
template<>
struct std::hash<Edge> {
size_t operator()(const Edge &edg) const {
size_t res = 0;
hash_combine(res, edg.cost);
hash_combine(res, edg.source);
hash_combine(res, edg.destination);
return res;
}
};
// ----- FUNCTIONS ------------------------------
inline std::vector<Point> collect_positions(std::vector<std::vector<int>> *grid, TileType target) {
// Iterate over grid and check each position
std::vector<Point> result;
for (int y = 0; y < grid->size(); y++) {
for (int x = 0; x < grid[y].size(); x++) {
if ((*grid)[y][x] == target) {
result.push_back(Point{
x, y
});
}
}
}
// Return result
return result;
}
void
split_bsp(Leaf *bsp, std::vector<std::vector<int>> *grid, std::mt19937 *random_generator, int split_iteration) {
// Start the splitting using a queue
std::queue<Leaf> queue;
queue.push(*bsp);
while (split_iteration > 0 && !queue.empty()) {
// Get the current leaf from the deque object
Leaf current = queue.front();
queue.pop();
// Split the bsp if possible
if (current.split(grid, random_generator, true) && current.left && current.right) {
// Add the child leafs so they can be split
queue.push(*current.left);
queue.push(*current.right);
// Decrement the split iteration
split_iteration -= 1;
}
}
}
std::vector<Rect> generate_rooms(Leaf *bsp, std::vector<std::vector<int>> *grid, std::mt19937 *random_generator) {
// Create the rooms
std::vector<Rect> rooms;
std::queue<Leaf> queue;
queue.push(*bsp);
while (!queue.empty()) {
// Get the current leaf from the stack
Leaf current = queue.front();
queue.pop();
// Check if a room already exists in this leaf
if (current.room) {
continue;
}
// Test if we can create a room in the current leaf
if (current.left && current.right) {
// Room creation not successful meaning there are child leafs so try again on the child
// leafs
queue.push(*current.left);
queue.push(*current.right);
} else {
// Create a room in the current leaf and save the rect
while (!current.create_room(grid, random_generator)) {
// Width to height ratio is outside of range so try again
continue;
}
// Add the created room to the rooms list
rooms.push_back(*current.room);
}
}
// Return all the created rooms
return rooms;
}
std::unordered_set<Edge> create_connections(std::unordered_map<Rect, std::vector<Rect>> *complete_graph) {
// Use Prim's algorithm to construct a minimum spanning tree from complete_graph
Rect start = complete_graph->begin()->first;
std::priority_queue<Edge> unexplored;
std::unordered_set<Rect> visited;
std::unordered_set<Edge> mst;
unexplored.push(Edge{0, start, start});
while (mst.size() < complete_graph->size() - 1) {
// Get the neighbour with the lowest cost
Edge lowest = unexplored.top();
unexplored.pop();
// Check if the neighbour is already visited or not
if (visited.count(lowest.destination)) {
continue;
}
// Neighbour isn't visited so mark it as visited and add its neighbours to the heap
visited.insert(lowest.destination);
for (Rect neighbour: complete_graph->at(lowest.destination)) {
if (!visited.count(neighbour)) {
unexplored.push(
Edge{
lowest.destination.get_distance_to(&neighbour),
lowest.destination,
neighbour,
}
);
}
}
// Add a new edge towards the lowest cost neighbour onto the mst
if (lowest.source != lowest.destination) {
// Save the connection
mst.insert(lowest);
}
}
// Return the constructed minimum spanning tree
return mst;
}
void create_hallways(std::vector<std::vector<int>> *grid, std::mt19937 *random_generator,
std::unordered_set<Edge> *connections, int obstacle_count) {
// Place random obstacles in the grid
std::vector<Point> obstacle_positions = collect_positions(grid, TileType::Empty);
for (int i = 0; i < obstacle_count; i++) {
std::uniform_int_distribution<> obstacle_point_distribution(0, (int) obstacle_positions.size());
int obstacle_point_index = obstacle_point_distribution(*random_generator);
Point obstacle_point = obstacle_positions[obstacle_point_index];
obstacle_positions.erase(obstacle_positions.begin() + obstacle_point_index);
(*grid)[obstacle_point.y][obstacle_point.x] = TileType::Obstacle;
}
// Use the A* algorithm with to connect each pair of rooms making sure to avoid the obstacles
// giving us natural looking hallways. Note that the width of the hallways will always be odd in
// this implementation due to numpy indexing
const int HALF_HALLWAY_SIZE = HALLWAY_SIZE / 2;
for (Edge connection: *connections) {
for (Point path_point: calculate_astar_path(grid, connection.source.center, connection.destination.center)) {
// Place a rect box around the path_point using HALLWAY_SIZE to determine the width and
// height
Rect{
Point{
path_point.x - HALF_HALLWAY_SIZE,
path_point.y - HALF_HALLWAY_SIZE,
},
Point{
path_point.x + HALF_HALLWAY_SIZE,
path_point.y + HALF_HALLWAY_SIZE,
}
}.place_rect(grid);
}
}
}
void place_tile(std::vector<std::vector<int>> *grid, std::mt19937 *random_generator, TileType target_tile,
std::vector<Point> *possible_tiles) {
// Get a random floor position and place the target tile
std::uniform_int_distribution<> possible_tiles_distribution(0, (int) (*possible_tiles).size());
int possible_tile_index = possible_tiles_distribution(*random_generator);
Point possible_tile = possible_tiles->at(possible_tile_index);
(*grid)[possible_tile.y][possible_tile.x] = target_tile;
}
std::pair<std::vector<std::vector<int>>, LevelConstants> create_map(int level, unsigned int seed) {
// Initialise a few variables needed for the map generation
int grid_width = MAP_GENERATION_CONSTANTS.width.generate_value(level);
int grid_height = MAP_GENERATION_CONSTANTS.height.generate_value(level);
std::mt19937 random_generator(seed);
std::vector<std::vector<int>> grid(grid_height, std::vector<int>(grid_width, TileType::Empty));
Leaf bsp = Leaf{
Rect{
Point{0, 0},
Point{grid_width - 1, grid_height - 1}
}
};
// Split the bsp and create the rooms
split_bsp(&bsp, &grid, &random_generator, MAP_GENERATION_CONSTANTS.split_iteration.generate_value(level));
std::vector<Rect> rooms = generate_rooms(&bsp, &grid, &random_generator);
// Create the hallways between the rooms
std::unordered_map<Rect, std::vector<Rect>> complete_graph;
for (Rect room: rooms) {
std::vector<Rect> temp;
for (Rect x: rooms) {
if (x != room) {
temp.push_back(x);
}
}
complete_graph.insert({room, temp});
}
create_hallways(&grid, &random_generator, &create_connections(&complete_graph),
MAP_GENERATION_CONSTANTS.obstacle_count.generate_value(level));
// Get all the tiles which can support items being placed on them and then place the player and
// all the items
int item_limit = MAP_GENERATION_CONSTANTS.item_count.generate_value(level);
std::vector<Point> possible_tiles = collect_positions(&grid, TileType::Floor);
place_tile(&grid, &random_generator, TileType::Player, &possible_tiles);
for (std::pair<TileType, double> item: ITEM_PROBABILITIES) {
int tile_limit = (int) round((double) (item.second * item_limit));
int tiles_placed = 0;
while (tiles_placed < tile_limit) {
place_tile(&grid, &random_generator, item.first, &possible_tiles);
tiles_placed += 1;
}
}
// Return the grid and a LevelConstants object
return std::make_pair(grid, LevelConstants{level, grid_width, grid_height});
}
The bsp.h file:
#ifndef PRIMITIVES_H
#define PRIMITIVES_H
// Custom includes
#include "primitives.h"
#endif
// External includes
#include <random>
// ----- STRUCTURES ------------------------------
struct Leaf {
// Parameters
Rect container;
// Attributes
Leaf *left, *right;
Rect *room;
bool split_vertical;
Leaf() {}
Leaf(Rect container_val) {
container = container_val;
}
bool split(std::vector<std::vector<int>> *grid, std::mt19937 *random_generator, bool debug_game) {
// Check if this leaf is already split or not
if (left && right) {
return false;
}
// To determine the direction of split, we test if the width is 25% larger than the height,
// if so we split vertically. However, if the height is 25% larger than the width, we split
// horizontally. Otherwise, we split randomly
std::uniform_int_distribution<> split_vertical_distribution(0, 1);
bool split_vertical_val = split_vertical_distribution(*random_generator);
if ((container.width > container.height) && ((double) (container.width / container.height) >= 1.25)) {
split_vertical_val = true;
} else if ((container.height > container.width) && ((double) (container.height / container.width) >= 1.25)) {
split_vertical_val = false;
}
// To determine the range of values that we could split on, we need to find out if the
// container is too small. Once we've done that, we can use the x1, y1, x2 and y2
// coordinates to specify the range of values
int max_size = (split_vertical_val) ? container.width - MIN_CONTAINER_SIZE : container.height -
MIN_CONTAINER_SIZE;
if (max_size <= MIN_CONTAINER_SIZE) {
// Container too small to split
return false;
}
// Create the split position. This ensures that there will be MIN_CONTAINER_SIZE on each
// side
std::uniform_int_distribution<> pos_distribution(MIN_CONTAINER_SIZE, max_size);
int pos = pos_distribution(*random_generator);
// Split the container
if (split_vertical_val) {
// Split vertically making sure to adjust pos, so it can be within range of the actual
// container
pos += container.top_left.x;
if (debug_game) {
for (int y = container.top_left.y; y <= container.bottom_right.y + 1; y++) {
(*grid)[y][pos] = TileType::DebugWall;
}
}
// Create the child leafs
left = &Leaf{
Rect{
Point{
container.top_left.x, container.top_left.y
},
Point{
pos - 1, container.bottom_right.y,
}
}
};
right = &Leaf{
Rect{
Point{
pos + 1, container.top_left.y,
},
Point{
container.bottom_right.x, container.bottom_right.y
}
}
};
} else {
// Split horizontally making sure to adjust pos, so it can be within range of the actual
// container
pos += container.top_left.y;
if (debug_game) {
for (int x = container.top_left.x; x <= container.bottom_right.x + 1; x++) {
(*grid)[pos][x] = TileType::DebugWall;
}
}
// Create the child leafs
left = &Leaf{
Rect{
Point{
container.top_left.x, container.top_left.y
},
Point{
container.bottom_right.x, pos - 1,
}
}
};
right = &Leaf{
Rect{
Point{
container.top_left.x, pos + 1,
},
Point{
container.bottom_right.x, container.bottom_right.y
}
}
};
}
// Set the leaf's split direction
split_vertical = split_vertical_val;
// Successful split
return true;
}
bool create_room(std::vector<std::vector<int>> *grid, std::mt19937 *random_generator) {
// Test if this container is already split or not. If it is, we do not want to create a room
// inside it otherwise it will overwrite other rooms
if (left && right) {
return false;
}
// Pick a random width and height making sure it is at least min_room_size but doesn't
// exceed the container
std::uniform_int_distribution<> width_distribution(MIN_ROOM_SIZE, container.width);
int width = width_distribution(*random_generator);
std::uniform_int_distribution<> height_distribution(MIN_ROOM_SIZE, container.height);
int height = height_distribution(*random_generator);
// Use the width and height to find a suitable x and y position which can create the room
std::uniform_int_distribution<> x_pos_distribution(container.top_left.x, container.bottom_right.x - width);
int x_pos = x_pos_distribution(*random_generator);
std::uniform_int_distribution<> y_pos_distribution(container.top_left.y, container.bottom_right.y - height);
int y_pos = y_pos_distribution(*random_generator);
// Create the room rect and test if its width to height ratio will make an oddly-shaped room
Rect rect = Rect{
Point{
x_pos, y_pos
},
Point{
x_pos + width - 1, y_pos + height - 1
}
};
if ((((double) std::min(rect.width, rect.height)) / ((double) std::min(rect.width, rect.height))) <
ROOM_RATIO) {
return false;
}
// Width to height ratio is fine so place the rect in the 2D grid and store it
rect.place_rect(grid);
room = ▭
// Successful room creation
return true;
}
};
The astar.h file:
#ifndef PRIMITIVES_H
#define PRIMITIVES_H
// Custom includes
#include "primitives.h"
#endif
// External includes
#include <queue>
// ----- CONSTANTS ------------------------------
/* The ID of a TileType obstacle */
const std::vector<Point> INTERCARDINAL_OFFSETS = {
{-1, -1},
{0, -1},
{1, -1},
{-1, 0},
{1, 0},
{-1, 1},
{0, 1},
{1, 1},
};
// ----- STRUCTURES ------------------------------
struct Neighbour {
int cost;
Point pair;
inline bool operator<(const Neighbour nghbr) const {
// The priority_queue data structure gets the maximum priority, so we need to
// override that functionality to get the minimum priority
return cost > nghbr.cost;
}
};
// ----- FUNCTIONS ------------------------------
std::vector<Point> grid_bfs(Point target, int height, int width) {
// Create a vector to store the neighbours
std::vector<Point> result;
// Iterate over each offset and check if it's a valid neighbour
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.push_back({x, y});
}
}
// Return the result
return result;
}
std::vector<Point> calculate_astar_path(std::vector<std::vector<int>> *grid, Point start, Point end) {
// Set up a few variables needed for the pathfinding
std::vector<Point> result;
std::priority_queue<Neighbour> queue;
std::unordered_map<Point, Point> came_from = ;
std::unordered_map<Point, int> distances = ;
int height = (int) grid->capacity();
int width = (int) grid[0].capacity();
queue.push({0, start});
// Loop until the priority queue is empty
while (!queue.empty()) {
// Get the lowest cost pair from the priority queue
Point current = queue.top().pair;
queue.pop();
// Check if we've reached our target
if (current == end) {
// Backtrack through came_from to get the path
while (!(came_from[current] == current)) {
// Add the current pair to the result list
result.push_back({current.x, current.y});
// Get the next pair in the path
current = came_from[current];
}
// Add the start pair and exit out of the loop
result.push_back({start.x, start.y});
break;
}
// Add all the neighbours to the heap with their cost being f = g + h:
// f - The total cost of traversing the neighbour.
// g - The distance between the start pair and the neighbour pair.
// h - The estimated distance from the neighbour pair to the end pair. We're using the Chebyshev distance for
// this.
for (Point neighbour: grid_bfs(current, height, width)) {
if (!came_from.count(neighbour)) {
// Store the neighbour's parent and calculate its distance from the start pair
came_from[neighbour] = current;
distances[neighbour] = distances[current] + 1;
// Check if the neighbour is an obstacle. If so, set the total cost to infinity, otherwise, set it to f = g + h
int f_cost = ((*grid)[neighbour.y][neighbour.x] == TileType::Obstacle) ? std::numeric_limits<int>::max()
:
distances[neighbour] +
std::max(abs(neighbour.x - current.x), abs(neighbour.y - current.y));
// Add the neighbour to the priority queue
queue.push({f_cost, neighbour});
}
}
}
// Return result
return result;
}
The primitives.h file:
// Custom includes
#include "constants.h"
// External includes
#include <unordered_map>
// ----- STRUCTURES ------------------------------
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() {}
Point(int x_val, int y_val) {
x = x_val;
y = y_val;
}
inline std::pair<int, int> sum(Point *other) {
return std::make_pair(x + other->x, y + other->y);
}
inline std::pair<int, int> abs_diff(Point *other) {
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;
}
};
struct Rect {
// Parameters
Point top_left, bottom_right;
// Attributes
Point center;
int width, height;
inline bool operator==(const Rect rct) const {
return top_left == rct.top_left && bottom_right == rct.bottom_right;
}
inline bool operator!=(const Rect rct) const {
return top_left != rct.top_left && bottom_right != rct.bottom_right;
}
Rect() {}
Rect(Point top_left_val, Point bottom_right_val) {
std::pair<int, int> sum = top_left_val.sum(&bottom_right_val);
std::pair<int, int> diff = bottom_right_val.abs_diff(&top_left_val);
top_left = top_left_val;
bottom_right = bottom_right_val;
center = Point((int) round(((double) sum.first) / 2.0), (int) round(((double) sum.second) / 2.0));
width = diff.first;
height = diff.second;
}
inline int get_distance_to(Rect *other) {
return std::max(abs(center.x - other->center.x), abs(center.y - other->center.y));
}
void place_rect(std::vector<std::vector<int>> *grid) {
// Get the width and height of the grid
int grid_height = (int) grid->size();
int grid_width = (int) grid[0].size();
// Place the walls
for (int y = std::max(top_left.y, 0); y < std::max(bottom_right.y + 1, grid_height); y++) {
for (int x = std::max(top_left.x, 0); x < std::max(bottom_right.x + 1, grid_width); x++) {
if (std::count(std::begin(REPLACEABLE_TILES), std::end(REPLACEABLE_TILES), (*grid)[y][x]) > 0) {
(*grid)[y][x] = TileType::Wall;
}
}
}
// Place the floors. The ranges must be -1 in all directions since we don't want to
// overwrite the walls keeping the player in, but we still want to overwrite walls that
// block the path for hallways
for (int y = std::max(top_left.y + 1, 1); y < std::max(bottom_right.y, grid_height - 1); y++) {
for (int x = std::max(top_left.x + 1, 1); x < std::max(bottom_right.x, grid_width - 1); x++) {
(*grid)[y][x] = TileType::Floor;
}
}
}
};
template<>
struct std::hash<Rect> {
size_t operator()(const Rect &rct) const {
size_t res = 0;
hash_combine(res, rct.top_left);
hash_combine(res, rct.bottom_right);
return res;
}
};
The constants.h file:
// External includes
#include <algorithm>
#include <math.h>
// ----- ENUMS ------------------------------
enum TileType {
DebugWall,
Empty,
Floor,
Wall,
Obstacle,
Player,
HealthPotion,
ArmourPotion,
HealthBoostPotion,
ArmourBoostPotion,
SpeedBoostPotion,
FireRateBoostPotion
};
// ----- STRUCTURES ------------------------------
struct MapGenerationConstant {
double base_value, increase, max_value;
inline int generate_value(int level) const {
return (int) std::min(round(base_value * pow(increase, level)), max_value);
}
};
struct MapGenerationConstants {
MapGenerationConstant width, height, split_iteration, obstacle_count, item_count;
};
// ----- CONSTANTS ------------------------------
// Defines the constants for the map generation
const MapGenerationConstants MAP_GENERATION_CONSTANTS = {
{30, 1.2, 150},
{20, 1.2, 100},
{5, 1.5, 25},
{20,1.3, 200},
{5, 1.1, 30},
};
// Defines the probabilities for each item
const std::pair<TileType, double> ITEM_PROBABILITIES[6] = {
{HealthPotion, 0.3},
{ArmourPotion, 0.3},
{HealthBoostPotion, 0.2},
{ArmourBoostPotion, 0.1},
{SpeedBoostPotion, 0.05},
{FireRateBoostPotion, 0.05},
};
// Defines constants for the binary space partition
const int MIN_CONTAINER_SIZE = 5;
const int MIN_ROOM_SIZE = 4;
const double ROOM_RATIO = 0.625;
// Defines constants for hallway and entity generation
const TileType REPLACEABLE_TILES[3] = {
Empty, Obstacle, DebugWall
};
const int HALLWAY_SIZE = 5;
Sometimes the program fails on the create_hallways function, but other times it fails on the split_bsp function and is not consistent. I think it may be because of the recursive Leaf struct and its left and right attriutes, however, I'm not sure. Any ideas why this might be occuring?
Thanks.
Aucun commentaire:
Enregistrer un commentaire