forums.ps2dev.org Forum Index forums.ps2dev.org
Homebrew PS2, PSP & PS3 Development Discussions
 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister 
 ProfileProfile   Log in to check your private messagesLog in to check your private messages   Log inLog in 

Game of Life speed help

 
Post new topic   Reply to topic    forums.ps2dev.org Forum Index -> PSP Lua Player Development
View previous topic :: View next topic  
Author Message
VgSlag



Joined: 30 Jun 2005
Posts: 43
PostPosted: Tue Apr 11, 2006 1:00 am    Post subject: Game of Life speed help Reply with quote
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:

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
Back to top
View user's profile Send private message
Zenurb



Joined: 30 Sep 2005
Posts: 106
Location: United Kingdom
PostPosted: Tue Apr 11, 2006 1:26 am    Post subject: Reply with quote
Dude, there are definately much more efficient ways to emulate cellular automata. Did you port this from a Java app or write it yourself?
_________________
Proud Dvorak User
US 1.5 PSP (Original)
Back to top
View user's profile Send private message Visit poster's website MSN Messenger
VgSlag



Joined: 30 Jun 2005
Posts: 43
PostPosted: Tue Apr 11, 2006 1:47 am    Post subject: Reply with quote
I just knocked it together. Any tips on faster ways?
Back to top
View user's profile Send private message
JorDy



Joined: 11 Dec 2005
Posts: 121
PostPosted: Tue Apr 11, 2006 5:24 am    Post subject: Reply with quote
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
Back to top
View user's profile Send private message
romero126



Joined: 24 Dec 2005
Posts: 200
PostPosted: Tue Apr 11, 2006 5:41 am    Post subject: Reply with quote
Remember kids simpler is better, any way you can simplify that to a few lines of code?

Less is more..
Back to top
View user's profile Send private message
VgSlag



Joined: 30 Jun 2005
Posts: 43
PostPosted: Tue Apr 11, 2006 7:27 am    Post subject: Reply with quote
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
Back to top
View user's profile Send private message
JorDy



Joined: 11 Dec 2005
Posts: 121
PostPosted: Tue Apr 11, 2006 8:08 am    Post subject: Reply with quote
your variables are just messy looking as for the code there are better more efficient ways with less lines
Back to top
View user's profile Send private message
VgSlag



Joined: 30 Jun 2005
Posts: 43
PostPosted: Tue Apr 11, 2006 9:35 am    Post subject: Reply with quote
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
Back to top
View user's profile Send private message
Zenurb



Joined: 30 Sep 2005
Posts: 106
Location: United Kingdom
PostPosted: Tue Apr 11, 2006 12:18 pm    Post subject: Reply with quote
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
_________________
Proud Dvorak User
US 1.5 PSP (Original)
Back to top
View user's profile Send private message Visit poster's website MSN Messenger
KawaGeo



Joined: 27 Aug 2005
Posts: 191
Location: Calif Mountains
PostPosted: Tue Apr 11, 2006 1:19 pm    Post subject: Reply with quote
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.)
_________________
Geo Massar
Retired Engineer
Back to top
View user's profile Send private message Send e-mail
Shine



Joined: 03 Dec 2004
Posts: 728
Location: Germany
PostPosted: Tue Apr 11, 2006 4:36 pm    Post subject: Reply with quote
KawaGeo wrote:
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:

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 (int y = 1; y < height - 2; y++) {
      for (int x = 1; x < width - 2; x++) {
         Color center = current->data[x + y * current->textureWidth];
         int result = center == green ? 1 : 0;

         // game of life rules
         int n = current->data[x + (y - 1) * current->textureWidth] == green ? 1 : 0;
         int ne = current->data[x + 1 + (y - 1) * current->textureWidth] == green ? 1 : 0;
         int e = current->data[x + 1 + y * current->textureWidth] == green ? 1 : 0;
         int se = current->data[x + 1 + (y + 1) * current->textureWidth] == green ? 1 : 0;
         int s = current->data[x + (y + 1) * current->textureWidth] == green ? 1 : 0;
         int sw = current->data[x - 1 + (y + 1) * current->textureWidth] == green ? 1 : 0;
         int w = current->data[x - 1 + y * current->textureWidth] == green ? 1 : 0;
         int nw = current->data[x - 1 + (y - 1) * current->textureWidth] == green ? 1 : 0;
         int sum = n + ne + e + se + s + sw + w + nw;
         if (sum == 3)
            result = 1;
         else if (sum != 2)
            result = 0;

         // set next state
         next->data[x + y * next->textureWidth] = result == 1 ? green : black;
      }
   }

   return 0;
}


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.
Back to top
View user's profile Send private message
VgSlag



Joined: 30 Jun 2005
Posts: 43
PostPosted: Tue Apr 11, 2006 5:20 pm    Post subject: Reply with quote
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
Back to top
View user's profile Send private message
LuMo



Joined: 21 Aug 2005
Posts: 410
Location: Austria
PostPosted: Tue Apr 11, 2006 6:00 pm    Post subject: Reply with quote
hi VgSlag!
long time no see!
what happened to your "Pyramid Panic" preview?
any chance to see the final released?

greets
lumo
_________________
"Good artists copy, great artists steal."
Pablo Picasso
go2lumo.com
Back to top
View user's profile Send private message Visit poster's website
VgSlag



Joined: 30 Jun 2005
Posts: 43
PostPosted: Tue Apr 11, 2006 6:31 pm    Post subject: Reply with quote
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
Back to top
View user's profile Send private message
Shine



Joined: 03 Dec 2004
Posts: 728
Location: Germany
PostPosted: Tue Apr 11, 2006 8:11 pm    Post subject: Reply with quote
In the new version 0.19 the Game Of Life demo is included:

http://forums.ps2dev.org/viewtopic.php?p=38455
Back to top
View user's profile Send private message
Kameku



Joined: 23 Mar 2006
Posts: 32
Location: Oregon, USA
PostPosted: Wed Apr 12, 2006 3:01 pm    Post subject: Reply with quote
I decided that making the boxes 2x2 works a lot faster, around 10 fps.

Code:

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[y][x] = 2
   elseif n == 3 then
    pal[y][x] = 1
   end
   if pal[y][x] == 1 then
    canvas:fillRect(x*2,y*2,2,2,white)
   else
    canvas:fillRect(x*2,y*2,2,2,black)
   end
  end
 end
 screen:clear()
 screen:blit(0,0,canvas)
 screen.flip()
 screen.waitVblankStart()
end

Just for an all Lua GoL. :([/code]
Back to top
View user's profile Send private message AIM Address Yahoo Messenger MSN Messenger
Display posts from previous:   
Post new topic   Reply to topic    forums.ps2dev.org Forum Index -> PSP Lua Player Development All times are GMT + 10 Hours
Page 1 of 1

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum


Powered by phpBB © 2001, 2005 phpBB Group