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