/* maze.c - Don Yang (uguu.org)

   07/15/01
                                                                           */

#include<assert.h>
#include<stdio.h>
#include<stdlib.h>
#include"maze.h"
#include"triangle.h"


/* Edge flags */
static int EdgeFlag[3] = {TRIANGLE_EDGE1, TRIANGLE_EDGE2, TRIANGLE_EDGE3};
static int WallFlag[3] = {TRIANGLE_WALL1, TRIANGLE_WALL2, TRIANGLE_WALL3};

/* Local functions */
static int Connected(Triangle **list, int a, int b);
static void ConnectNodes(Triangle *triangle);
static void EnableEdge(Triangle *triangle, int edge);
static void FlattenTree(Triangle *root, Triangle **list, int *index);
static void SelectWalls(Triangle **list, int nodes);
static void SetGoal(Triangle **list, int nodes,
                    Triangle **start, Triangle **end);
static int SetRoot(Triangle **list, int x);
static int Union(Triangle **list, int nodes);

/************************************************************** CreateMaze */
int CreateMaze(Triangle *triangles)
{
   Triangle **list, *start, *end;
   int nodes, i;

   /* Create flat array of triangles */
   nodes = CountTriangles(triangles);       /* (triangle.c) */
   if( nodes < 3 )
   {
      fprintf(stderr, "nodes = %d, need at least 3\n", nodes);
      return 1;
   }
   if( (list = (Triangle**)malloc(nodes * sizeof(Triangle*))) == NULL )
      return 1;
   i = 0;
   FlattenTree(triangles, list, &i);

   /* Find all edges in graph */
   for(i = 0; i < nodes; i++)
   {
      list[i]->flags = 0;
      ConnectNodes(list[i]);
   }

   /* Assign goal nodes */
   SetGoal(list, nodes, &start, &end);

   /* Create random spanning tree */
   if( Union(list, nodes) )
   {
      free(list);
      return 1;
   }

   /* Solve maze */
   for(i = 0; i < nodes; i++)
      list[i]->flags &= ~TRIANGLE_PATH;
   if( !Solve(start, end) )
      fputs("No path from start to end\n", stderr);

   SelectWalls(list, nodes);
   free(list);
   return 0;

} /* CreateMaze() */

/******************************************************************* Solve */
int Solve(Triangle *node, Triangle *goal)
{
   int i;

   assert(goal);
   if( node == NULL )
      return 0;

   if( node->flags & TRIANGLE_PATH )
      return 0;
   node->flags |= TRIANGLE_PATH;
   if( node == goal )
      return 1;

   for(i = 0; i < 3; i++)
   {
      if( (node->flags & EdgeFlag[i]) && Solve(node->n[i], goal) )
         return 1;
   }

   node->flags &= ~TRIANGLE_PATH;
   return 0;

} /* Solve() */


/*************************************************************** Connected */
static int Connected(Triangle **list, int a, int b)
{
   return SetRoot(list, a) == SetRoot(list, b);

} /* Connected() */

/************************************************************ ConnectNodes */
static void ConnectNodes(Triangle *triangle)
{
   TList *i, *j;
   int edge;

   for(edge = 0; edge < 3; edge++)
   {
      triangle->n[edge] = NULL;

      /* For each edge, find triangle sharing two vertices */
      for(i = triangle->v[Edge1[edge]]->tlist; i; i = i->next)
      {
         if( i->t == triangle )
            continue;
         for(j = triangle->v[Edge2[edge]]->tlist; j; j = j->next)
         {
            if( i->t == triangle )
               continue;
            if( i->t == j->t )
               triangle->n[edge] = i->t;
         }
      }
   }

} /* ConnectNodes() */

/************************************************************** EnableEdge */
static void EnableEdge(Triangle *triangle, int edge)
{
   int i;

   triangle->flags |= EdgeFlag[edge];
   for(i = 0; i < 3; i++)
   {
      if( triangle->n[edge]->n[i] == triangle )
      {
         triangle->n[edge]->flags |= EdgeFlag[i];
         return;
      }
   }
   assert(0);

} /* EnableEdge() */

/************************************************************* FlattenTree */
static void FlattenTree(Triangle *root, Triangle **list, int *index)
{
   while( root )
   {
      FlattenTree(root->left, list, index);
      list[(*index)++] = root;
      root = root->right;
   }

} /* FlattenTree() */

/************************************************************* SelectWalls */
static void SelectWalls(Triangle **list, int nodes)
{
   int i, j, k;

   for(i = 0; i < nodes; i++)
   {
      for(j = 0; j < 3; j++)
      {
         if( !(list[i]->flags & EdgeFlag[j]) )
         {
            list[i]->flags |= WallFlag[j];
            if( list[i]->n[j] )
            {
               for(k = 0; k < 3; k++)
               {
                  if( list[i]->n[j]->n[k] == list[i] )
                     list[i]->n[j]->flags &= ~WallFlag[k];
               }
            }
         }
      }
   }

} /* SelectWalls() */

/***************************************************************** SetGoal */
static void SetGoal(Triangle **list, int nodes,
                    Triangle **start, Triangle **end)
{
   double sy, ey, y, max, min;
   int i, j;

   *start = *end = *list;
   sy = ey = (*start)->v[0]->y + (*start)->v[1]->y + (*start)->v[2]->y;
   for(i = 1; i < nodes; i++)
   {
      /* Reject triangles with too small area (rectangular approximation) */
      max = min = list[i]->v[0]->x;
      for(j = 1; j < 3; j++)
      {
         if( min > list[i]->v[j]->x )  min = list[i]->v[j]->x;
         if( max < list[i]->v[j]->x )  max = list[i]->v[j]->x;
      }
      if( max - min < MIN_GOAL_AREA_R )
         continue;
      max = min = list[i]->v[0]->y;
      for(j = 1; j < 3; j++)
      {
         if( min > list[i]->v[j]->y )  min = list[i]->v[j]->y;
         if( max < list[i]->v[j]->y )  max = list[i]->v[j]->y;
      }
      if( max - min < MIN_GOAL_AREA_R )
         continue;

      /* Select start/end base on Y value, break ties by X */
      y = list[i]->v[0]->y + list[i]->v[1]->y + list[i]->v[2]->y;
      if( (sy > y) || (sy == y && (*start)->v[0]->x > list[i]->v[0]->x) )
      {
         sy = y;
         *start = list[i];
      }
      if( (ey < y) || (ey == y && (*end)->v[0]->x < list[i]->v[0]->x) )
      {
         ey = y;
         *end = list[i];
      }
   }

   (*start)->flags |= TRIANGLE_GOAL;
   (*end)->flags |= TRIANGLE_GOAL;

} /* SetGoal() */

/****************************************************************** SetRoot */
static int SetRoot(Triangle **list, int x)
{
   while( x != list[x]->id )
      x = list[x]->id;
   return x;

} /* SetRoot() */

/******************************************************************* Union */
static int Union(Triangle **list, int nodes)
{
   Triangle *t;
   int *index;
   int i, j, k;

   assert(nodes > 3);

   /* Create forest */
   for(i = 0; i < nodes; i++)
      list[i]->id = i;

   if( (index = (int*)malloc(nodes * sizeof(int))) == NULL )
      return 1;
   for(i = 0; i < nodes; i++)
      index[i] = i;
   do
   {
      /* Set random order to join nodes */
      for(k = 0; k < nodes * SHUFFLE_RATIO; k++)
      {
         i = rand() % nodes;
         while( (j = rand() % nodes) == i );
         index[i] ^= index[j];
         index[j] ^= index[i];
         index[i] ^= index[j];
      }
      for(i = 0; i < nodes; i++)
      {
         t = list[index[i]];

         /* Check for detached node */
         if( !t->n[0] && !t->n[1] && !t->n[2] )
         {
            fprintf(stderr, "Detached triangle (%g, %g), (%g, %g), (%g, %g)\n",
               t->v[0]->x, t->v[0]->y,
               t->v[1]->x, t->v[1]->y,
               t->v[2]->x, t->v[2]->y);
            free(index);
            return 1;
         }

         /* Link to random unconnected subset */
         for(j = 0; j < 3; j++)
         {
            while( t->n[k = rand() % 3] == NULL );
            if( !Connected(list, t->id, t->n[k]->id) )
               break;
         }
         if( j < 3 )
         {
            list[SetRoot(list, t->id)]->id = SetRoot(list, t->n[k]->id);

            /* Create graph edge */
            EnableEdge(t, k);
         }
      }

      /* Compress all paths */
      for(i = 0; i < nodes; i++)
         list[i]->id = SetRoot(list, list[i]->id);

      /* Loop until all nodes are of same subset */
      for(i = 1; i < nodes; i++)
      {
         if( list[i]->id != list[0]->id )
            break;
      }
   } while( i < nodes );

   free(index);
   return 0;

} /* Union() */