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"
#include "priority_queue.h"

int map_offset_x = 2;
int map_offset_y = 1;
char message[MESSAGE_MAX_SIZE] = "";

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;
}

/* Honestly, what a shitty fucking way to implement this */
/* TODO: maybe merge them, add `dirs` parameter, like we do in path.c? */
unsigned int neighbours_4dir(Position neighbour_array[4], size_t cost_array[4], Position pos, size_t width, size_t height, \
        char **visited, size_t **costs) {
    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;
        if (cost_array != NULL) {
            if (costs != NULL) cost_array[cur] = costs[pos.y][pos.x - 1] * COST_ORTHOGONAL;
            else cost_array[cur] = COST_ORTHOGONAL;
        }
        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;
        if (cost_array != NULL) {
            if (costs != NULL) cost_array[cur] = costs[pos.y][pos.x + 1] * COST_ORTHOGONAL;
            else cost_array[cur] = COST_ORTHOGONAL;
        }
        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;
        if (cost_array != NULL) {
            if (costs != NULL) cost_array[cur] = costs[pos.y - 1][pos.x] * COST_ORTHOGONAL;
            else cost_array[cur] = COST_ORTHOGONAL;
        }
        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;
        if (cost_array != NULL) {
            if (costs != NULL) cost_array[cur] = costs[pos.y + 1][pos.x] * COST_ORTHOGONAL;
            else cost_array[cur] = COST_ORTHOGONAL;
        }
        cur += 1;
    }

    return cur;
}

unsigned int neighbours_8dir(Position neighbour_array[8], size_t cost_array[8], Position pos, size_t width, size_t height, \
        char **visited, size_t **costs) {
    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;
        if (cost_array != NULL) {
            if (costs != NULL) cost_array[cur] = costs[pos.y][pos.x - 1] * COST_ORTHOGONAL;
            else cost_array[cur] = COST_ORTHOGONAL;
        }
        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;
        if (cost_array != NULL) {
            if (costs != NULL) cost_array[cur] = costs[pos.y][pos.x + 1] * COST_ORTHOGONAL;
            else cost_array[cur] = COST_ORTHOGONAL;
        }
        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;
        if (cost_array != NULL) {
            if (costs != NULL) cost_array[cur] = costs[pos.y - 1][pos.x] * COST_ORTHOGONAL;
            else cost_array[cur] = COST_ORTHOGONAL;
        }
        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;
        if (cost_array != NULL) {
            if (costs != NULL) cost_array[cur] = costs[pos.y + 1][pos.x] * COST_ORTHOGONAL;
            else cost_array[cur] = COST_ORTHOGONAL;
        }
        cur += 1;
    }

    if (pos.x > 0 && pos.y > 0 && !visited[pos.y - 1][pos.x - 1]) {
        neighbour_array[cur].x = pos.x - 1;
        neighbour_array[cur].y = pos.y - 1;
        if (cost_array != NULL) {
            if (costs != NULL) cost_array[cur] = costs[pos.y - 1][pos.x - 1] * COST_DIAGONAL;
            else cost_array[cur] = COST_DIAGONAL;
        }
        cur += 1;
    }
    if (pos.x + 1 < width && pos.y > 0 && !visited[pos.y - 1][pos.x + 1]) {
        neighbour_array[cur].x = pos.x + 1;
        neighbour_array[cur].y = pos.y - 1;
        if (cost_array != NULL) {
            if (costs != NULL) cost_array[cur] = costs[pos.y - 1][pos.x + 1] * COST_DIAGONAL;
            else cost_array[cur] = COST_DIAGONAL;
        }
        cur += 1;
    }
    if (pos.x + 1 < width && pos.y + 1 < height && !visited[pos.y + 1][pos.x + 1]) {
        neighbour_array[cur].x = pos.x + 1;
        neighbour_array[cur].y = pos.y + 1;
        if (cost_array != NULL) {
            if (costs != NULL) cost_array[cur] = costs[pos.y + 1][pos.x + 1] * COST_DIAGONAL;
            else cost_array[cur] = COST_DIAGONAL;
        }
        cur += 1;
    }
    if (pos.x > 0 && pos.y + 1 < height && !visited[pos.y + 1][pos.x - 1]) {
        neighbour_array[cur].x = pos.x - 1;
        neighbour_array[cur].y = pos.y + 1;
        if (cost_array != NULL) {
            if (costs != NULL) cost_array[cur] = costs[pos.y + 1][pos.x - 1] * COST_DIAGONAL;
            else cost_array[cur] = COST_DIAGONAL;
        }
        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 = visited_new(width, height);
    visited_clear(visited, 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_4dir(na, NULL, ps_peek(ps), width, height, visited, NULL);
        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) ;

    visited_free(visited, height);
    ps_free(ps);
    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;
}

size_t **file_plaintext_costs(char *filename, size_t width, size_t height) {
    FILE *file = fopen(filename, "r");
    if (file == NULL) {
        error("Failed to open file %s\n", filename);
    }

    size_t fw, fh; /* file width and height */
    if (fscanf(file, "%zux%zu\n", &fw, &fh) != 2) {
        error("Failed reading size of cost file %s\n", filename);
    }
    if (fw != width || fh != height) {
        set_message("Wrong size (%zux%zu vs %zux%zu) in cost file %s\n", fw, fh, width, height, filename);
        print_message(height);
        return NULL;
    }

    size_t **costs = cost_new(width, height);
    if (costs == NULL) error("Failed to create a new costs array\n");

    for (size_t row = 0; row < fh; row++) {
        for (size_t col = 0; col < fw; col++) {
            if (fscanf(file, "%zu", &costs[row][col]) != 1) error("Failed reading cost on x = %zu, y = %zu in cost file %s\n", col, row, filename);
        }
        fgetc(file); /* the newline */
    }

    set_message("Loaded costs from %s", filename);
    print_message(height);
    return costs;
}

void map_to_file_plaintext(char *filename, Map map, size_t width, size_t height, Position start, Position end) {
    FILE *file = fopen(filename, "w");
    if (file == NULL) {
        set_message("Couldn't open %s for writing", filename);
        print_message(height);
        return;
    }

    /* Size and chars */
    fprintf(file, "%zux%zu\n.#@x\n", width, height);
    for (size_t row = 0; row < height; row++) {
        for (size_t col = 0; col < width; col++) {
            if (row == start.y && col == start.x) { putc('@', file); continue; }
            if (row == end.y && col == end.x) { putc('x', file); continue; }
            switch (map[row][col]) {
                case EMPTY: putc('.', file); break;
                case WALL: putc('#', file); break;
            }
        }
        putc('\n', file);
    }

    set_message("Saved the map to %s", filename);
    print_message(height);
    return;
}

/* TODO: so many fucking arguments lmao. Break it down into several functions? */
/* TODO: draw the start and goal with no background, allowing us to see the frontier/path/whatever's underneath. I think attr_get() will be useful */
/* TODO: draw arrow for visited too */
void draw_map(Map map, size_t **cell_costs, size_t width, size_t height, Position start, Position goal, Position *cursor, Path path, char **visited, PositionPQ *frontier) {
    /* I think it flickers less when we do that
     * UPD: it was causing a bug, so I commented it out. I don't know why either */
    //wnoutrefresh(stdscr);

    erase();

    /* Rendering boundaries, used to not render stuff that's outside the screen for performance */
    size_t top_boundary = 0,
           bottom_boundary = height,
           left_boundary = 0,
           right_boundary = width;
    if (map_offset_y < 0) top_boundary = -map_offset_y;
    if (map_offset_x < 0) left_boundary = -(map_offset_x / 2);
    if (top_boundary + LINES < height) bottom_boundary = top_boundary + LINES;
    if (left_boundary + COLS/2 < height) right_boundary = left_boundary + COLS/2 + 1;

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

    /* Draw field */
    if (map != NULL) {
        char c = '\0'; /* The char for the current tile */
        for (size_t row = top_boundary; row < bottom_boundary; row++) {
            for (size_t col = left_boundary; col < right_boundary; col++) {
                int color_pair = 0; /* The color pair of the current char  */
                switch (map[row][col]) {
                    case EMPTY:
                        if (visited != NULL && visited[row][col])
                            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(row + map_offset_y, col*2 + map_offset_x, c);
                mvaddch(row + map_offset_y, col*2 + 1 + map_offset_x, c);
                attroff(color_pair);
            }
        }
    } else {
        for (size_t i = 0; i < height; i++) {
            for (size_t j = 0; j < width; j++) {
                if (visited != NULL && visited[i][j]) attron(COLOR_PAIR(VISITED_COLOR));
                mvaddch(i + map_offset_y, j*2 + map_offset_x, ' ');
                mvaddch(i + map_offset_y, j*2 + 1 + map_offset_x, ' ');
                if (visited != NULL && visited[i][j]) attroff(COLOR_PAIR(VISITED_COLOR));
            }
        }
    }

    /* Render the frontier */
    if (frontier != NULL) {
        attron(COLOR_PAIR(FRONTIER_COLOR));
        while (frontier->next != NULL) {
            mvaddch(frontier->pos.y + map_offset_y, frontier->pos.x*2 + map_offset_x, ' ');
            mvaddch(frontier->pos.y + map_offset_y, frontier->pos.x*2 + 1 + map_offset_x, ' ');
            frontier = frontier->next;
        }
        mvaddch(frontier->pos.y + map_offset_y, frontier->pos.x*2 + map_offset_x, ' ');
        mvaddch(frontier->pos.y + map_offset_y, frontier->pos.x*2 + 1 + map_offset_x, ' ');

        attroff(COLOR_PAIR(FRONTIER_COLOR));
    }

    /* Draw path */
    if (path != NULL) {
        size_t length = 0;
        attron(COLOR_PAIR(PATH_COLOR));
        Position prev = goal;
        Position cur = goal;
        while (cur.x != start.x || cur.y != start.y) {
            if (cur.x >= left_boundary && cur.x < right_boundary\
                    && cur.y >= top_boundary && cur.y < bottom_boundary) {
                char c1 = ' ', c2 = ' ';
                if (cur.x + 1 - prev.x == 0) { /* To the right */
                    if (cur.y == prev.y) {
                        c1 = ' '; c2 = '>';
                    } else if (cur.y + 1 - prev.y == 0) {
                        c1 = ' '; c2 = 'J';
                    } else {
                        c1 = ' '; c2 = '*';
                    }
                } else if (cur.x - prev.x == 1) { /* To the left */
                    if (cur.y == prev.y) {
                        c1 = '<'; c2 = ' ';
                    } else if (cur.y + 1 - prev.y == 0) {
                        c1 = 'L'; c2 = ' ';
                    } else {
                        c1 = 'F'; c2 = ' ';
                    }
                } else { /* Purely vertical */
                    if (cur.y + 1 - prev.y == 0) {
                        c1 = '\\'; c2 = '/';
                    } else if (cur.y - prev.y == 1) {
                        c1 = '/'; c2 = '\\';
                    }
                }
                mvaddch(cur.y + map_offset_y, cur.x*2 + map_offset_x, c1);
                mvaddch(cur.y + map_offset_y, cur.x*2 + 1 + map_offset_x, c2);
            }

            if (cur.x - path[cur.y][cur.x].x == 0 || cur.y - path[cur.y][cur.x].y == 0) {
                if (cell_costs != NULL) length += cell_costs[cur.y][cur.x] * COST_ORTHOGONAL;
                else length += COST_ORTHOGONAL;
            } else {
                if (cell_costs != NULL) length += cell_costs[cur.y][cur.x] * COST_DIAGONAL;
                else length += COST_DIAGONAL;
            }
            prev = cur;
            cur = path[cur.y][cur.x];
        }
        attroff(COLOR_PAIR(PATH_COLOR));
        attron(COLOR_PAIR(WALL_TEXT_COLOR));
        mvprintw(map_offset_y - 1, map_offset_x, "Path cost: %zu", length);
        attroff(COLOR_PAIR(WALL_TEXT_COLOR));
    }

    if (visited != NULL) {
        attron(COLOR_PAIR(WALL_TEXT_COLOR));
        mvprintw(height + map_offset_y, map_offset_x, "Visited %zu cells", visited_count(visited, width, height));
        attroff(COLOR_PAIR(WALL_TEXT_COLOR));
    }

    /* Draw the start */
    attron(A_BOLD);
    attron(COLOR_PAIR(START_COLOR));
    mvaddch(start.y + map_offset_y, start.x*2 + map_offset_x, START_CHAR_1);
    mvaddch(start.y + map_offset_y, start.x*2 + 1 + map_offset_x, START_CHAR_2);
    attroff(COLOR_PAIR(START_COLOR));

    /* Draw the goal */
    attron(COLOR_PAIR(GOAL_COLOR));
    mvaddch(goal.y + map_offset_y, goal.x*2 + map_offset_x, GOAL_CHAR_1);
    mvaddch(goal.y + map_offset_y, goal.x*2 + 1 + map_offset_x, GOAL_CHAR_2);
    attroff(COLOR_PAIR(GOAL_COLOR));

    /* Draw the cursor */
    if (cursor != NULL) {
        attron(COLOR_PAIR(CURSOR_COLOR));
        mvaddch(cursor->y + map_offset_y, cursor->x*2 + map_offset_x, CURSOR_CHAR_1);
        mvaddch(cursor->y + map_offset_y, cursor->x*2 + 1 + map_offset_x, CURSOR_CHAR_2);
        attroff(COLOR_PAIR(CURSOR_COLOR));
    }
    attroff(A_BOLD);

    print_message(height);

    /* Read the comment at the start of this function */
    //doupdate();
}

void print_message(size_t height) {
    if (mvaddnstr(height + map_offset_y + 1, map_offset_x - 2, message, MESSAGE_MAX_SIZE) == OK) clrtoeol();
}

void map_free(Map map, size_t height) {
    if (map == NULL) return;
    for (size_t i = 0; i < height; i++) {
        free(map[i]);
    }
    free(map);
}

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');
    }
}

void map_editor(Map *map, size_t *width, size_t *height, Position *start, Position *goal, int dirs) {
    char should_pathfind = 0;

    char **visited = NULL;
    Path path = NULL;

    draw_map(*map, NULL, *width, *height, *start, *goal, NULL, path, visited, NULL);
    set_message("You've entered the map editor. 'q' to quit");
    print_message(*height);

    MEVENT event;
    mmask_t oldmask;
    mousemask(ALL_MOUSE_EVENTS | REPORT_MOUSE_POSITION, &oldmask);
    mouseinterval(0);
    printf("\033[?1003h\n"); /* Makes the terminal report mouse movements */

    char m1down = 0;
    MapTile cur = EMPTY;
    while (1) {
        int ch = getch();

        /*
         * Keybindings:
         *    [k]    \
         * [h]   [l] } Move the view
         *    [j]    /
         *
         *    [K]    \
         * [H]   [L] } Move the view faster
         *    [J]    /
         *
         *    [z]    - Move the view to the top left corner
         *    [x]    - Move the view to the bottom right corner
         *
         *    [g] followed by:
         *       [s] - Move the view to the start
         *       [e] - Move the view to the end
         *
         *    [a]    - Toggle pathfinding
         *
         *    [d]    - Switch algorithms (A* or Dijsktra's)
         *
         *    [s]    - Save the map to a plaintext file
         *
         *    [q]    - Exit the map editor
         *
         * Mousebindings:
         *   LMB on wall/empty space to toggle them
         *   Drag start/goal with LMB to move them
         *   Drag right/bottom borders with LMB to resize the map
         *   Drag with MMB to move the view (buggy)
         */
        switch (ch) {
            case 'q': clear_message(); visited_free(visited, *height); path_free(path, *height); mousemask(oldmask, NULL); printf("\033[?1003l\n"); return;

            case 'h': map_offset_x += 2; break;
            case 'l': map_offset_x -= 2; break;
            case 'j': map_offset_y -= 1; break;
            case 'k': map_offset_y += 1; break;

            case 'H': clear(); map_offset_x += 20; break;
            case 'L': clear(); map_offset_x -= 20; break;
            case 'J': clear(); map_offset_y -= 10; break;
            case 'K': clear(); map_offset_y += 10; break;

            case 'z': clear(); map_offset_x = 2; map_offset_y = 1; break; /* Move to top left corner */
            case 'x': clear(); map_offset_x = - *width * 2 + COLS - 2; map_offset_y = - *height + LINES - 2; break; /* Move to bottom right corner */
            case 'a':
                      should_pathfind = !should_pathfind;
                      if (should_pathfind) {
                          set_message("Will pathfind");
                          visited = visited_new(*width, *height);
                          path = path_func(dirs, *map, NULL, *width, *height, *start, *goal, visited, 0);
                      } else {
                          set_message("Won't pathfind");
                          visited_free(visited, *height); visited = NULL;
                          path_free(path, *height); path = NULL;
                      }
                      print_message(*height);
                      break;

            case 'g':
                      switch (getch()) {
                          case 's':
                              clear();
                              map_offset_x = -start->x * 2 + COLS/2;
                              map_offset_y = -start->y + LINES/2;
                              break;
                          case 'e':
                              clear();
                              map_offset_x = -goal->x * 2 + COLS/2;
                              map_offset_y = -goal->y + LINES/2;
                              break;
                      }
                      break;

            case 'd':
                      if (path_func == astar_path) { set_message("Dijkstra"); path_func = &dijkstra_path; }
                      else { set_message("A*"); path_func = &astar_path; };
                      path_free(path, *height);
                      if (should_pathfind) path = path_func(dirs, *map, NULL, *width, *height, *start, *goal, visited, 0);
                      break;

            case 's':
                      curs_set(2);   /* Show the cursor */
                      echo();        /* Echo characters */

                      set_message(FILENAME_PROMPT);
                      print_message(*height);
                      char filename[FILENAME_BUF_SIZE] = "map";
                      mvgetnstr(*height + map_offset_y + 1, map_offset_x - 2 + sizeof(FILENAME_PROMPT), filename, FILENAME_BUF_SIZE - 1);

                      curs_set(0);   /* Hide the cursor */
                      noecho();      /* Don't echo characters */

                      map_to_file_plaintext(filename, *map, *width, *height, *start, *goal);

                      break;

            /* TODO: keybindings to resize the map */
        }

        /* Handle mouse */
        if (ch == KEY_MOUSE) {
            if (getmouse(&event) == OK) {
                if (event.bstate & BUTTON2_PRESSED) {
                    int init_x = event.x,
                        init_y = event.y,
                        init_map_offset_x = map_offset_x,
                        init_map_offset_y = map_offset_y;
                    while ((ch = getch()) == KEY_MOUSE \
                            && getmouse(&event) == OK && !(event.bstate & BUTTON2_RELEASED)) {
                        map_offset_y = init_map_offset_y + (event.y - init_y);
                        map_offset_x = init_map_offset_x + ((event.x - init_x) / 2 * 2);
                        draw_map(*map, NULL, *width, *height, *start, *goal, NULL, path, visited, NULL);
                    }
                }
                if (event.bstate & BUTTON1_PRESSED) {
                    /* Translate event coordinates into map coordinates */
                    size_t row = event.y - map_offset_y,
                           col = (event.x - map_offset_x) / 2;

                    if (start->x == col && start->y == row) { /* Move the start */
                        while ((ch = getch()) == KEY_MOUSE && getmouse(&event) == OK && !(event.bstate & BUTTON1_RELEASED)) {
                            row = event.y - map_offset_y;
                            col = (event.x - map_offset_x) / 2;
                            if (row < *height && col < *width && (*map)[row][col] != WALL && (col != goal->x || row != goal->y)) {
                                start->x = col;
                                start->y = row;
                                if (should_pathfind) path = path_func(dirs, *map, NULL, *width, *height, *start, *goal, visited, 0);
                                draw_map(*map, NULL, *width, *height, *start, *goal, NULL, path, visited, NULL);
                            }
                        }
                    } else if (goal->x == col && goal->y == row) { /* Move the goal */
                        while ((ch = getch()) == KEY_MOUSE && getmouse(&event) == OK && !(event.bstate & BUTTON1_RELEASED)) {
                            row = event.y - map_offset_y;
                            col = (event.x - map_offset_x) / 2;
                            if (row < *height && col < *width && (*map)[row][col] != WALL && (col != start->x || row != start->y)) {
                                goal->x = col;
                                goal->y = row;
                                if (should_pathfind) path = path_func(dirs, *map, NULL, *width, *height, *start, *goal, visited, 0);
                                draw_map(*map, NULL, *width, *height, *start, *goal, NULL, path, visited, NULL);
                            }
                        }
                    } else if (row == *height) { /* Resize vertically */
                        /* Draw the line when we just click the border */
                        for (size_t i = map_offset_x; i < *width*2 + map_offset_x; i++) {
                            mvaddch(event.y, i, '=');
                        }

                        /* Wait for BUTTON1_RELEASED */
                        while ((ch = getch()) == KEY_MOUSE && getmouse(&event) == OK && !(event.bstate & BUTTON1_RELEASED)) {
                            if (event.y <= map_offset_y) continue;
                            draw_map(*map, NULL, *width, *height, *start, *goal, NULL, path, visited, NULL);
                            for (size_t i = map_offset_x; i < *width*2 + map_offset_x; i++) {
                                mvaddch(event.y, i, '=');
                            }
                            mvprintw(event.y, map_offset_x, "%u", event.y - map_offset_y);
                        };

                        size_t new_height = event.y - map_offset_y;
                        if (event.y <= map_offset_y) continue;

                        Map new_map = empty_map(*width, new_height);
                        map_copy(*map, *width, *height, new_map, *width, new_height);

                        map_free(*map, *height);
                        visited_free(visited, *height);
                        path_free(path, *height);

                        *height = new_height;
                        *map = new_map;

                        /* Make sure start and goal aren't outside of the map */
                        if (start->y >= *height) {
                            start->y = *height - 1;
                        }
                        if (goal->y >= *height) {
                            goal->y = *height - 1;
                        }
                        if ((*map)[goal->y][goal->x] == WALL || (*map)[start->y][start->x] == WALL) {
                            set_message("WARNING: start or goal is on a wall");
                            print_message(*height);
                        }

                        if (should_pathfind) {
                            visited = visited_new(*width, *height);
                            path = path_func(dirs, *map, NULL, *width, *height, *start, *goal, visited, 0);
                        }
                        draw_map(*map, NULL, *width, *height, *start, *goal, NULL, path, visited, NULL);
                    } else if (col == *width) { /* Resize horizontally */
                        size_t new_width = (event.x - map_offset_x) / 2;

                        /* Draw the line when we just click the border */
                        for (size_t i = map_offset_y; i < *height + map_offset_y; i++) {
                            mvaddch(i, new_width * 2 + map_offset_x, '|');
                            mvaddch(i, new_width * 2 + map_offset_x + 1, '|');
                        }

                        /* Wait for BUTTON1_RELEASED */
                        while ((ch = getch()) == KEY_MOUSE && getmouse(&event) == OK && !(event.bstate & BUTTON1_RELEASED)) {
                            size_t new_width = (event.x - map_offset_x) / 2;
                            if (event.x <= map_offset_x || new_width == 0) continue;
                            draw_map(*map, NULL, *width, *height, *start, *goal, NULL, path, visited, NULL);
                            for (size_t i = map_offset_y; i < *height + map_offset_y; i++) {
                                mvaddch(i, new_width * 2 + map_offset_x, '|');
                                mvaddch(i, new_width * 2 + map_offset_x + 1, '|');
                            }
                            mvprintw(map_offset_y, new_width*2 + map_offset_x, "%u", (event.x - map_offset_x) / 2);
                        };

                        new_width = (event.x - map_offset_x) / 2;
                        if (event.x <= map_offset_x || new_width == 0) continue;

                        Map new_map = empty_map(new_width, *height);
                        map_copy(*map, *width, *height, new_map, new_width, *height);

                        map_free(*map, *height);
                        visited_free(visited, *height);
                        path_free(path, *height);

                        *width = new_width;
                        *map = new_map;

                        /* Make sure start and goal aren't outside of the map */
                        if (start->x >= *width) {
                            start->x = *width - 1;
                        }
                        if (goal->x >= *width) {
                            goal->x = *width - 1;
                        }
                        if ((*map)[goal->y][goal->x] == WALL || (*map)[start->y][start->x] == WALL) {
                            set_message("WARNING: start or goal is on a wall");
                            print_message(*height);
                        }

                        if (should_pathfind) {
                            visited = visited_new(*width, *height);
                            path = path_func(dirs, *map, NULL, *width, *height, *start, *goal, visited, 0);
                        }
                        draw_map(*map, NULL, *width, *height, *start, *goal, NULL, path, visited, NULL);
                    } else { /* Start drawing */
                        m1down = 1;
                        if (row < *height && col < *width) {
                            if ((*map)[row][col] == WALL)
                                cur = EMPTY;
                            else
                                cur = WALL;
                        }
                    }
                } else if (event.bstate & BUTTON1_RELEASED) {
                    m1down = 0;
                }
                /* Draw */
                if (m1down) {
                    size_t row = event.y - map_offset_y,
                           col = (event.x - map_offset_x) / 2;
                    if (!((row == start->y && col == start->x) || (row == goal->y && col == goal->x)) && row < *height && col < *width) {
                        (*map)[row][col] = cur;
                        path_free(path, *height);
                        if (should_pathfind) {
                            path = path_func(dirs, *map, NULL, *width, *height, *start, *goal, visited, 0);
                        }
                        draw_map(*map, NULL, *width, *height, *start, *goal, NULL, path, visited, NULL);
                    }
                }
            }
        } else { /* Only update the map if not a mouse event */
            /* FIXME: I don't like in how many places we call draw_map(), maybe there's a better way? */
            draw_map(*map, NULL, *width, *height, *start, *goal, NULL, path, visited, NULL);
        }
    }

    mousemask(oldmask, NULL);
    printf("\033[?1003l\n"); /* Makes the terminal NOT report mouse movements */
}

void map_copy(Map src, size_t src_w, size_t src_h, Map dest, size_t dest_w, size_t dest_h) {
    for (size_t row = 0; row < src_h && row < dest_h; row++) {
        for (size_t col = 0; col < src_w && col < dest_w; col++) {
            dest[row][col] = src[row][col];
        }
    }
}