]> git.saurik.com Git - wxWidgets.git/blob - demos/life/game.cpp
Remove all lines containing cvs/svn "$Id$" keyword.
[wxWidgets.git] / demos / life / game.cpp
1 /////////////////////////////////////////////////////////////////////////////
2 // Name: game.cpp
3 // Purpose: Life! game logic
4 // Author: Guillermo Rodriguez Garcia, <guille@iies.es>
5 // Modified by:
6 // Created: Jan/2000
7 // Copyright: (c) 2000, Guillermo Rodriguez Garcia
8 // Licence: wxWindows licence
9 /////////////////////////////////////////////////////////////////////////////
10
11 // ==========================================================================
12 // headers, declarations, constants
13 // ==========================================================================
14
15 // For compilers that support precompilation, includes "wx/wx.h".
16 #include "wx/wxprec.h"
17
18 #ifdef __BORLANDC__
19 #pragma hdrstop
20 #endif
21
22 #ifndef WX_PRECOMP
23 #include "wx/wx.h"
24 #endif
25
26 #include "wx/log.h"
27 #include "wx/module.h"
28 #include "game.h"
29
30 #include <string.h> // for memset
31
32
33 #define CELLSARRAYSIZE 1024 // static array for BeginFind & co.
34 #define ALLOCBOXES 16 // number of cellboxes to alloc at once
35 #define MAXDEAD 8 // tics before removing cellbox from list
36
37
38 // ==========================================================================
39 // CellBox
40 // ==========================================================================
41
42 #define HASH(x, y) (((x >> 3) & 0x7f) << 7) + ((y >> 3) & 0x7f)
43
44 #define HASHSIZE 16384 // hash table size (do not change!)
45 #define CELLBOX 8 // cells in a cellbox (do not change!)
46
47
48 class LifeCellBox
49 {
50 public:
51 // members
52 inline bool IsAlive(int dx, int dy) const;
53 inline bool SetCell(int dx, int dy, bool alive);
54
55 // attributes
56 wxInt32 m_x, m_y; // position in universe
57 wxUint32 m_live1, m_live2; // alive cells (1 bit per cell)
58 wxUint32 m_old1, m_old2; // old values for m_live1, 2
59 wxUint32 m_on[8]; // neighbouring info
60 wxUint32 m_dead; // been dead for n generations
61 LifeCellBox *m_up, *m_dn, *m_lf, *m_rt; // neighbour CellBoxes
62 LifeCellBox *m_prev, *m_next; // in linked list
63 LifeCellBox *m_hprev, *m_hnext; // in hash table
64 };
65
66
67 // IsAlive:
68 // Returns whether cell dx, dy in this box is alive
69 //
70 bool LifeCellBox::IsAlive(int dx, int dy) const
71 {
72 if (dy > 3)
73 return (m_live2 & 1 << ((dy - 4) * 8 + dx)) ? true : false ;
74 else
75 return (m_live1 & 1 << ((dy) * 8 + dx)) ? true : false ;
76 }
77
78 // SetCell:
79 // Sets cell dx, dy in this box to 'alive', returns true if
80 // the previous value was different, false if it was the same.
81 //
82 bool LifeCellBox::SetCell(int dx, int dy, bool alive)
83 {
84 if (IsAlive(dx, dy) != alive)
85 {
86 if (dy > 3)
87 m_live2 ^= 1 << ((dy - 4) * 8 + dx);
88 else
89 m_live1 ^= 1 << ((dy) * 8 + dx);
90
91 // reset this here to avoid updating problems
92 m_dead = 0;
93
94 return true;
95 }
96 else
97 return false;
98 }
99
100
101 // ==========================================================================
102 // Life
103 // ==========================================================================
104
105 // --------------------------------------------------------------------------
106 // Ctor and dtor
107 // --------------------------------------------------------------------------
108
109 Life::Life()
110 {
111 // pattern description
112 m_name = wxEmptyString;
113 m_rules = wxEmptyString;
114 m_description = wxEmptyString;
115
116 // pattern data
117 m_numcells = 0;
118 m_boxes = new LifeCellBox *[HASHSIZE];
119 m_head = NULL;
120 m_available = NULL;
121 for (int i = 0; i < HASHSIZE; i++)
122 m_boxes[i] = NULL;
123
124 // state vars for BeginFind & FindMore
125 m_cells = new LifeCell[CELLSARRAYSIZE];
126 m_ncells = 0;
127 m_findmore = false;
128 m_changed = false;
129 }
130
131 Life::~Life()
132 {
133 Clear();
134
135 delete[] m_boxes;
136 delete[] m_cells;
137 }
138
139 // Clear:
140 // Clears the board, freeing all storage.
141 //
142 void Life::Clear()
143 {
144 LifeCellBox *c, *nc;
145
146 // clear the hash table pointers
147 for (int i = 0; i < HASHSIZE; i++)
148 m_boxes[i] = NULL;
149
150 // free used boxes
151 c = m_head;
152 while (c)
153 {
154 nc = c->m_next;
155 delete c;
156 c = nc;
157 }
158 m_head = NULL;
159
160 // free available boxes
161 c = m_available;
162 while (c)
163 {
164 nc = c->m_next;
165 delete c;
166 c = nc;
167 }
168 m_available = NULL;
169
170 // reset state
171 m_name = wxEmptyString;
172 m_rules = wxEmptyString;
173 m_description = wxEmptyString;
174 m_numcells = 0;
175 }
176
177 // --------------------------------------------------------------------------
178 // Test and set individual cells
179 // --------------------------------------------------------------------------
180
181 // IsAlive:
182 // Returns whether cell (x, y) is alive.
183 //
184 bool Life::IsAlive(wxInt32 x, wxInt32 y)
185 {
186 LifeCellBox *c = LinkBox(x, y, false);
187
188 return (c && c->IsAlive( x - c->m_x, y - c->m_y ));
189 }
190
191 // SetCell:
192 // Sets or clears cell (x, y), according to the 'alive' param.
193 //
194 void Life::SetCell(wxInt32 x, wxInt32 y, bool alive)
195 {
196 LifeCellBox *c = LinkBox(x, y);
197 wxUint32 dx = x - c->m_x;
198 wxUint32 dy = y - c->m_y;
199
200 if (c->SetCell(dx, dy, alive))
201 {
202 if (alive)
203 m_numcells++;
204 else
205 m_numcells--;
206 }
207 }
208
209 void Life::SetPattern(const LifePattern& pattern)
210 {
211 wxArrayString data = pattern.m_shape;
212 wxString line;
213 long x = 0,
214 y = 0;
215
216 Clear();
217 for (size_t n = 0; n < data.GetCount(); n++)
218 {
219 line = data[n];
220
221 if ( (line.GetChar(0) != wxT('*')) &&
222 (line.GetChar(0) != wxT('.')) )
223 {
224 // assume that it is a digit or a minus sign
225 line.BeforeFirst(wxT(' ')).ToLong(&x);
226 line.AfterFirst(wxT(' ')).ToLong(&y);
227 }
228 else
229 {
230 // pattern data
231 for (size_t k = 0; k < line.Len(); k++)
232 SetCell(x + k, y, line.GetChar(k) == wxT('*'));
233
234 y++;
235 }
236 }
237
238 m_name = pattern.m_name;
239 m_rules = pattern.m_rules;
240 m_description = pattern.m_description;
241 }
242
243 // --------------------------------------------------------------------------
244 // Cellbox management functions
245 // --------------------------------------------------------------------------
246
247 // CreateBox:
248 // Creates a box in x, y, either taking it from the list
249 // of available boxes, or allocating a new one.
250 //
251 LifeCellBox* Life::CreateBox(wxInt32 x, wxInt32 y, wxUint32 hv)
252 {
253 LifeCellBox *c;
254
255 // if there are no available boxes, alloc a few more
256 if (!m_available)
257 for (int i = 1; i <= ALLOCBOXES; i++)
258 {
259 c = new LifeCellBox();
260
261 if (!c)
262 {
263 // TODO: handle memory errors. Note that right now, if we
264 // couldn't allocate at least one cellbox, we will crash
265 // before leaving CreateBox(). Probably we should try to
266 // allocate some boxes *before* the m_available list goes
267 // empty, so that we have a margin to handle errors
268 // gracefully.
269 wxLogFatalError(_("Out of memory! Aborting..."));
270
271 // NOTREACHED
272 }
273
274 c->m_next = m_available;
275 m_available = c;
276 }
277
278 // take a cellbox from the list of available boxes
279 c = m_available;
280 m_available = c->m_next;
281
282 // reset everything
283 memset((void *) c, 0, sizeof(LifeCellBox));
284 c->m_x = x;
285 c->m_y = y;
286
287 // insert c in the list
288 c->m_next = m_head;
289 m_head = c;
290 if (c->m_next) c->m_next->m_prev = c;
291
292 // insert c in the hash table
293 c->m_hnext = m_boxes[hv];
294 m_boxes[hv] = c;
295 if (c->m_hnext) c->m_hnext->m_hprev = c;
296
297 return c;
298 }
299
300 // LinkBox:
301 // Returns a pointer to the box (x, y); if it didn't exist yet,
302 // it returns NULL or creates a new one, depending on the value
303 // of the 'create' parameter.
304 //
305 LifeCellBox* Life::LinkBox(wxInt32 x, wxInt32 y, bool create)
306 {
307 wxUint32 hv;
308 LifeCellBox *c;
309
310 x &= 0xfffffff8;
311 y &= 0xfffffff8;
312 hv = HASH(x, y);
313
314 // search in the hash table
315 for (c = m_boxes[hv]; c; c = c->m_hnext)
316 if ((c->m_x == x) && (c->m_y == y)) return c;
317
318 // if not found, and (create == true), create a new one
319 return create? CreateBox(x, y, hv) : (LifeCellBox*) NULL;
320 }
321
322 // KillBox:
323 // Removes this box from the list and the hash table and
324 // puts it in the list of available boxes.
325 //
326 void Life::KillBox(LifeCellBox *c)
327 {
328 wxUint32 hv = HASH(c->m_x, c->m_y);
329
330 // remove from the list
331 if (c != m_head)
332 c->m_prev->m_next = c->m_next;
333 else
334 m_head = c->m_next;
335
336 // remove from the hash table
337 if (c != m_boxes[hv])
338 c->m_hprev->m_hnext = c->m_hnext;
339 else
340 m_boxes[hv] = c->m_hnext;
341
342 // update neighbours
343 if (c->m_next) c->m_next->m_prev = c->m_prev;
344 if (c->m_hnext) c->m_hnext->m_hprev = c->m_hprev;
345 if (c->m_up) c->m_up->m_dn = NULL;
346 if (c->m_dn) c->m_dn->m_up = NULL;
347 if (c->m_lf) c->m_lf->m_rt = NULL;
348 if (c->m_rt) c->m_rt->m_lf = NULL;
349
350 // append to the list of available boxes
351 c->m_next = m_available;
352 m_available = c;
353 }
354
355 // --------------------------------------------------------------------------
356 // Navigation
357 // --------------------------------------------------------------------------
358
359 LifeCell Life::FindCenter()
360 {
361 double sx, sy;
362 int n;
363 sx = 0.0;
364 sy = 0.0;
365 n = 0;
366
367 LifeCellBox *c;
368 for (c = m_head; c; c = c->m_next)
369 if (!c->m_dead)
370 {
371 sx += c->m_x;
372 sy += c->m_y;
373 n++;
374 }
375
376 if (n > 0)
377 {
378 sx = (sx / n) + CELLBOX / 2;
379 sy = (sy / n) + CELLBOX / 2;
380 }
381
382 LifeCell cell;
383 cell.i = (wxInt32) sx;
384 cell.j = (wxInt32) sy;
385 return cell;
386 }
387
388 LifeCell Life::FindNorth()
389 {
390 wxInt32 x = 0, y = 0;
391 bool first = true;
392
393 LifeCellBox *c;
394 for (c = m_head; c; c = c->m_next)
395 if (!c->m_dead && ((first) || (c->m_y < y)))
396 {
397 x = c->m_x;
398 y = c->m_y;
399 first = false;
400 }
401
402 LifeCell cell;
403 cell.i = first? 0 : x + CELLBOX / 2;
404 cell.j = first? 0 : y + CELLBOX / 2;
405 return cell;
406 }
407
408 LifeCell Life::FindSouth()
409 {
410 wxInt32 x = 0, y = 0;
411 bool first = true;
412
413 LifeCellBox *c;
414 for (c = m_head; c; c = c->m_next)
415 if (!c->m_dead && ((first) || (c->m_y > y)))
416 {
417 x = c->m_x;
418 y = c->m_y;
419 first = false;
420 }
421
422 LifeCell cell;
423 cell.i = first? 0 : x + CELLBOX / 2;
424 cell.j = first? 0 : y + CELLBOX / 2;
425 return cell;
426 }
427
428 LifeCell Life::FindWest()
429 {
430 wxInt32 x = 0, y = 0;
431 bool first = true;
432
433 LifeCellBox *c;
434 for (c = m_head; c; c = c->m_next)
435 if (!c->m_dead && ((first) || (c->m_x < x)))
436 {
437 x = c->m_x;
438 y = c->m_y;
439 first = false;
440 }
441
442 LifeCell cell;
443 cell.i = first? 0 : x + CELLBOX / 2;
444 cell.j = first? 0 : y + CELLBOX / 2;
445 return cell;
446 }
447
448 LifeCell Life::FindEast()
449 {
450 wxInt32 x = 0, y = 0;
451 bool first = true;
452
453 LifeCellBox *c;
454 for (c = m_head; c; c = c->m_next)
455 if (!c->m_dead && ((first) || (c->m_x > x)))
456 {
457 x = c->m_x;
458 y = c->m_y;
459 first = false;
460 }
461
462 LifeCell cell;
463 cell.i = first? 0 : x + CELLBOX / 2;
464 cell.j = first? 0 : y + CELLBOX / 2;
465 return cell;
466 }
467
468 // --------------------------------------------------------------------------
469 // FindMore & co.
470 // --------------------------------------------------------------------------
471
472 // DoLine:
473 // Post eight cells to the cell arrays - leave out the fourth
474 // argument (or pass 0, the default value) to post alive cells
475 // only, else it will post cells which have changed.
476 //
477 void Life::DoLine(wxInt32 x, wxInt32 y, wxUint32 live, wxUint32 old)
478 {
479 wxUint32 diff = (live ^ old) & 0xff;
480
481 if (!diff) return;
482
483 for (wxInt32 k = 8; k; k--, x++)
484 {
485 if (diff & 0x01)
486 {
487 m_cells[m_ncells].i = x;
488 m_cells[m_ncells].j = y;
489 m_ncells++;
490 }
491 diff >>= 1;
492 }
493 }
494
495 void Life::BeginFind(wxInt32 x0, wxInt32 y0, wxInt32 x1, wxInt32 y1, bool changed)
496 {
497 // TODO: optimize for the case where the maximum number of
498 // cellboxes that fit in the specified viewport is smaller
499 // than the current total of boxes; iterating over the list
500 // should then be faster than searching in the hash table.
501
502 m_x0 = m_x = x0 & 0xfffffff8;
503 m_y0 = m_y = y0 & 0xfffffff8;
504 m_x1 = (x1 + 7) & 0xfffffff8;
505 m_y1 = (y1 + 7) & 0xfffffff8;
506
507 m_findmore = true;
508 m_changed = changed;
509 }
510
511 bool Life::FindMore(LifeCell *cells[], size_t *ncells)
512 {
513 LifeCellBox *c;
514 *cells = m_cells;
515 m_ncells = 0;
516
517 if (m_changed)
518 {
519 for ( ; m_y <= m_y1; m_y += 8, m_x = m_x0)
520 for ( ; m_x <= m_x1; m_x += 8)
521 {
522 if ((c = LinkBox(m_x, m_y, false)) == NULL)
523 continue;
524
525 // check whether there is enough space left in the array
526 if (m_ncells > (CELLSARRAYSIZE - 64))
527 {
528 *ncells = m_ncells;
529 return false;
530 }
531
532 DoLine(m_x, m_y , c->m_live1, c->m_old1 );
533 DoLine(m_x, m_y + 1, c->m_live1 >> 8, c->m_old1 >> 8 );
534 DoLine(m_x, m_y + 2, c->m_live1 >> 16, c->m_old1 >> 16);
535 DoLine(m_x, m_y + 3, c->m_live1 >> 24, c->m_old1 >> 24);
536 DoLine(m_x, m_y + 4, c->m_live2, c->m_old2 );
537 DoLine(m_x, m_y + 5, c->m_live2 >> 8, c->m_old2 >> 8 );
538 DoLine(m_x, m_y + 6, c->m_live2 >> 16, c->m_old2 >> 16);
539 DoLine(m_x, m_y + 7, c->m_live2 >> 24, c->m_old2 >> 24);
540 }
541 }
542 else
543 {
544 for ( ; m_y <= m_y1; m_y += 8, m_x = m_x0)
545 for ( ; m_x <= m_x1; m_x += 8)
546 {
547 if ((c = LinkBox(m_x, m_y, false)) == NULL)
548 continue;
549
550 // check whether there is enough space left in the array
551 if (m_ncells > (CELLSARRAYSIZE - 64))
552 {
553 *ncells = m_ncells;
554 return false;
555 }
556
557 DoLine(m_x, m_y , c->m_live1 );
558 DoLine(m_x, m_y + 1, c->m_live1 >> 8 );
559 DoLine(m_x, m_y + 2, c->m_live1 >> 16);
560 DoLine(m_x, m_y + 3, c->m_live1 >> 24);
561 DoLine(m_x, m_y + 4, c->m_live2 );
562 DoLine(m_x, m_y + 5, c->m_live2 >> 8 );
563 DoLine(m_x, m_y + 6, c->m_live2 >> 16);
564 DoLine(m_x, m_y + 7, c->m_live2 >> 24);
565 }
566 }
567
568 *ncells = m_ncells;
569 m_findmore = false;
570 return true;
571 }
572
573 // --------------------------------------------------------------------------
574 // Evolution engine
575 // --------------------------------------------------------------------------
576
577 extern unsigned char *g_tab;
578 extern int g_tab1[];
579 extern int g_tab2[];
580
581 // NextTic:
582 // Advance one step in evolution :-)
583 //
584 bool Life::NextTic()
585 {
586 LifeCellBox *c, *up, *dn, *lf, *rt;
587 wxUint32 t1, t2, t3, t4;
588 bool changed = false;
589
590 m_numcells = 0;
591
592 // Stage 1:
593 // Compute neighbours of each cell
594 //
595 // WARNING: unrolled loops and lengthy code follows!
596 //
597 c = m_head;
598
599 while (c)
600 {
601 if (! (c->m_live1 || c->m_live2))
602 {
603 c = c->m_next;
604 continue;
605 }
606 up = c->m_up;
607 dn = c->m_dn;
608 lf = c->m_lf;
609 rt = c->m_rt;
610
611 // up
612 t1 = c->m_live1 & 0x000000ff;
613 if (t1)
614 {
615 if (!up)
616 {
617 up = LinkBox(c->m_x, c->m_y - 8);
618 up->m_dn = c;
619 }
620 t2 = g_tab1[t1];
621 up->m_on[7] += t2;
622 c->m_on[1] += t2;
623 c->m_on[0] += g_tab2[t1];
624 }
625
626 // down
627 t1 = (c->m_live2 & 0xff000000) >> 24;
628 if (t1)
629 {
630 if (!dn)
631 {
632 dn = LinkBox(c->m_x, c->m_y + 8);
633 dn->m_up = c;
634 }
635 t2 = g_tab1[t1];
636 dn->m_on[0] += t2;
637 c->m_on[6] += t2;
638 c->m_on[7] += g_tab2[t1];
639 }
640
641 t1 = c->m_live1;
642 t2 = c->m_live2;
643
644 // left
645 if (t1 & 0x01010101)
646 {
647 if (!lf)
648 {
649 lf = LinkBox(c->m_x - 8, c->m_y);
650 lf->m_rt = c;
651 }
652 if (t1 & 0x00000001)
653 {
654 if (!lf->m_up)
655 {
656 lf->m_up = LinkBox(c->m_x - 8, c->m_y - 8);
657 lf->m_up->m_dn = lf;
658 }
659 lf->m_up->m_on[7] += 0x10000000;
660 lf->m_on[0] += 0x10000000;
661 lf->m_on[1] += 0x10000000;
662 }
663 if (t1 & 0x00000100)
664 {
665 lf->m_on[0] += 0x10000000;
666 lf->m_on[1] += 0x10000000;
667 lf->m_on[2] += 0x10000000;
668 }
669 if (t1 & 0x00010000)
670 {
671 lf->m_on[1] += 0x10000000;
672 lf->m_on[2] += 0x10000000;
673 lf->m_on[3] += 0x10000000;
674 }
675 if (t1 & 0x01000000)
676 {
677 lf->m_on[2] += 0x10000000;
678 lf->m_on[3] += 0x10000000;
679 lf->m_on[4] += 0x10000000;
680 }
681 }
682 if (t2 & 0x01010101)
683 {
684 if (!lf)
685 {
686 lf = LinkBox(c->m_x - 8, c->m_y);
687 lf->m_rt = c;
688 }
689 if (t2 & 0x00000001)
690 {
691 lf->m_on[3] += 0x10000000;
692 lf->m_on[4] += 0x10000000;
693 lf->m_on[5] += 0x10000000;
694 }
695 if (t2 & 0x00000100)
696 {
697 lf->m_on[4] += 0x10000000;
698 lf->m_on[5] += 0x10000000;
699 lf->m_on[6] += 0x10000000;
700 }
701 if (t2 & 0x00010000)
702 {
703 lf->m_on[5] += 0x10000000;
704 lf->m_on[6] += 0x10000000;
705 lf->m_on[7] += 0x10000000;
706 }
707 if (t2 & 0x01000000)
708 {
709 if (!lf->m_dn)
710 {
711 lf->m_dn = LinkBox(c->m_x - 8, c->m_y + 8);
712 lf->m_dn->m_up = lf;
713 }
714 lf->m_on[6] += 0x10000000;
715 lf->m_on[7] += 0x10000000;
716 lf->m_dn->m_on[0] += 0x10000000;
717 }
718 }
719
720 // right
721 if (t1 & 0x80808080)
722 {
723 if (!rt)
724 {
725 rt = LinkBox(c->m_x + 8, c->m_y);
726 rt->m_lf = c;
727 }
728 if (t1 & 0x00000080)
729 {
730 if (!rt->m_up)
731 {
732 rt->m_up = LinkBox(c->m_x + 8, c->m_y - 8);
733 rt->m_up->m_dn = rt;
734 }
735 rt->m_up->m_on[7] += 0x00000001;
736 rt->m_on[0] += 0x00000001;
737 rt->m_on[1] += 0x00000001;
738 }
739 if (t1 & 0x00008000)
740 {
741 rt->m_on[0] += 0x00000001;
742 rt->m_on[1] += 0x00000001;
743 rt->m_on[2] += 0x00000001;
744 }
745 if (t1 & 0x00800000)
746 {
747 rt->m_on[1] += 0x00000001;
748 rt->m_on[2] += 0x00000001;
749 rt->m_on[3] += 0x00000001;
750 }
751 if (t1 & 0x80000000)
752 {
753 rt->m_on[2] += 0x00000001;
754 rt->m_on[3] += 0x00000001;
755 rt->m_on[4] += 0x00000001;
756 }
757 }
758 if (t2 & 0x80808080)
759 {
760 if (!rt)
761 {
762 rt = LinkBox(c->m_x + 8, c->m_y);
763 rt->m_lf = c;
764 }
765 if (t2 & 0x00000080)
766 {
767 rt->m_on[3] += 0x00000001;
768 rt->m_on[4] += 0x00000001;
769 rt->m_on[5] += 0x00000001;
770 }
771 if (t2 & 0x00008000)
772 {
773 rt->m_on[4] += 0x00000001;
774 rt->m_on[5] += 0x00000001;
775 rt->m_on[6] += 0x00000001;
776 }
777 if (t2 & 0x00800000)
778 {
779 rt->m_on[5] += 0x00000001;
780 rt->m_on[6] += 0x00000001;
781 rt->m_on[7] += 0x00000001;
782 }
783 if (t2 & 0x80000000)
784 {
785 if (!rt->m_dn)
786 {
787 rt->m_dn = LinkBox(c->m_x + 8, c->m_y + 8);
788 rt->m_dn->m_up = rt;
789 }
790 rt->m_on[6] += 0x00000001;
791 rt->m_on[7] += 0x00000001;
792 rt->m_dn->m_on[0] += 0x00000001;
793 }
794 }
795
796 // inner cells
797 int i;
798 for (i = 1; i <= 3; i++)
799 {
800 t1 = ((c->m_live1) >> (i * 8)) & 0x000000ff;
801 if (t1)
802 {
803 c->m_on[i - 1] += g_tab1[t1];
804 c->m_on[i ] += g_tab2[t1];
805 c->m_on[i + 1] += g_tab1[t1];
806 }
807 }
808 for (i = 0; i <= 2; i++)
809 {
810 t1 = ((c->m_live2) >> (i * 8)) & 0x000000ff;
811 if (t1)
812 {
813 c->m_on[i + 3] += g_tab1[t1];
814 c->m_on[i + 4] += g_tab2[t1];
815 c->m_on[i + 5] += g_tab1[t1];
816 }
817 }
818
819 c->m_up = up;
820 c->m_dn = dn;
821 c->m_lf = lf;
822 c->m_rt = rt;
823 c = c->m_next;
824 }
825
826 // Stage 2:
827 // Stabilize
828 //
829 c = m_head;
830
831 while (c)
832 {
833 t1 = 0;
834 t2 = 0;
835
836 t3 = c->m_live1;
837 c->m_old1 = t3;
838
839 t4 = c->m_on[0];
840 t1 |= g_tab[ ((t4 & 0x0000ffff) << 4 ) + ((t3 ) & 0xf) ];
841 t1 |= g_tab[ ((t4 & 0xffff0000) >> 12) + ((t3 >> 4 ) & 0xf) ] << 4;
842 t4 = c->m_on[1];
843 t1 |= g_tab[ ((t4 & 0x0000ffff) << 4 ) + ((t3 >> 8 ) & 0xf) ] << 8;
844 t1 |= g_tab[ ((t4 & 0xffff0000) >> 12) + ((t3 >> 12) & 0xf) ] << 12;
845 t4 = c->m_on[2];
846 t1 |= g_tab[ ((t4 & 0x0000ffff) << 4 ) + ((t3 >> 16) & 0xf) ] << 16;
847 t1 |= g_tab[ ((t4 & 0xffff0000) >> 12) + ((t3 >> 20) & 0xf) ] << 20;
848 t4 = c->m_on[3];
849 t1 |= g_tab[ ((t4 & 0x0000ffff) << 4 ) + ((t3 >> 24) & 0xf) ] << 24;
850 t1 |= g_tab[ ((t4 & 0xffff0000) >> 12) + ((t3 >> 28) & 0xf) ] << 28;
851
852 t3 = c->m_live2;
853 c->m_old2 = t3;
854
855 t4 = c->m_on[4];
856 t2 |= g_tab[ ((t4 & 0x0000ffff) << 4 ) + ((t3 ) & 0xf) ];
857 t2 |= g_tab[ ((t4 & 0xffff0000) >> 12) + ((t3 >> 4 ) & 0xf) ] << 4;
858 t4 = c->m_on[5];
859 t2 |= g_tab[ ((t4 & 0x0000ffff) << 4 ) + ((t3 >> 8 ) & 0xf) ] << 8;
860 t2 |= g_tab[ ((t4 & 0xffff0000) >> 12) + ((t3 >> 12) & 0xf) ] << 12;
861 t4 = c->m_on[6];
862 t2 |= g_tab[ ((t4 & 0x0000ffff) << 4 ) + ((t3 >> 16) & 0xf) ] << 16;
863 t2 |= g_tab[ ((t4 & 0xffff0000) >> 12) + ((t3 >> 20) & 0xf) ] << 20;
864 t4 = c->m_on[7];
865 t2 |= g_tab[ ((t4 & 0x0000ffff) << 4 ) + ((t3 >> 24) & 0xf) ] << 24;
866 t2 |= g_tab[ ((t4 & 0xffff0000) >> 12) + ((t3 >> 28) & 0xf) ] << 28;
867
868 c->m_on[0] = c->m_on[1] = c->m_on[2] = c->m_on[3] =
869 c->m_on[4] = c->m_on[5] = c->m_on[6] = c->m_on[7] = 0;
870 c->m_live1 = t1;
871 c->m_live2 = t2;
872
873 // count alive cells
874 #if 1
875 wxUint32 t1_, t2_;
876
877 t1_ = (t1 & 0x55555555) + (t1 >> 1 & 0x55555555);
878 t1_ = (t1_ & 0x33333333) + (t1_ >> 2 & 0x33333333);
879
880 t2_ = (t2 & 0x55555555) + (t2 >> 1 & 0x55555555);
881 t2_ = (t2_ & 0x33333333) + (t2_ >> 2 & 0x33333333) + t1_;
882 t2_ = (t2_ & 0x0F0F0F0F) + (t2_ >> 4 & 0x0F0F0F0F);
883 t2_ = (t2_ & 0x00FF00FF) + (t2_ >> 8 & 0x00FF00FF);
884
885 m_numcells += (t2_ & 0xFF) + (t2_ >> 16 & 0xFF);
886 #else
887 // Original, slower code
888 for (int i = 0; i < 32; i++)
889 {
890 if (t1 & (1 << i)) m_numcells++;
891 if (t2 & (1 << i)) m_numcells++;
892 }
893 #endif
894
895 changed |= ((t1 ^ c->m_old1) || (t2 ^ c->m_old2));
896
897 // mark, and discard if necessary, dead boxes
898 if (t1 || t2)
899 {
900 c->m_dead = 0;
901 c = c->m_next;
902 }
903 else
904 {
905 LifeCellBox *aux = c->m_next;
906 if (c->m_dead++ > MAXDEAD)
907 KillBox(c);
908
909 c = aux;
910 }
911 }
912
913 return changed;
914 }
915
916 // ==========================================================================
917 // LifeModule
918 // ==========================================================================
919
920 // A module to pregenerate lookup tables without having to do it
921 // from the application.
922
923 class LifeModule: public wxModule
924 {
925 DECLARE_DYNAMIC_CLASS(LifeModule)
926
927 public:
928 LifeModule() {};
929 bool OnInit();
930 void OnExit();
931 };
932
933 IMPLEMENT_DYNAMIC_CLASS(LifeModule, wxModule)
934
935 bool LifeModule::OnInit()
936 {
937 // see below
938 g_tab = new unsigned char [0xfffff];
939
940 if (!g_tab) return false;
941
942 for (wxUint32 i = 0; i < 0xfffff; i++)
943 {
944 wxUint32 val = i >> 4;
945 wxUint32 old = i & 0x0000f;
946 wxUint32 live = 0;
947
948 for (int j = 0; j < 4; j++)
949 {
950 live >>= 1;
951
952 if (((val & 0xf) == 3) || (((val & 0xf) == 2) && (old & 0x1)))
953 live |= 0x8;
954
955 old >>= 1;
956 val >>= 4;
957 }
958
959 g_tab[i] = (unsigned char) live;
960 }
961
962 return true;
963 }
964
965 void LifeModule::OnExit()
966 {
967 delete [] g_tab;
968 }
969
970
971 // This table converts from number of neighbors (like in on[]) to
972 // bits, for a set of four cells. It takes as index a five-digit
973 // hexadecimal value (0xNNNNB) where Ns hold number of neighbors
974 // for each cell and B holds their previous state.
975 //
976 unsigned char *g_tab;
977
978 // This table converts from bits (like in live1, live2) to number
979 // of neighbors for each cell in the upper or lower row.
980 //
981 int g_tab1[]=
982 {
983 0x00000000,
984 0x00000011,
985 0x00000111,
986 0x00000122,
987 0x00001110,
988 0x00001121,
989 0x00001221,
990 0x00001232,
991 0x00011100,
992 0x00011111,
993 0x00011211,
994 0x00011222,
995 0x00012210,
996 0x00012221,
997 0x00012321,
998 0x00012332,
999 0x00111000,
1000 0x00111011,
1001 0x00111111,
1002 0x00111122,
1003 0x00112110,
1004 0x00112121,
1005 0x00112221,
1006 0x00112232,
1007 0x00122100,
1008 0x00122111,
1009 0x00122211,
1010 0x00122222,
1011 0x00123210,
1012 0x00123221,
1013 0x00123321,
1014 0x00123332,
1015 0x01110000,
1016 0x01110011,
1017 0x01110111,
1018 0x01110122,
1019 0x01111110,
1020 0x01111121,
1021 0x01111221,
1022 0x01111232,
1023 0x01121100,
1024 0x01121111,
1025 0x01121211,
1026 0x01121222,
1027 0x01122210,
1028 0x01122221,
1029 0x01122321,
1030 0x01122332,
1031 0x01221000,
1032 0x01221011,
1033 0x01221111,
1034 0x01221122,
1035 0x01222110,
1036 0x01222121,
1037 0x01222221,
1038 0x01222232,
1039 0x01232100,
1040 0x01232111,
1041 0x01232211,
1042 0x01232222,
1043 0x01233210,
1044 0x01233221,
1045 0x01233321,
1046 0x01233332,
1047 0x11100000,
1048 0x11100011,
1049 0x11100111,
1050 0x11100122,
1051 0x11101110,
1052 0x11101121,
1053 0x11101221,
1054 0x11101232,
1055 0x11111100,
1056 0x11111111,
1057 0x11111211,
1058 0x11111222,
1059 0x11112210,
1060 0x11112221,
1061 0x11112321,
1062 0x11112332,
1063 0x11211000,
1064 0x11211011,
1065 0x11211111,
1066 0x11211122,
1067 0x11212110,
1068 0x11212121,
1069 0x11212221,
1070 0x11212232,
1071 0x11222100,
1072 0x11222111,
1073 0x11222211,
1074 0x11222222,
1075 0x11223210,
1076 0x11223221,
1077 0x11223321,
1078 0x11223332,
1079 0x12210000,
1080 0x12210011,
1081 0x12210111,
1082 0x12210122,
1083 0x12211110,
1084 0x12211121,
1085 0x12211221,
1086 0x12211232,
1087 0x12221100,
1088 0x12221111,
1089 0x12221211,
1090 0x12221222,
1091 0x12222210,
1092 0x12222221,
1093 0x12222321,
1094 0x12222332,
1095 0x12321000,
1096 0x12321011,
1097 0x12321111,
1098 0x12321122,
1099 0x12322110,
1100 0x12322121,
1101 0x12322221,
1102 0x12322232,
1103 0x12332100,
1104 0x12332111,
1105 0x12332211,
1106 0x12332222,
1107 0x12333210,
1108 0x12333221,
1109 0x12333321,
1110 0x12333332,
1111 0x11000000,
1112 0x11000011,
1113 0x11000111,
1114 0x11000122,
1115 0x11001110,
1116 0x11001121,
1117 0x11001221,
1118 0x11001232,
1119 0x11011100,
1120 0x11011111,
1121 0x11011211,
1122 0x11011222,
1123 0x11012210,
1124 0x11012221,
1125 0x11012321,
1126 0x11012332,
1127 0x11111000,
1128 0x11111011,
1129 0x11111111,
1130 0x11111122,
1131 0x11112110,
1132 0x11112121,
1133 0x11112221,
1134 0x11112232,
1135 0x11122100,
1136 0x11122111,
1137 0x11122211,
1138 0x11122222,
1139 0x11123210,
1140 0x11123221,
1141 0x11123321,
1142 0x11123332,
1143 0x12110000,
1144 0x12110011,
1145 0x12110111,
1146 0x12110122,
1147 0x12111110,
1148 0x12111121,
1149 0x12111221,
1150 0x12111232,
1151 0x12121100,
1152 0x12121111,
1153 0x12121211,
1154 0x12121222,
1155 0x12122210,
1156 0x12122221,
1157 0x12122321,
1158 0x12122332,
1159 0x12221000,
1160 0x12221011,
1161 0x12221111,
1162 0x12221122,
1163 0x12222110,
1164 0x12222121,
1165 0x12222221,
1166 0x12222232,
1167 0x12232100,
1168 0x12232111,
1169 0x12232211,
1170 0x12232222,
1171 0x12233210,
1172 0x12233221,
1173 0x12233321,
1174 0x12233332,
1175 0x22100000,
1176 0x22100011,
1177 0x22100111,
1178 0x22100122,
1179 0x22101110,
1180 0x22101121,
1181 0x22101221,
1182 0x22101232,
1183 0x22111100,
1184 0x22111111,
1185 0x22111211,
1186 0x22111222,
1187 0x22112210,
1188 0x22112221,
1189 0x22112321,
1190 0x22112332,
1191 0x22211000,
1192 0x22211011,
1193 0x22211111,
1194 0x22211122,
1195 0x22212110,
1196 0x22212121,
1197 0x22212221,
1198 0x22212232,
1199 0x22222100,
1200 0x22222111,
1201 0x22222211,
1202 0x22222222,
1203 0x22223210,
1204 0x22223221,
1205 0x22223321,
1206 0x22223332,
1207 0x23210000,
1208 0x23210011,
1209 0x23210111,
1210 0x23210122,
1211 0x23211110,
1212 0x23211121,
1213 0x23211221,
1214 0x23211232,
1215 0x23221100,
1216 0x23221111,
1217 0x23221211,
1218 0x23221222,
1219 0x23222210,
1220 0x23222221,
1221 0x23222321,
1222 0x23222332,
1223 0x23321000,
1224 0x23321011,
1225 0x23321111,
1226 0x23321122,
1227 0x23322110,
1228 0x23322121,
1229 0x23322221,
1230 0x23322232,
1231 0x23332100,
1232 0x23332111,
1233 0x23332211,
1234 0x23332222,
1235 0x23333210,
1236 0x23333221,
1237 0x23333321,
1238 0x23333332
1239 };
1240
1241 // This table converts from bits (like in live1, live2) to number
1242 // of neighbors for each cell in the same row (excluding ourselves)
1243 //
1244 int g_tab2[]=
1245 {
1246 0x00000000,
1247 0x00000010,
1248 0x00000101,
1249 0x00000111,
1250 0x00001010,
1251 0x00001020,
1252 0x00001111,
1253 0x00001121,
1254 0x00010100,
1255 0x00010110,
1256 0x00010201,
1257 0x00010211,
1258 0x00011110,
1259 0x00011120,
1260 0x00011211,
1261 0x00011221,
1262 0x00101000,
1263 0x00101010,
1264 0x00101101,
1265 0x00101111,
1266 0x00102010,
1267 0x00102020,
1268 0x00102111,
1269 0x00102121,
1270 0x00111100,
1271 0x00111110,
1272 0x00111201,
1273 0x00111211,
1274 0x00112110,
1275 0x00112120,
1276 0x00112211,
1277 0x00112221,
1278 0x01010000,
1279 0x01010010,
1280 0x01010101,
1281 0x01010111,
1282 0x01011010,
1283 0x01011020,
1284 0x01011111,
1285 0x01011121,
1286 0x01020100,
1287 0x01020110,
1288 0x01020201,
1289 0x01020211,
1290 0x01021110,
1291 0x01021120,
1292 0x01021211,
1293 0x01021221,
1294 0x01111000,
1295 0x01111010,
1296 0x01111101,
1297 0x01111111,
1298 0x01112010,
1299 0x01112020,
1300 0x01112111,
1301 0x01112121,
1302 0x01121100,
1303 0x01121110,
1304 0x01121201,
1305 0x01121211,
1306 0x01122110,
1307 0x01122120,
1308 0x01122211,
1309 0x01122221,
1310 0x10100000,
1311 0x10100010,
1312 0x10100101,
1313 0x10100111,
1314 0x10101010,
1315 0x10101020,
1316 0x10101111,
1317 0x10101121,
1318 0x10110100,
1319 0x10110110,
1320 0x10110201,
1321 0x10110211,
1322 0x10111110,
1323 0x10111120,
1324 0x10111211,
1325 0x10111221,
1326 0x10201000,
1327 0x10201010,
1328 0x10201101,
1329 0x10201111,
1330 0x10202010,
1331 0x10202020,
1332 0x10202111,
1333 0x10202121,
1334 0x10211100,
1335 0x10211110,
1336 0x10211201,
1337 0x10211211,
1338 0x10212110,
1339 0x10212120,
1340 0x10212211,
1341 0x10212221,
1342 0x11110000,
1343 0x11110010,
1344 0x11110101,
1345 0x11110111,
1346 0x11111010,
1347 0x11111020,
1348 0x11111111,
1349 0x11111121,
1350 0x11120100,
1351 0x11120110,
1352 0x11120201,
1353 0x11120211,
1354 0x11121110,
1355 0x11121120,
1356 0x11121211,
1357 0x11121221,
1358 0x11211000,
1359 0x11211010,
1360 0x11211101,
1361 0x11211111,
1362 0x11212010,
1363 0x11212020,
1364 0x11212111,
1365 0x11212121,
1366 0x11221100,
1367 0x11221110,
1368 0x11221201,
1369 0x11221211,
1370 0x11222110,
1371 0x11222120,
1372 0x11222211,
1373 0x11222221,
1374 0x01000000,
1375 0x01000010,
1376 0x01000101,
1377 0x01000111,
1378 0x01001010,
1379 0x01001020,
1380 0x01001111,
1381 0x01001121,
1382 0x01010100,
1383 0x01010110,
1384 0x01010201,
1385 0x01010211,
1386 0x01011110,
1387 0x01011120,
1388 0x01011211,
1389 0x01011221,
1390 0x01101000,
1391 0x01101010,
1392 0x01101101,
1393 0x01101111,
1394 0x01102010,
1395 0x01102020,
1396 0x01102111,
1397 0x01102121,
1398 0x01111100,
1399 0x01111110,
1400 0x01111201,
1401 0x01111211,
1402 0x01112110,
1403 0x01112120,
1404 0x01112211,
1405 0x01112221,
1406 0x02010000,
1407 0x02010010,
1408 0x02010101,
1409 0x02010111,
1410 0x02011010,
1411 0x02011020,
1412 0x02011111,
1413 0x02011121,
1414 0x02020100,
1415 0x02020110,
1416 0x02020201,
1417 0x02020211,
1418 0x02021110,
1419 0x02021120,
1420 0x02021211,
1421 0x02021221,
1422 0x02111000,
1423 0x02111010,
1424 0x02111101,
1425 0x02111111,
1426 0x02112010,
1427 0x02112020,
1428 0x02112111,
1429 0x02112121,
1430 0x02121100,
1431 0x02121110,
1432 0x02121201,
1433 0x02121211,
1434 0x02122110,
1435 0x02122120,
1436 0x02122211,
1437 0x02122221,
1438 0x11100000,
1439 0x11100010,
1440 0x11100101,
1441 0x11100111,
1442 0x11101010,
1443 0x11101020,
1444 0x11101111,
1445 0x11101121,
1446 0x11110100,
1447 0x11110110,
1448 0x11110201,
1449 0x11110211,
1450 0x11111110,
1451 0x11111120,
1452 0x11111211,
1453 0x11111221,
1454 0x11201000,
1455 0x11201010,
1456 0x11201101,
1457 0x11201111,
1458 0x11202010,
1459 0x11202020,
1460 0x11202111,
1461 0x11202121,
1462 0x11211100,
1463 0x11211110,
1464 0x11211201,
1465 0x11211211,
1466 0x11212110,
1467 0x11212120,
1468 0x11212211,
1469 0x11212221,
1470 0x12110000,
1471 0x12110010,
1472 0x12110101,
1473 0x12110111,
1474 0x12111010,
1475 0x12111020,
1476 0x12111111,
1477 0x12111121,
1478 0x12120100,
1479 0x12120110,
1480 0x12120201,
1481 0x12120211,
1482 0x12121110,
1483 0x12121120,
1484 0x12121211,
1485 0x12121221,
1486 0x12211000,
1487 0x12211010,
1488 0x12211101,
1489 0x12211111,
1490 0x12212010,
1491 0x12212020,
1492 0x12212111,
1493 0x12212121,
1494 0x12221100,
1495 0x12221110,
1496 0x12221201,
1497 0x12221211,
1498 0x12222110,
1499 0x12222120,
1500 0x12222211,
1501 0x12222221
1502 };