home *** CD-ROM | disk | FTP | other *** search
/ Computerworld 1996 March / Computerworld_1996-03_cd.bin / idg_cd3 / grafika / fraktaly / frasr192 / ant.c < prev    next >
Text File  |  1995-04-10  |  14KB  |  453 lines
  1. /* The Ant Automaton is based on an article in Scientific American, July 1994.
  2.  * The original Fractint implementation was by Tim Wegner in Fractint 19.0.
  3.  * This routine is a major rewrite by Luciano Genero & Fulvio Cappelli using
  4.  * tables for speed, and adds a second ant type, multiple ants, and random
  5.  * rules.
  6.  *
  7.  * Revision history:
  8.  * 20 Mar 95 LG/FC First release of table driven version 
  9.  * 31 Mar 95 LG/FC Fixed a bug that writes one pixel off the screen
  10.  * 31 Mar 95 LG/FC Changed ant type 1 to produce the same pattern as the 
  11.  *                   original implementation (they were mirrored on the 
  12.  *                   x axis)
  13.  * 04 Apr 95 TW    Added wrap option and further modified the code to match 
  14.  *                   the original algorithm. It now matches exactly.
  15.  * 10 Apr 95 TW    Suffix array does not contain enough memory. Crashes at 
  16.  *                   over 1024x768. Changed to extraseg.
  17.  */
  18. #include <stdio.h>
  19. #include <stdlib.h>
  20. #include <string.h>
  21. #include "prototyp.h"
  22. #include "helpdefs.h"
  23.  
  24. #define RANDOM(n)       ((int)((long)((long)rand() * (long)(n)) >> 15)) /* Generate Random
  25.                                                                          * Number 0 <= r < n */
  26. #define MAX_ANTS        256
  27. #define XO              (xdots/2)
  28. #define YO              (ydots/2)
  29. #define DIRS            4
  30. #define INNER_LOOP      100
  31.  
  32. /* possible value of idir e relative movement in the 4 directions
  33.  * for x 0, 1, 0, -1
  34.  * for y 1, 0, -1, 0
  35.  */
  36. static int far *incx[DIRS];         /* tab for 4 directions */
  37. static int far *incy[DIRS];
  38.  
  39. void
  40. setwait(long *wait)
  41. {
  42.    char msg[30];
  43.    int kbdchar;
  44.  
  45.    for (;;)
  46.    {
  47.       sprintf(msg, "Delay %4ld", *wait);
  48.       while (strlen(msg) < 15)
  49.          strcat(msg, " ");
  50.       msg[15] = '\0';
  51.       showtempmsg((char far *) msg);
  52.       kbdchar = getakey();
  53.       switch (kbdchar)
  54.       {
  55.       case RIGHT_ARROW_2:
  56.       case UP_ARROW_2:
  57.          (*wait) += 100;
  58.          break;
  59.       case RIGHT_ARROW:
  60.       case UP_ARROW:
  61.          (*wait) += 10;
  62.          break;
  63.       case DOWN_ARROW_2:
  64.       case LEFT_ARROW_2:
  65.          (*wait) -= 100;
  66.          break;
  67.       case LEFT_ARROW:
  68.       case DOWN_ARROW:
  69.          (*wait) -= 10;
  70.          break;
  71.       default:
  72.          cleartempmsg();
  73.          return;
  74.       }
  75.       if (*wait < 0)
  76.          *wait = 0;
  77.    }
  78. }
  79.  
  80. /* turkmite from scientific american july 1994 pag 91
  81.  * Tweaked by Luciano Genero & Fulvio Cappelli
  82.  */
  83. void
  84. TurkMite1(int maxtur, int rule_len, char *ru, long maxpts, long wait)
  85. {
  86.    int color, ix, iy, idir, pixel, i;
  87.    int kbdchar, step, antwrap;
  88.    int x[MAX_ANTS + 1], y[MAX_ANTS + 1];
  89.    int next_col[MAX_ANTS + 1], rule[MAX_ANTS + 1], dir[MAX_ANTS + 1];
  90.    long count;
  91.    antwrap = ((param[4] == 0) ? 0 : 1);
  92.    step = (int) wait;
  93.    if (step == 1)
  94.       wait = 0;
  95.    else
  96.       step = 0;
  97.    if (rule_len == 0)
  98.    {                            /* random rule */
  99.       for (color = 0; color < MAX_ANTS; color++)
  100.       {                         /* init the rules and colors for the
  101.                                  * turkmites: 1 turn left, -1 turn right */
  102.          rule[color] = 1 - (RANDOM(2) * 2);
  103.          next_col[color] = color + 1;
  104.       }
  105.       /* close the cycle */
  106.       next_col[color] = 0;
  107.    }
  108.    else
  109.    {                            /* user defined rule */
  110.       for (color = 0; color < rule_len; color++)
  111.       {                         /* init the rules and colors for the
  112.                                  * turkmites: 1 turn left, -1 turn right */
  113.          rule[color] = (ru[color] * 2) - 1;
  114.          next_col[color] = color + 1;
  115.       }
  116.       /* repeats to last color */
  117.       for (color = rule_len; color < MAX_ANTS; color++)
  118.       {                         /* init the rules and colors for the
  119.                                  * turkmites: 1 turn left, -1 turn right */
  120.          rule[color] = rule[color % rule_len];
  121.          next_col[color] = color + 1;
  122.       }
  123.       /* close the cycle */
  124.       next_col[color] = 0;
  125.    }
  126.    for (color = maxtur; color; color--)
  127.    {                            /* init the various turmites N.B. non usa
  128.                                  * x[0], y[0], dir[0] */
  129.       if (rule_len)
  130.       {
  131.          dir[color] = 1;
  132.          x[color] = XO;
  133.          y[color] = YO;
  134.       }
  135.       else
  136.       {
  137.          dir[color] = RANDOM(DIRS);
  138.          x[color] = RANDOM(xdots);
  139.          y[color] = RANDOM(ydots);
  140.       }
  141.    }
  142.    maxpts = maxpts / (long) INNER_LOOP;
  143.    for (count = 0; count < maxpts; count++)
  144.    {
  145.       /* check for a key only every inner_loop times */
  146.       kbdchar = keypressed();
  147.       if (kbdchar || step)
  148.       {
  149.          int done = 0;
  150.          if (kbdchar == 0)
  151.             kbdchar = getakey();
  152.          switch (kbdchar)
  153.          {
  154.          case SPACE:
  155.             step = 1 - step;
  156.             break;
  157.          case ESC:
  158.             done = 1;
  159.             break;
  160.          case RIGHT_ARROW:
  161.          case UP_ARROW:
  162.          case DOWN_ARROW:
  163.          case LEFT_ARROW:
  164.          case RIGHT_ARROW_2:
  165.          case UP_ARROW_2:
  166.          case DOWN_ARROW_2:
  167.          case LEFT_ARROW_2:
  168.             setwait(&wait);
  169.             break;
  170.          default:
  171.             done = 1;
  172.             break;
  173.          }
  174.          if (done)
  175.             goto exit_ant;
  176.          if (keypressed())
  177.             getakey();
  178.       }
  179.       for (i = INNER_LOOP; i; i--)
  180.       {
  181.          if (wait > 0 && step == 0)
  182.          {
  183.             for (color = maxtur; color; color--)
  184.             {                   /* move the various turmites */
  185.                ix = x[color];   /* temp vars */
  186.                iy = y[color];
  187.                idir = dir[color];
  188.  
  189.                pixel = getcolor(ix, iy);
  190.                putcolor(ix, iy, 15);
  191.                sleepms(wait);
  192.                putcolor(ix, iy, next_col[pixel]);
  193.                idir += rule[pixel];
  194.                idir &= 3;
  195.                if (antwrap == 0)
  196.                   if ((idir == 0 && iy == ydots - 1) ||
  197.                       (idir == 1 && ix == xdots - 1) ||
  198.                       (idir == 2 && iy == 0) ||
  199.                       (idir == 3 && ix == 0))
  200.                      goto exit_ant;
  201.                x[color] = incx[idir][ix];
  202.                y[color] = incy[idir][iy];
  203.                dir[color] = idir;
  204.             }
  205.          }
  206.          else
  207.          {
  208.             for (color = maxtur; color; color--)
  209.             {                   /* move the various turmites without delay */
  210.                ix = x[color];   /* temp vars */
  211.                iy = y[color];
  212.                idir = dir[color];
  213.                pixel = getcolor(ix, iy);
  214.                putcolor(ix, iy, next_col[pixel]);
  215.                idir += rule[pixel];
  216.                idir &= 3;
  217.                if (antwrap == 0)
  218.                   if ((idir == 0 && iy == ydots - 1) ||
  219.                       (idir == 1 && ix == xdots - 1) ||
  220.                       (idir == 2 && iy == 0) ||
  221.                       (idir == 3 && ix == 0))
  222.                      goto exit_ant;
  223.                x[color] = incx[idir][ix];
  224.                y[color] = incy[idir][iy];
  225.                dir[color] = idir;
  226.             }
  227.          }
  228.       }
  229.    }
  230. exit_ant:
  231.    return;
  232. }
  233.  
  234. /* this one ignore the color of the current cell is more like a white ant */
  235. void
  236. TurkMite2(int maxtur, int rule_len, char *ru, long maxpts, long wait)
  237. {
  238.    int color, ix, iy, idir, pixel, dir[MAX_ANTS + 1], i;
  239.    int kbdchar, step, antwrap;
  240.    int x[MAX_ANTS + 1], y[MAX_ANTS + 1];
  241.    int rule[MAX_ANTS + 1], rule_mask;
  242.    long count;
  243.  
  244.    antwrap = ((param[4] == 0) ? 0 : 1);
  245.  
  246.    step = (int) wait;
  247.    if (step == 1)
  248.       wait = 0;
  249.    else
  250.       step = 0;
  251.    if (rule_len == 0)
  252.    {                            /* random rule */
  253.       for (color = MAX_ANTS - 1; color; color--)
  254.       {                         /* init the various turmites N.B. don't use
  255.                                  * x[0], y[0], dir[0] */
  256.          dir[color] = RANDOM(DIRS);
  257.          rule[color] = (rand() << RANDOM(2)) | RANDOM(2);
  258.          x[color] = RANDOM(xdots);
  259.          y[color] = RANDOM(ydots);
  260.       }
  261.    }
  262.    else
  263.    {                            /* the same rule the user wants for every
  264.                                  * turkmite (max rule_len = 16 bit) */
  265.       rule_len = min(rule_len, 8 * sizeof(int));
  266.       for (i = 0, rule[0] = 0; i < rule_len; i++)
  267.          rule[0] = (rule[0] << 1) | ru[i];
  268.       for (color = MAX_ANTS - 1; color; color--)
  269.       {                         /* init the various turmites N.B. non usa
  270.                                  * x[0], y[0], dir[0] */
  271.          dir[color] = 0;
  272.          rule[color] = rule[0];
  273.          x[color] = XO;
  274.          y[color] = YO;
  275.       }
  276.    }
  277. /* use this rule when a black pixel is found */
  278.    rule[0] = 0;
  279.    rule_mask = 1;
  280.    maxpts = maxpts / (long) INNER_LOOP;
  281.    for (count = 0; count < maxpts; count++)
  282.    {
  283.       /* check for a key only every inner_loop times */
  284.       kbdchar = keypressed();
  285.       if (kbdchar || step)
  286.       {
  287.          int done = 0;
  288.          if (kbdchar == 0)
  289.             kbdchar = getakey();
  290.          switch (kbdchar)
  291.          {
  292.          case SPACE:
  293.             step = 1 - step;
  294.             break;
  295.          case ESC:
  296.             done = 1;
  297.             break;
  298.          case RIGHT_ARROW:
  299.          case UP_ARROW:
  300.          case DOWN_ARROW:
  301.          case LEFT_ARROW:
  302.          case RIGHT_ARROW_2:
  303.          case UP_ARROW_2:
  304.          case DOWN_ARROW_2:
  305.          case LEFT_ARROW_2:
  306.             setwait(&wait);
  307.             break;
  308.          default:
  309.             done = 1;
  310.             break;
  311.          }
  312.          if (done)
  313.             goto exit_ant;
  314.          if (keypressed())
  315.             getakey();
  316.       }
  317.       for (i = INNER_LOOP; i; i--)
  318.       {
  319.          for (color = maxtur; color; color--)
  320.          {                      /* move the various turmites */
  321.             ix = x[color];      /* temp vars */
  322.             iy = y[color];
  323.             idir = dir[color];
  324.             pixel = getcolor(ix, iy);
  325.             putcolor(ix, iy, 15);
  326.  
  327.             if (wait > 0 && step == 0)
  328.                sleepms(wait);
  329.  
  330.             if (rule[pixel] & rule_mask)
  331.             {                   /* turn right */
  332.                idir--;
  333.                putcolor(ix, iy, 0);
  334.             }
  335.             else
  336.             {                   /* turn left */
  337.                idir++;
  338.                putcolor(ix, iy, color);
  339.             }
  340.             idir &= 3;
  341.             if (antwrap == 0)
  342.                if ((idir == 0 && iy == ydots - 1) ||
  343.                    (idir == 1 && ix == xdots - 1) ||
  344.                    (idir == 2 && iy == 0) ||
  345.                    (idir == 3 && ix == 0))
  346.                   goto exit_ant;
  347.             x[color] = incx[idir][ix];
  348.             y[color] = incy[idir][iy];
  349.             dir[color] = idir;
  350.          }
  351.          rule_mask = _rotl(rule_mask, 1);
  352.       }
  353.    }
  354. exit_ant:
  355.    return;
  356. }
  357.  
  358. /* N.B. use the common memory in extraseg - suffix not large enough*/
  359. int
  360. ant(void)
  361. {
  362.    int maxants, type, i;
  363.    int oldhelpmode, rule_len;
  364.    long maxpts, wait;
  365.    char rule[MAX_ANTS];
  366.    char far *extra;
  367.    
  368.    extra = MK_FP(extraseg,0);
  369.  
  370.    for (i = 0; i < DIRS; i++)
  371.    {
  372.       incx[i] = (int far *) (extra + (xdots + 2) * sizeof(int) * i);       /* steal some memory */
  373.       incy[i] = (int far *) (extra + (xdots + 2) * sizeof(int) * DIRS + (ydots + 2) *sizeof(int) * i);     /* steal some memory */
  374.    }
  375.  
  376. /* In this vectors put all the possible point that the ants can visit.
  377.  * Wrap them from a side to the other insted of simply end calculation
  378.  */
  379.    for (i = 0; i < xdots; i++)
  380.    {
  381.       incx[0][i] = i;
  382.       incx[2][i] = i;
  383.    }
  384.  
  385.    for(i = 0; i < xdots; i++)
  386.       incx[3][i] = i + 1;
  387.    incx[3][xdots-1] = 0; /* wrap from right of the screen to left */
  388.  
  389.    for(i = 1; i < xdots; i++)
  390.       incx[1][i] = i - 1;
  391.    incx[1][0] = xdots-1; /* wrap from left of the screen to right */
  392.  
  393.    for (i = 0; i < ydots; i++)
  394.    {
  395.       incy[1][i] = i;
  396.       incy[3][i] = i;
  397.    }
  398.    for (i = 0; i < ydots; i++)
  399.       incy[0][i] = i + 1;
  400.    incy[0][ydots - 1] = 0;      /* wrap from the top of the screen to the
  401.                                  * bottom */
  402.    for (i = 1; i < ydots; i++)
  403.       incy[2][i] = i - 1;
  404.    incy[2][0] = ydots - 1;      /* wrap from the bottom of the screen to the
  405.                                  * top */
  406.    oldhelpmode = helpmode;
  407.    helpmode = ANTCOMMANDS;
  408.    maxpts = (long) param[1];
  409.    maxpts = labs(maxpts);
  410.    wait = abs(orbit_delay);
  411.    sprintf(rule, "%.17g", param[0]);
  412.    rule_len = strlen(rule);
  413.    if (rule_len > 1)
  414.    {                            /* if rule_len == 0 random rule */
  415.       for (i = 0; i < rule_len; i++)
  416.       {
  417.          if (rule[i] != '1')
  418.             rule[i] = (char) 0;
  419.          else
  420.             rule[i] = (char) 1;
  421.       }
  422.    }
  423.    else
  424.       rule_len = 0;
  425.    maxants = (int) param[2];
  426.    
  427.    /* set random seed for reproducibility */
  428.    if ((!rflag) && param[5] == 1)
  429.       --rseed;
  430.    if (param[5] != 0 && param[5] != 1)
  431.       rseed = (int)param[5];
  432.  
  433.    srand(rseed);
  434.    if (!rflag) ++rseed;
  435.  
  436.    if (maxants < 1)             /* if max_ants == 0 max_ants random */
  437.       maxants = 2 + RANDOM(MAX_ANTS - 2);
  438.    type = (int) param[3] - 1;
  439.    if (type < 0 || type > 1)
  440.       type = RANDOM(2);         /* if type == 0 choose a random type */
  441.    switch (type)
  442.    {
  443.    case 0:
  444.       TurkMite1(maxants, rule_len, rule, maxpts, wait);
  445.       break;
  446.    case 1:
  447.       TurkMite2(maxants, rule_len, rule, maxpts, wait);
  448.       break;
  449.    }
  450.    helpmode = oldhelpmode;
  451.    return 0;
  452. }
  453.