#include <stdlib.h>
#include "maze_generator.h"
#include "utilities.h"
#include "maze.h"

static void remove_wall(int **graph, struct point a, struct point b)
{
    int diff_x = a.x - b.x;
    int diff_y = a.y - b.y;
    if (diff_y == 0)
    {
        if (diff_x == 1)
            graph[b.x][b.y] &= 3;
        else if (diff_x == -1)
            graph[a.x][a.y] &= 3;
    }
    else if (diff_x == 0)
    {
        if (diff_y == 1)
            graph[b.x][b.y] &= 5;
        else if (diff_y == -1)
            graph[a.x][a.y] &= 5;
    }
}

static void generate_maze_graph(int **graph, int width, int height, struct point point)
{
    //I've been here.
    graph[point.x][point.y] &= 6;
    struct point points[4];
    int index = 0;
    //Possibilities:
    if (point.x > 0)
        points[index++] = relative_point(point, -1, 0);
    if (point.x < width - 1)
        points[index++] = relative_point(point, 1, 0);
    if (point.y > 0)
        points[index++] = relative_point(point, 0, -1);
    if (point.y < height - 1)
        points[index++] = relative_point(point, 0, 1);
    //Shuffle:
    shuffle(points, index, sizeof(struct point));
    //Examine possibilities:
    index--;
    struct point new_point;
    while (index >= 0)
    {
        new_point = points[index];
        if ((graph[new_point.x][new_point.y] & 1) == 1)
        {
            //Remove wall:
            remove_wall(graph, point, new_point);
            //Go on:
            generate_maze_graph(graph, width, height, new_point);
        }
        index--;
    }
}

int generate_maze(struct maze *maze)
{
    if (!is_valid_maze_size(maze->width) || !is_valid_maze_size(maze->height))
        return -1;
    //Init graph:
    int graph_width = ((maze->width - 2) + 1) / 2;
    int graph_height = ((maze->height - 2) + 1) / 2;
    char mem[sizeof_2d(graph_width, graph_height, sizeof(int))];
    init2d((void **)mem, graph_width, graph_height, sizeof(int));
    int **graph = (int **)mem;
    for (int x = 0; x < graph_width; x++)
        for (int y = 0; y < graph_height; y++)
            graph[x][y] = 7;
    //Generate graph:
    struct point starting_point;
    starting_point.x = 0;
    starting_point.y = 0;
    generate_maze_graph(graph, graph_width, graph_height, starting_point);
    //Convert:
    for (int x = 0; x < graph_width; x++)
    {
        for (int y = 0; y < graph_height; y++)
        {
            int real_x = (2 * x) + 1;
            int real_y = (2 * y) + 1;
            int is_last_x = x == maze->width - 2;
            int is_last_y = y == maze->height - 2;
            maze->map[real_x][real_y] = 0;
            if (!is_last_x)
                maze->map[real_x + 1][real_y] = (graph[x][y] & 4) == 4;
            if (!is_last_y)
                maze->map[real_x][real_y + 1] = (graph[x][y] & 2) == 2;
            if (!(is_last_x || is_last_y))
                maze->map[real_x + 1][real_y + 1] = 1;
        }
    }
    //Set sides:
    for (int x = 0; x < maze->width; x++)
    {
        maze->map[x][0] = 1;
        maze->map[x][maze->height - 1] = 1;
    }
    for (int y = 0; y < maze->height; y++)
    {
        maze->map[0][y] = 1;
        maze->map[maze->width - 1][y] = 1;
    }
    //Set start and end:
    maze->starting_point.x = 1;
    maze->starting_point.y = 1;
    maze->end_point.x = maze->width - 2;
    maze->end_point.y = maze->height - 2;
    return 0;
}