/****************************************************************/

/* pacman.c - a simple pacman game  */
/* Original version written by Eric Lorenzo */

/****************************************************************/

#include <sys/types.h>
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <curses.h>
#include <time.h>
#include "pacman.h"

/****************************************************************/

/* The definition of the routine that defines the player. */
extern int player_action(BOARD *b);

/****************************************************************/
/* RANDOM NUMBER GENERATION */

/* some systems apparently don't define this in their include files */
#ifndef RAND_MAX
#define RAND_MAX 0x7FFFFFFF
#endif

/* Get a random nonnegative integer less than n */
int get_rand(int n) {
  int i, j;
  i = RAND_MAX / n;
  i *= n;
  while ((j = rand()) >= i) continue;
  return j % n;
}

/****************************************************************/

/* quickly constructs an ordered pair */
ORDPAIR op(int x, int y) {
  ORDPAIR r;
  r.x = x;
  r.y = y;
  return r;
}

/* component sum of two ordered pairs */
ORDPAIR op_sum(ORDPAIR op1, ORDPAIR op2) {
  ORDPAIR ret;

  ret.x = op1.x + op2.x;
  ret.y = op1.y + op2.y;

  return ret;
}

/* test equality of two ordered pairs */
int op_eq(ORDPAIR op1, ORDPAIR op2) {
  return (op1.x == op2.x) && (op1.y == op2.y);
}

/* return an ordered pair that points in the given direction */
ORDPAIR op_from_dir(int direction) {
  switch (direction)
    {
    default: 
    case STAY:  return op( 0,  0);
    case UP:    return op( 0, -1);
    case RIGHT: return op( 1,  0);
    case DOWN:  return op( 0,  1);
    case LEFT:  return op(-1,  0);
    }
}

/****************************************************************/

/* create a new, empty board */   
BOARD *board_new() {
  int x, y;
  BOARD *nb;

  nb = malloc(sizeof(BOARD));
  if (nb == NULL)
    {
      fprintf(stderr, "board_new: memory allocation error\n");
      return NULL;
    }
  
  nb->status = PLAYING;
  nb->score = 0;
  nb->food_count = 0;
  nb->round = 0;
  nb->player_pos = op(0, 0);
  for (x = 0; x < GHOSTCOUNT; x++)
    nb->ghost_pos[x] = op(0, 0);

  for (y = 0; y < HEIGHT; y++)
    for (x = 0; x < WIDTH; x++)
      {
	nb->board_data[x][y].wall  = 0;
	nb->board_data[x][y].food  = 0;
      }
      
  return nb;
}

/* create a copy of the board */
BOARD *board_copy(BOARD *b) {
  BOARD *nb;

  nb = malloc(sizeof(BOARD));
  if (nb == NULL)
    {
      fprintf(stderr, "board_copy: memory allocation error\n");
      return NULL;
    }

  memcpy(nb, b, sizeof(BOARD));
  return nb;
}


/* free up a board's memory */
void board_destroy(BOARD *b) {
  free(b);
}

/* display a board using curses */
void board_display_curses(BOARD *b) {
  int i, x, y;

  move(0, 0);
  for (y = 0; y < HEIGHT; y++)
    {
      for (x = 0; x < WIDTH; x++)
	{
	  if ((b->player_pos.x == x) && (b->player_pos.y == y))
	    {
	      addch('P');
	      addch(' ');
	      continue;
	    }

	  for (i = 0; i < GHOSTCOUNT; i++) 
	    if ((b->ghost_pos[i].x == x) && (b->ghost_pos[i].y == y))
	      {
		addch('1' + i);
		addch(' ');
		break;
	      }
	  if (i != GHOSTCOUNT) continue;

	  if (b->board_data[x][y].wall)
	    {
	      addch('#');
	      addch('#');
	      continue;
	    }
	  
	  if (b->board_data[x][y].food)
	    {
	      addch('.');
	      addch(' ');
	      continue;
	    }
	  
	  addch(' ');
	  addch(' ');
	}

      switch (y)
	{
	case 0: printw(" Round: %d", b->round); break;
	case 1: printw(" Score: %d", b->score); break;
	case 2: printw(" Food:  %d", b->food_count); break;
	}

      addch('\n');
    }
  addch(' ');
  move(HEIGHT, 0);
  refresh();
}


/* the default board layout (# is wall, . is food, <space> is neither) */
char *default_board[] = {
  "####################",
  "#.....########.....#",
  "#.###..........###.#",
  "#.#.#..##..##..#.#.#",
  "#.#......##......#.#",
  "#...####.##.####...#",
  "#.#....######....#.#",
  "#.#.##.#    #.##.#.#",
  "#.#....##  ##....#.#",
  "#...####....####...#",
  "#.#......##......#.#",
  "#.#...#......#...#.#",
  "#.###.###..###.###.#",
  "#..................#",
  "####################"
};


/* this makes it possible to semi-graphically draw a board layout with a
   text editor, as seen above */
void board_init_from_strings(BOARD *b, char *data[]) {
  int x, y;

  b->food_count = 0;
  for (y = 0; y < HEIGHT; y++)
    for (x = 0; x < WIDTH; x++)
      switch (data[y][x])
	{
	case '#':
	  b->board_data[x][y].wall = 1;
	  b->board_data[x][y].food = 0;
	  break;

	case '.':
	  b->board_data[x][y].wall = 0;
	  b->board_data[x][y].food = 1;
	  b->food_count++;
	  break;

	default:
	  b->board_data[x][y].wall = 0;
	  b->board_data[x][y].food = 0;
	  break;
	}

  /* the player always starts on food */
  do 
    b->player_pos = op(get_rand(WIDTH), get_rand(HEIGHT));
  while (!b->board_data[b->player_pos.x][b->player_pos.y].food);

  /* the player automatically gets the food it starts on */
  b->board_data[b->player_pos.x][b->player_pos.y].food = 0;
  b->food_count--;
  b->score++;
  
  /* the ghosts always start in the middle */
  for (x = 0; x < GHOSTCOUNT; x++)
    b->ghost_pos[x] = op((WIDTH/2) - (GHOSTCOUNT/2) + x, HEIGHT/2);
  
  b->status = PLAYING;
}

/****************************************************************/
/* Ghost control system                                         */
/****************************************************************/

/* A ghost's "memory" */
typedef struct {
  int has_momentum;      
  int distance;
  ORDPAIR momentum_dir;
  ORDPAIR last_pos;
} GHOST;

/* global structure to contain all ghosts's memories */
GHOST ghost_record[GHOSTCOUNT];

/* initialization of the ghost memories */
void ghost_initrecs() {
  int i;
  for (i = 0; i < GHOSTCOUNT; i++)
    {
      ghost_record[i].has_momentum = 0;
      ghost_record[i].last_pos = op(-1, -1);
    }  
}


/* get a ghost's action - this function *must* return only legal moves */
ORDPAIR ghost_action(BOARD *b, int gn) {
  ORDPAIR dir, new_pos;

  if (op_eq(b->player_pos, b->ghost_pos[gn])) return op(0, 0);

  /* first look along the x corridor */
  if (b->player_pos.x == b->ghost_pos[gn].x) {
    int y, dy;
    
    dy = (b->player_pos.y < b->ghost_pos[gn].y) ? -1 : 1;
    
    for (y = b->ghost_pos[gn].y + dy; y != b->player_pos.y; y += dy)
      if (b->board_data[b->player_pos.x][y].wall) break;

    if (y == b->player_pos.y) {
      ghost_record[gn].has_momentum = 1;
      ghost_record[gn].distance = abs(b->ghost_pos[gn].y - b->player_pos.y);
      ghost_record[gn].momentum_dir = op(0, dy);
    }
  }

  /* now look along the y corridor */
  if (b->player_pos.y == b->ghost_pos[gn].y) {
    int x, dx;
    
    dx = (b->player_pos.x < b->ghost_pos[gn].x) ? -1 : 1;
    
    for (x = b->ghost_pos[gn].x + dx; x != b->player_pos.x; x += dx)
      if (b->board_data[x][b->player_pos.y].wall) break;

    if (x == b->player_pos.x) {
      ghost_record[gn].has_momentum = 1;
      ghost_record[gn].distance = abs(b->ghost_pos[gn].x - b->player_pos.x);
      ghost_record[gn].momentum_dir = op(dx, 0);
    }
  }

  /* check to see if the ghost saw the player recently */
  if (ghost_record[gn].has_momentum) {
    dir = op_sum(b->ghost_pos[gn], ghost_record[gn].momentum_dir);

    if (!b->board_data[dir.x][dir.y].wall) {
      ghost_record[gn].distance--;
      
      if (ghost_record[gn].distance == 0)
	ghost_record[gn].has_momentum = 0;
      
      ghost_record[gn].last_pos = b->ghost_pos[gn];

      return ghost_record[gn].momentum_dir;
    }

    ghost_record[gn].has_momentum = 0;
  }

  /* no momentum, do random walk, no stepping backwards */
  do
    {
      dir = op_from_dir(get_rand(5));
      new_pos = op_sum(b->ghost_pos[gn], dir);
    }
  while (b->board_data[new_pos.x][new_pos.y].wall ||
	 op_eq(new_pos, ghost_record[gn].last_pos) );

  ghost_record[gn].last_pos = b->ghost_pos[gn];

  return dir;
}
    
    
/****************************************************************/
/****************************************************************/



/* update the board - b contains board to update, action contains
   player's move */
int update_board(BOARD *b, int action) {
  ORDPAIR newpos;
  int i, retval = 1;

  newpos = op_sum(b->player_pos, op_from_dir(action));
  if (b->board_data[newpos.x][newpos.y].wall)
    newpos = b->player_pos;

  for (i = 0; i < GHOSTCOUNT; i++) 
    {
      if (op_eq(newpos, b->ghost_pos[i]))
	{
	  b->status = GAME_OVER;
	  retval = 0;
	  continue;
	}

      b->ghost_pos[i] = op_sum(b->ghost_pos[i], ghost_action(b, i));

      if (op_eq(newpos, b->ghost_pos[i]))
	{
	  b->status = GAME_OVER;
	  retval = 0;
	}
    }
      
  if (b->board_data[newpos.x][newpos.y].food)
    {
      b->board_data[newpos.x][newpos.y].food = 0;
      b->score++;
      b->food_count--;
      if (b->food_count == 0)
	{
	  b->status = ROUND_OVER;
	  retval = 0;
	}
    }

  b->player_pos = newpos;

  return retval;
}

/****************************************************************/
/****************************************************************/

int main(int argc, char *argv[]) {
  BOARD *b;

  srand(time(NULL));

  /* init curses */
  initscr();
  clear();

  b = board_new();
  ghost_initrecs();

  /* outer loop of rounds */
  do 
    {
      board_init_from_strings(b, default_board);

      /* inner loop of moves */
      do
	board_display_curses(b);
      while (update_board(b, player_action(b)));
      b->round++;
    }
  while (b->status != GAME_OVER);

  /* display last board */
  board_display_curses(b);

  endwin();

  return 1;
}

/****************************************************************/