#include <stdlib.h>
#include <stdio.h>
#include <assert.h>
#include <time.h>

#define LEFT		1
#define RIGHT		2
#define UP		4
#define DOWN		8

#define MALE		1
#define FEMALE		2

/* START USER-DEFINABLE PARAMETERS */
#define WIDTH		8
#define HEIGHT		8
#define N_ANIMALS	12
#define SHOW_MOVES	0
/* END USER-DEFINABLE PARAMETERS */

char *m_names[] = { "Nils", "Sparky", "Hamlet", "Jones", "Steven", "Marty", "Paul", "Theo",
                    "Randy", "Horse", "Nate", "Wilhem", "House", "Fredde", "Lance", "Wolfe",
                    "Vojtek", "Red", "Cleo", "Mack", "Rand", "Corinth", "Puck", "Andrew" };
char *f_names[] = { "Carrie", "Tress", "Josie", "Karen", "Allie", "Madge", "Wendy", "Yolanda",
                    "Flower", "Raven", "Jewel", "Meagan", "Alyx", "Camille", "Bop", "Bette",
                    "Sara", "Marg", "Petra", "Loretta", "Lynn", "Olive", "Sama", "Mary" };

unsigned long m_name_idx = 0;
unsigned long f_name_idx = 0;
unsigned long count = 0;
char _direction[] = { UP, LEFT, DOWN, RIGHT, UP | LEFT, UP | RIGHT, DOWN | LEFT, DOWN | RIGHT };

#define RAND_DIR1 ((int) (rand() / (RAND_MAX / 8.0)))
#define RAND_DIR (_direction[(int) (rand() / (RAND_MAX / 8.0))])
#define RAND_X   ((int) (rand() / (RAND_MAX / WIDTH)))
#define RAND_Y   ((int) (rand() / (RAND_MAX / HEIGHT)))
#define RAND_SEX ((int) (rand() / (RAND_MAX / 2.0)))

typedef struct _animal {
  unsigned int x;
  unsigned int y;
  unsigned int gender;
  char *name;
  struct _animal *prev;
  struct _animal *next;
} Animal;

int attempt_move(Animal *grid[HEIGHT][WIDTH], Animal *animal, unsigned int x, unsigned int y, unsigned int move_dir, Animal **list) {
  unsigned int dir_mask  = 0;
  unsigned int dir_index = 0;
  unsigned int direction = 0;

  assert(animal != NULL);
  assert(grid != NULL);
  assert(grid[animal->y][animal->x] == animal);
  assert(x < WIDTH);
  assert(y < HEIGHT);

 /* Set move_dir to opposite of given direction, for reference so that
  * if we need to spawn a new guy, we don't overwrite any parents.
  */
  if(move_dir & LEFT) {  move_dir |= RIGHT;  move_dir ^= LEFT; }
  if(move_dir & RIGHT){  move_dir |= LEFT;  move_dir ^= RIGHT; }
  if(move_dir & DOWN) {  move_dir |= UP;  move_dir ^= DOWN; }
  if(move_dir & UP)   {  move_dir |= DOWN;  move_dir ^= UP; }

 /* Case 1: unoccupied; make move */
  if(grid[y][x] == NULL) {
#if SHOW_MOVES
    printf("Moving %s from (%d, %d) to (%d, %d).\n", animal->name, animal->x, animal->y, x, y);
#endif
    grid[animal->y][animal->x] = NULL;
    grid[y][x] = animal;
    animal->y = y;
    animal->x = x;
    return 1;
  }
 /* Case 2: meet rival; kill each other */
  else if(grid[y][x]->gender == animal->gender) {
    printf("%s and %s met, killed each other!\n", animal->name, grid[y][x]->name);
    if(animal->prev)  animal->prev->next = animal->next;
    if(animal->next)  animal->next->prev = animal->prev;
    if(grid[y][x]->prev)  grid[y][x]->prev->next = grid[y][x]->next;
    if(grid[y][x]->next)  grid[y][x]->next->prev = grid[y][x]->prev;
    while(*list == grid[y][x] || *list == animal)
      *list = (*list)->next;
    free(grid[y][x]);
    grid[y][x] = NULL;
    grid[animal->y][animal->x] = NULL;
    return 2;
  }
 /* Case 3: meet mate; reproduce */
  else if(grid[y][x]->gender != animal->gender) {
    Animal *new;
    /* Choose random direction */
    while(direction == 0) {
      if(dir_mask == 255)
        return -3;

      dir_index = RAND_DIR1;
      direction = _direction[dir_index];
      dir_mask |= 1 << dir_index;

      if(direction == move_dir)
        direction = 0;
      else if((x == 0          && direction & LEFT)  ||
              (x == WIDTH - 1  && direction & RIGHT) ||
              (y == 0          && direction & UP)    ||
              (y == HEIGHT - 1 && direction & DOWN))
        direction = 0;
      else if((direction == LEFT  && grid[y][x - 1] != NULL) ||
              (direction == RIGHT && grid[y][x + 1] != NULL) ||
              (direction == DOWN && grid[y + 1][x] != NULL) ||
              (direction == UP   && grid[y - 1][x] != NULL) ||
              (direction == (UP   | LEFT)  && grid[y - 1][x - 1] != NULL) ||
              (direction == (UP   | RIGHT) && grid[y - 1][x + 1] != NULL) ||
              (direction == (DOWN | LEFT)  && grid[y + 1][x - 1] != NULL) ||
              (direction == (DOWN | RIGHT) && grid[y + 1][x + 1] != NULL))
        direction = 0;
    }
   /* Wow! All that just to find a valid direction. Now we spawn a new guy: */
    new = malloc(sizeof *new);
    if(new == NULL)
      return -2;
    new->gender = RAND_SEX;
    if(new->gender == MALE)
      new->name = m_names[m_name_idx++];
    else
      new->name = f_names[f_name_idx++];

    printf("%s and %s met and made %s!\n", animal->name, grid[y][x]->name, new->name);

    new->prev = NULL;
    new->next = *list;
    (*list)->prev = new;
    *list = new;

    switch(direction) {
      case LEFT:  new->x = x - 1; new->y = y; break;
      case RIGHT: new->x = x + 1; new->y = y; break;
      case UP:    new->x = x; new->y = y - 1; break;
      case DOWN:  new->x = x; new->y = y + 1; break;
      case UP   | LEFT:  new->x = x - 1; new->y = y - 1; break;
      case UP   | RIGHT: new->x = x + 1; new->y = y - 1; break;
      case DOWN | LEFT:  new->x = x - 1; new->y = y + 1; break;
      case DOWN | RIGHT: new->x = x + 1; new->y = y + 1; break;
    }
    grid[new->y][new->x] = new;

    return 3;
  }

  fputs("Uh-oh! Something weird happened.\n", stderr);
  return -1;
}

int main(void) {
  unsigned int direction, result = 0;
  unsigned int i, j;
  unsigned int n_left = N_ANIMALS;
  Animal *animal = NULL, *current = NULL;
  Animal *grid[HEIGHT][WIDTH];

  assert(HEIGHT > 1);
  assert(WIDTH  > 1);

  srand(time(NULL));

 /* Set up board */
  for(i = 0; i < HEIGHT; ++i)
    for(j = 0; j < WIDTH; ++j)
      grid[i][j] = NULL;

  for(i = 0; i < N_ANIMALS; ++i) {
   /* Allocate new animal */
    Animal *new = malloc(sizeof *new);
    if(new == NULL)
      exit(EXIT_FAILURE);
    new->next = animal;
    new->prev = NULL;
    if(animal != NULL)
      animal->prev = new;
    animal = new;

   /* Set animal attributes */
    new->gender = RAND_SEX;
    if(new->gender == MALE)
      new->name = m_names[m_name_idx++];
    else
      new->name = f_names[f_name_idx++];
    do {
      new->x = RAND_X;
      new->y = RAND_Y;
    } while(grid[new->y][new->x] != NULL);

   /* Load onto map */
    grid[new->y][new->x] = new;

    printf("Spawned %s at (%d, %d).\n", new->name, new->x, new->y);
  }
  puts("");

 /* Main loop: */
  while(n_left > 1) {
    current = animal;
    do {
     if(m_name_idx == 24)
       m_name_idx = 0;
     if(f_name_idx == 24)
       f_name_idx = 0;

     assert(current != NULL);
     assert(current->x < WIDTH);
     assert(current->y < HEIGHT);
     assert(grid[current->y][current->x] == current);

     /* Select direction */
      direction = 0;
      while(!direction) {
        direction = RAND_DIR;
        if((current->x == 0          && direction & LEFT)  ||
           (current->x == WIDTH - 1  && direction & RIGHT) ||
           (current->y == 0          && direction & UP)    ||
           (current->y == HEIGHT - 1 && direction & DOWN))
          direction = 0;
      }
     /* Attempt move */
      switch(direction) {
        case UP:    result = attempt_move(grid, current, current->x, current->y - 1, direction, &animal); break;
        case DOWN:  result = attempt_move(grid, current, current->x, current->y + 1, direction, &animal); break;
        case LEFT:  result = attempt_move(grid, current, current->x - 1, current->y, direction, &animal); break;
        case RIGHT: result = attempt_move(grid, current, current->x + 1, current->y, direction, &animal); break;
        case UP   | RIGHT: result = attempt_move(grid, current, current->x + 1, current->y - 1, direction, &animal); break;
        case UP   | LEFT:  result = attempt_move(grid, current, current->x - 1, current->y - 1, direction, &animal); break;
        case DOWN | RIGHT: result = attempt_move(grid, current, current->x + 1, current->y + 1, direction, &animal); break;
        case DOWN | LEFT:  result = attempt_move(grid, current, current->x - 1, current->y + 1, direction, &animal); break;
      }
     /* Update n_left */
      if(result == 2) {
        Animal *tofree = current;
        current = current->next;
        free(tofree);
        n_left -= 2;
        if(current)
          continue;
        else
          break;
      }
      if(result == 3)
        ++n_left;

    } while((current = current->next));
  }
  if(n_left)
    printf("Only %s remains.\n", animal->name);
  else
    puts("Everyone is dead.");
  return 0;
}