TreasureFinder

// (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");
}