# Conway's Game Of Life Problem Parallel (OpenMP)

I am currently working in solving Conway's Game Of Life problem for a Parallel and Distributed Computing course.

The problem is a little bit different form the original, in the sense that instead of having a 2D representation of the cells we have a 3D one, each cell is represented by three ints. When considering neighbours, only the x + 1, x - 1, y + 1, y - 1, z + 1 and z - 1 are considered (no diagonals).

The input of the problem is constituted by the size of the cube (size) where the cells are present, followed by a list of positions of live cells.

The number of cells, is in the order of O(size^2), and the space is in the order of O(size^3).

My current implementation uses C++ maps, in which a key is a tuple with x, y and z, and the value is an integer telling in that position the cell is alive or not. My current approach is to just go through every position available in the cube and check the number of neighbours and update that position accordingly, but i believe this is not ideal because the number of live cells is in the order of O(size^2) and not O(size^3).

My question is how would you improve this solution ? Is there a better data structure to use ? Considering that I have to build an OpenMP implementation (shared memory) for very large input cases (size > 10000).

Thank you !

• Welcome to CS.SE! What do you mean by "number of individuals"? (Are you counting the number of non-empty cells?) What do you mean by "the space"? What do you mean by "size"? What data structures have you already considered, and why have you rejected them? It often works better here if you can articulate specific requirements you have for the data structure, rather than asking for open-ended advice. What do you mean by O(size^3) complexity? O(size^3) complexity, for what operation(s)? Why do you think a hashtable will have that complexity? – D.W. Mar 27 '17 at 20:34
• Thank you D.W., I have updated the question, to better answer your questions. Can you please take a look ? – jbernardo Mar 27 '17 at 20:47
• While initially the number of live cells may be quadratic, as the game progressed it may become cubic. Is the goal simulating only a few steps? In that case, usually the answer is to use some sparse representation, or perhaps some data structure from computational geometry like an octree. – Yuval Filmus Mar 27 '17 at 20:53
• The number of simulation rounds is lower than 2000, but what you said is interesting, and I think that is the case. The professor told us that the number of cells compared to the cube will be sparse, I will investigate the octree, never heard of them. Thanks you ! – jbernardo Mar 27 '17 at 20:58