Converting a bidimensional list in a bidimensional array

[Santiago Romero]

Hi

First of all, I must apologize for my poor english

I'm starting with python and pygame and for testing (and learning)
purposes I wrote an small "Map Editor" for a small game project I'm
going to start next month.

The tilemap editor is working fine, but reading Guido's Van Rossum
PYTHON TUTORIAL I found that my game map is "wasting" memory by using
about 16 bytes for each item in it, because every item in a python
list takes 16 bytes in memory. In the same tutorial, I found
references to the "array()" function of the "array" module.

I'm trying to change my current working source code so that it works
with an array instead of using a list, but I'm not managing to do it.

My tilemap is something like (think on 0=empty, 1=floor, 2=rock, and
so...):

[
[0 ,0, 0, 0, 0, 0, 0, 0 ,0],
[0 ,0, 0, 0, 0, 0, 0, 0 ,0],
[2 ,0, 0, 0, 0, 2, 2, 0 ,0],
(...)
[2 ,2, 0, 0, 2, 2, 2, 0 ,0],
[1 ,1, 1, 1, 1, 1, 1, 1 ,1],
]

This is how I create the tilemap (and the clipboard, a copy of my
tilemap):

def __init__( self, bw, bh, tiles ):
self.width, self.height = bw, bh
self.tilemap = []
self.clipboard = []
(...)
for i in range(bh):
self.tilemap.append([0] * bw)
self.clipboard.append([0] * bw)


And that's how I'm using it (the functions I'm having trouble to
convert to use the array):

#-------------------------------------
def CopyToClipboard( self ):
for j in range( self.height ):
self.clipboard[j][:] = self.tilemap[j][:]

#-------------------------------------
def Draw( self, clear=1 ):
screen = pygame.display.get_surface()
if clear: self.Clear()

for j in range(self.GetHeight()):
for i in range(self.GetWidth()):
self.DrawBlock( i, j )

#-------------------------------------
def DrawBlock( self, x, y ):
screen = pygame.display.get_surface()
xd = (x * self.TileWidth()) + self.originx;
yd = (y * self.TileHeight()) + self.originy;
b = self.tilemap[y][x]
self.tileset.tiles.Draw( screen, xd, yd )

#-------------------------------------
def ResizeWidth( self, new ):
bw, bh = self.GetWidth(), self.GetHeight()

if new > bw:
for j in range(bh):
for i in range(new-bw):
self.tilemap[j].append( 0 )
self.clipboard[j].append( 0 )
self.SetWidth( new )

elif new < bw:
for j in range(bh):
for i in range(bw-new):
del self.tilemap[j][-1]
del self.clipboard[j][-1]
self.SetWidth( new )

#-------------------------------------
def ResizeHeight( self, new ):
bw, bh = self.GetWidth(), self.GetHeight()

if new > bh:
for i in range(new-bh):
self.tilemap.append([0] * bw)
self.clipboard.append([0] * bw)
self.SetHeight( new )

elif new < bh:
for i in range(1,bh-new):
del self.tilemap[-1]
self.SetHeight( new )



In fact, I'm even unable to create the array correctly:


I've tried:

self.tilemap = array('H', [])

for i in range(bh):
self.tilemap.append([0] * bw)

and:

for i in range(bh):

for j in range(bw):
self.tilemap.append(0)


But I receive errors like (either defining or using the array):

b = self.tilemap[y][x]
TypeError: 'int' object is unsubscriptable

or:

self.tilemap.append( [0] * bw )
TypeError: an integer is required



So ... please ... any idea on how to convert my "python object" array
of lists to a bidimensional array and how to use it to index [y][x]
elements, or even resize it with the ResizeWidth() and Height()
functions?

Thanks everybody.


PS: Please, think that I come from C/C++ so I still have some "C ways
of doing things" while there are better/faster ways to do the same in
Python. Feel free also to correct any "C-Style" programming way that
you can find in my source code above...

 

[Scott David Daniels]

I'm trying to change my current working source code so that it works
with an array instead of using a list, but I'm not managing to do it.
...

This is how I create the tilemap (and the clipboard, a copy of my
tilemap):

def __init__( self, bw, bh, tiles ):
self.width, self.height = bw, bh
self.tilemap = []
self.clipboard = []
(...)
for i in range(bh):
self.tilemap.append([0] * bw)
self.clipboard.append([0] * bw)

def __init__( self, bw, bh, tiles ):
self.width, self.height = bw, bh
self.tilemap = array.array('b', [0]) * bw * bh
self.clipboard = array.array('b', self.tilemap)

Gives a pure linearization (you do the math for lines).

def __init__( self, bw, bh, tiles ):
self.width, self.height = bw, bh
self.tilemap = [array.array('b', [0]) * bw for row in range(bh)]
self.clipboard = [array.array('b', [0]) * bw for row in range(bh)]

Gives a list of arrays. I punted on the type arg here; you should make
a definite decision based on your data.

--Scott David Daniels
(e-mail address removed)

 

[Santiago Romero]

This is how I create the tilemap (and the clipboard, a copy of my

tilemap):

def __init__( self, bw, bh, tiles ):
self.tilemap = []
(...)
for i in range(bh):
self.tilemap.append([0] * bw)

def __init__( self, bw, bh, tiles ):
self.width, self.height = bw, bh
self.tilemap = array.array('b', [0]) * bw * bh

Gives a pure linearization (you do the math for lines).

Do you mean : tilemap[(width*y)+x] ?

def __init__( self, bw, bh, tiles ):
self.width, self.height = bw, bh
self.tilemap = [array.array('b', [0]) * bw for row in range(bh)]

Gives a list of arrays. I punted on the type arg here; you should make
a definite decision based on your data.

What do you think about:

- Memory Performance: Of course, my maps will take ( 16 bytes / 2-4
bytes ) = 8 or 4 times less memory (32 / 64 bit processores) ...
right?

- Speed Performance: Do you think that changing from list to Array()
would improve speed? I'm going to do lots of tilemap[y][x] checks (I
mean, player jumping around the screen, checking if it's falling over
a non-zero tile, and so).

And thanks a lot for your answer

 

[bearophileHUGS]

Santiago Romero:

- Speed Performance: Do you think that changing from list to Array()
would improve speed? I'm going to do lots of tilemap[y][x] checks (I
mean, player jumping around the screen, checking if it's falling over
a non-zero tile, and so).

First of all: if you have enough memory to use a python list, then I
suggest you to use a list.

That said, often the best way to know the speed is to write a little
testing code.

Often python lists are faster than array.array (maybe because python
lists actually contain pyobjects).

If you want an array.array to be faster than a list you can use Psyco.

Bye,
bearophile

 

[Scott David Daniels]

... [I wrote]

def __init__( self, bw, bh, tiles ):
self.width, self.height = bw, bh
self.tilemap = array.array('b', [0]) * bw * bh
Gives a pure linearization (you do the math for lines).

Do you mean : tilemap[(width*y)+x] ?

Yup, exactly.

....

What do you think about:
- Memory Performance: Of course, my maps will take ( 16 bytes / 2-4
bytes ) = 8 or 4 times less memory (32 / 64 bit processores) ...
right?

How many distinct values do you have? If you have under a hundred (and
they are all positive), the actual integers are shared, so a byte array
only saves you at 4:1 (or 8:1 on a 64-bit processor).

- Speed Performance: Do you think that changing from list to Array()
would improve speed? I'm going to do lots of tilemap[y][x] checks (I
mean, player jumping around the screen, checking if it's falling over
a non-zero tile, and so).

The Pythonic answer to this is, "try it both ways." Don't intuit;
measure. Now if you are as old-school as I am, you start by thinking,
"<invective expurgated>, I don't want to spend a week writing and
running benchmarks."

Joy, Python excels here. at the command prompt (in 2.5, at least),
[a single line, I've broken it to three for newsgroup reading only]
C:\> \python25\python -m -s "import array; a = [array.array('b',
[0]*1000) for n in range(100)]"
"v = a[1][2] + a[2][1] + a[3][3]"

You can also use:
C:\> \python25\python -m -s "import m; m.setup()" "m.my_fun(123)"

Try it, you'll be addicted in no time. Check the documentation on
package "timeit."

--Scott David Daniels
(e-mail address removed)

 

[Santiago Romero]

C:\> \python25\python -m -s

Thanks a lot

 

[Santiago Romero]

- Speed Performance: Do you think that changing from list to Array()

would improve speed? I'm going to do lots of tilemap[y][x] checks (I
mean, player jumping around the screen, checking if it's falling over
a non-zero tile, and so).

First of all: if you have enough memory to use a python list, then I
suggest you to use a list.

Often python lists are faster than array.array (maybe because python
lists actually contain pyobjects).

My problem is that, in my game, each screen is 30x20, and I have
about 100 screens, so my tilemap contains 32*20*100 = 60000 python
objects (integers).

If each integer-python-object takes 16 bytes, this makes 60000 * 16 =
almost 1MB of memory just for the tilemaps...

Using array of type H (16 bits per item = 2 bytes), my maps take just
60000*2 = 120KB of memory.

After that, I just will access tilemap data for reading (i.e. value
= tilemap.GetTile(x,y)) ...

Do you think I should still go with lists instead of an H-type array?

 

[bearophileHUGS]

Santiago Romero:

If each integer-python-object takes 16 bytes, this makes 60000 * 16 =
almost 1MB of memory just for the tilemaps...
Using array of type H (16 bits per item = 2 bytes), my maps take just
60000*2 = 120KB of memory.
Do you think I should still go with lists instead of an H-type array?

1 MB or RAM may be small enough nowdays, so you may use lists.
If not, then the array.array solution can be good.
You may even store just the rows of your images as arrays, so you can
use the usual syntax [][].
Another alternative is to use some external numerical lib, it's quite
useful if you use pygame, to blit, process images, store and process
bitmaps, etc.

Bye,
bearophile

 

[Fredrik Lundh]

My problem is that, in my game, each screen is 30x20, and I have
about 100 screens, so my tilemap contains 32*20*100 = 60000 python
objects (integers).

If each integer-python-object takes 16 bytes, this makes 60000 * 16 =
almost 1MB of memory just for the tilemaps...

or more likely, 240k for pointers to a few distinct integer objects,
each of which occupies 16 bytes.

if you're really running this on a machine with only a few megabytes
free memory, maybe you could compress the screens you're not working
with? zlib.compress(cPickle.dumps(screen)) should compress each
640-item list to say, 50 to 500 bytes, depending on the contents.

</F>

 

[Diez B. Roggisch]

- Speed Performance: Do you think that changing from list to Array()
would improve speed? I'm going to do lots of tilemap[y][x] checks (I
mean, player jumping around the screen, checking if it's falling over
a non-zero tile, and so).

First of all: if you have enough memory to use a python list, then I
suggest you to use a list.

Often python lists are faster than array.array (maybe because python
lists actually contain pyobjects).

My problem is that, in my game, each screen is 30x20, and I have
about 100 screens, so my tilemap contains 32*20*100 = 60000 python
objects (integers).

If each integer-python-object takes 16 bytes, this makes 60000 * 16 =
almost 1MB of memory just for the tilemaps...

Using array of type H (16 bits per item = 2 bytes), my maps take just
60000*2 = 120KB of memory.

After that, I just will access tilemap data for reading (i.e. value
= tilemap.GetTile(x,y)) ...

Do you think I should still go with lists instead of an H-type array?

With these requirements, there is no need to jump through hoops to try
and save memeroy. You even can load levels from disk while the player
moves through the world.

Seriously - even a decade old machine would have had enough ram for
this. And nowadays .5GB to 2GB are the minimum. Don't waste time you
could spend designing a nice game on saving memory....

Diez