Public Pastes
SHARE
TWEET

TreasureFinder

Archon Nov 13th, 2010 101 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. // (C) 2010 Tim Gurto
  2.  
  3. #include <stdio.h>
  4. #include <time.h>
  5. #include <stdlib.h>
  6. #include <assert.h>
  7. #include <string.h>
  8.  
  9. #define BLANK     (' ')
  10. #define TREE      (219) //need to use unsigned chars
  11. #define TREASURE  ('$')
  12. #define CHARACTER (1)
  13. #define PATH      (249)
  14.  
  15. typedef struct{
  16.    int size;
  17.    unsigned char **grid;
  18. } Map;
  19.  
  20. typedef struct pathNode{
  21.    int x;
  22.    int y;
  23.    struct pathNode *next;
  24. } PathNode;
  25.  
  26. typedef struct queueNode{
  27.    PathNode path;
  28.    struct queueNode *next;
  29. } QueueNode;
  30.  
  31. Map newMap(int size);
  32. void freeMap(Map map);
  33. void populateMap(Map *map, int numTrees);
  34. void printMap(Map map);
  35. void findFreeSpace(Map map, int *x, int *y);
  36. int findSolution(Map *map);
  37. int isSolution(PathNode *path, Map map);
  38. PathNode *copyPath(PathNode *original);
  39. PathNode *pathEnd(PathNode *path);
  40. void printPath(PathNode *path);
  41.  
  42. int main(int argc, char **argv){
  43.    int numTrees;
  44.    int mapSize;
  45.    Map map;
  46.    int found;
  47.  
  48.    srand(time(0));
  49.    
  50.    //parse args
  51.    assert (argc == 3);
  52.    mapSize = atoi(argv[1]);
  53.    numTrees = atoi(argv[2]);
  54.  
  55.    //new map
  56.    map = newMap(mapSize);
  57.    populateMap(&map, numTrees);
  58.    //printMap(map);
  59.  
  60.    found = findSolution(&map);
  61.    printMap(map);
  62.    if (!found)
  63.       printf("No path found.\n");
  64.  
  65.    //clean up
  66.    freeMap(map);
  67. }
  68.  
  69. //allocates a new size*size grid of chars
  70. Map newMap(int size){
  71.    int i, j;
  72.    Map map;
  73.    map.size = size;
  74.    map.grid = malloc(sizeof(char*) * map.size);
  75.    for (i = 0; i < map.size; ++i){
  76.       map.grid[i] = malloc(map.size); //array of chars
  77.       for (j = 0; j < map.size; ++j)
  78.          map.grid[i][j] = BLANK;
  79.    }
  80.    return map;
  81. }
  82.  
  83. //deallocates the map
  84. void freeMap(Map map){
  85.    int i;
  86.    for (i = 0; i < map.size; ++i)
  87.       free(map.grid[i]);
  88.    free(map.grid);
  89. }
  90.  
  91. //populates map with character, treasure and trees
  92. void populateMap(Map *map, int numTrees){
  93.    int x, y;
  94.    int i;
  95.  
  96.    //place character and treasure
  97.    findFreeSpace(*map, &x, &y);
  98.    map->grid[x][y] = CHARACTER;
  99.  
  100.    findFreeSpace(*map, &x, &y);
  101.    map->grid[x][y] = TREASURE;
  102.  
  103.    //place trees
  104.    for (i = 0; i < numTrees; ++i){
  105.       findFreeSpace(*map, &x, &y);
  106.       map->grid[x][y] = TREE;
  107.    }
  108. }
  109.  
  110. void printMap(Map map){
  111.    int i, j;
  112.    
  113.    //top line
  114.    printf("+");
  115.    for (i = 0; i < map.size; ++i)
  116.       printf("-");
  117.    printf("+\n");
  118.  
  119.    //map
  120.    for (i = 0; i < map.size; ++i){
  121.       printf("|");
  122.  
  123.       for (j = 0; j < map.size; ++j)
  124.          printf("%c", map.grid[j][i]);
  125.  
  126.       printf("|\n");
  127.    }
  128.  
  129.    //bottom line
  130.    printf("+");
  131.    for (i = 0; i < map.size; ++i)
  132.       printf("-");
  133.    printf("+\n");
  134.  
  135. }
  136.  
  137. //find random location which isn't occupied
  138. void findFreeSpace(Map map, int *x, int *y){
  139.    //TODO max tries
  140.    do{
  141.       *x = rand() % map.size;
  142.       *y = rand() % map.size;
  143.    }while(map.grid[*x][*y] != BLANK);
  144. }
  145.  
  146. int findSolution(Map *map){
  147.    int playerX = -1, playerY = -1;
  148.    int i, j;
  149.    QueueNode *queueStart, *queueEnd;
  150.    int **tested;
  151.    PathNode *newPath;
  152.    int horDist, verDist;
  153.    int oldX, oldY;
  154.    PathNode *it;
  155.    PathNode *copy;
  156.    int x, y;
  157.    QueueNode *temp;
  158.  
  159.    //initialize tested map
  160.    tested = malloc(sizeof(int*) * map->size);
  161.    for (i = 0; i < map->size; ++i)
  162.       tested[i] = calloc(map->size, sizeof(int)); //0-initialized
  163.  
  164.    //find player location
  165.    for (i = 0; i < map->size && playerX == -1; ++i)
  166.       for (j = 0; j < map->size && playerX == -1; ++j)
  167.          if (map->grid[i][j] == CHARACTER)
  168.             playerX = i, playerY = j;
  169.    assert(playerX != -1 && playerY != -1);
  170.  
  171.    //new queue, with one path in it, holding only the start location
  172.    queueStart = queueEnd = malloc(sizeof(QueueNode));
  173.    queueStart->next = NULL;
  174.    queueStart->path.next = NULL;
  175.    queueStart->path.x = playerX; //character's location
  176.    queueStart->path.y = playerY;
  177.    tested[playerX][playerY] = 1;
  178.  
  179.    //while front of queue is not a solution (solution: last element is the treasure)
  180.    while (!isSolution(&queueStart->path, *map)){
  181.  
  182.       //new path for each direction (if new location is not taken, and is a space)
  183.       it = pathEnd(&queueStart->path);
  184.       oldX = it->x;
  185.       oldY = it->y;
  186.  
  187.       for (horDist = -1; horDist <= 1; ++horDist)
  188.          for (verDist = -1; verDist <= 1; ++verDist){   //skip if:
  189.             x = oldX + horDist;
  190.             y = oldY + verDist;
  191.             if (horDist == 0 && verDist == 0)             //no movement
  192.                continue;
  193.             if (horDist != 0 && verDist != 0)             //diagonal
  194.                continue;
  195.             if (x < 0 || x >= map->size)                  //x out of bounds
  196.                continue;
  197.             if (y < 0 || y >= map->size)                  //y out of bounds
  198.                continue;
  199.             if (map->grid[x][y] == TREE)                  //moving into a tree
  200.                continue;
  201.             if (tested[x][y])                             //new tile is already part of a path
  202.                continue;
  203.            
  204.             tested[x][y] = 1;
  205.  
  206.             //add new path to end of queue
  207.             copy = copyPath(&queueStart->path);
  208.             newPath = malloc(sizeof(PathNode));
  209.             newPath->next = NULL;
  210.             newPath->x = x;
  211.             newPath->y = y;
  212.             pathEnd(copy)->next = newPath; //add new direction to the end of the path
  213.             queueEnd->next = malloc(sizeof(QueueNode));
  214.             queueEnd = queueEnd->next;
  215.             queueEnd->path = *copy;
  216.             queueEnd->next = NULL;
  217.          }
  218.  
  219.       //remove front of queue
  220.       //printPath(&queueStart->path);
  221.       temp = queueStart->next;
  222.       free(queueStart);
  223.       queueStart = temp;
  224.  
  225.       if (temp == NULL) //no more paths; no solution
  226.          return 0;
  227.  
  228.    }//while solution not found
  229.  
  230.    //solution found; add path to map
  231.    it = queueStart->path.next; //start on 2nd step; 1st is the character
  232.    while (it->next != NULL){
  233.       if (map->grid[it->x][it->y] != TREASURE) //don't replace treasure character on map
  234.          map->grid[it->x][it->y] = PATH;
  235.       it = it->next;
  236.    }
  237.  
  238.    //TODO clean up queue
  239.  
  240.    //clean up tested map
  241.    for (i = 0; i < map->size; ++i)
  242.       free(tested[i]);
  243.    free(tested);
  244.  
  245.    return 1;
  246. }
  247.  
  248. //determines whether the given path is a solution
  249. int isSolution(PathNode *path, Map map){
  250.    path = pathEnd(path);
  251.    return (map.grid[path->x][path->y] == TREASURE);
  252. }
  253.  
  254. //creates a deep copy of a path
  255. PathNode *copyPath(PathNode *original){
  256.    PathNode *copy, *temp;
  257.    copy = malloc(sizeof(PathNode));
  258.    *copy = *original;
  259.    temp = copy;
  260.    while (original->next != NULL){
  261.       original = original->next; //iterate
  262.       temp->next = malloc(sizeof(PathNode));
  263.       temp = temp->next;
  264.       *temp = *original;
  265.       temp->next = NULL;
  266.  
  267.    }
  268.    return copy;
  269. }
  270.  
  271. //finds the end of a path
  272. PathNode *pathEnd(PathNode *path){
  273.    while (path->next != NULL)
  274.       path = path->next;
  275.    return path;
  276. }
  277.  
  278. //prints a path
  279. void printPath(PathNode *path){
  280.    do{
  281.       printf("(%d,%d) ", path->x, path->y);
  282.       path = path->next;
  283.    }while(path != NULL);
  284.    printf("\n");
  285. }
RAW Paste Data
Top