Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
- // (C) 2010 Tim Gurto
- #include <stdio.h>
- #include <time.h>
- #include <stdlib.h>
- #include <assert.h>
- #include <string.h>
- #define BLANK (' ')
- #define TREE (219) //need to use unsigned chars
- #define TREASURE ('$')
- #define CHARACTER (1)
- #define PATH (249)
- typedef struct{
- int size;
- unsigned char **grid;
- } Map;
- typedef struct pathNode{
- int x;
- int y;
- struct pathNode *next;
- } PathNode;
- typedef struct queueNode{
- PathNode path;
- struct queueNode *next;
- } QueueNode;
- Map newMap(int size);
- void freeMap(Map map);
- void populateMap(Map *map, int numTrees);
- void printMap(Map map);
- void findFreeSpace(Map map, int *x, int *y);
- int findSolution(Map *map);
- int isSolution(PathNode *path, Map map);
- PathNode *copyPath(PathNode *original);
- PathNode *pathEnd(PathNode *path);
- void printPath(PathNode *path);
- int main(int argc, char **argv){
- int numTrees;
- int mapSize;
- Map map;
- int found;
- srand(time(0));
- //parse args
- assert (argc == 3);
- mapSize = atoi(argv[1]);
- numTrees = atoi(argv[2]);
- //new map
- map = newMap(mapSize);
- populateMap(&map, numTrees);
- //printMap(map);
- found = findSolution(&map);
- printMap(map);
- if (!found)
- printf("No path found.\n");
- //clean up
- freeMap(map);
- }
- //allocates a new size*size grid of chars
- Map newMap(int size){
- int i, j;
- Map map;
- map.size = size;
- map.grid = malloc(sizeof(char*) * map.size);
- for (i = 0; i < map.size; ++i){
- map.grid[i] = malloc(map.size); //array of chars
- for (j = 0; j < map.size; ++j)
- map.grid[i][j] = BLANK;
- }
- return map;
- }
- //deallocates the map
- void freeMap(Map map){
- int i;
- for (i = 0; i < map.size; ++i)
- free(map.grid[i]);
- free(map.grid);
- }
- //populates map with character, treasure and trees
- void populateMap(Map *map, int numTrees){
- int x, y;
- int i;
- //place character and treasure
- findFreeSpace(*map, &x, &y);
- map->grid[x][y] = CHARACTER;
- findFreeSpace(*map, &x, &y);
- map->grid[x][y] = TREASURE;
- //place trees
- for (i = 0; i < numTrees; ++i){
- findFreeSpace(*map, &x, &y);
- map->grid[x][y] = TREE;
- }
- }
- void printMap(Map map){
- int i, j;
- //top line
- printf("+");
- for (i = 0; i < map.size; ++i)
- printf("-");
- printf("+\n");
- //map
- for (i = 0; i < map.size; ++i){
- printf("|");
- for (j = 0; j < map.size; ++j)
- printf("%c", map.grid[j][i]);
- printf("|\n");
- }
- //bottom line
- printf("+");
- for (i = 0; i < map.size; ++i)
- printf("-");
- printf("+\n");
- }
- //find random location which isn't occupied
- void findFreeSpace(Map map, int *x, int *y){
- //TODO max tries
- do{
- *x = rand() % map.size;
- *y = rand() % map.size;
- }while(map.grid[*x][*y] != BLANK);
- }
- int findSolution(Map *map){
- int playerX = -1, playerY = -1;
- int i, j;
- QueueNode *queueStart, *queueEnd;
- int **tested;
- PathNode *newPath;
- int horDist, verDist;
- int oldX, oldY;
- PathNode *it;
- PathNode *copy;
- int x, y;
- QueueNode *temp;
- //initialize tested map
- tested = malloc(sizeof(int*) * map->size);
- for (i = 0; i < map->size; ++i)
- tested[i] = calloc(map->size, sizeof(int)); //0-initialized
- //find player location
- for (i = 0; i < map->size && playerX == -1; ++i)
- for (j = 0; j < map->size && playerX == -1; ++j)
- if (map->grid[i][j] == CHARACTER)
- playerX = i, playerY = j;
- assert(playerX != -1 && playerY != -1);
- //new queue, with one path in it, holding only the start location
- queueStart = queueEnd = malloc(sizeof(QueueNode));
- queueStart->next = NULL;
- queueStart->path.next = NULL;
- queueStart->path.x = playerX; //character's location
- queueStart->path.y = playerY;
- tested[playerX][playerY] = 1;
- //while front of queue is not a solution (solution: last element is the treasure)
- while (!isSolution(&queueStart->path, *map)){
- //new path for each direction (if new location is not taken, and is a space)
- it = pathEnd(&queueStart->path);
- oldX = it->x;
- oldY = it->y;
- for (horDist = -1; horDist <= 1; ++horDist)
- for (verDist = -1; verDist <= 1; ++verDist){ //skip if:
- x = oldX + horDist;
- y = oldY + verDist;
- if (horDist == 0 && verDist == 0) //no movement
- continue;
- if (horDist != 0 && verDist != 0) //diagonal
- continue;
- if (x < 0 || x >= map->size) //x out of bounds
- continue;
- if (y < 0 || y >= map->size) //y out of bounds
- continue;
- if (map->grid[x][y] == TREE) //moving into a tree
- continue;
- if (tested[x][y]) //new tile is already part of a path
- continue;
- tested[x][y] = 1;
- //add new path to end of queue
- copy = copyPath(&queueStart->path);
- newPath = malloc(sizeof(PathNode));
- newPath->next = NULL;
- newPath->x = x;
- newPath->y = y;
- pathEnd(copy)->next = newPath; //add new direction to the end of the path
- queueEnd->next = malloc(sizeof(QueueNode));
- queueEnd = queueEnd->next;
- queueEnd->path = *copy;
- queueEnd->next = NULL;
- }
- //remove front of queue
- //printPath(&queueStart->path);
- temp = queueStart->next;
- free(queueStart);
- queueStart = temp;
- if (temp == NULL) //no more paths; no solution
- return 0;
- }//while solution not found
- //solution found; add path to map
- it = queueStart->path.next; //start on 2nd step; 1st is the character
- while (it->next != NULL){
- if (map->grid[it->x][it->y] != TREASURE) //don't replace treasure character on map
- map->grid[it->x][it->y] = PATH;
- it = it->next;
- }
- //TODO clean up queue
- //clean up tested map
- for (i = 0; i < map->size; ++i)
- free(tested[i]);
- free(tested);
- return 1;
- }
- //determines whether the given path is a solution
- int isSolution(PathNode *path, Map map){
- path = pathEnd(path);
- return (map.grid[path->x][path->y] == TREASURE);
- }
- //creates a deep copy of a path
- PathNode *copyPath(PathNode *original){
- PathNode *copy, *temp;
- copy = malloc(sizeof(PathNode));
- *copy = *original;
- temp = copy;
- while (original->next != NULL){
- original = original->next; //iterate
- temp->next = malloc(sizeof(PathNode));
- temp = temp->next;
- *temp = *original;
- temp->next = NULL;
- }
- return copy;
- }
- //finds the end of a path
- PathNode *pathEnd(PathNode *path){
- while (path->next != NULL)
- path = path->next;
- return path;
- }
- //prints a path
- void printPath(PathNode *path){
- do{
- printf("(%d,%d) ", path->x, path->y);
- path = path->next;
- }while(path != NULL);
- printf("\n");
- }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.