/* File: t-grids.c */

/*
 * This file can be used to dump the definition of the 'vinfo_type' structure,
 * and the 'vinfo_type' array called 'vinfo', used by the "update_view()" code.
 */


#include <stdio.h>


/*
 * Absolute value
 */
#define ABS(N) (((N) < 0) ? -(N) : (N))


/*
 * Maximum view radius
 */
#define MAX_SIGHT 20

/*
 * Dungeon size
 */
#define DUNGEON_HGT 25
#define DUNGEON_WID 60

/*
 * Dungeon size (allocated)
 */
#define DUNGEON_HGT_ALLOC 25 
#define DUNGEON_WID_ALLOC 256

/*
 * Grids and locations
 */
#define GRID(Y,X) (DUNGEON_WID_ALLOC * (Y) + (X))
#define GRID_Y(G) ((G) / DUNGEON_WID_ALLOC)
#define GRID_X(G) ((G) % DUNGEON_WID_ALLOC)


/*
 * An unsigned 8 bit value
 */
typedef unsigned char byte;

/*
 * A signed 16 bit value
 */
typedef short s16b;

/*
 * An unsigned 32 bit value
 */
typedef unsigned long u32b;


/*
 * Optimized pseudo-distance
 */
static int distance(int y1, int x1, int y2, int x2)
{
  int dy, dx, d;

  /* Find the absolute y/x distance components */
  dy = (y1 > y2) ? (y1 - y2) : (y2 - y1);
  dx = (x1 > x2) ? (x1 - x2) : (x2 - x1);

  /* Hack -- approximate the distance */
  d = (dy > dx) ? (dy + (dx>>1)) : (dx + (dy>>1));

  /* Return the distance */
  return (d);
}


/***** The lines above can be acquired from Angband itself *****/


/*
 * Slope scale factor
 */
#define SCALE 100000L


/*
 * Maximum number of grids
 */
#define VINFO_MAX_GRIDS 256

/*
 * Maximum number of slopes
 */
#define VINFO_MAX_SLOPES 128


/*
 * The 'vinfo_type' structure
 */

typedef struct vinfo_type vinfo_type;

struct vinfo_type
{
  s16b grid_0;
  s16b grid_1;
  s16b grid_2;
  s16b grid_3;
  s16b grid_4;
  s16b grid_5;
  s16b grid_6;
  s16b grid_7;

  u32b bits_3;
  u32b bits_2;
  u32b bits_1;
  u32b bits_0;

  vinfo_type *next_0;
  vinfo_type *next_1;

  byte y;
  byte x;
  byte d;
  byte r;
};


/*
 * Number of grids
 */
static int max_grids = 0;

/*
 * Number of slopes
 */
static int max_slopes = 0;

/*
 * Slope values
 */
static long slopes[VINFO_MAX_SLOPES];

/*
 * Slope range per grid
 */
static long slopes_min[MAX_SIGHT+1][MAX_SIGHT+1];
static long slopes_max[MAX_SIGHT+1][MAX_SIGHT+1];

/*
 * Slope intersections
 */
static int intersects[VINFO_MAX_SLOPES];

/*
 * Grid info
 */
static vinfo_type vinfo[VINFO_MAX_GRIDS];

/*
 * Grid queue
 */
static int queue_head = 0;
static int queue_tail = 0;
static vinfo_type *queue[VINFO_MAX_GRIDS];


/*
 * Compare two long's (for 'qsort()')
 */
static int cmp_long(long *i, long *j)
{
  if (*i > *j)
    return (1);
  if (*i < *j)
    return (-1);
  return (0);
}


/*
 * Slope analysis
 *
 * Octagon (radius 20), Grids=1149
 *
 * Quadrant (south east), Grids=308, Slopes=251
 *
 * Octant (east then south), Grids=161, Slopes=126
 */
int main(int argc, char *argv[])
{
  int i, g;
  int y, x;

  long m;


  /*
   * Analyze the slopes
   */

  /* Analyze grids */
  for (y = 0; y <= MAX_SIGHT; ++y)
  {
    for (x = y; x <= MAX_SIGHT; ++x)
    {
      if (distance(0, 0, y, x) <= MAX_SIGHT)
      {
        /* Default */
        slopes_min[y][x] = 999999999;
        slopes_max[y][x] = 0;

        /* Paranoia */
        if (max_grids >= VINFO_MAX_GRIDS)
        {
          printf("Too many grids!\n");
          exit(1);
        }

        /* Count */
        max_grids++;

        /* Slope to the top right corner */
        m = SCALE * (1000L * y - 500) / (1000L * x + 500);

        /* Handle "legal" slopes */
        if ((m > 0) && (m <= SCALE))
        {
          /* Save that slope (if unique) */
          for (i = 0; i < max_slopes; i++)
          {
            if (slopes[i] == m) break;
          }
          if ((i == max_slopes) && (max_slopes < VINFO_MAX_SLOPES))
          {
            slopes[max_slopes++] = m;
          }
        }

        /* Track slope range */
        if (slopes_min[y][x] > m) slopes_min[y][x] = m;
        if (slopes_max[y][x] < m) slopes_max[y][x] = m;

        /* Slope to top left corner */
        m = SCALE * (1000L * y - 500) / (1000L * x - 500);

        /* Handle "legal" slopes */
        if ((m > 0) && (m <= SCALE))
        {
          /* Save that slope (if unique) */
          for (i = 0; i < max_slopes; i++)
          {
            if (slopes[i] == m) break;
          }
          if ((i == max_slopes) && (max_slopes < VINFO_MAX_SLOPES))
          {
            slopes[max_slopes++] = m;
          }
        }

        /* Track slope range */
        if (slopes_min[y][x] > m) slopes_min[y][x] = m;
        if (slopes_max[y][x] < m) slopes_max[y][x] = m;

        /* Slope to bottom right corner */
        m = SCALE * (1000L * y + 500) / (1000L * x + 500);

        /* Handle "legal" slopes */
        if ((m > 0) && (m <= SCALE))
        {
          /* Save that slope (if unique) */
          for (i = 0; i < max_slopes; i++)
          {
            if (slopes[i] == m) break;
          }
          if ((i == max_slopes) && (max_slopes < VINFO_MAX_SLOPES))
          {
            slopes[max_slopes++] = m;
          }
        }

        /* Track slope range */
        if (slopes_min[y][x] > m) slopes_min[y][x] = m;
        if (slopes_max[y][x] < m) slopes_max[y][x] = m;

        /* Slope to bottom left corner */
        m = SCALE * (1000L * y + 500) / (1000L * x - 500);

        /* Handle "legal" slopes */
        if ((m > 0) && (m <= SCALE))
        {
          /* Save that slope (if unique) */
          for (i = 0; i < max_slopes; i++)
          {
            if (slopes[i] == m) break;
          }
          if ((i == max_slopes) && (max_slopes < VINFO_MAX_SLOPES))
          {
            slopes[max_slopes++] = m;
          }
        }

        /* Track slope range */
        if (slopes_min[y][x] > m) slopes_min[y][x] = m;
        if (slopes_max[y][x] < m) slopes_max[y][x] = m;
      }
    }
  }

  /* Paranoia */
  if (max_slopes > VINFO_MAX_SLOPES)
  {
    printf("Too many slopes!\n");
    exit(1);
  }

  /* Sort the (unique) slopes */
  qsort(slopes, max_slopes, sizeof(long), cmp_long);


  /*
   * Analyze the intersections
   */

  /* Count intersections */
  for (i = 0; i < max_slopes; ++i)
  {
    m = slopes[i];

    for (y = 0; y <= MAX_SIGHT; ++y)
    {
      for (x = y; x <= MAX_SIGHT; ++x)
      {
        if (distance(0, 0, y, x) <= MAX_SIGHT)
        {
          if ((slopes_min[y][x] < m) && (m < slopes_max[y][x]))
          {
            intersects[i]++;
          }
        }
      }
    }
  }


  /*
   * Analyze and Dump the grid info
   */

  /* Header */
  printf("/* XXX XXX XXX Begin machine generated code XXX XXX XXX */\n\n\n");

  /* The 'vinfo_type' structure */
  printf("/* The 'vinfo_type' structure */\n\n");
  printf("typedef struct vinfo_type vinfo_type;\n\n");
  printf("struct vinfo_type\n");
  printf("{\n");
  printf("\ts16b grid_0;\n");
  printf("\ts16b grid_1;\n");
  printf("\ts16b grid_2;\n");
  printf("\ts16b grid_3;\n");
  printf("\ts16b grid_4;\n");
  printf("\ts16b grid_5;\n");
  printf("\ts16b grid_6;\n");
  printf("\ts16b grid_7;\n\n");
  printf("\tu32b bits_3;\n");
  printf("\tu32b bits_2;\n");
  printf("\tu32b bits_1;\n");
  printf("\tu32b bits_0;\n\n");
  printf("\tvinfo_type *next_0;\n");
  printf("\tvinfo_type *next_1;\n\n");
  printf("\tbyte y;\n");
  printf("\tbyte x;\n");
  printf("\tbyte d;\n");
  printf("\tbyte r;\n");
  printf("};\n\n\n");


  /* Total number of grids */
  printf("#define VINFO_MAX_GRIDS %d\n\n", max_grids);

  /* Dump 'vinfo' */
  printf("static vinfo_type vinfo[VINFO_MAX_GRIDS] =\n");
  printf("{\n\n");

  /* Enqueue player grid */
  queue[queue_tail++] = &vinfo[0];

  /* Process queue */
  while (queue_head < queue_tail)
  {
    int e;
    vinfo_type *p;


    /* Index */
    e = queue_head;

    /* Dequeue next grid */
    p = queue[queue_head++];

    /* Main Grid */
    g = vinfo[e].grid_0;

    /* Location */
    y = GRID_Y(g);
    x = GRID_X(g);


    /* Dump open */
    printf("\t/* vinfo[%d] */\n", e);
    printf("\t{\n");


    /* Dump grids */
    printf("\t\t");
    printf("GRID(%+d,%+d), ",  +y, +x);
    printf("GRID(%+d,%+d), ",  +x, +y);
    printf("GRID(%+d,%+d), ",  +x, -y);
    printf("GRID(%+d,%+d),\n", +y, -x);
    printf("\t\t");
    printf("GRID(%+d,%+d), ",  -y, -x);
    printf("GRID(%+d,%+d), ",  -x, -y);
    printf("GRID(%+d,%+d), ",  -x, +y);
    printf("GRID(%+d,%+d),\n", -y, +x);


    /* Analyze slopes */
    for (i = 0; i < max_slopes; ++i)
    {
      m = slopes[i];

      /* Memorize intersection slopes (for non-player-grids) */
      if ((e > 0) && (slopes_min[y][x] < m) && (m < slopes_max[y][x]))
      {
        switch (i / 32)
        {
          case 3: vinfo[e].bits_3 |= (1L << (i % 32)); break;
          case 2: vinfo[e].bits_2 |= (1L << (i % 32)); break;
          case 1: vinfo[e].bits_1 |= (1L << (i % 32)); break;
          case 0: vinfo[e].bits_0 |= (1L << (i % 32)); break;
        }
      }
    }


    /* Dump bit flags */
    printf("\t\t0x%08lX, 0x%08lX, 0x%08lX, 0x%08lX,\n",
           vinfo[e].bits_3, vinfo[e].bits_2,
           vinfo[e].bits_1, vinfo[e].bits_0);


    /* Default */
    vinfo[e].next_0 = &vinfo[0];

    /* Grid next child */
    if (distance(0, 0, y, x+1) <= MAX_SIGHT)
    {
      g = GRID(y,x+1);

      if (queue[queue_tail-1]->grid_0 != g)
      {
        vinfo[queue_tail].grid_0 = g;
        queue[queue_tail] = &vinfo[queue_tail];
        queue_tail++;
      }

      vinfo[e].next_0 = &vinfo[queue_tail - 1];
    }


    /* Default */
    vinfo[e].next_1 = &vinfo[0];

    /* Grid diag child */
    if (distance(0, 0, y+1, x+1) <= MAX_SIGHT)
    {
      g = GRID(y+1,x+1);

      if (queue[queue_tail-1]->grid_0 != g)
      {
        vinfo[queue_tail].grid_0 = g;
        queue[queue_tail] = &vinfo[queue_tail];
        queue_tail++;
      }

      vinfo[e].next_1 = &vinfo[queue_tail - 1];
    }


    /* Hack -- main diagonal has special children */
    if (y == x) vinfo[e].next_0 = vinfo[e].next_1;


    /* Dump children */
    printf("\t\t&vinfo[%d], &vinfo[%d],",
           (vinfo[e].next_0 - &vinfo[0]),
           (vinfo[e].next_1 - &vinfo[0]));


    /* Dump extra info */
    printf(" %d, %d, %d, %d\n",
           y, x,
           ((y > x) ? (y + x/2) : (x + y/2)),
           ((!y) ? x : (!x) ? y : (y == x) ? y : 0));


    /* Dump shut */
    printf("\t},\n\n");
  }

  /* Done */
  printf("};\n\n\n");


  /*
   * Dump the slopes and intersections
   */

  /* Total number of slopes */
  printf("#define VINFO_MAX_SLOPES %d\n\n", max_slopes);

  /* Header */
  printf("/* %3s : %9s  %6s */\n",
         "Bit", "Slope", "Grids");
  printf("/* %3s : %9s  %6s */\n",
         "---", "-----", "-----");

  /* Dump */
  for (i = 0; i < max_slopes; ++i)
  {
    m = slopes[i];

    printf("/* %3d : %9ld  %6d */\n",
           i, m, intersects[i]);
  }

  /* Skip */
  printf("\n");

  /* Maximal bits */
  printf("#define VINFO_BITS_3 0x%08lX\n",
         vinfo[1].bits_3 | vinfo[2].bits_3);
  printf("#define VINFO_BITS_2 0x%08lX\n",
         vinfo[1].bits_2 | vinfo[2].bits_2);
  printf("#define VINFO_BITS_1 0x%08lX\n",
         vinfo[1].bits_1 | vinfo[2].bits_1);
  printf("#define VINFO_BITS_0 0x%08lX\n",
         vinfo[1].bits_0 | vinfo[2].bits_0);

  /* Done */
  printf("\n\n");

  /* Footer */
  printf("/* XXX XXX XXX End machine generated code XXX XXX XXX */\n\n\n");

  /* Success */
  return (0);
}