Game of Life speed help

[VgSlag]

Hi guys,

I wrote "Game of Life" (not the board game) in Lua and it was running very slow. I used to get the pixel color to see if it was alive or not but then changed the alive state into a 2d array.

My current code is:

Code: Select all

while not Controls.read():start() do

	-- Create the colors
	color_green = Color.new(0, 255, 0)
	color_black = Color.new(0, 0, 0)

	-- Create the pixelData array
	o_pixelData = {}

	-- Create the 2d array
	for i_counter_0 = 1, 480 do
		o_pixelData[i_counter_0]  = {}
		for i_counter_1 = 1, 272 do
			o_pixelData[i_counter_0][i_counter_1] = color_black
		end
	end

	-- Background
	g_backGround = Image.createEmpty(480, 272)
	
	-- Fill it black
	g_backGround:fillRect(0, 0, 480, 272, color_black) 
	
	o_liveCells = {}
	g_backGround:pixel(200, 200, color_green)
	o_liveCells["o_cell_" .. 200 .. "_" .. 200] = {["i_x"] = 200, ["i_y"] = 200}
	o_pixelData[200][200] = color_green
	
	g_backGround:pixel(201, 200, color_green)
	o_liveCells["o_cell_" .. 201 .. "_" .. 200] = {["i_x"] = 201, ["i_y"] = 200}
	o_pixelData[201][200] = color_green
	
	g_backGround:pixel(202, 200, color_green)
	o_liveCells["o_cell_" .. 202 .. "_" .. 200] = {["i_x"] = 202, ["i_y"] = 200}
	o_pixelData[202][200] = color_green

	g_backGround:pixel(201, 199, color_green)
	o_liveCells["o_cell_" .. 201 .. "_" .. 199] = {["i_x"] = 201, ["i_y"] = 199}
	o_pixelData[201][199] = color_green
	
	g_backGround:pixel(201, 201, color_green)
	o_liveCells["o_cell_" .. 201 .. "_" .. 201] = {["i_x"] = 201, ["i_y"] = 201}
	o_pixelData[201][201] = color_green
	
	g_backGround:pixel(203, 201, color_green)
	o_liveCells["o_cell_" .. 203 .. "_" .. 201] = {["i_x"] = 203, ["i_y"] = 201}
	o_pixelData[203][201] = color_green
	
	-- Function to process life
	function f_process()  
	
		-- Clear storage
		o_toChange = {}
		o_deadCells = {}
	
		-- Process each live cell
		for i_counter_0 in o_liveCells do
	
			-- Init the neighbours we have
			i_neighbours = 0
	
			-- Find out how many neighbours
			-- Up left
			i_xToUse = o_liveCells[i_counter_0]["i_x"] - 1
			i_yToUse = o_liveCells[i_counter_0]["i_y"] - 1
			if o_pixelData[i_xToUse][i_yToUse] == color_green then
					
				-- It's taken, add to the neightbours
				i_neighbours = i_neighbours + 1
			else
	
				-- No taken, add to dead cells
				o_deadCells["o_cell_" .. i_xToUse .. "_" .. i_yToUse] = {["i_x"] = i_xToUse, ["i_y"] = i_yToUse}
			end
	
			-- Up
			i_xToUse = o_liveCells[i_counter_0]["i_x"]
			i_yToUse = o_liveCells[i_counter_0]["i_y"] - 1
			if o_pixelData[i_xToUse][i_yToUse] == color_green then
					
				-- It's taken, add to the neightbours
				i_neighbours = i_neighbours + 1
			else
	
				-- No taken, add to dead cells
				o_deadCells["o_cell_" .. i_xToUse .. "_" .. i_yToUse] = {["i_x"] = i_xToUse, ["i_y"] = i_yToUse}
			end
	
			-- Up right
			i_xToUse = o_liveCells[i_counter_0]["i_x"] + 1
			i_yToUse = o_liveCells[i_counter_0]["i_y"] - 1
			if o_pixelData[i_xToUse][i_yToUse] == color_green then
					
				-- It's taken, add to the neightbours
				i_neighbours = i_neighbours + 1
			else
	
				-- No taken, add to dead cells
				o_deadCells["o_cell_" .. i_xToUse .. "_" .. i_yToUse] = {["i_x"] = i_xToUse, ["i_y"] = i_yToUse}
			end
	
			-- Left
			i_xToUse = o_liveCells[i_counter_0]["i_x"] - 1
			i_yToUse = o_liveCells[i_counter_0]["i_y"]
			if o_pixelData[i_xToUse][i_yToUse] == color_green then
					
				-- It's taken, add to the neightbours
				i_neighbours = i_neighbours + 1
			else
	
				-- No taken, add to dead cells
				o_deadCells["o_cell_" .. i_xToUse .. "_" .. i_yToUse] = {["i_x"] = i_xToUse, ["i_y"] = i_yToUse}
			end
		
			-- Right
			i_xToUse = o_liveCells[i_counter_0]["i_x"] + 1
			i_yToUse = o_liveCells[i_counter_0]["i_y"]
			if o_pixelData[i_xToUse][i_yToUse] == color_green then
					
				-- It's taken, add to the neightbours
				i_neighbours = i_neighbours + 1
			else
	
				-- No taken, add to dead cells
				o_deadCells["o_cell_" .. i_xToUse .. "_" .. i_yToUse] = {["i_x"] = i_xToUse, ["i_y"] = i_yToUse}
			end
	
			-- Down left
			i_xToUse = o_liveCells[i_counter_0]["i_x"] - 1
			i_yToUse = o_liveCells[i_counter_0]["i_y"] + 1
			if o_pixelData[i_xToUse][i_yToUse] == color_green then
					
				-- It's taken, add to the neightbours
				i_neighbours = i_neighbours + 1
			else
	
				-- No taken, add to dead cells
				o_deadCells["o_cell_" .. i_xToUse .. "_" .. i_yToUse] = {["i_x"] = i_xToUse, ["i_y"] = i_yToUse}
			end
	
			-- Down
			i_xToUse = o_liveCells[i_counter_0]["i_x"]
			i_yToUse = o_liveCells[i_counter_0]["i_y"] + 1
			if o_pixelData[i_xToUse][i_yToUse] == color_green then
					
				-- It's taken, add to the neightbours
				i_neighbours = i_neighbours + 1
			else
		
				-- No taken, add to dead cells
				o_deadCells["o_cell_" .. i_xToUse .. "_" .. i_yToUse] = {["i_x"] = i_xToUse, ["i_y"] = i_yToUse}
			end
	
			-- Down right
			i_xToUse = o_liveCells[i_counter_0]["i_x"] + 1
			i_yToUse = o_liveCells[i_counter_0]["i_y"] + 1
			if o_pixelData[i_xToUse][i_yToUse] == color_green then
					
				-- It's taken, add to the neightbours
				i_neighbours = i_neighbours + 1
			else
	
				-- No taken, add to dead cells
				o_deadCells["o_cell_" .. i_xToUse .. "_" .. i_yToUse] = {["i_x"] = i_xToUse, ["i_y"] = i_yToUse}
			end
	
			-- Does the cell die?
			if i_neighbours ~= 2 and i_neighbours ~= 3 then
				o_toChange["o_cell_" .. o_liveCells[i_counter_0]["i_x"] .. "_" .. o_liveCells[i_counter_0]["i_y"]] = {["i_x"] = o_liveCells[i_counter_0]["i_x"], ["i_y"] = o_liveCells[i_counter_0]["i_y"], ["i_color"] = color_black}
			end
		end
		
		-- Process each dead cell
		for i_counter_0 in o_deadCells do
	
			-- Init the neighbours we have
			i_neighbours = 0
	
			-- Find out how many neighbours
			-- Up left
			i_xToUse = o_deadCells[i_counter_0]["i_x"] - 1
			i_yToUse = o_deadCells[i_counter_0]["i_y"] - 1
			if o_pixelData[i_xToUse][i_yToUse] == color_green then
					
				-- It's taken, add to the neightbours
				i_neighbours = i_neighbours + 1
			end
	
			-- Up
			i_xToUse = o_deadCells[i_counter_0]["i_x"]
			i_yToUse = o_deadCells[i_counter_0]["i_y"] - 1
			if o_pixelData[i_xToUse][i_yToUse] == color_green then
					
				-- It's taken, add to the neightbours
				i_neighbours = i_neighbours + 1
			end
	
			-- Up right
			i_xToUse = o_deadCells[i_counter_0]["i_x"] + 1
			i_yToUse = o_deadCells[i_counter_0]["i_y"] - 1
			if o_pixelData[i_xToUse][i_yToUse] == color_green then
					
				-- It's taken, add to the neightbours
				i_neighbours = i_neighbours + 1
			end
	
			-- Left
			i_xToUse = o_deadCells[i_counter_0]["i_x"] - 1
			i_yToUse = o_deadCells[i_counter_0]["i_y"]
			if o_pixelData[i_xToUse][i_yToUse] == color_green then
					
				-- It's taken, add to the neightbours
				i_neighbours = i_neighbours + 1
			end
	
			-- Right
			i_xToUse = o_deadCells[i_counter_0]["i_x"] + 1
			i_yToUse = o_deadCells[i_counter_0]["i_y"]
			if o_pixelData[i_xToUse][i_yToUse] == color_green then
					
				-- It's taken, add to the neightbours
				i_neighbours = i_neighbours + 1
			end
	
			-- Down left
			i_xToUse = o_deadCells[i_counter_0]["i_x"] - 1
			i_yToUse = o_deadCells[i_counter_0]["i_y"] + 1
			if o_pixelData[i_xToUse][i_yToUse] == color_green then
					
				-- It's taken, add to the neightbours
				i_neighbours = i_neighbours + 1
			end
	
			-- Down
			i_xToUse = o_deadCells[i_counter_0]["i_x"]
			i_yToUse = o_deadCells[i_counter_0]["i_y"] + 1
			if o_pixelData[i_xToUse][i_yToUse] == color_green then
					
				-- It's taken, add to the neightbours
				i_neighbours = i_neighbours + 1
			end
	
			-- Down right
			i_xToUse = o_deadCells[i_counter_0]["i_x"] + 1
			i_yToUse = o_deadCells[i_counter_0]["i_y"] + 1
			if o_pixelData[i_xToUse][i_yToUse] == color_green then
					
				-- It's taken, add to the neightbours
				i_neighbours = i_neighbours + 1
			end
	
			-- Does the cell come alive?
			if i_neighbours == 3 then
				o_toChange["o_cell_" .. o_deadCells[i_counter_0]["i_x"] .. "_" .. o_deadCells[i_counter_0]["i_y"]] = {["i_x"] = o_deadCells[i_counter_0]["i_x"], ["i_y"] = o_deadCells[i_counter_0]["i_y"], ["i_color"] = color_green}
			end
		end
	
		-- Change all the cells that need it
		for i_counter_0 in o_toChange do
		
			-- Change the color
			g_backGround:pixel(o_toChange[i_counter_0]["i_x"], o_toChange[i_counter_0]["i_y"], o_toChange[i_counter_0]["i_color"])
			o_pixelData[o_toChange[i_counter_0]["i_x"]][o_toChange[i_counter_0]["i_y"]] = o_toChange[i_counter_0]["i_color"]

			-- Do we need to add it or remove it from live cells?
			if o_toChange[i_counter_0]["i_color"] == color_green then
	
				-- Add it
				o_liveCells["o_cell_" .. o_toChange[i_counter_0]["i_x"] .. "_" .. o_toChange[i_counter_0]["i_y"]] = {["i_x"] = o_toChange[i_counter_0]["i_x"], ["i_y"] = o_toChange[i_counter_0]["i_y"]}
			else
	
				-- Remove it
				o_liveCells["o_cell_" .. o_toChange[i_counter_0]["i_x"] .. "_" .. o_toChange[i_counter_0]["i_y"]] = nil
			end
	
		end
	end
	
	-- Game loop
	while true do

		-- Draw the background
		screen:blit(0, 0, g_backGround)
	
		-- Process the life function
		f_process() 
	
		-- Flip the screen
		screen.flip()
	end
end

This still gets slow fast. Can Lua just not loop that quickly? Is string concatination really slow?

Can anyone see any obvious slow errors?

Thanks,

G

[Zenurb]

Dude, there are definately much more efficient ways to emulate cellular automata. Did you port this from a Java app or write it yourself?

[VgSlag]

I just knocked it together. Any tips on faster ways?

[JorDy]

set out your code better!! dont use huge messy variables like that
i mean theres no need for g_backGround it could just be backgoround, the i counter variable sould just be a local i. it makes your code hard reading

[romero126]

Remember kids simpler is better, any way you can simplify that to a few lines of code?

Less is more..

[VgSlag]

Jordy, surely my code is set out fine? Your statement seems a little odd.

I would have thought that prefixing my variables with an indication of thier type would make it easier to understand, not harder.

It lets people who read the code see what values I'll be pushing into the variables.

But, that aside, could anyone give a better example of "cellular automata" please?

Thanks,

G

[JorDy]

your variables are just messy looking as for the code there are better more efficient ways with less lines

[VgSlag]

Yes Jordy, we've established both that you don't like my code and also that there are better ways with less lines.

I would hazzard a guess that "more efficent code" would be more efficent too, but without some examples or ideas it's not going to get any better.

For my part I've been reading up on "cellular automata" (I wasn't initially sure as to what to google) but most of the example doesn't offer methods or ideas, simply "look at this cool stuff" moments.

Anyoe got any ideas or ways I can speed this up?

G

[Zenurb]

Well, Conway's game of life is a cellular automata based engine. The rules are simple and as follows:

For a space that is 'populated':
Each cell with one or no neighbors dies, as if by loneliness.
Each cell with four or more neighbors dies, as if by overpopulation.
Each cell with two or three neighbors survives.
For a space that is 'empty' or 'unpopulated'
Each cell with three neighbors becomes populated.

http://tomas.rokicki.com/hlife/

^ info

[KawaGeo]

Try http://en.wikipedia.org/wiki/Cellular_automaton

It has a good stuff to read. Warning: lot of discussions involved.

Since Lua is an interpreting language, all interpreters are intented to preform in slow motion, pixel by pixel.

Best bet is to code some of them in C/C++ where the bottleneck occurs. And then bind it to your Lua script. (Don't ask me how to do this for PSP Lua Player.)

[Shine]

Best bet is to code some of them in C/C++ where the bottleneck occurs. And then bind it to your Lua script. (Don't ask me how to do this for PSP Lua Player.)

Yes, this would be the best. I've done this last night and will be released as a demo module with the next Lua Player release. It calculates about 12 full-screen Game Of Life generations per second. I've used nearly the same code like in my Java applet:

Code: Select all

static int lua_lifeStep(lua_State *L)
{
	// check for correct number of arguments
	int argc = lua_gettop(L);
	if (argc != 2) return luaL_error(L, "lifeStep(currentImage, nextImage) takes two arguments.");

	// get images
	Image* current = (Image*) *((Image**)lua_touserdata(L, 1));
	if (!current) luaL_typerror(L, 1, "Image");
	Image* next = (Image*) *((Image**)lua_touserdata(L, 2));
	if (!next) luaL_typerror(L, 2, "Image");

	// the colors of the cellular automaton
	Color green = 0xff00ff00;
	Color black = 0xff000000;

	// get dimension
	int width = current->imageWidth;
	int height = current->imageHeight;

	// check dimensions
	if (width != next->imageWidth || height != next->imageHeight)
		return luaL_error(L, "current and next image must be of the same size.");
	
	// calculate next Game Of Life generation
	for &#40;int y = 1; y < height - 2; y++&#41; &#123;
		for &#40;int x = 1; x < width - 2; x++&#41; &#123;
			Color center = current->data&#91;x + y * current->textureWidth&#93;;
			int result = center == green ? 1 &#58; 0;

			// game of life rules
			int n = current->data&#91;x + &#40;y - 1&#41; * current->textureWidth&#93; == green ? 1 &#58; 0;
			int ne = current->data&#91;x + 1 + &#40;y - 1&#41; * current->textureWidth&#93; == green ? 1 &#58; 0;
			int e = current->data&#91;x + 1 + y * current->textureWidth&#93; == green ? 1 &#58; 0;
			int se = current->data&#91;x + 1 + &#40;y + 1&#41; * current->textureWidth&#93; == green ? 1 &#58; 0;
			int s = current->data&#91;x + &#40;y + 1&#41; * current->textureWidth&#93; == green ? 1 &#58; 0;
			int sw = current->data&#91;x - 1 + &#40;y + 1&#41; * current->textureWidth&#93; == green ? 1 &#58; 0;
			int w = current->data&#91;x - 1 + y * current->textureWidth&#93; == green ? 1 &#58; 0;
			int nw = current->data&#91;x - 1 + &#40;y - 1&#41; * current->textureWidth&#93; == green ? 1 &#58; 0;
			int sum = n + ne + e + se + s + sw + w + nw;
			if &#40;sum == 3&#41;
				result = 1;
			else if &#40;sum != 2&#41;
				result = 0;

			// set next state
			next->data&#91;x + y * next->textureWidth&#93; = result == 1 ? green &#58; black;
		&#125;
	&#125;

	return 0;
&#125;

This module can be used by everyone for implementing other image related functions in C, which are too slow in Lua, like soft fade-in/fade-out of images or other things, like a FFT in C.

[VgSlag]

Shine - Excellent!
KawaGeo - Great, thanks :)
Zenurb - Cheers, I was actually following those rules in this example but cheers for the help :)

Thanks for all your help guys, you've been great as usual.

G

[LuMo]

hi VgSlag!
long time no see!
what happened to your "Pyramid Panic" preview?
any chance to see the final released?

greets
lumo

[VgSlag]

Hey Lumo,

I started Pyramid Panic after I split up with my girlfriend... I then subsequently got a new one meaning no free time for personal programing.

I've just started working from home now meaning I no longer have to do 5 hours of commuting a day which means I now have free time!!

I was knocking up GOL with Flash 8's bitmap data and just thought I'd have a shot on the PSP too.

I was looking at Pyramid Panic too and thougth I must get back into it.

There are still some kinks in the engine, mainly jumping left and hitting a tile mid jump.

I will get back onto this, and it will be out one day :)

As soon as I start workign on it again I'll send you a version :)

G

[Shine]

In the new version 0.19 the Game Of Life demo is included:

http://forums.ps2dev.org/viewtopic.php?p=38455

[Kameku]

I decided that making the boxes 2x2 works a lot faster, around 10 fps.

Code: Select all

math.randomseed(os.time())
math.random();math.random();math.random()
white = Color.new(255,255,255)
black = Color.new(0,0,0)
canvas = Image.createEmpty(480,272)
canvas:clear()
pal = {}
for y=0,136 do
 pal[y] = {}
 for x=0,240 do
  pal[y][x] = math.random(1,12)
 end
end

function ncount(x,y)
 n = 0
 if pal[y+1][x] == 1 then n=n+1 end
 if pal[y][x+1] == 1 then n=n+1 end
 if pal[y+1][x+1] == 1 then n=n+1 end
 if pal[y+1][x-1] == 1 then n=n+1 end
 if pal[y-1][x+1] == 1 then n=n+1 end
 if pal[y-1][x] == 1 then n=n+1 end
 if pal[y][x-1] == 1 then n=n+1 end
 if pal[y-1][x-1] == 1 then n=n+1 end
 return n
end

while true do
 for y=1,135 do
  for x=1,239 do
   n = ncount(x,y)
   if n > 3 then
    pal[y][x] = 2
   elseif n < 2 then
    pal&#91;y&#93;&#91;x&#93; = 2
   elseif n == 3 then
    pal&#91;y&#93;&#91;x&#93; = 1
   end
   if pal&#91;y&#93;&#91;x&#93; == 1 then
    canvas&#58;fillRect&#40;x*2,y*2,2,2,white&#41;
   else
    canvas&#58;fillRect&#40;x*2,y*2,2,2,black&#41;
   end
  end
 end
 screen&#58;clear&#40;&#41;
 screen&#58;blit&#40;0,0,canvas&#41;
 screen.flip&#40;&#41;
 screen.waitVblankStart&#40;&#41;
end

Just for an all Lua GoL. :([/code]