Skip to content

Instantly share code, notes, and snippets.

@onsclom

onsclom/maze.c Secret

Created August 6, 2023 00:17
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
Star You must be signed in to star a gist
Save onsclom/3df0815ed2e3c1f30e8483234e9b643c to your computer and use it in GitHub Desktop.
c maze gen
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
typedef struct
{
int x, y;
} Vector2d;
#define WALL "#"
#define SPACE " "
void printMaze(int mazeSize, int **sides, int **topAndBots)
{
int y, x;
for (y = 0; y <= mazeSize * 2; y++)
{
for (x = 0; x <= mazeSize * 2; x++)
if (y % 2 == 0 && x % 2 == 0)
printf(WALL);
else if (y % 2 == 0)
if (topAndBots[y / 2][x / 2])
printf(SPACE);
else
printf(WALL);
else if (x % 2 == 0)
if (sides[y / 2][x / 2])
printf(SPACE);
else
printf(WALL);
else
printf(SPACE);
putchar('\n');
}
}
int main(int argc, char **argv)
{
srand((unsigned int)time(NULL));
int mazeSize = argc > 1 ? atoi(argv[1]) : 10;
/* TODO: handle invalid input */
int **sides = (int **)calloc(mazeSize, sizeof(int *));
int **topAndBots = (int **)calloc(mazeSize + 1, sizeof(int *));
int **visited = (int **)calloc(mazeSize, sizeof(int *));
int i;
for (i = 0; i < mazeSize; i++)
{
sides[i] = (int *)calloc(mazeSize + 1, sizeof(int));
topAndBots[i] = (int *)calloc(mazeSize, sizeof(int));
visited[i] = (int *)calloc(mazeSize, sizeof(int));
}
topAndBots[mazeSize] = (int *)calloc(mazeSize, sizeof(int));
Vector2d *toVisitStack = (Vector2d *)calloc(mazeSize * mazeSize, sizeof(Vector2d));
/* TODO: check callocs success */
long toVisitLast = 0;
toVisitStack[0] = (Vector2d){0, 0};
visited[0][0] = 1;
const Vector2d dirs[4] = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
while (toVisitLast >= 0)
{
Vector2d cur = toVisitStack[toVisitLast];
int visitable = 0;
Vector2d visitableDirs[4];
for (i = 0; i < 4; i++)
{
Vector2d dir = dirs[i];
Vector2d next = {cur.x + dir.x, cur.y + dir.y};
if (next.x < 0 || next.x >= mazeSize || next.y < 0 || next.y >= mazeSize)
continue;
if (visited[next.y][next.x])
continue;
visitableDirs[visitable++] = dir;
}
if (!visitable)
{
toVisitLast--;
continue;
}
Vector2d nextDir = visitableDirs[rand() % visitable];
Vector2d next = {cur.x + nextDir.x, cur.y + nextDir.y};
visited[next.y][next.x] = 1;
toVisitStack[++toVisitLast] = next;
if (nextDir.x == 0 && nextDir.y == 1)
topAndBots[next.y][next.x] = 1;
else if (nextDir.x == 1 && nextDir.y == 0)
sides[next.y][next.x] = 1;
else if (nextDir.x == 0 && nextDir.y == -1)
topAndBots[cur.y][cur.x] = 1;
else if (nextDir.x == -1 && nextDir.y == 0)
sides[cur.y][cur.x] = 1;
}
// printMaze(mazeSize, sides, topAndBots);
/* TODO: free all memory */
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment