path: root/map.c

#include <string.h>
#include <stdlib.h>
#include <curses.h>
#include <limits.h>

#include "map.h"
#include "config.h"
#include "stack.h"
#include "error.h"
#include "path.h"

Map empty_map(size_t width, size_t height) {
    Map map = malloc(sizeof(MapTile*) * height);
    if (map == NULL) return NULL;

    for (size_t row = 0; row < height; row++) {
        map[row] = malloc(sizeof(MapTile) * width);
        if (map[row] == NULL) return NULL;
        memset(map[row], 0, width*sizeof(MapTile)); 
    }

    return map;
}

unsigned int neighbours(Position neighbour_array[], Position pos, size_t width, size_t height, \
        char visited[height][width]) {
    size_t cur = 0;
    if (pos.x > 0 && !visited[pos.y][pos.x - 1]) {
        neighbour_array[cur].x = pos.x - 1;
        neighbour_array[cur].y = pos.y;
        cur += 1;
    }
    if (pos.x + 1 < width && !visited[pos.y][pos.x + 1]) {
        neighbour_array[cur].x = pos.x + 1;
        neighbour_array[cur].y = pos.y;
        cur += 1;
    }
    if (pos.y > 0 && !visited[pos.y - 1][pos.x]) {
        neighbour_array[cur].x = pos.x;
        neighbour_array[cur].y = pos.y - 1;
        cur += 1;
    }
    if (pos.y + 1 < height && !visited[pos.y + 1][pos.x]) {
        neighbour_array[cur].x = pos.x;
        neighbour_array[cur].y = pos.y + 1;
        cur += 1;
    }

    return cur;
}

Map rbt_maze_map(size_t width, size_t height, unsigned int seed) {
    size_t map_width  = width * 2 - 1,
           map_height = height * 2 - 1;
    Map map = empty_map(map_width, map_height);

    /* Vertical walls */
    for (size_t i = 1; i < map_width; i += 2) {
        for (size_t j = 0; j < map_height; j += 1) {
            map[j][i] = WALL;
        }
    }
    /* Horizontal walls */
    for (size_t i = 1; i < map_height; i += 2) {
        for (size_t j = 0; j < map_width; j += 1) {
            map[i][j] = WALL;
        }
    }

    Position beginning_cell = {width - 1, height - 1};

    char visited[height][width]; /* 1 if visited, 0 if not */
    memset(visited, 0, sizeof(char) * width * height);

    PositionStack ps = ps_new();
    ps_push(&ps, beginning_cell);
    visited[beginning_cell.y][beginning_cell.x] = 1;

    Position na[4];

    srand(seed);

    do {
        int nc = neighbours(na, ps_peek(ps), width, height, visited);
        if (nc > 0) {
            Position next = na[rand() % nc];
            Position prev = ps_peek(ps);
            ps_push(&ps, next);
            visited[next.y][next.x] = 1;
            map[(next.y * 2 + prev.y * 2) / 2][(next.x * 2 + prev.x * 2) / 2] = EMPTY;
        } else {
            (void)ps_pop(&ps);
        }
    } while (ps_peek(ps).x != beginning_cell.x || ps_peek(ps).y != beginning_cell.y) ;

    return map;
}

/* Reads the map from a file, saves size in `width` and `height`
 *
 * FILE FORMAT IS AS FOLLOWS:
 * {WIDTH}x{HEIGHT}
 * {EMPTY_CHAR}{WALL_CHAR}{START_CHAR}{END_CHAR}
 * {MAP, one line at a time}
 *
 * EXAMPLE:
 * 10x4
 * .#@x
 * .......x..
 * ....###...
 * ....#.#...
 * ..@....... */
/* TODO: handle errors better */
Map file_plaintext_map(char *filename, size_t *width, size_t *height, Position *start_pos, Position *end_pos) {
    FILE *file = fopen(filename, "r");
    if (file == NULL) {
        error("Failed to open file %s\n", filename);
    }

    if (fscanf(file, "%zux%zu\n", width, height) != 2) {
        error("Failed reading size of file %s\n", filename);
    }

    Map map = empty_map(*width, *height);

    char empty_char, wall_char, start_char, end_char;
    if (fscanf(file, "%c%c%c%c\n", &empty_char, &wall_char, &start_char, &end_char) != 4) {
        error("Failed reading chars of file %s\n", filename);
    }

    for (size_t row = 0; row < *height; row++) {
        for (size_t col = 0; col < *width; col++) {
            char c = (char)fgetc(file);
            if (c == empty_char) continue;
            if (c == wall_char) { map[row][col] = WALL; continue; }
            if (c == start_char) { start_pos->x = col; start_pos->y = row; continue; }
            if (c == end_char) { end_pos->x = col; end_pos->y = row; continue; }
        }
        fgetc(file);
    }

    return map;
}

/* FIXME: I don't think we need DRAW_MAP_OFFSET_{X,Y} anymore
 * Although, at the same time, it does make less magic values, so I guess it's fine */
/* TODO: Maybe add an option to render with ▄? that doubles the resolution, but requires us to use ncursesw, probably. */
void draw_map(Map map, size_t width, size_t height, int offset_x, int offset_y, Position start, Position goal, Path path, char visited[height][width]) {
    (void)path;
    /* I think it flickers less when we do that */
    wnoutrefresh(stdscr);

    /* Clean up the area around the map */
    for (ssize_t i = -1; i <= (ssize_t)(width*2 + 4); i++) { /* Horizontal */
        mvaddch(DRAW_MAP_OFFSET_Y - 1 + offset_y - 1, i + offset_x, ' ');
        mvaddch(DRAW_MAP_OFFSET_Y + height + offset_y + 1, i + offset_x, ' ');
    }
    for (size_t i = 0; i <= height + 2; i++) { /* Horizontal */
        mvaddch(i + offset_y, DRAW_MAP_OFFSET_X - 2 + offset_x - 2, ' ');
        mvaddch(i + offset_y, DRAW_MAP_OFFSET_X - 1 + offset_x - 2, ' ');
        mvaddch(i + offset_y, DRAW_MAP_OFFSET_X + width * 2 + offset_x + 2, ' ');
        mvaddch(i + offset_y, DRAW_MAP_OFFSET_X + width * 2 + 1 + offset_x + 2, ' ');
    }

    /* Draw the borders*/
    attron(COLOR_PAIR(WALL_COLOR));
    for (size_t i = 0; i <= width*2 + 3; i++) { /* Horizontal */
        mvaddch(DRAW_MAP_OFFSET_Y - 1 + offset_y, i + offset_x, WALL_CHAR);
        mvaddch(DRAW_MAP_OFFSET_Y + height + offset_y, i + offset_x, WALL_CHAR);
    }
    for (size_t i = 1; i <= height; i++) { /* Vertical */
        mvaddch(i + offset_y, DRAW_MAP_OFFSET_X - 2 + offset_x, WALL_CHAR);
        mvaddch(i + offset_y, DRAW_MAP_OFFSET_X - 1 + offset_x, WALL_CHAR);
        mvaddch(i + offset_y, DRAW_MAP_OFFSET_X + width * 2 + offset_x, WALL_CHAR);
        mvaddch(i + offset_y, DRAW_MAP_OFFSET_X + width * 2 + 1 + offset_x, WALL_CHAR);
    }
    attroff(COLOR_PAIR(WALL_COLOR));

    /* Draw field */
    char c; /* The char for the current tile */
    for (size_t i = 0; i < height; i++) {
        for (size_t j = 0; j < width; j++) {
            int color_pair = 0; /* The color pair of the current char  */
            switch (map[i][j]) {
                case EMPTY: 
                    if (visited[i][j])
                        color_pair = COLOR_PAIR(VISITED_COLOR);
                    else 
                        color_pair = COLOR_PAIR(EMPTY_COLOR);
                    c = EMPTY_CHAR; 
                    break;
                case WALL: 
                    color_pair = COLOR_PAIR(WALL_COLOR);
                    c = WALL_CHAR; 
                    break;

            }
            attron(color_pair);
            /* We draw two characters because they roughly make a square together.
             * It looks WAY better if we do this. */
            mvaddch(i + DRAW_MAP_OFFSET_Y + offset_y, j*2 + DRAW_MAP_OFFSET_X + offset_x, c);
            mvaddch(i + DRAW_MAP_OFFSET_Y + offset_y, j*2 + DRAW_MAP_OFFSET_X + 1 + offset_x, c);
            attroff(color_pair);
        }
    }

    /* Draw path */
    if (path != NULL) {
        attron(COLOR_PAIR(PATH_COLOR));
        Position cur = goal;
        while (cur.x != start.x || cur.y != start.y) {
            mvaddch(cur.y + DRAW_MAP_OFFSET_Y + offset_y, cur.x*2 + DRAW_MAP_OFFSET_X + offset_x, ' ');
            mvaddch(cur.y + DRAW_MAP_OFFSET_Y + offset_y, cur.x*2 + DRAW_MAP_OFFSET_X + 1 + offset_x, ' ');
            cur = path[cur.y][cur.x].parent;
        }
    }

    /* Draw the start */
    attron(A_BOLD);
    attron(COLOR_PAIR(START_COLOR));
    mvaddch(start.y + DRAW_MAP_OFFSET_Y + offset_y, start.x*2 + DRAW_MAP_OFFSET_X + offset_x, START_CHAR_1);
    mvaddch(start.y + DRAW_MAP_OFFSET_Y + offset_y, start.x*2 + DRAW_MAP_OFFSET_X + 1 + offset_x, START_CHAR_2);
    attroff(COLOR_PAIR(START_COLOR));

    /* Draw the goal */
    attron(COLOR_PAIR(GOAL_COLOR));
    mvaddch(goal.y + DRAW_MAP_OFFSET_Y + offset_y, goal.x*2 + DRAW_MAP_OFFSET_X + offset_x, GOAL_CHAR_1);
    mvaddch(goal.y + DRAW_MAP_OFFSET_Y + offset_y, goal.x*2 + DRAW_MAP_OFFSET_X + 1 + offset_x, GOAL_CHAR_2);
    attroff(COLOR_PAIR(GOAL_COLOR));
    attroff(A_BOLD);

    doupdate();
}

void print_map_out(Map map, size_t width, size_t height) {
    for (size_t i = 0; i < height; i++) {
        for (size_t j = 0; j < width; j++) {
            switch(map[i][j]) {
                case EMPTY: putchar(EMPTY_CHAR); break;
                case WALL: putchar(WALL_CHAR); break;
            }
        }
        putchar('\n');
    }
}