headerimage

SneManden.com

main.c

/**
 * Casper Kehlet Jensen, 2014-10-03 to 2014-10-04
 * Compiled with:   gcc -Wall -std=c89 -pedantic main.c -o main
 * 
 * TASK:
 * Implement the Wavefront algorithm using a potential function of own choosing
 * Calculate the length from Qstart=(9,85) to Qend=(832,874) in ”Labyrinth.pgm”
 * Upload an image of the path and of how the wave expand from the Qend.
 *
 * SOURCES:
 *   [wavefront algo.](http://www.cs.tufts.edu/comp/150IR/labs/wavefront.html)
 *   [PGM fileformat](http://netpbm.sourceforge.net/doc/pgm.html)
 */

#include <math.h>                       /* pow */
#include <time.h>                       /* time, localtime, strftime */
#include <ctype.h>                      /* isspace */
#include <stdio.h>                      /* printf, fopen, fclose, fprintf */
#include <stdlib.h>                     /* malloc */
#include <string.h>                     /* memset */

#define INFTY (pow(2, 8*sizeof(int))-1) /* 2^(8*4)-1 = 2^32-1 = 4294967295 */


struct {
    unsigned int value;             /* value set by wavefront (dist to start) */
    unsigned int neighbour[4];      /* index (pointer) to neighbour cell */
} typedef Node;

struct {
    Node *board;                    /* Array of Nodes (i.e pixels) */
    int width;
    int height;
    int size;                       /* # of pixels in image (nodes in board) */
    int maxGrey;                    /* Must be 0<maxGrey<65536 */
} typedef Image;

struct {
    int x;
    int y;
} typedef Point;


/* Forward declerations */
Image *parse_image(char *filename, int tolerance);
int wavefront(Image *img, Point start, Point goal);
int writepath(Image *img, Point start, Point goal, char *filename);



/**
 * MAIN
 */
int main(int argc, char **argv) {
    Point qStart, qEnd;
    int tolerance;
    Image *img;

    /* Create img */
    if (argc >= 6) {
        if (argc == 7)
            tolerance = atoi(argv[6]);
        img = parse_image(argv[1], tolerance);
        qStart.x = atoi(argv[2]);
        qStart.y = atoi(argv[3]);
        qEnd.x = atoi(argv[4]);
        qEnd.y = atoi(argv[5]);
    } else {
        fprintf(stderr, "Usage: %s %s %s %s [%s]\n",
            argv[0], "Image.pgm", "startx starty", "endx endy", "tolerance");
        return 1;
    }
    if (img == NULL) return 1;

    /* Perform algorithm */
    if (wavefront(img, qStart, qEnd) == 0) /* no error */
        writepath(img, qStart, qEnd, NULL);

    /* Free and exit */
    free(img->board);
    free(img);
    return 0;
}



/**
 * Performs the wavefront algorithm: use breadfirst search from goal to start
 *     assigning each neighbour the value of current cell + 1
 *     and put unvisited neighbours in a queue. If queue is empty => done
 * start and goal should be the ith pixel from top-left corner
 * @return       -1 on error, 0 on success
 */
int wavefront(Image *img, Point start, Point goal) {
    int i, j, queueSize, steps = 0;
    Node elm;
    int *queue = NULL;
    int queuetop = 0;
    int iGoal = goal.x + goal.y*img->width;

    printf("wavefront(img, (%d,%d), (%d,%d))\n",
        start.x, start.y, goal.x, goal.y);

    /* Initialize queue */
    queue = malloc(img->size * sizeof(int));
    if (queue == NULL) {
        fprintf(stderr, "Error: Out of memory\n");
        return -1;
    }

    /* Set goal value to 2 and put it in the queue */
    img->board[iGoal].value = 2;
    queue[0] = iGoal;
    queueSize = 1;
    while (queueSize != 0) {
        /* i = top of queue; offset queue by 1 and decrease size of queue */
        i = queue[queuetop];
        elm = img->board[i];
        queuetop++;
        queueSize--;
        /* for each neighbour: */
        for (j=0; j<4; j++) {
            /* if neighbour is valid AND value of neighbour == free cell */
            if (elm.neighbour[j] < img->size &&
                    img->board[elm.neighbour[j]].value == 0) {
                /* Set value of neighbour to elementvalue+1, and add to queue */
                img->board[elm.neighbour[j]].value = elm.value + 1;
                queue[queuetop+queueSize] = elm.neighbour[j];
                queueSize++;
            }
        }
        steps++;
        if (steps > img->size) { /* steps should never be more than #pixels */
            fprintf(stderr, "  Error: Too many iterations for wavefront!\n");
            return -1;
        }
    }
    free(queue);

    printf("wavefront finished\n");
    return 0;
}



/**
 * Finds the shortest (or one of them) path from start to goal
 * It just starts at start, and goes in the direction that has smallest value
 *     (from values of map generated by wavefront)
 * Writes the path to a new file with name "filename"
 *     or YYYY-MM-DD_HHMMSS.pgm if NULL
 * start and goal should be the ith pixel from top-left corner 
 * @return          -1 on error, distance>0 on success
 */
int writepath(Image *img, Point start, Point goal, char *filename) {
    int xs = start.x,   ys = start.y,
        xg = goal.x,    yg = goal.y;
    int iStart = start.x + start.y*img->width,
        iGoal = goal.x + goal.y*img->width;
    int pos, i, nval, smallest, steps;
    int colFree = 255, colObst = 200, colPath = 0;
    unsigned int smallestval;
    char *path = NULL;
    FILE *file;
    Node elm;
    time_t now;
    struct tm *current_time;
    char time_string[24];
    

    if (filename == NULL) {
        time(&now);
        current_time = localtime(&now);
        strftime(time_string, 24, "%Y-%m-%d_%H%M%S.pgm", current_time);
        file = fopen(time_string, "w");
    } else
        file = fopen(filename, "w");
    if (!file) {
        fprintf(stderr, "Error: Could not open file '%s' for writing\n",
            (filename == NULL ? time_string : filename) );
        return -1;
    }

    path = (char*) malloc(img->size * sizeof(char));
    if (path == NULL) {
        fprintf(stderr, "Error: Out of memory (char *path)\n");
        return -1;
    }
    memset(path, 0, img->size*sizeof(char)); /* set all pixels of path to 0 */

    pos = iStart;
    steps = 0;
    while (pos != iGoal) {
        path[pos] = 1; /* pixel is part of path (1=true) */
        elm = img->board[pos];
        /* Find neighbour with smallest value (chooses first if equal) */
        smallest = 0;
        smallestval = INFTY;
        for (i=0; i<4; i++) {
            if (elm.neighbour[i] >= img->size) continue; /* invalid neighbour */
            nval = img->board[elm.neighbour[i]].value;
            if (nval == 1) continue; /* neighbour is obstacle */
            smallest = (nval < smallestval ? i : smallest);
            smallestval = (nval < smallestval ? nval : smallestval);
        }
        /* Update pos to this neighbour */
        if (elm.neighbour[smallest] == pos) break;
        pos = elm.neighbour[smallest];
        steps++;
        if (steps > img->size) { /* steps should never be more than #pixels */
            fprintf(stderr, "  Error: Too many iterations for writepath!\n");
            return -1;
        }
    }
    printf("=> Distance from (%d,%d) to (%d,%d) is %d\n", xs,ys,xg,yg,steps);

    /* Write path to pgm file: header + #(img->size) pixels */
    fprintf(file, "P2\n%d %d\n%d\n", img->width, img->height, img->maxGrey);
    for (i=0; i<img->size; i++) {
        if (path[i] == 0) /* regular pixel write color according to obst/free */
            fprintf(file, "%d\n", (img->board[i].value==1 ? colObst : colFree));
        else /* pixel is part of path; write path color */
            fprintf(file, "%d\n", colPath);
    }
    fclose(file);

    free(path);
    return steps;
}



/**
 * Helper function for parse_image; skips the current line if is a comment
 *     The line is a comment if it starts with '#'
 */
void skipComment(FILE *file) {
    char c;
    char line[71]; /* Any line is maximally 70 characters long */

    while ( (c = getc(file)) != EOF && isspace(c) ) ; /* skip whitespace */
    if (c == '#') /* it is a comment => while line is read and discarded */
        fgets(line, sizeof(line), file);
    else /* Not a comment => take back that character */
        ungetc(c, file);
}



/**
 * Parses a .pgm file (very simple image file)
 * @param  filename name of .pgm file
 * @return          array of char's (interpreted as ints)
 */
Image *parse_image(char *filename, int tolerance) {
    FILE *file;
    char format[3]; /* Magic number */
    int width, height, maxGrey;
    int pixels, x, y, color, pos;
    Image *img;

    file = fopen(filename, "r");
    if (!file) {
        fprintf(stderr, "Error: Could not open file '%s'" \
                        " for reading\n", filename);
        return NULL;
    }

    img = (Image*) malloc(sizeof(Image));
    if (img == NULL) {
        fprintf(stderr, "Error: Out of memory (Image *img)\n");
        return NULL;
    }

    /* Determine fileformat */
    fscanf(file, "%2[P0-9]", format);
    if (strcmp(format, "P2") != 0) {
        fprintf(stderr, "Error: Filetype is not plain pgm (magic number P2)\n");
        return NULL;
    }
    /* Get width, height and maxGrey value from header */
    skipComment(file);
    fscanf(file, "%d", &width);
    skipComment(file);
    fscanf(file, "%d", &height);
    skipComment(file);
    fscanf(file, "%d", &maxGrey);

    img->board = (Node*) malloc(width*height*sizeof(Node));
    if (img->board == NULL) {
        fprintf(stderr, "Error: Out of memory (Node *img->board)\n");
        return NULL;
    }
    img->width = width;
    img->height = height;
    img->maxGrey = maxGrey;
    img->size = width*height;

    /* Read pixels; pos is translated (x,y) to ith pixel */
    for (pixels=0, y=0, x=0; fscanf(file, "%d", &color) != EOF; pixels++) {
        pos = y*width + x;
        img->board[pos].value = (color>tolerance ? 0 : 1); /* free/obstacle */
        /* Neighbours: 0=north, 1=south, 2=east, 3=west */
        /* if on a boundary, assign INFTY to neighbour (=> invalid index) */
        img->board[pos].neighbour[0] = (y > 0 ? (y-1)*width + x : INFTY);
        img->board[pos].neighbour[1] = (y < height-1 ? (y+1)*width + x : INFTY);
        img->board[pos].neighbour[2] = (x < width-1 ? pos+1 : INFTY);
        img->board[pos].neighbour[3] = (x > 0 ? pos-1 : INFTY);
        x = ((x+1) % width);
        y = (pixels+1)/width;
    }
    if (img->size != pixels) {
        fprintf(stderr, "Error: number of pixels does not match image size\n");
        fprintf(stderr, "  imagesize=%d vs. pixels=%d\n", img->size, pixels);
        return NULL;
    }
    return img;
}