215 lines
8.4 KiB
C
215 lines
8.4 KiB
C
#include <stdlib.h>
|
|
#include "grid.h"
|
|
#include "options.h"
|
|
#include "config.h"
|
|
|
|
#define MAX_EDGE_WEIGHT 100
|
|
#define TOP_LEFT_CORNER "\xe2\x94\x8f"
|
|
#define TOP_RIGHT_CORNER "\xe2\x94\x93"
|
|
#define BOTTOM_LEFT_CORNER "\xe2\x94\x97"
|
|
#define BOTTOM_RIGHT_CORNER "\xe2\x94\x9b"
|
|
#define HORIZONTAL_BAR "\xe2\x94\x81"
|
|
#define VERTICAL_BAR "\xe2\x94\x83"
|
|
#define TOP_TEE "\xe2\x94\xb3"
|
|
#define BOTTOM_TEE "\xe2\x94\xbb"
|
|
#define LEFT_TEE "\xe2\x94\xa3"
|
|
#define RIGHT_TEE "\xe2\x94\xab"
|
|
#define CROSS "\xe2\x95\x8b"
|
|
#define VERTICAL_HALF_BOTTOM "\xe2\x95\xbb"
|
|
#define VERTICAL_HALF_TOP "\xe2\x95\xb9"
|
|
#define HORIZONTAL_HALF_LEFT "\xe2\x95\xb8"
|
|
#define HORIZONTAL_HALF_RIGHT "\xe2\x95\xba"
|
|
|
|
static edgeweight_t random_edgeweight(mazeoptions_t const* options) {
|
|
if (!options->seed_set) {
|
|
#ifdef HAVE_ARC4RANDOM
|
|
return arc4random_uniform(MAX_EDGE_WEIGHT);
|
|
#else // HAVE_ARC4RANDOM
|
|
return random()%MAX_EDGE_WEIGHT;
|
|
#endif // HAVE_ARC4RANDOM
|
|
} else {
|
|
// use deterministic random number generator
|
|
return rand()%MAX_EDGE_WEIGHT;
|
|
}
|
|
}
|
|
|
|
#ifdef HAVE_SRAND_DETERMINISTIC
|
|
#define SRAND(x) (srand_deterministic(x))
|
|
#else
|
|
#define SRAND(x) (srand(x))
|
|
#endif // defined(HAVE_SRAND_DETERMINISTIC)
|
|
|
|
mazegrid_t mazegrid_new(size_t width, size_t height) {
|
|
mazeedges_t** grid = calloc(height, sizeof(mazeedges_t*));
|
|
for (size_t i = 0; i < height; i++) {
|
|
grid[i] = calloc(width, sizeof(mazeedges_t));
|
|
for (size_t j = 0; j < width; j++) {
|
|
grid[i][j].up = 0;
|
|
grid[i][j].right = 0;
|
|
}
|
|
}
|
|
mazegrid_t result = { .width = width, .height = height, .grid = grid };
|
|
return result;
|
|
}
|
|
|
|
void mazegrid_free(mazegrid_t* g) {
|
|
for (size_t i = 0; i < g->height; i++) {
|
|
free(g->grid[i]);
|
|
}
|
|
free(g->grid);
|
|
g->width = g->height = 0;
|
|
}
|
|
|
|
int mazegrid_set_edge(mazegrid_t* g, size_t x, size_t y, mazeedge_dir_t dir, edgeweight_t wt) {
|
|
if ((x >= g->width) || (y >= g->height)) return 0;
|
|
if ((x == 0) && (dir == EDGE_LEFT)) return 0;
|
|
if ((y == 0) && (dir == EDGE_DOWN)) return 0;
|
|
if ((x == g->width - 1) && (dir == EDGE_RIGHT)) return 0;
|
|
if ((y == g->height - 1) && (dir == EDGE_UP)) return 0;
|
|
if (dir == EDGE_LEFT) return mazegrid_set_edge(g, x - 1, y, EDGE_RIGHT, wt);
|
|
if (dir == EDGE_DOWN) return mazegrid_set_edge(g, x, y - 1, EDGE_UP, wt);
|
|
if (dir == EDGE_RIGHT) { g->grid[y][x].right = wt; return 1; }
|
|
g->grid[y][x].up = wt; return 1;
|
|
}
|
|
|
|
edgeweight_t mazegrid_get_edge(mazegrid_t const* g, size_t x, size_t y, mazeedge_dir_t dir) {
|
|
if ((x >= g->width) || (y >= g->height)) return 0;
|
|
if ((x == 0) && (dir == EDGE_LEFT)) return 0;
|
|
if ((y == 0) && (dir == EDGE_DOWN)) return 0;
|
|
if ((x == g->width - 1) && (dir == EDGE_RIGHT)) return 0;
|
|
if ((y == g->height - 1) && (dir == EDGE_UP)) return 0;
|
|
if (dir == EDGE_LEFT) return mazegrid_get_edge(g, x - 1, y, EDGE_RIGHT);
|
|
if (dir == EDGE_DOWN) return mazegrid_get_edge(g, x, y - 1, EDGE_UP);
|
|
if (dir == EDGE_RIGHT) return g->grid[y][x].right;
|
|
else return g->grid[y][x].up;
|
|
}
|
|
|
|
void mazegrid_randomize(mazegrid_t* g, mazeoptions_t const* options) {
|
|
// initialize random system
|
|
if (options->seed_set) {
|
|
SRAND(options->seed);
|
|
}
|
|
|
|
for (size_t i = 0; i < g->height; i++) {
|
|
for (size_t j = 0; j < g->width; j++) {
|
|
if (i < g->height - 1) g->grid[i][j].up = random_edgeweight(options);
|
|
if (j < g->width - 1) g->grid[i][j].right = random_edgeweight(options);
|
|
}
|
|
}
|
|
}
|
|
|
|
void mazegrid_uniform(mazegrid_t* g) {
|
|
for (size_t i = 0; i < g->height; i++) {
|
|
for (size_t j = 0; j < g->width; j++) {
|
|
if (i < g->height - 1) g->grid[i][j].up = (int)(255.0 - (i - g->height / 2) * (i - g->height / 2) * (255.0 * 4 / (g->height * g->height)));
|
|
if (j < g->width - 1) g->grid[i][j].right = (int)(255.0 - (j - g->width / 2) * (j - g->width / 2) * (255.0 * 4 / (g->width * g->width)));
|
|
}
|
|
}
|
|
}
|
|
|
|
void mazegrid_print(mazegrid_t const* g, FILE * f) {
|
|
fprintf(f, TOP_LEFT_CORNER);
|
|
for (size_t i = 0; i < g->width; i++) {
|
|
fprintf(f, HORIZONTAL_BAR);
|
|
if (i == g->width - 1) fprintf(f, HORIZONTAL_HALF_LEFT);
|
|
else if (mazegrid_get_edge(g, i, g->height - 1, EDGE_RIGHT)) fprintf(f, HORIZONTAL_BAR);
|
|
else fprintf(f, TOP_TEE);
|
|
}
|
|
fprintf(f, "\n");
|
|
|
|
size_t row = g->height - 1;
|
|
|
|
while (1) {
|
|
if (row > 0) fprintf(f, VERTICAL_BAR);
|
|
else fprintf(f, " ");
|
|
for (size_t col = 0; col < g->width; col++) {
|
|
if ((row == g->height - 1) && (col == g->width - 1)) fprintf(f, " ");
|
|
else if (col == g->width - 1) fprintf(f, " " VERTICAL_BAR);
|
|
else if (mazegrid_get_edge(g, col, row, EDGE_RIGHT)) fprintf(f, " ");
|
|
else fprintf(f, " " VERTICAL_BAR);
|
|
}
|
|
fprintf(f, "\n");
|
|
if (row == 0) break;
|
|
row--;
|
|
if (mazegrid_get_edge(g, 0, row, EDGE_UP)) fprintf(f, VERTICAL_BAR);
|
|
else if (row > 0) fprintf(f, LEFT_TEE);
|
|
else fprintf(f, BOTTOM_LEFT_CORNER);
|
|
for (size_t col = 0; col < g->width - 1; col++) {
|
|
if (mazegrid_get_edge(g, col, row, EDGE_UP)) fprintf(f, " ");
|
|
else fprintf(f, HORIZONTAL_BAR);
|
|
if (mazegrid_get_edge(g, col, row, EDGE_UP)) {
|
|
if (mazegrid_get_edge(g, col, row + 1, EDGE_RIGHT)) {
|
|
if (mazegrid_get_edge(g, col + 1, row, EDGE_UP)) {
|
|
fprintf(f, VERTICAL_HALF_BOTTOM);
|
|
} else {
|
|
if (mazegrid_get_edge(g, col, row, EDGE_RIGHT)) {
|
|
fprintf(f, HORIZONTAL_HALF_RIGHT);
|
|
} else fprintf(f, TOP_LEFT_CORNER);
|
|
}
|
|
} else {
|
|
if (mazegrid_get_edge(g, col + 1, row, EDGE_UP)) {
|
|
if (mazegrid_get_edge(g, col, row, EDGE_RIGHT)) {
|
|
fprintf(f, VERTICAL_HALF_TOP);
|
|
} else fprintf(f, VERTICAL_BAR);
|
|
} else {
|
|
if (mazegrid_get_edge(g, col, row, EDGE_RIGHT)) {
|
|
fprintf(f, BOTTOM_LEFT_CORNER);
|
|
} else fprintf(f, LEFT_TEE);
|
|
}
|
|
}
|
|
} else {
|
|
if (mazegrid_get_edge(g, col, row + 1, EDGE_RIGHT)) {
|
|
if (mazegrid_get_edge(g, col + 1, row, EDGE_UP)) {
|
|
if (mazegrid_get_edge(g, col, row, EDGE_RIGHT)) {
|
|
fprintf(f, HORIZONTAL_HALF_LEFT);
|
|
} else fprintf(f, TOP_RIGHT_CORNER);
|
|
} else {
|
|
if (mazegrid_get_edge(g, col, row, EDGE_RIGHT)) {
|
|
fprintf(f, HORIZONTAL_BAR);
|
|
} else fprintf(f, TOP_TEE);
|
|
}
|
|
} else {
|
|
if (mazegrid_get_edge(g, col + 1, row, EDGE_UP)) {
|
|
if (mazegrid_get_edge(g, col, row, EDGE_RIGHT)) {
|
|
fprintf(f, BOTTOM_RIGHT_CORNER);
|
|
} else fprintf(f, RIGHT_TEE);
|
|
} else {
|
|
if (mazegrid_get_edge(g, col, row, EDGE_RIGHT)) {
|
|
fprintf(f, BOTTOM_TEE);
|
|
} else fprintf(f, CROSS);
|
|
}
|
|
}
|
|
}
|
|
/*
|
|
if (mazegrid_get_edge(g, col, row, EDGE_UP)) {
|
|
fprintf(f, " ");
|
|
if (mazegrid_get_edge(g, col + 1, row, EDGE_UP)) fprintf(f, VERTICAL_BAR);
|
|
else {
|
|
fprintf(f, TOP_LEFT_CORNER);
|
|
}
|
|
}
|
|
else {
|
|
fprintf(f, HORIZONTAL_BAR);
|
|
if (mazegrid_get_edge(g, col + 1, row, EDGE_UP)) fprintf(f, RIGHT_TEE);
|
|
else fprintf(f, HORIZONTAL_BAR);
|
|
}
|
|
*/
|
|
}
|
|
if (mazegrid_get_edge(g, g->width - 1, row, EDGE_UP)) fprintf(f, " " VERTICAL_BAR);
|
|
else {
|
|
fprintf(f, HORIZONTAL_BAR);
|
|
if (row + 2 == g->height) fprintf(f, TOP_RIGHT_CORNER);
|
|
else fprintf(f, RIGHT_TEE);
|
|
}
|
|
fprintf(f, "\n");
|
|
}
|
|
fprintf(f, HORIZONTAL_HALF_RIGHT);
|
|
for (size_t i = 0; i < g->width; i++) {
|
|
fprintf(f, HORIZONTAL_BAR);
|
|
if (mazegrid_get_edge(g, i, 0, EDGE_RIGHT)) fprintf(f, HORIZONTAL_BAR);
|
|
else if (i == g->width - 1) fprintf(f, BOTTOM_RIGHT_CORNER);
|
|
else fprintf(f, BOTTOM_TEE);
|
|
}
|
|
fprintf(f, "\n");
|
|
}
|