www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Conway's game of life

reply "gedaiu" <szabobogdan yahoo.com> writes:
Hi,

I implemented Conway's game of life in D. What do you think that
I can improve to this program to take advantage of more D
features?

https://github.com/gedaiu/Game-Of-Life-D

Thanks,
Bogdan
Feb 01 2015
next sibling parent "Tobias Pankrath" <tobias pankrath.net> writes:
1. I prefer

alias CellList = Cell[];
over
alias Cell[] CellList;

2. Do you really need to create a complete new CellList for every 
single removal? If so, you'd know the size of the new list in 
advance and can allocate it directly at the correct size.

I get the impression that you think Cell[] is a linked list but 
it's an array slice.
Feb 01 2015
prev sibling next sibling parent reply "Foo" <Foo test.de> writes:
On Sunday, 1 February 2015 at 21:00:07 UTC, gedaiu wrote:

 Hi,

 I implemented Conway's game of life in D. What do you think that
 I can improve to this program to take advantage of more D
 features?

 https://github.com/gedaiu/Game-Of-Life-D

 Thanks,
 Bogdan


For each remove you create a new array. That is lavish. You 
should use a bool inside the struct Cell. If it's false, the cell 
is not displayed and is out of the game.
My suggestion: don't use the D GC, it's crap. Try to circumvent 
the GC wherever possible. Therefore you should use the -vgc 
compiler flag and the  nogc attribute.
Feb 01 2015
parent "gedaiu" <szabobogdan yahoo.com> writes:
It's true that I have to change that function. Thanks for the 
notice!

Why do you think that D's GC is crap?




On Sunday, 1 February 2015 at 21:54:43 UTC, Foo wrote:

 On Sunday, 1 February 2015 at 21:00:07 UTC, gedaiu wrote:

 Hi,

 I implemented Conway's game of life in D. What do you think 
 that
 I can improve to this program to take advantage of more D
 features?

 https://github.com/gedaiu/Game-Of-Life-D

 Thanks,
 Bogdan


 For each remove you create a new array. That is lavish. You 
 should use a bool inside the struct Cell. If it's false, the 
 cell is not displayed and is out of the game.
 My suggestion: don't use the D GC, it's crap. Try to circumvent 
 the GC wherever possible. Therefore you should use the -vgc 
 compiler flag and the  nogc attribute.
Feb 02 2015
prev sibling next sibling parent reply FG <home fgda.pl> writes:
On 2015-02-01 at 22:00, gedaiu wrote:

 I implemented Conway's game of life in D.


I think you are playing a different game here.

     /// Count cell neighbours
     long neighbours(Cell myCell, CellList list) {
         long cnt;
         foreach(cell; list) {
             auto diff1 = abs(myCell.x - cell.x);
             auto diff2 = abs(myCell.y - cell.y);
             if(diff1 == 1 || diff2 == 1) cnt++;   // Why || instead of && ???
         }
         return cnt;
     }
Feb 01 2015
parent reply "gedaiu" <szabobogdan yahoo.com> writes:
I don't think that the line of code is wrong. If use && the 
function will check for neighbours only on diagonals. Having || 
allows the search on the vertical and horizontal axis and 
diagonals.

There are some tests that check the function:

unittest {
	CellList world = [ Cell(0,0), Cell(0,1), Cell(0,2), Cell(1,0), 
Cell(1,2), Cell(2,0), Cell(2,1), Cell(2,2) ];
	assertEqual(Cell(1,1).neighbours(world), world.length);
}

unittest {
	CellList world = [ Cell(0,0), Cell(1,1), Cell(2,2), Cell(3,3) ];
	assertEqual(Cell(1,1).neighbours(world), 2);
}

I don't see a glitch.

Thanks,
Bogdan



On Sunday, 1 February 2015 at 22:51:42 UTC, FG wrote:

 On 2015-02-01 at 22:00, gedaiu wrote:

 I implemented Conway's game of life in D.


 I think you are playing a different game here.

     /// Count cell neighbours
     long neighbours(Cell myCell, CellList list) {
         long cnt;
         foreach(cell; list) {
             auto diff1 = abs(myCell.x - cell.x);
             auto diff2 = abs(myCell.y - cell.y);
             if(diff1 == 1 || diff2 == 1) cnt++;   // Why || 
 instead of && ???
         }
         return cnt;
     }
Feb 02 2015
parent reply FG <home fgda.pl> writes:
Bloody Thunderbird has sent a reply to the OP and not to the NG.

On 2015-02-02 at 11:45, gedaiu wrote:

 I don't think that the line of code is wrong. If use && the function will
check for neighbours only on diagonals. Having || allows the search on the
vertical and horizontal axis and diagonals.


In short: Yes, && alone would check only diagonals, but I forgot to tell you to
also change the ==.

(diff1 == 1 || diff2 == 1) -- bad, accepts whole neighbouring rows and columns
(diff1 == 1 && diff2 == 1) -- bad, accepts only neighbouring diagonals
(diff1 <= 1 && diff2 <= 1) -- correct, I think :)

This unittest should show the difference:

unittest {
     CellList world = [ Cell(0,0), Cell(0,1), Cell(0,2), Cell(0,3) ];
     assertEqual(Cell(1,1).neighbours(world), 3);
}

Cell(0,3) is not a neighbour bit fits the (diff1 == 1 || diff2 == 1) criterion.
Feb 02 2015
next sibling parent FG <home fgda.pl> writes:
On 2015-02-02 at 12:23, FG wrote:

 Cell(0,3) is not a neighbour bit fits the (diff1 == 1 || diff2 == 1) criterion.


s/bit/but/
Feb 02 2015
prev sibling parent "gedaiu" <szabobogdan yahoo.com> writes:
Uf...  you are right!

I've fixed it.

Thanks!


On Monday, 2 February 2015 at 11:23:17 UTC, FG wrote:

 Bloody Thunderbird has sent a reply to the OP and not to the NG.

 On 2015-02-02 at 11:45, gedaiu wrote:

 I don't think that the line of code is wrong. If use && the 
 function will check for neighbours only on diagonals. Having 
 || allows the search on the vertical and horizontal axis and 
 diagonals.


 In short: Yes, && alone would check only diagonals, but I 
 forgot to tell you to also change the ==.

 (diff1 == 1 || diff2 == 1) -- bad, accepts whole neighbouring 
 rows and columns
 (diff1 == 1 && diff2 == 1) -- bad, accepts only neighbouring 
 diagonals
 (diff1 <= 1 && diff2 <= 1) -- correct, I think :)

 This unittest should show the difference:

 unittest {
     CellList world = [ Cell(0,0), Cell(0,1), Cell(0,2), 
 Cell(0,3) ];
     assertEqual(Cell(1,1).neighbours(world), 3);
 }

 Cell(0,3) is not a neighbour bit fits the (diff1 == 1 || diff2 
 == 1) criterion.
Feb 02 2015
prev sibling next sibling parent "data man" <datamanrb gmail.com> writes:
On Sunday, 1 February 2015 at 21:00:07 UTC, gedaiu wrote:

 Hi,

 I implemented Conway's game of life in D. What do you think that
 I can improve to this program to take advantage of more D
 features?

 https://github.com/gedaiu/Game-Of-Life-D

 Thanks,
 Bogdan


If the subject of the game "Life" is interesting to you, look at 
these links:
http://en.wikipedia.org/wiki/Hashlife
http://golly.sourceforge.net
Feb 01 2015
prev sibling parent reply "bearophile" <bearophileHUGS lycos.com> writes:
gedaiu:


 https://github.com/gedaiu/Game-Of-Life-D


A bare-bones implementation:
http://rosettacode.org/wiki/Conway%27s_Game_of_Life#Faster_Version

The quality of the D GC is not important for a simple Life 
implementation, you just need two arrays.

Bye,
bearophile
Feb 02 2015
parent reply "Paul" <paul example.com> writes:
On Monday, 2 February 2015 at 16:58:43 UTC, bearophile wrote:

 The quality of the D GC is not important for a simple Life 
 implementation, you just need two arrays.


Here's my 30 minute sandwich-break version, sorry it's not very 
arractive 'D'...

import std.stdio;
import std.random;


void main(){

	enum WORLDSIZE = 20;
	enum INITIALPOP = 70;	//experimental
	enum DEAD = 0;
	enum ALIVE = 1;

	int world[WORLDSIZE][WORLDSIZE];
	int buffer[WORLDSIZE][WORLDSIZE];
	
	//sprinkle life
	foreach(i; 0..INITIALPOP){
		//find an empty cell
		int rX, rY;
		do{
			rX = uniform(0, WORLDSIZE);
			rY = uniform(0, WORLDSIZE);
		} while(world[rX][rY] == ALIVE);
		world[rX][rY] = ALIVE;
	}
			
	//loop forever
	while (true){
	
		//work on the buffer
		buffer = world;

		foreach(x; 0..WORLDSIZE){
			foreach(y; 0..WORLDSIZE){

				int neighbourCount;
									
				//get index to left, right, above and below current cell, 
wrapping if necessary
				int left = (x == 0) ? WORLDSIZE-1 : x-1;
				int right = (x == (WORLDSIZE-1) ) ? 0 : x+1;
				int top = (y == 0) ? WORLDSIZE-1 : y-1;
				int bottom = (y == (WORLDSIZE-1) ) ? 0 : y+1;
				
				//add up surrounding cells
				neighbourCount += world[left][y];
				neighbourCount += world[left][top];
				neighbourCount += world[left][bottom];
				neighbourCount += world[x][top];
				neighbourCount += world[x][bottom];
				neighbourCount += world[right][top];
				neighbourCount += world[right][y];
				neighbourCount += world[right][bottom];
					

				//if this cell is alive
				if( world[x][y] == ALIVE){
					//decide what to do
					switch(neighbourCount){
						case 2:
						buffer[x][y] = ALIVE;
						break;
						case 3:
						buffer[x][y] = ALIVE;
						break;
						default:
						buffer[x][y] = DEAD;
					}
				}
				else{
					//just like today's news, newborn has three parents!			
					if(neighbourCount == 3) buffer[x][y] = ALIVE;
				}
			}		
		}
		
		//update world with contents of buffer
		world = buffer;
		
		//show current state of world with fancy graphics :P
		foreach(x; 0..WORLDSIZE){
			foreach(y; 0..WORLDSIZE){
				write( world[x][y] == ALIVE ? "X" : "." );
			}
			writeln();
		}

		readln();
		
	}//end loop
}
Feb 03 2015
next sibling parent "Paul" <paul example.com> writes:
On Tuesday, 3 February 2015 at 13:35:37 UTC, Paul wrote:

 On Monday, 2 February 2015 at 16:58:43 UTC, bearophile wrote:

 The quality of the D GC is not important for a simple Life 
 implementation, you just need two arrays.


 Here's my 30 minute sandwich-break version, sorry it's not very 
 arractive 'D'...


Meant to say - hold down return to avoid tedium and Ctrl+C to 
quit (of course!).
Feb 03 2015
prev sibling parent reply "bearophile" <bearophileHUGS lycos.com> writes:
Paul:


 	enum WORLDSIZE = 20;
 	enum INITIALPOP = 70;	//experimental
 	enum DEAD = 0;
 	enum ALIVE = 1;


D enums don't need to be ALL UPPERCASE :-)



 	int world[WORLDSIZE][WORLDSIZE];


Don't forget to compile with warnings active (it's a design error 
of the D compiler to have them disabled by default).



 	foreach(i; 0..INITIALPOP){


It's less bug-prone to make that index immutable:

         foreach(immutable i; 0 .. initialPop) {

Bye,
bearophile
Feb 03 2015
parent reply "Paul" <paul example.com> writes:
On Tuesday, 3 February 2015 at 14:01:51 UTC, bearophile wrote:

 Paul:


 	enum WORLDSIZE = 20;
 	enum INITIALPOP = 70;	//experimental
 	enum DEAD = 0;
 	enum ALIVE = 1;


 D enums don't need to be ALL UPPERCASE :-)



 	int world[WORLDSIZE][WORLDSIZE];


 Don't forget to compile with warnings active (it's a design 
 error of the D compiler to have them disabled by default).



 	foreach(i; 0..INITIALPOP){


 It's less bug-prone to make that index immutable:

         foreach(immutable i; 0 .. initialPop) {

 Bye,
 bearophile


Thanks for the comments. The all-caps enums is just habit. I 
don't get any warnings using the dmd -w switch, I take it you 
mean use int[size][size] var instead?

Regarding the immutable loop variable, I've conditioned myself 
never to interfere with loop control values - it gives me the 
same bad feeling as goto/continue (and to a lesser extent 
'break').
Feb 03 2015
parent "bearophile" <bearophileHUGS lycos.com> writes:
Paul:


 Regarding the immutable loop variable, I've conditioned myself 
 never to interfere with loop control values


But adding "immutable" you don't risk modifying the variable by 
mistake.

It's another design mistake of D. Variables (like foreach loop 
indexes) must be immutable by default because otherwise 
programmers often don't bother making them immutable. It's a lost 
war.

Bye,
bearophile
Feb 03 2015