Visualization of Simple Solving A Maze (DFS & BFS)

ReadMe.md

• This is Visualization of Simple Solving A Maze by C.

• To generate gif file, we need ImageMagick.

• We can generate gif file following commands.

• DFS

gcc main.c img.c -std=c99 -o main && ./main dfs;
convert -set delay 5 img*.ppm dfs.gif
rm img*.ppm

• BFS

gcc main.c img.c -std=c99 -o main && ./main bfs;
convert -set delay 5 img*.ppm bfs.gif
rm img*.ppm

• Both (unite) Large Memory consumption

gcc main.c img.c -std=c99 -o main && ./main;
convert -set delay 5 img*.ppm unite.gif
rm img*.ppm

img.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "img.h"

// image data (ppm format)
static unsigned char buf[HEIGHT][WIDTH][3];
static int filecnt = 0;
static char fname[100];

// direction vector
int dx[4] = {0, -1, 0, 1};
int dy[4] = {-1, 0, 1, 0};

// using array like a queue
Point que[4000];
int head = 0, tail = 0;

int flag = 1;

// maze data (20 * 20)
char maze[21][21] = {
    "####################",
    "#.................S#",
    "#.####.####.######.#",
    "#.#......##.#....#.#",
    "#.######.##.####.#.#",
    "#..#...####....#.#.#",
    "#.##.#.#.#####.#.#.#",
    "#.####.#.#...#.#.#.#",
    "#..........###.#.#.#",
    "#.###..#.###...#.#.#",
    "#.#.#######..###...#",
    "#.........#.######.#",
    "#.#######.#.#......#",
    "#.#.......#.####.#.#",
    "####.###.#####...#.#",
    "#.##...###.....#.#.#",
    "#..##..#.#.#####.#.#",
    "##.##.##.#.#.#######",
    "#........#........G#",
    "####################",
};

char tmp[21][21];

// fill image date by 0xff (white)
void img_clear() {
    for (int i = 0; i < HEIGHT; i++) {
        for (int j = 0; j < WIDTH; j++) {
            buf[i][j][0] = buf[i][j][1] = buf[i][j][2] = 0xff;
        }
    }
}

// generate image file
void img_write() {
    sprintf(fname, "img%04d.ppm", ++filecnt);
    FILE *f = fopen(fname, "wb");
    if (f == NULL) { fprintf(stderr, "can't open %s\n", fname); exit(1); }
    fprintf(f, "P6\n%d %d\n255\n", WIDTH, HEIGHT);
    fwrite(buf, sizeof(buf), 1, f);
    fclose(f);
}

void img_putpixel(color c, int x, int y) {
    if (x < 0 || x >= WIDTH || y < 0 || y >= HEIGHT) { return; }
    buf[HEIGHT-y-1][x][0] = c.r;
    buf[HEIGHT-y-1][x][1] = c.g;
    buf[HEIGHT-y-1][x][2] = c.b;
}

void fill_square(color c, int x, int y) {
    for (int i = 0; i < 10; i++) {
        for (int j = 0; j < 10; j++) {
            img_putpixel(c, x+i, y+j);
        }
    }
}

void fill_s(int x, int y) {
    color c = {0, 0, 0};
    char s[10][10] = {
        "..........",
        "...######.",
        "...######.",
        "##.##..##.",
        "##.##..##.",
        "##.##..##.",
        "##.##..##.",
        "#####.....",
        ".####.....",
        "..........",
    };
    for (int i = 0; i < 10; i++) {
        for (int j = 0; j < 10; j++) {
            if (s[i][j] == '#') {
                img_putpixel(c, x+i, y+j);
            }
        }
    }
}

void fill_g(int x, int y) {
    color c = {0, 0, 0};
    char s[10][10] = {
        "..........",
        ".########.",
        ".##....##.",
        ".##....##.",
        ".##....##.",
        ".##.##.##.",
        ".#####.##.",
        ".#####....",
        "....##....",
    };
    for (int i = 0; i < 10; i++) {
        for (int j = 0; j < 10; j++) {
            if (s[i][j] == '#') {
                img_putpixel(c, x+i, y+j);
            }
        }
    }
}

void draw_maze() {
    color c = {0, 0, 0};

    for (int i = 0; i < 20; i++) {
        for (int j = 0; j < 20; j++) {
            if (maze[i][j] == 'G') {
                fill_g(i*10, j*10);
            }
            else if (maze[i][j] == '#') {
                fill_square(c, i*10, j*10);
            }
        }
    }
}

void enqueue(Point c) {
    if (tail == 4000)  { tail = 0; }
    que[tail++] = c;
}

Point dequeue() {
    if (head == 4000) { head = 0; }
    return que[head++];
}

void copy_arr() {
    for (int i = 0; i < 20; i++) {
        for (int j = 0; j < 20; j++) {
            tmp[i][j] = maze[i][j];
        }
    }
}

void dfs(int sx, int sy, int gx, int gy) {
    color c = {0, 255, 0};
    fill_square(c, sx*10, sy*10);
    fill_s(10, 180);
    fill_g(180, 180);
    img_write();
    tmp[sx][sy] = '#';
    for (int i = 0; i < 4; i++) {
        int nx = sx + dx[i], ny = sy + dy[i];
        // 範囲外かどうかの判定
        if (nx < 0 || 19 < nx || ny < 0 || 19 < ny) { continue; }
        // 壁の判定
        if (tmp[nx][ny] == '#') { continue; }
        // 未訪問かつ flag が立っていたら (ゴールが見つかっていなかったら) 進む
        else if (flag) {
            if (nx == gx && ny == gy) { flag = 0; }
            dfs(nx, ny, gx, gy);
        }
    }
    return ;
}

void bfs(int sx, int sy, int gx, int gy) {
    flag = 1;
    color c = {0, 255, 255};
    fill_square(c, sx*10, sy*10);
    Point p; p.x = sx; p.y = sy;
    enqueue(p);
    fill_s(10, 180);
    fill_g(180, 180);
    img_write();

    while (head != tail) {
        // Queue の先頭を取り出す
        p = dequeue();
        int x = p.x, y = p.y;
        img_write();
        // 移動を4方向にループ
        for (int i = 0; i < 4; i++) {
            // 移動した後の点を(nx, ny) とする
            int nx = x + dx[i], ny = y + dy[i];
            p.x = nx; p.y = ny;
            // 範囲外かどうかの判定
            if (nx < 0 || 19 < nx || ny < 0 || 19 < ny) { continue; }
            // 壁の判定
            if (tmp[nx][ny] == '#') { continue; }

            else if (flag) {
                if (nx == gx && ny == gy) { flag = 0; }
                fill_square(c, nx*10, ny*10);
                tmp[nx][ny] = '#';
                fill_s(10, 180);
                fill_g(180, 180);
                enqueue(p);
                img_write();
            }
            else {
                return ;
            }
        }
    }
}

img.h

#define WIDTH 200
#define HEIGHT 200

typedef struct { unsigned char r, g, b; } color;
typedef struct { int x, y; } Point;

void img_clear();
void img_write();
void img_putpixel(color c, int x, int y);
void fill_square(color c, int x, int y);
void fill_s(int x, int y);
void fill_g(int x, int y);
void draw_maze();
void copy_arr();
void dfs(int sx, int sy, int gx, int gy);
void bfs(int sx, int sy, int gx, int gy);

main.c

#include <stdio.h>
#include <string.h>
#include "img.h"

int main(int argc, char *argv[]) {
    Point start = {1, 18};
    Point goal  = {18, 18};

    img_clear();
    draw_maze();
    copy_arr();
    if (argc < 2) {
        dfs(start.x, start.y, goal.x, goal.y);
        for (int i = 0; i < 10; i++) { img_write(); }
        img_clear();
        draw_maze();
        copy_arr();
        bfs(start.x, start.y, goal.x, goal.y);
    }
    else if (!strcmp(argv[1], "dfs")) {
        dfs(start.x, start.y, goal.x, goal.y);
    }
    else if (!strcmp(argv[1], "bfs")) {
        bfs(start.x, start.y, goal.x, goal.y);
    }
    else {
        printf("Usage: ./a.out [dfs or bfs]");
    }

    img_write();
    for (int i = 0; i < 10; i++) {
        img_write();
    }
    return 0;
}

make.sh

#!/bin/bash
gcc main.c img.c -std=c99 -o main && ./main dfs;
convert -set delay 5 img*.ppm dfs.gif
rm img*.ppm

gcc main.c img.c -std=c99 -o main && ./main bfs;
convert -set delay 5 img*.ppm bfs.gif
rm img*.ppm

dfs.gif

bfs.gif

unite.gif