Can multithreading affect Conway's Game of Life clone?

Question

Hi folks,

I've been implementing this little game idea, which is (somehow?) similar to Conway's Game of Life:

0) You have a matrix of colored dots (RGB values) 1) If the adjacent cell has a lower X value than your Y, put Y = 0 on that cell (Where X and Y are Red || Green || Blue) 2) Red beats Green beats Blue beats Red

What I'm doing now it's just going cell by cell, checking if the above rules are met. However, the behavior it's not quite what I intended since sometimes cells on the first rows have advantage over those at the ending rows.

Can multithreading prevent this (say, launching two threads, one initiating in the first cell and the other on the last one)? Please pardon my ignorance on concurrency, but I felt this was a nice way to begin working with it.

Answer 1

You'll be better off adapting your algorithm to prevent this.

Relying on multithreading to change behavior is not a good thing. This is, in essence, trying to introduce a race condition into your code. Normally, when adding multi-threading to an algorithm, the first priority is to prevent any changes in behavior.

By trying to use a race condition to change behavior, you're making this very non-deterministic, but not in a good way. You'd be much better off trying to come up with a different solution to this (potentially using a pseudo-random number generator, etc), and then introducing multi-threading to make it faster (hopefully without affecting the results).

Answer 2

My guess is that you are updating the matrix inplace, whereas you should copy keep a track of the old state of the matrix, updating a new one, then replacing the original one by the updated. This way, you won't update some cells, then on the next line test their values. Thus, it would be an algorithm problem, not related with programmation (and therefore multithreading cannot help).

Answer 3

No. Your problem is an inherent flaw. The trouble that you have is that you're using intermediate results, i.e., the change in one cell affects the next cell immediately, in this update. It shouldn't. You should create a new matrix, store the changed values in there, and then swap them so that the new values are loaded. Repeat.

Answer 4

It depends on what part of the processing you choose to multithread. The prototypical multithreading example is the matrix multiplier. You can basically break it up into quadrants and calculate one quadrant in each thread, with no sharing of information except the original matrix. Note that the Game of Life is a sparse matrix, though, and may or may not benefit from multithreading.

However, if you do decide to do so, keep in mind that everything should calculate what it needs to for the "next turn" and place it in a new matrix, when swap-in the matrix (preferrably not copy, just change a pointer someplace) at the end of the turn, so that one thread isn't changing the values that the other ones need to do their calculations. So the thread's can't be allowed to "get a turn ahead" of each other. This might mean that it turns out to be inefficient to do with multiple threads - your mileage may vary.