Game of Life Hash Table help

norcalaussie (5)
Hi everyone, I am trying to use my HashTable template with a Game of Life simulation. The hash table is made of a static array of STL lists. It compiles and runs, but there is something wrong because the output after the first generation isn't correct. I have a feeling it something with me clear() function, but it seems correct to me. Any help is appreciated.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
 
#ifndef HashTable_h
#define HashTable_h

#define HASHTABLE_CAPACITY 1009

#include <list>
#include <algorithm>
#include <cassert>




template<class DataType>
class HashTable{
    public:
        HashTable();
        void insert(const DataType & newObject);
        bool retrieve(DataType & ret);
        bool remove(DataType & rem);
        bool replace(DataType & newData);
        int getSize();
        bool first(DataType& getData);
        bool getNext(DataType& getData);
        void clear();
    private:
        list<DataType> data[HASHTABLE_CAPACITY];
        typename list<DataType>::const_iterator it2;
        typename list<DataType>::iterator it;
        int size;
        int current;
        void setWrappedIndex(int dI);
        int wrappedI;
};

template<class DataType>
HashTable<DataType>::HashTable()
:size(0), current(-1), wrappedI(0){
}

template<class DataType>
void HashTable<DataType>::insert(const DataType & newObject){
    setWrappedIndex(newObject.hashCode());
    it = find(data[wrappedI].begin(), data[wrappedI].end(), newObject);
    if(it != data[wrappedI].end()) *it = newObject;
    else {
        data[wrappedI].push_back(newObject);
        current = wrappedI;
        size++;
    }
}

template<class DataType>
bool HashTable<DataType>::retrieve(DataType & ret){
    setWrappedIndex(ret.hashCode());
    it2 = find(data[wrappedI].begin(), data[wrappedI].end(), ret);
    if (it2 == data[wrappedI].end()) return false;
    ret = *it2;
    current = wrappedI;
    return true;
}

template<class DataType>
bool HashTable<DataType>::replace(DataType & newData){
    setWrappedIndex(newData.hashCode());
    it = find(data[wrappedI].begin(), data[wrappedI].end(), newData);
    if (it == data[wrappedI].end()) return false;
    else{
        *it = newData;
        current = wrappedI;
        return true;
    }
}

template<class DataType>
bool HashTable<DataType>::remove(DataType & rem){
    setWrappedIndex(rem.hashCode());
    it = find(data[wrappedI].begin(), data[wrappedI].end(), rem);
    if (it == data[wrappedI].end()) return false;
    else{
        data[wrappedI].erase(it);
        size--;
        current = wrappedI;
        return true;
    }
}

template<class DataType>
bool HashTable<DataType>::first(DataType& getData){
    assert(current >= -1 && current < HASHTABLE_CAPACITY);
    for (current = 0; current < HASHTABLE_CAPACITY; current++){
        if (!data[current].empty()){
            it = data[current].begin();
            break;
        }
    }
    if (current == HASHTABLE_CAPACITY) current = -1;
    if (current == -1) return false;
    getData = *it;
    return true;
}

template<class DataType>
bool HashTable<DataType>::getNext(DataType& getData){
    assert(current >= -1 && current < HASHTABLE_CAPACITY);
    if (current == -1) return false;
    assert(!data[current].empty());
    if (++it == data[current].end()){
        for (current = current + 1; current < HASHTABLE_CAPACITY; current++){
            if (!data[current].empty()){
                it = data[current].begin();
                break;
            }
        }
    }
    if (current == HASHTABLE_CAPACITY) current = -1;
    else getData = *it;
    return current >= 0;
}

template<class DataType>
void HashTable<DataType>::clear(){
    for(int i=0;i<HASHTABLE_CAPACITY;i++){
        data[wrappedI].clear();
    }
    current = -1;
    size = 0;
    wrappedI = 0;
}

template<class DataType>
void HashTable<DataType>::setWrappedIndex(int dI){
    if (dI>HASHTABLE_CAPACITY){
        wrappedI = dI % HASHTABLE_CAPACITY;
        if (wrappedI > HASHTABLE_CAPACITY){
            while (wrappedI > HASHTABLE_CAPACITY)
                wrappedI = wrappedI % HASHTABLE_CAPACITY;
        }
    }else if (dI < 0){
        while (dI < 0 && dI < HASHTABLE_CAPACITY)
            dI += HASHTABLE_CAPACITY;
        wrappedI = dI;
    }
    wrappedI = dI;
}

template<class DataType>
int HashTable<DataType>::getSize(){
    return size;
}



#endif


For reference here is the Game OF Life simulation that uses the HashTable template, but its code was provided to us so there shouldn't be errors there.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
 
#include <iostream>
using namespace std;

struct cell
{
  int value; // equal to 1, so 0,0 is not a blank
  int row; // any +/0/- value
  int col; // any +/0/- value

  bool operator==(const cell& c) const {return row == c.row && col == c.col;}
  bool operator<(const cell& c) const {return (1000000 * row + col) < (1000000 * c.row + c.col);}
  int hashCode() const {return 31 * row + col;}
};

#include "HashTable.h"
HashTable<cell> grid;
HashTable<cell> newGrid;

const int MINROW = -25;
const int MAXROW = 25;
const int MINCOL = -25;
const int MAXCOL = 25;

int neighborCount(int row, int col)
{
  cell temp;
  int count = 0;
  for (temp.row = row - 1; temp.row <= row + 1; temp.row++)
    for (temp.col = col - 1; temp.col <= col + 1; temp.col++)
      if (temp.row != row || temp.col != col)
        if (grid.retrieve(temp))
          ++count;
  return count;
}

void initialize()
{
  cout << "List the coordinates for living cells.\n";
  cout << "Terminate the list with a special pair -1 -1\n";

  cell temp;
  while (true)
  {
    cin >> temp.row >> temp.col;
    if (temp.row == -1 && temp.col == -1) break;
    grid.insert(temp);
  }
  cin.ignore();
}

void print()
{
  cell temp = {1};
  cout << "\nThe current Life configuration is:\n";
  for (temp.row = MINROW; temp.row <= MAXROW; temp.row++)
  {
    for (temp.col = MINCOL; temp.col <= MAXCOL; temp.col++)
      if (grid.retrieve(temp))
        cout << '*';
      else
        cout << ' ';
    cout << endl;
  }
  cout << endl;
}

void update()
{
  cell temp = {1};
  newGrid.clear();
  for (temp.row = MINROW; temp.row <= MAXROW; temp.row++)
    for (temp.col = MINCOL; temp.col <= MAXCOL; temp.col++)
      switch (neighborCount(temp.row, temp.col))
      {
        case 2:
          if (grid.retrieve(temp)) newGrid.insert(temp);
          break;
        case 3:
          newGrid.insert(temp);
          break;
      }

  grid = newGrid;
};

int main()
{
  cout << "Welcome to Conway's game of Life\n";
  cout << "This game uses a grid in which\n";
  cout << "each cell can either be occupied by an organism or not.\n";
  cout << "The occupied cells change from generation to generation\n";
  cout << "according to the number of neighboring cells which are alive.\n";

  initialize();
  print();

  while (grid.getSize())
  {
    cout << "Press ENTER to continue, X-ENTER to quit...\n";
    if (cin.get() > 31) break;
    update();
    print();
  }
  return 0;
}
norcalaussie (5)
Anyone?
Last edited on
norcalaussie (5)
bump
SIK (309)
Check your clear method for HashTable.

You are calling data[wrappedI].clear()

I think this should be:

1
2
3
4
5
6
7
8
9
 
template<class DataType>
void HashTable<DataType>::clear(){
    for(int i=0;i<HASHTABLE_CAPACITY;i++){
        data[i].clear();
    }
    current = -1;
    size = 0;
    wrappedI = 0;
}


I think this was causing most of your issues.

Also review your HashTable<DataType>::setWrappedIndex method.

You are checking if the index dI is strictly greater than the [HASHTABLE_CAPACITY] - this then causes no action to be taken when dI is equal to [HASHTABLE_CAPACITY] which causes an indexing error when referencing the internal array of lists. Arrays are zero-based referenced, thus index equal to length of array will be one unit out of bounds.

You could try changing method to:

1
2
3
4
5
6
7
8
9
 
template<class DataType>
void HashTable<DataType>::setWrappedIndex(int dI){
   while (dI < 0)
   {
      dI += HASHTABLE_CAPACITY;
   }

   wrappedI = dI % HASHTABLE_CAPACITY;
}



You should also review your logic for neighborCount when the cell you are counting neighbours for lies on a boundary (ie, MINCOL, MAXCOL, MINROW, MAXROW). You are correct to start scanning for neigbours from (row -1, col - 1), however, when row - 1 or col - 1, (or actually your iterating indexes) falls out of boundary range, then your model isn't catering for logically wrapping your neighbours on your screen dimensions.

It can be appreaciated that your model caters for "an infinite screen" by allowing for negative row and col indexing, but unless you make your view model a pan-viewer there isn't much point in proceeding in such a fashion. (And besides, Game of Life is emulated on life existing within finite space as is natural even if we consider expanding to the rest of the universe :))

With this said, you may want to consider changing your (MINCOL, MAXCOL, MINROW, MAXROW) concept to a ROWCNT & COLCNT concept or will need to consider such concept as ROWCNT = MAXROW-MINROW and likewise for COLCNT to impose row, col wrapping w.r.t. screen dims when counting neighbours.

Maybe try changing it to:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 
const int ROWCNT = MAXROW - MINROW + 1;
const int COLCNT = MAXCOL - MINCOL + 1;


int neighborCount(int row, int col)
{
  cell temp;
  int count = 0;
  for (int r=row-1; r<=row+1; r++)
    for (int c=col-1; c<=col+1; c++)
    {
      temp.row = r;
      temp.col = c;
      while (temp.row < 0)    temp.row += ROWCNT;
      while (temp.col < 0)    temp.col += COLCNT;
      temp.row %= ROWCNT;
      temp.col %= COLCNT;
      if (temp.row != row || temp.col != col)
        if (grid.retrieve(temp))
          ++count;
    }
  return count;
}


Consequently you should also range check values when intializing or force them into screen dimension range.

You may even want to consider having an init_load function that loads live cell points from a file - this will eliminate the need to enter these in by hand each time you run your program.


Topic archived. No new replies allowed.