Python :: game of life
-
Hi, i know there's a topic about the game of life called coding challenge, but i actually started this little project before that topic was there, and just want some constructive tips/critc on my little project.
In want to learn python a bit better; So i thought i should write the game of life. I've never actually wrote it before so i thaught it would be a good exercise. <br>
I also never looked at examples besides some stuff in the wikipedia article about GOF, so i might be doing some pretty stupid things, but i just wanted to see if i could implement it when only knowing the basic rules.So far it's working pretty well, there only seems to be a bug with my corners. (that should wrap around to the other side, but for some reason i haven't found yet it doesn't do that correctly)
Starting the little project i took two basic rules;
- i don't want to iterate x,y a lot, because i rather not care where points actually are.
- everything in python is pass by reference, so let's make some use of that.
the current result of that is the following code:
#!/usr/bin/env python
import os
import random
import time
import sys;
class GameOfLife:
def __init__(self):
self.width=50;
self.height=50; # a place to keep all the points.
self.points = {};
self.short_list = []; # used to keep track of "set" points
self.construct_board();
def construct_board(self):
# create all the needed points on the board
x=1;
id=0;
while x<=self.width:
y=1;
empty_dict = {};
self.points.update({x:{}})
row = self.points[x];
while y<=self.height:
row.update({y:Point(id,x,y)})
id = id + 1;
y = y + 1;
x = x + 1;
# for fast lookup tell every point whom his neigbor is.
# (everything between -1,-1 and +1,+1
x=1;
while x<=self.width:
y=1;
while y<=self.height:
point = self.points[x][y];
if (x-1 <=0): x_minus = self.width;
else: x_minus = x-1;
if x+1 >=self.width: x_plus = 1
else: x_plus = x+1
if (y-1 <=0): y_minus = self.height;
else: y_minus = y-1;
if y+1 >=self.height: y_plus = 1
else: y_plus = y+1
try:
point.add_neighbor(self.points[x_minus][y])
point.add_neighbor(self.points[x_minus][y_minus])
point.add_neighbor(self.points[x_minus][y_plus])
point.add_neighbor(self.points[x][y_minus])
point.add_neighbor(self.points[x][y_plus])
point.add_neighbor(self.points[x_plus][y_minus])
point.add_neighbor(self.points[x_plus][y])
point.add_neighbor(self.points[x_plus][y_plus])
except:
print point.x,point.y
print "x_plus",x_plus
print "x_minus",x_minus
print "y_plus",y_plus
print "y_minus",y_minus
sys.exit();
set_alive=0;
#insert a glider.
if (
(y==11 and x==11)
or
(y==11 and x==12)
or
(y==11 and x==13)
or
(y==12 and x==11)
or
(y==13 and x==12)
): set_alive=1;
#fill the wall
if (
x==1
or
y==1
): set_alive=1
# put some random stuff in
if (random.randint(1,10)==1): set_alive=1;
if (set_alive==1):
status = 1
self.short_list.append(point);
else:
status =0
point.set_status(status);
y = y + 1;
x = x + 1;
def print_board(self,print_type):
y=1;
row = "";
while y<=self.height:
x=1;
row += "\n";
while x<=self.width:
if print_type==1:
if (self.points[x][y].status == 0):
row += " ";
else:
row += "X";
else:
if (self.points[x][y].score>0):
row += str(self.points[x][y].score);
else:
row += " "
x =x + 1;
y = y + 1;
print row;
def step(self):
begin_time = time.time();
gray_list = [];
list = {}; #list is used to keep track of what points we already added (huge lookup time saver)
for point in self.short_list:
if point.id not in list:
gray_list.append(point);
list.update({point.id:point.id});
begin_time_small = time.time();
for neighbor in point.neighbors:
id = neighbor.id;
neighbor.add_score();
if id not in list:
gray_list.append(neighbor);
list.update({id:id});
self.grey_list_time = time.time() - begin_time;
self.short_list = [];
# 1. Any live cell with fewer than two live neighbours dies, as if by loneliness.
# 2. Any live cell with more than three live neighbours dies, as if by overcrowding.
# 3. Any live cell with two or three live neighbours lives, unchanged, to the next generation.
# 4. Any dead cell with exactly three live neighbours comes to life.
## uncomment for point distribution debug ##
#self.print_board(0);
# @TODO this could be so much beter
for point in gray_list:
if (point.score<=1): #die of loneliness
point.status = 0;
point.score = 0;
elif (point.score>=4): #die of over population
point.status = 0;
point.score = 0;
elif (point.status==1 and point.score>=2 and point.score<=3): # has two or 3 neighbors and survives
point.status = 1;
point.score = 0;
self.short_list.append(point);
elif (point.status==0 and point.score==3):
point.status = 1;
point.score = 0;
self.short_list.append(point);
else:
point.status = 0;
point.score = 0;
class Point:
def __init__(self,id,x,y):
self.id=id;
self.x=x;
self.y=y;
self.status=0;
self.score=0;
self.neighbors = [];
def set_status(self,status):
self.status = status;
def add_neighbor(self,point):
self.neighbors.append(point);
def add_score(self):
self.score += 1;
GOL = GameOfLife();
#print "Going to first step";
GOL.print_board(1);
time.sleep(0.5);
resp = raw_input("press enter")
i=1;
while (i<=500):
begin = time.time();
GOL.step();
print time.time() - begin;
#print "step ",i
GOL.print_board(1);
time.sleep(0.2);
i += 1;
# resp = raw_input("press enter")i'm really looking for comment on how i could have implemented it beter, especially on the part of python specific implementations
Also after i've solved why the borders don't work correctly, i'm probably going to try and make it borderless.
I'm all ready thinking of a idea by only creating the points that are 'alive', and not care much about where they are, but just give them the correct x and y coordinate, even if it's -20 or what not.
The displaying code would get a bit more difficult because of that, but that's not where the speed bottleneck is anyway.edit:
mmm, aparently some white space lines got eaten in the code; Just so you know i don't actually put methods back to back :)
-
On every real implementation of GOL the sides do not wrap around (AFAIK)
i prefer it that way, make a bigger game board if you want more space.
The fact that it doesn't wrap around allows you to make "guns" and other such constructs on the playing field, whereas a wraparound idea would allow a gun's fire to affect itself... and that's against the idea.
-
oh, i don't know python, but good job if it works as intended. :-)
-
@GeneWitch said:
On every real implementation of GOL the sides do not wrap around (AFAIK)
On any real implementation of GOL there are no sides.
-
The following part seems too elaborate:
if (point.score<=1): #die of loneliness
point.status = 0;
point.score = 0;
elif (point.score>=4): #die of over population
point.status = 0;
point.score = 0;
elif (point.status==1 and point.score>=2 and point.score<=3): # has two or 3 neighbors and survives
point.status = 1;
point.score = 0;
self.short_list.append(point);
elif (point.status==0 and point.score==3):
point.status = 1;
point.score = 0;
self.short_list.append(point);
else:
point.status = 0;
point.score = 0;
could be shorter....
if (point.score==3 or point.score==2 and point.status==1): #alive
point.status = 1;
else:
point.status = 0;
point.score = 0;You don't have to know why a cell dies, dead is dead.
-
-
@dhromed said:
@ammoQ said:
You don't have to know why a cell dies, dead is dead.
How existential of you.
There's one million ways to die, but only one way to be dead. ;-)
-
I would redo this bit:
try:
point.add_neighbor(self.points[x_minus][y])
point.add_neighbor(self.points[x_minus][y_minus])
point.add_neighbor(self.points[x_minus][y_plus])
point.add_neighbor(self.points[x][y_minus])
point.add_neighbor(self.points[x][y_plus])
point.add_neighbor(self.points[x_plus][y_minus])
point.add_neighbor(self.points[x_plus][y])
point.add_neighbor(self.points[x_plus][y_plus])
except:
print point.x,point.y
print "x_plus",x_plus
print "x_minus",x_minus
print "y_plus",y_plus
print "y_minus",y_minus
sys.exit();Firstly, I wouldn't do a try, except. That would hide any errors in the try block. I would also rewrite the add neighbours bit as a list comprehension
point.neighbours = [self.points[a][b] for a in xrange(x_minus,x_plus +1) for b in xrange(y_minus,y_plus+1) if (a != x) or (b != y)
You can probabably make this simpler by just setting the offsets from x and y, so instead of a, you have x + l, with l = [-1,0,1], although it might be tricky to work with the edges. If you want to wrap-around the edges, you might be able to simplify by using the modulus operator %. x % 3, for example, should end up in the range 0,1,2, although you'll have to check that for negative values of x.
This section:
#insert a glider.
if (
(y==11 and x==11)
or
(y==11 and x==12)
or
(y==11 and x==13)
or
(y==12 and x==11)
or
(y==13 and x==12)
): set_alive=1;Would work better, if you just use the co-ordinates to set the points manually, rather than looping through all the points to find these 5 points. Similarly for the wall. I would also make the neighbours setting loop into a seperate loop from the wall, and the randomizing bit, so they'll be a few small loops, rather than one bit one, and thus they'll probably be easier to read.
A general comment, that applies to most of your loops. A for loop is generally easier to read than a while loop, for just looping over a range of numbers. Use "for a in xrange(1,10)" to loop a over 1..9, for example.
-
@bouk said:
@GeneWitch said:
On every real implementation of GOL the sides do not wrap around (AFAIK)
On any real implementation of GOL there are no sides.
Yah that's what i was saying... if a glider goes "off the board" it just doesn't exist anymore. it ceases to interact with the environment that you are watching. Right?
I could be wrong...
-
You misunderstand. Conway's Game of Life is defined against an unbounded playfield. The board has no "off".
-
@Angstrom said:
You misunderstand. Conway's Game of Life is defined against an unbounded playfield. The board has no "off".
No i get it, but we have a finite amount of ram and storage to do this in, so if your viewport is say 80 dots by 80 dots, when something goes outside that 80 dots you just ignore it (from a programming perspective), you cease calculating the stuff outside the arbitrary borders you've set.
I'm currently working on getting VS installed on the new rig so i can try implementing the "infinite board size"
with 2 gigs of ram you should be able to have a board roughly 46340 by 46340... in ram. That should suffice (with a huge virtual memory pool, you could theoretically go on until you just stopped adding storage space)
I'm trying to figure out how to double that, i have to re-read the rules and see if i can't at least double if not triple that boardsize.
-
@GeneWitch said:
with 2 gigs of ram you should be able to have a board roughly 46340 by 46340... in ram. That should suffice (with a huge virtual memory pool, you could theoretically go on until you just stopped adding storage space)
I'm trying to figure out how to double that, i have to re-read the rules and see if i can't at least double if not triple that boardsize.
That's just for a most trivial implementation using a 2D byte array. Doing that you waste most of the RAM on storing empty cells. If you grow the board dynamically, you'll still run out of space after evolving something like a glider cannon for 46000 steps (since you won't have any ram left to enlarge the field)
If you store the coordinates of each point instead, using 16 bits for the X coordinate and 16 bits for Y you can already represent a 65k size board with up to 536848900 points. That's much more ram-efficient, but of course horrible I/O bound (worst case: linear search through the 2GB for each point to check for neighbours)
You'll have to find a copromise somwhere inbetween the two options, i.e. keeping the points in a (B)Tree so that you can check for neighbours efficiently without wasting too much time searching the data. I'd look into using a SQL database (possible SQLite) to store points and see how that scales :-)
-
@Nandurius said:
@GeneWitch said:
with 2 gigs of ram you should be able to have a board roughly 46340 by 46340... in ram. That should suffice (with a huge virtual memory pool, you could theoretically go on until you just stopped adding storage space)
I'm trying to figure out how to double that, i have to re-read the rules and see if i can't at least double if not triple that boardsize.
That's just for a most trivial implementation using a 2D byte array. Doing that you waste most of the RAM on storing empty cells. If you grow the board dynamically, you'll still run out of space after evolving something like a glider cannon for 46000 steps (since you won't have any ram left to enlarge the field)
If you store the coordinates of each point instead, using 16 bits for the X coordinate and 16 bits for Y you can already represent a 65k size board with up to 536848900 points. That's much more ram-efficient, but of course horrible I/O bound (worst case: linear search through the 2GB for each point to check for neighbours)
You'll have to find a copromise somwhere inbetween the two options, i.e. keeping the points in a (B)Tree so that you can check for neighbours efficiently without wasting too much time searching the data. I'd look into using a SQL database (possible SQLite) to store points and see how that scales :-)
Lewl@ DB solution.
I spoke too soon. i am very tired. I am going to be doing sort of what you said, except i don't know a damn thing about the Tree ADT (i... i suck! ).
basically each dot is a byte. Literally
byte Dot;
Then you have a 2D vector of bytes (i'm hoping that .NET supports 'vector' or something similar to a dynamic array) that grows as it gets filled with dots.
I haven't worked it all out, to me this isn't trivial because i let years go by between writing software.
[0] [1] [2]
Dot Xcoord Ycoord
The way i have the Dot structure in my head you can figure all neighbors around it with simple math, and you can probably even do away with the 2d vector. I'm trying to think of another way to implement the board that doesn't require any arrays... cause i think that would be neat. I'll even use a class, for good measure (i usually don't use them in VB.NET)
-
Don't usually use classes? That doesn't sound very good :-)
Also, databases are very good at storing large amounts of data and acessing it quickly (with indexes.) It's what I'd do (because I'm lazy.)
Also, the Golly game of life client is quite impressive: http://golly.sourceforge.net/ From what I've seen so far, it's able to display a virtually infinite universe very quickly.
-
@stratos said:
i'm really looking for comment on how i could have implemented it beter, especially on the part of python specific implementations
This is a difficult question to answer, because your program is quite long. Instead of writing a number of paragraphs on this, I've written an alternative implementation in Python which makes more use of classes, generators and comprehensions than yours does. It has more or less the same functionality, so far as I can tell:
neighbour_deltas = [(1, 0), (-1, 0), (1, 1), (-1, 1), (0, 1), (0, -1), (-1, -1), (1, -1)] class Board: cell = 'X' blank = ' ' def __init__(self, (width, height)): self.content = [[self.blank for x in xrange(width)] for y in xrange(height)] self.width, self.height = width, height def in_bounds(self, (x, y)): return x >= 0 and x < self.width and y >= 0 and y < self.height def get_neighbours(self, (x, y)): neighbours = [(x + dx, y + dy) for dx, dy in neighbour_deltas] return filter(self.in_bounds, neighbours) def is_cell(self, (x, y)): return self.content[y][x] == self.cell def add(self, (x, y)): self.content[y][x] = self.cell def add_many(self, *seq): for pos in seq: self.add(pos) def add_predicate(self, predicate): for pos in self.coords(): if predicate(pos): self.add(pos) def remove(self, (x, y)): self.content[y][x] = self.blank def is_alive(self, pos): n = len(filter(self.is_cell, self.get_neighbours(pos))) return n == 3 or (self.is_cell(pos) and n >= 2 and n <= 3) def coords(self): for x in xrange(self.width): for y in xrange(self.height): yield x, y def take_turn(self): births, deaths = [], [] for pos in self.coords(): if self.is_alive(pos): if not self.is_cell(pos): births.append(pos) elif self.is_cell(pos): deaths.append(pos) for cell in births: self.add(cell) for cell in deaths: self.remove(cell) def __repr__(self): return "\n".join(" ".join(cell for cell in row) for row in self.content) import random, time def construct_board(): board = Board((50, 50)) # insert a glider board.add_many((11, 11), (11, 12), (11, 13), (12, 11), (13, 12)) # fill the wall board.add_predicate(lambda (x, y): x == 1 or y == 1) # put some random stuff in board.add_predicate(lambda _: random.randint(1, 10) == 1) return board if __name__ == '__main__': board = construct_board() print board raw_input("press enter") for i in xrange(1, 501): begin = time.time() board.take_turn() print time.time() - begin print board time.sleep(0.2)The above code uses nested lists to maintain the cells, but it's not too hard to change this to a hash. Just replace the __init__, add, remove and is_cell functions:
def __init__(self, (width, height)):
self.content = {}
self.width, self.height = width, height
def is_cell(self, position):
return self.content[position] == self.cell
def add(self, position):
self.content[position] = self.cell
def remove(self, position):
self.content[position] = self.blankI thought about designing it to take an storage object of some kind, so you could use a list, dict, or whatever structure you wanted to store the data. However time was short, and it sounded a bit too much like feature creep.
-
very cool, thanks :)
i'll be sure to play around with your code to get a feel for the constructions you use.
