sasa/maze32
1
0
Fork 0
Code Issues Pull Requests Actions Packages Projects Releases Wiki Activity
Files
main
maze32/components/maze32_maze/maze32_maze.c
T

717 lines
31 KiB
C
Raw Permalink Blame History

#include "maze32_maze.h"
#include <limits.h>
#include <string.h>
typedef struct {
uint32_t state;
} maze32_rng_t;
static uint16_t cell_count(const maze32_maze_t* maze) {
return (uint16_t)(maze->config.width * maze->config.height);
}
static uint32_t next_random(maze32_rng_t* random) {
uint32_t value = random->state;
value ^= value << 13U;
value ^= value >> 17U;
value ^= value << 5U;
random->state = value;
return value;
}
static uint32_t bounded_random(maze32_rng_t* random, uint32_t limit) {
return limit == 0U ? 0U : next_random(random) % limit;
}
static int config_is_valid(const maze32_maze_config_t* config) {
if (config == NULL || config->width < 8U || config->height < 8U ||
config->width > MAZE32_MAZE_MAX_WIDTH || config->height > MAZE32_MAZE_MAX_HEIGHT ||
(config->width & 1U) != 0U || (config->height & 1U) != 0U ||
config->cross_half_pairs < 2U || config->cross_half_pairs > config->height / 2U ||
config->minimum_exit_separation > config->width + config->height - 2U ||
config->landmark_pairs > MAZE32_MAZE_MAX_LANDMARK_PAIRS || config->artifact_pairs == 0U ||
config->artifact_pairs > MAZE32_MAZE_MAX_ARTIFACT_PAIRS || config->maximum_attempts == 0U) {
return 0;
}
return (uint32_t)config->width * config->height <= MAZE32_MAZE_MAX_CELLS;
}
static int cells_equal(maze32_cell_t first, maze32_cell_t second) {
return first.x == second.x && first.y == second.y;
}
static maze32_cell_t cell_from_index(const maze32_maze_t* maze, uint16_t index) {
maze32_cell_t cell = {
.x = (uint16_t)(index % maze->config.width),
.y = (uint16_t)(index / maze->config.width),
};
return cell;
}
uint16_t maze32_maze_cell_index(const maze32_maze_t* maze, maze32_cell_t cell) {
if (maze == NULL || cell.x >= maze->config.width || cell.y >= maze->config.height) {
return UINT16_MAX;
}
return (uint16_t)(cell.y * maze->config.width + cell.x);
}
maze32_cell_t maze32_maze_rotate(const maze32_maze_t* maze, maze32_cell_t cell) {
maze32_cell_t rotated = {UINT16_MAX, UINT16_MAX};
if (maze != NULL && cell.x < maze->config.width && cell.y < maze->config.height) {
rotated.x = (uint16_t)(maze->config.width - 1U - cell.x);
rotated.y = (uint16_t)(maze->config.height - 1U - cell.y);
}
return rotated;
}
static maze32_passage_t opposite_passage(maze32_passage_t passage) {
switch (passage) {
case MAZE32_PASSAGE_NORTH:
return MAZE32_PASSAGE_SOUTH;
case MAZE32_PASSAGE_EAST:
return MAZE32_PASSAGE_WEST;
case MAZE32_PASSAGE_SOUTH:
return MAZE32_PASSAGE_NORTH;
case MAZE32_PASSAGE_WEST:
return MAZE32_PASSAGE_EAST;
default:
return 0;
}
}
static int neighbor_for(const maze32_maze_t* maze, uint16_t index, maze32_passage_t passage,
uint16_t* neighbor) {
maze32_cell_t cell = cell_from_index(maze, index);
if (passage == MAZE32_PASSAGE_NORTH && cell.y > 0U) {
cell.y--;
} else if (passage == MAZE32_PASSAGE_EAST && cell.x + 1U < maze->config.width) {
cell.x++;
} else if (passage == MAZE32_PASSAGE_SOUTH && cell.y + 1U < maze->config.height) {
cell.y++;
} else if (passage == MAZE32_PASSAGE_WEST && cell.x > 0U) {
cell.x--;
} else {
return 0;
}
*neighbor = maze32_maze_cell_index(maze, cell);
return 1;
}
static void open_edge(maze32_maze_t* maze, uint16_t first, uint16_t second,
maze32_passage_t passage) {
maze->passages[first] |= (uint8_t)passage;
maze->passages[second] |= (uint8_t)opposite_passage(passage);
}
static void open_symmetric_edge(maze32_maze_t* maze, uint16_t first, uint16_t second,
maze32_passage_t passage) {
open_edge(maze, first, second, passage);
maze32_cell_t rotated_first = maze32_maze_rotate(maze, cell_from_index(maze, first));
maze32_cell_t rotated_second = maze32_maze_rotate(maze, cell_from_index(maze, second));
open_edge(maze, maze32_maze_cell_index(maze, rotated_first),
maze32_maze_cell_index(maze, rotated_second), opposite_passage(passage));
}
static void clear_visited(maze32_maze_workspace_t* workspace) {
memset(workspace->visited, 0, sizeof(workspace->visited));
}
static int is_visited(const maze32_maze_workspace_t* workspace, uint16_t index) {
return (workspace->visited[index / 8U] & (uint8_t)(1U << (index % 8U))) != 0U;
}
static void mark_visited(maze32_maze_workspace_t* workspace, uint16_t index) {
workspace->visited[index / 8U] |= (uint8_t)(1U << (index % 8U));
}
static int build_half_tree(maze32_maze_t* maze, maze32_maze_workspace_t* workspace,
maze32_rng_t* random) {
static const maze32_passage_t DIRECTIONS[] = {
MAZE32_PASSAGE_NORTH,
MAZE32_PASSAGE_EAST,
MAZE32_PASSAGE_SOUTH,
MAZE32_PASSAGE_WEST,
};
uint16_t half_width = maze->config.width / 2U;
uint16_t target_cells = (uint16_t)(half_width * maze->config.height);
uint16_t visited_cells = 1U;
size_t stack_size = 1U;
clear_visited(workspace);
workspace->traversal[0] = 0U;
mark_visited(workspace, 0U);
while (stack_size > 0U) {
uint16_t current = workspace->traversal[stack_size - 1U];
maze32_passage_t choices[4];
uint16_t neighbors[4];
size_t choice_count = 0U;
for (size_t direction_index = 0U; direction_index < 4U; ++direction_index) {
uint16_t neighbor = 0U;
if (neighbor_for(maze, current, DIRECTIONS[direction_index], &neighbor)) {
maze32_cell_t neighbor_cell = cell_from_index(maze, neighbor);
if (neighbor_cell.x < half_width && !is_visited(workspace, neighbor)) {
choices[choice_count] = DIRECTIONS[direction_index];
neighbors[choice_count] = neighbor;
choice_count++;
}
}
}
if (choice_count == 0U) {
stack_size--;
continue;
}
size_t selected = bounded_random(random, (uint32_t)choice_count);
open_symmetric_edge(maze, current, neighbors[selected], choices[selected]);
mark_visited(workspace, neighbors[selected]);
workspace->traversal[stack_size++] = neighbors[selected];
visited_cells++;
}
return visited_cells == target_cells;
}
static int add_cycle_pairs(maze32_maze_t* maze, maze32_rng_t* random) {
uint16_t half_width = maze->config.width / 2U;
uint16_t added = 0U;
uint32_t attempt_limit = (uint32_t)maze->config.extra_cycle_pairs * 64U + 256U;
for (uint32_t attempt = 0U; attempt < attempt_limit && added < maze->config.extra_cycle_pairs;
++attempt) {
maze32_cell_t cell = {
.x = (uint16_t)bounded_random(random, half_width),
.y = (uint16_t)bounded_random(random, maze->config.height),
};
maze32_passage_t passage =
bounded_random(random, 2U) == 0U ? MAZE32_PASSAGE_EAST : MAZE32_PASSAGE_SOUTH;
uint16_t first = maze32_maze_cell_index(maze, cell);
uint16_t second = 0U;
if (!neighbor_for(maze, first, passage, &second) ||
cell_from_index(maze, second).x >= half_width ||
(maze->passages[first] & passage) != 0U) {
continue;
}
open_symmetric_edge(maze, first, second, passage);
added++;
}
return added == maze->config.extra_cycle_pairs;
}
static int add_cross_half_connections(maze32_maze_t* maze, maze32_maze_workspace_t* workspace,
maze32_rng_t* random) {
clear_visited(workspace);
uint16_t added_pairs = 0U;
uint16_t half_height = maze->config.height / 2U;
while (added_pairs < maze->config.cross_half_pairs) {
uint16_t y = (uint16_t)bounded_random(random, half_height);
if (is_visited(workspace, y)) {
continue;
}
mark_visited(workspace, y);
maze32_cell_t left = {(uint16_t)(maze->config.width / 2U - 1U), y};
uint16_t first = maze32_maze_cell_index(maze, left);
uint16_t second = 0U;
if (!neighbor_for(maze, first, MAZE32_PASSAGE_EAST, &second)) {
return 0;
}
open_symmetric_edge(maze, first, second, MAZE32_PASSAGE_EAST);
added_pairs++;
}
return 1;
}
static uint16_t calculate_distances(const maze32_maze_t* maze, maze32_maze_workspace_t* workspace,
maze32_cell_t start) {
uint16_t count = cell_count(maze);
for (uint16_t index = 0U; index < count; ++index) {
workspace->distances[index] = UINT16_MAX;
}
uint16_t start_index = maze32_maze_cell_index(maze, start);
size_t head = 0U;
size_t tail = 1U;
workspace->traversal[0] = start_index;
workspace->distances[start_index] = 0U;
while (head < tail) {
uint16_t current = workspace->traversal[head++];
const maze32_passage_t directions[] = {MAZE32_PASSAGE_NORTH, MAZE32_PASSAGE_EAST,
MAZE32_PASSAGE_SOUTH, MAZE32_PASSAGE_WEST};
for (size_t direction_index = 0U; direction_index < 4U; ++direction_index) {
maze32_passage_t passage = directions[direction_index];
uint16_t neighbor = 0U;
if ((maze->passages[current] & passage) != 0U &&
neighbor_for(maze, current, passage, &neighbor) &&
workspace->distances[neighbor] == UINT16_MAX) {
workspace->distances[neighbor] = (uint16_t)(workspace->distances[current] + 1U);
workspace->traversal[tail++] = neighbor;
}
}
}
return (uint16_t)tail;
}
static int required_cell_occupied(const maze32_maze_t* maze, maze32_cell_t cell,
unsigned int placement_stage) {
unsigned int pair_counts[] = {2U, 2U, 2U, 2U};
const maze32_cell_t* required[] = {maze->starts, maze->keys, maze->exits, maze->compasses};
for (unsigned int group = 0U; group < placement_stage && group < 4U; ++group) {
for (unsigned int index = 0U; index < pair_counts[group]; ++index) {
if (cells_equal(cell, required[group][index])) {
return 1;
}
}
}
unsigned int placed_landmarks = placement_stage > 4U ? placement_stage - 4U : 0U;
if (placed_landmarks > maze->config.landmark_pairs) {
placed_landmarks = maze->config.landmark_pairs;
}
for (unsigned int pair = 0U; pair < placed_landmarks; ++pair) {
if (cells_equal(cell, maze->landmarks[pair].cells[0]) ||
cells_equal(cell, maze->landmarks[pair].cells[1])) {
return 1;
}
}
unsigned int artifact_stage = 4U + maze->config.landmark_pairs;
unsigned int placed_artifacts =
placement_stage > artifact_stage ? placement_stage - artifact_stage : 0U;
if (placed_artifacts > maze->config.artifact_pairs) {
placed_artifacts = maze->config.artifact_pairs;
}
for (unsigned int pair = 0U; pair < placed_artifacts; ++pair) {
if (cells_equal(cell, maze->artifacts[pair][0]) ||
cells_equal(cell, maze->artifacts[pair][1])) {
return 1;
}
}
return 0;
}
static int pair_is_available(const maze32_maze_t* maze, maze32_cell_t first,
unsigned int placement_stage) {
maze32_cell_t second = maze32_maze_rotate(maze, first);
return !cells_equal(first, second) && !required_cell_occupied(maze, first, placement_stage) &&
!required_cell_occupied(maze, second, placement_stage);
}
static int choose_farthest(const maze32_maze_t* maze, maze32_maze_workspace_t* workspace,
unsigned int placement_stage, int boundary_only,
uint16_t maximum_distance, const maze32_cell_t* separated_from,
uint16_t minimum_separation, maze32_cell_t* selected) {
uint16_t best_distance = 0U;
int found = 0;
uint16_t count = cell_count(maze);
for (uint16_t index = 0U; index < count; ++index) {
maze32_cell_t cell = cell_from_index(maze, index);
int on_boundary = cell.x == 0U || cell.y == 0U || cell.x + 1U == maze->config.width ||
cell.y + 1U == maze->config.height;
uint16_t separation = 0U;
if (separated_from != NULL) {
separation = (uint16_t)((cell.x > separated_from->x ? cell.x - separated_from->x
: separated_from->x - cell.x) +
(cell.y > separated_from->y ? cell.y - separated_from->y
: separated_from->y - cell.y));
}
uint16_t distance = workspace->distances[index];
if ((!boundary_only || on_boundary) && distance != UINT16_MAX &&
distance <= maximum_distance && separation >= minimum_separation &&
pair_is_available(maze, cell, placement_stage) &&
(!found || distance > best_distance)) {
*selected = cell;
best_distance = distance;
found = 1;
}
}
return found;
}
static int choose_random_pair(const maze32_maze_t* maze, maze32_rng_t* random,
unsigned int placement_stage, maze32_cell_t* selected) {
uint16_t count = cell_count(maze);
for (uint32_t attempt = 0U; attempt < (uint32_t)count * 2U; ++attempt) {
maze32_cell_t candidate = cell_from_index(maze, (uint16_t)bounded_random(random, count));
if (pair_is_available(maze, candidate, placement_stage)) {
*selected = candidate;
return 1;
}
}
for (uint16_t index = 0U; index < count; ++index) {
maze32_cell_t candidate = cell_from_index(maze, index);
if (pair_is_available(maze, candidate, placement_stage)) {
*selected = candidate;
return 1;
}
}
return 0;
}
static int place_objects(maze32_maze_t* maze, maze32_maze_workspace_t* workspace,
maze32_rng_t* random) {
maze->starts[0].x = 0U;
maze->starts[0].y = (uint16_t)bounded_random(random, maze->config.height);
maze->starts[1] = maze32_maze_rotate(maze, maze->starts[0]);
calculate_distances(maze, workspace, maze->starts[0]);
if (!choose_farthest(maze, workspace, 1U, 0, UINT16_MAX, NULL, 0U, &maze->keys[0])) {
return 0;
}
maze->keys[1] = maze32_maze_rotate(maze, maze->keys[0]);
uint16_t start_key_distance = workspace->distances[maze32_maze_cell_index(maze, maze->keys[0])];
calculate_distances(maze, workspace, maze->keys[0]);
if (!choose_farthest(maze, workspace, 2U, 1, start_key_distance, &maze->starts[0],
maze->config.minimum_exit_separation, &maze->exits[0])) {
return 0;
}
maze->exits[1] = maze32_maze_rotate(maze, maze->exits[0]);
if (!choose_random_pair(maze, random, 3U, &maze->compasses[0])) {
return 0;
}
maze->compasses[1] = maze32_maze_rotate(maze, maze->compasses[0]);
for (unsigned int pair = 0U; pair < maze->config.landmark_pairs; ++pair) {
if (!choose_random_pair(maze, random, 4U + pair, &maze->landmarks[pair].cells[0])) {
return 0;
}
maze->landmarks[pair].cells[1] = maze32_maze_rotate(maze, maze->landmarks[pair].cells[0]);
maze->landmarks[pair].kind = (uint8_t)(pair % 4U + 1U);
}
for (unsigned int pair = 0U; pair < maze->config.artifact_pairs; ++pair) {
if (!choose_random_pair(maze, random, 4U + maze->config.landmark_pairs + pair,
&maze->artifacts[pair][0])) {
return 0;
}
maze->artifacts[pair][1] = maze32_maze_rotate(maze, maze->artifacts[pair][0]);
}
return 1;
}
static maze32_maze_result_t generate_candidate(maze32_maze_t* maze,
maze32_maze_workspace_t* workspace,
const maze32_maze_config_t* config,
uint32_t requested_seed, uint32_t generation_seed,
uint8_t attempt) {
memset(maze, 0, sizeof(*maze));
maze->config = *config;
maze->requested_seed = requested_seed;
maze->generation_seed = generation_seed;
maze->generation_attempts = attempt;
maze32_rng_t random = {.state = generation_seed == 0U ? 0x6d2b79f5U : generation_seed};
if (!build_half_tree(maze, workspace, &random) || !add_cycle_pairs(maze, &random) ||
!add_cross_half_connections(maze, workspace, &random) ||
!place_objects(maze, workspace, &random)) {
return MAZE32_MAZE_PLACEMENT_COLLISION;
}
return MAZE32_MAZE_OK;
}
static int validate_passages(const maze32_maze_t* maze, maze32_maze_metrics_t* metrics) {
uint16_t count = cell_count(maze);
for (uint16_t index = 0U; index < count; ++index) {
if ((maze->passages[index] & 0xf0U) != 0U) {
return 0;
}
unsigned int degree = 0U;
const maze32_passage_t directions[] = {MAZE32_PASSAGE_NORTH, MAZE32_PASSAGE_EAST,
MAZE32_PASSAGE_SOUTH, MAZE32_PASSAGE_WEST};
for (size_t direction_index = 0U; direction_index < 4U; ++direction_index) {
maze32_passage_t passage = directions[direction_index];
uint16_t neighbor = 0U;
if ((maze->passages[index] & passage) == 0U) {
continue;
}
if (!neighbor_for(maze, index, passage, &neighbor) ||
(maze->passages[neighbor] & opposite_passage(passage)) == 0U) {
return 0;
}
degree++;
if (passage == MAZE32_PASSAGE_EAST || passage == MAZE32_PASSAGE_SOUTH) {
metrics->passage_edges++;
}
}
if (degree == 1U) {
metrics->dead_end_count++;
} else if (degree >= 3U) {
metrics->branching_cells++;
}
maze32_cell_t cell = cell_from_index(maze, index);
maze32_cell_t rotated = maze32_maze_rotate(maze, cell);
uint16_t rotated_index = maze32_maze_cell_index(maze, rotated);
uint8_t expected = 0U;
if ((maze->passages[index] & MAZE32_PASSAGE_NORTH) != 0U) {
expected |= MAZE32_PASSAGE_SOUTH;
}
if ((maze->passages[index] & MAZE32_PASSAGE_EAST) != 0U) {
expected |= MAZE32_PASSAGE_WEST;
}
if ((maze->passages[index] & MAZE32_PASSAGE_SOUTH) != 0U) {
expected |= MAZE32_PASSAGE_NORTH;
}
if ((maze->passages[index] & MAZE32_PASSAGE_WEST) != 0U) {
expected |= MAZE32_PASSAGE_EAST;
}
if (maze->passages[rotated_index] != expected) {
return 0;
}
}
return 1;
}
static int object_pair_is_valid(const maze32_maze_t* maze, const maze32_cell_t pair[2]) {
return maze32_maze_cell_index(maze, pair[0]) != UINT16_MAX &&
maze32_maze_cell_index(maze, pair[1]) != UINT16_MAX &&
cells_equal(maze32_maze_rotate(maze, pair[0]), pair[1]);
}
static maze32_maze_result_t validate_objects(const maze32_maze_t* maze,
maze32_maze_workspace_t* workspace,
maze32_maze_metrics_t* metrics) {
maze32_cell_t
occupied[8U + MAZE32_MAZE_MAX_LANDMARK_PAIRS * 2U + MAZE32_MAZE_MAX_ARTIFACT_PAIRS * 2U];
size_t occupied_count = 0U;
const maze32_cell_t* required[] = {maze->starts, maze->keys, maze->exits, maze->compasses};
for (size_t group = 0U; group < 4U; ++group) {
if (!object_pair_is_valid(maze, required[group])) {
return MAZE32_MAZE_UNFAIR_PLACEMENT;
}
for (size_t index = 0U; index < 2U; ++index) {
for (size_t previous = 0U; previous < occupied_count; ++previous) {
if (cells_equal(required[group][index], occupied[previous])) {
return MAZE32_MAZE_PLACEMENT_COLLISION;
}
}
occupied[occupied_count++] = required[group][index];
}
}
for (size_t pair = 0U; pair < maze->config.landmark_pairs; ++pair) {
if (!object_pair_is_valid(maze, maze->landmarks[pair].cells)) {
return MAZE32_MAZE_UNFAIR_PLACEMENT;
}
for (size_t index = 0U; index < 2U; ++index) {
for (size_t previous = 0U; previous < occupied_count; ++previous) {
if (cells_equal(maze->landmarks[pair].cells[index], occupied[previous])) {
return MAZE32_MAZE_PLACEMENT_COLLISION;
}
}
occupied[occupied_count++] = maze->landmarks[pair].cells[index];
}
}
for (size_t pair = 0U; pair < maze->config.artifact_pairs; ++pair) {
if (!object_pair_is_valid(maze, maze->artifacts[pair])) {
return MAZE32_MAZE_UNFAIR_PLACEMENT;
}
for (size_t index = 0U; index < 2U; ++index) {
for (size_t previous = 0U; previous < occupied_count; ++previous) {
if (cells_equal(maze->artifacts[pair][index], occupied[previous])) {
return MAZE32_MAZE_PLACEMENT_COLLISION;
}
}
occupied[occupied_count++] = maze->artifacts[pair][index];
}
}
for (size_t player = 0U; player < 2U; ++player) {
maze32_cell_t start = maze->starts[player];
maze32_cell_t exit = maze->exits[player];
int start_on_boundary = start.x == 0U || start.y == 0U ||
start.x + 1U == maze->config.width ||
start.y + 1U == maze->config.height;
int exit_on_boundary = exit.x == 0U || exit.y == 0U || exit.x + 1U == maze->config.width ||
exit.y + 1U == maze->config.height;
uint16_t exit_separation =
(uint16_t)((start.x > exit.x ? start.x - exit.x : exit.x - start.x) +
(start.y > exit.y ? start.y - exit.y : exit.y - start.y));
if (!start_on_boundary || !exit_on_boundary ||
exit_separation < maze->config.minimum_exit_separation) {
return MAZE32_MAZE_UNFAIR_PLACEMENT;
}
}
metrics->reachable_cells = calculate_distances(maze, workspace, maze->starts[0]);
if (metrics->reachable_cells != cell_count(maze)) {
return MAZE32_MAZE_UNREACHABLE;
}
metrics->start_to_key[0] = workspace->distances[maze32_maze_cell_index(maze, maze->keys[0])];
metrics->start_to_exit[0] = workspace->distances[maze32_maze_cell_index(maze, maze->exits[0])];
metrics->start_to_compass[0] =
workspace->distances[maze32_maze_cell_index(maze, maze->compasses[0])];
for (size_t pair = 0U; pair < maze->config.landmark_pairs; ++pair) {
metrics->landmark_distance_total[0] +=
workspace->distances[maze32_maze_cell_index(maze, maze->landmarks[pair].cells[0])];
}
for (size_t pair = 0U; pair < maze->config.artifact_pairs; ++pair) {
metrics->artifact_distance_total[0] +=
workspace->distances[maze32_maze_cell_index(maze, maze->artifacts[pair][0])];
}
for (size_t player = 0U; player < 2U; ++player) {
int x_distance = maze->starts[player].x > maze->keys[player].x
? maze->starts[player].x - maze->keys[player].x
: maze->keys[player].x - maze->starts[player].x;
int y_distance = maze->starts[player].y > maze->keys[player].y
? maze->starts[player].y - maze->keys[player].y
: maze->keys[player].y - maze->starts[player].y;
if (x_distance <= maze->config.initial_view_radius &&
y_distance <= maze->config.initial_view_radius) {
return MAZE32_MAZE_KEY_IN_INITIAL_VIEW;
}
}
calculate_distances(maze, workspace, maze->keys[0]);
metrics->key_to_exit[0] = workspace->distances[maze32_maze_cell_index(maze, maze->exits[0])];
metrics->start_to_key[1] = metrics->start_to_key[0];
metrics->key_to_exit[1] = metrics->key_to_exit[0];
metrics->start_to_exit[1] = metrics->start_to_exit[0];
metrics->start_to_compass[1] = metrics->start_to_compass[0];
metrics->landmark_distance_total[1] = metrics->landmark_distance_total[0];
metrics->artifact_distance_total[1] = metrics->artifact_distance_total[0];
if (metrics->start_to_key[0] < metrics->key_to_exit[0]) {
return MAZE32_MAZE_UNFAIR_PLACEMENT;
}
return MAZE32_MAZE_OK;
}
maze32_maze_config_t maze32_maze_default_config(void) {
maze32_maze_config_t config = {
.width = MAZE32_MAZE_DEFAULT_WIDTH,
.height = MAZE32_MAZE_DEFAULT_HEIGHT,
.initial_view_radius = 3U,
.cross_half_pairs = 2U,
.extra_cycle_pairs = 8U,
.minimum_exit_separation = 22U,
.landmark_pairs = 2U,
.artifact_pairs = 1U,
.maximum_attempts = 8U,
};
return config;
}
maze32_maze_result_t maze32_maze_validate(const maze32_maze_t* maze,
maze32_maze_workspace_t* workspace,
maze32_maze_metrics_t* metrics) {
if (maze == NULL || workspace == NULL || metrics == NULL) {
return MAZE32_MAZE_INVALID_ARGUMENT;
}
memset(metrics, 0, sizeof(*metrics));
if (!config_is_valid(&maze->config)) {
return MAZE32_MAZE_INVALID_CONFIG;
}
if (!validate_passages(maze, metrics)) {
return MAZE32_MAZE_ASYMMETRIC;
}
maze32_maze_result_t object_result = validate_objects(maze, workspace, metrics);
if (object_result != MAZE32_MAZE_OK) {
return object_result;
}
metrics->cycle_count = (uint16_t)(metrics->passage_edges - metrics->reachable_cells + 1U);
if (metrics->cycle_count == 0U || metrics->dead_end_count == 0U) {
return MAZE32_MAZE_INSUFFICIENT_CYCLES;
}
uint16_t seam_x = maze->config.width / 2U - 1U;
for (uint16_t y = 0U; y < maze->config.height; ++y) {
maze32_cell_t cell = {seam_x, y};
if (maze32_maze_has_passage(maze, cell, MAZE32_PASSAGE_EAST)) {
metrics->cross_half_connections++;
}
}
if (metrics->cross_half_connections < 4U) {
return MAZE32_MAZE_INSUFFICIENT_CROSSINGS;
}
return MAZE32_MAZE_OK;
}
maze32_maze_result_t maze32_maze_generate(maze32_maze_t* maze, maze32_maze_workspace_t* workspace,
const maze32_maze_config_t* config, uint32_t seed,
maze32_maze_report_t* report) {
if (maze == NULL || workspace == NULL || config == NULL || report == NULL) {
return MAZE32_MAZE_INVALID_ARGUMENT;
}
memset(report, 0, sizeof(*report));
if (!config_is_valid(config)) {
report->result = MAZE32_MAZE_INVALID_CONFIG;
return report->result;
}
maze32_maze_result_t last_result = MAZE32_MAZE_GENERATION_EXHAUSTED;
uint32_t generation_seed = seed;
for (uint8_t attempt = 1U; attempt <= config->maximum_attempts; ++attempt) {
generation_seed += 0x9e3779b9U;
last_result = generate_candidate(maze, workspace, config, seed, generation_seed, attempt);
if (last_result == MAZE32_MAZE_OK) {
last_result = maze32_maze_validate(maze, workspace, &report->metrics);
}
report->attempts = attempt;
report->last_validation_result = last_result;
if (last_result == MAZE32_MAZE_OK) {
report->result = MAZE32_MAZE_OK;
return MAZE32_MAZE_OK;
}
}
report->result = MAZE32_MAZE_GENERATION_EXHAUSTED;
return report->result;
}
int maze32_maze_has_passage(const maze32_maze_t* maze, maze32_cell_t cell,
maze32_passage_t passage) {
uint16_t index = maze32_maze_cell_index(maze, cell);
return index != UINT16_MAX && (maze->passages[index] & passage) != 0U;
}
static void hash_bytes(uint64_t* hash, const void* data, size_t size) {
const uint8_t* bytes = data;
for (size_t index = 0U; index < size; ++index) {
*hash ^= bytes[index];
*hash *= UINT64_C(1099511628211);
}
}
uint64_t maze32_maze_hash(const maze32_maze_t* maze) {
if (maze == NULL || !config_is_valid(&maze->config)) {
return 0U;
}
uint64_t hash = UINT64_C(1469598103934665603);
hash_bytes(&hash, &maze->config.width, sizeof(maze->config.width));
hash_bytes(&hash, &maze->config.height, sizeof(maze->config.height));
hash_bytes(&hash, &maze->config.initial_view_radius, sizeof(maze->config.initial_view_radius));
hash_bytes(&hash, &maze->config.cross_half_pairs, sizeof(maze->config.cross_half_pairs));
hash_bytes(&hash, &maze->config.extra_cycle_pairs, sizeof(maze->config.extra_cycle_pairs));
hash_bytes(&hash, &maze->config.minimum_exit_separation,
sizeof(maze->config.minimum_exit_separation));
hash_bytes(&hash, &maze->config.landmark_pairs, sizeof(maze->config.landmark_pairs));
hash_bytes(&hash, &maze->config.artifact_pairs, sizeof(maze->config.artifact_pairs));
hash_bytes(&hash, &maze->config.maximum_attempts, sizeof(maze->config.maximum_attempts));
hash_bytes(&hash, &maze->requested_seed, sizeof(maze->requested_seed));
hash_bytes(&hash, &maze->generation_seed, sizeof(maze->generation_seed));
hash_bytes(&hash, maze->passages, cell_count(maze));
hash_bytes(&hash, maze->starts, sizeof(maze->starts));
hash_bytes(&hash, maze->keys, sizeof(maze->keys));
hash_bytes(&hash, maze->exits, sizeof(maze->exits));
hash_bytes(&hash, maze->compasses, sizeof(maze->compasses));
hash_bytes(&hash, maze->landmarks, maze->config.landmark_pairs * sizeof(maze->landmarks[0]));
hash_bytes(&hash, maze->artifacts, maze->config.artifact_pairs * sizeof(maze->artifacts[0]));
return hash;
}
const char* maze32_maze_result_name(maze32_maze_result_t result) {
switch (result) {
case MAZE32_MAZE_OK:
return "ok";
case MAZE32_MAZE_INVALID_ARGUMENT:
return "invalid_argument";
case MAZE32_MAZE_INVALID_CONFIG:
return "invalid_config";
case MAZE32_MAZE_UNREACHABLE:
return "unreachable";
case MAZE32_MAZE_ASYMMETRIC:
return "asymmetric";
case MAZE32_MAZE_INSUFFICIENT_CYCLES:
return "insufficient_cycles";
case MAZE32_MAZE_INSUFFICIENT_CROSSINGS:
return "insufficient_crossings";
case MAZE32_MAZE_PLACEMENT_COLLISION:
return "placement_collision";
case MAZE32_MAZE_UNFAIR_PLACEMENT:
return "unfair_placement";
case MAZE32_MAZE_KEY_IN_INITIAL_VIEW:
return "key_in_initial_view";
case MAZE32_MAZE_GENERATION_EXHAUSTED:
return "generation_exhausted";
default:
return "unknown";
}
}
Reference in New Issue View Git Blame Copy Permalink