Computer Science question (python list is slow with my cruddy algorithm )

Terry Hancock hancock at anansispaceworks.com
Fri Aug 23 14:43:47 CEST 2002


From: "Mr. Neutron" <nicktsocanos at charter.net>
> What I am trying to do is build a game. It is a very simple game it is
> not fancy like Quake or anything like that. I have a World structure
> that contains squares. These squares are just an area of the world
> (1 mile x 1 mile) that have interesting features on them. I wanted
> to make a big world that would be interesting. I can play the game
> in a small world ( 64x64 squares ). That is ok and fast. But I wanted the
> idea of huge worlds too (even though it is not necessary for the game).
> For my simple game so far, MyLIst = [ [0] * 64 for i in range(64) ]
> is fast. Is this 64x64x4 = 16384 bytes in Python memory?
> 
> You make a robot, give it a purpose in life [...]world to find resources.
> It moves about looking for things to collect. I am working on the store
> so that it can go to the store and buy items and upgrade. 
> 
> Now that that is out of the way, are there any better ways to represent
> the world than a list of lists? I just need to be able to say
> World[Y][X] = ( values ). Or be able to say what is at World[Position].
> Ideally I could say World[ (X,Y) ] = (Values) but I have not tried this.
> If World[ (X,Y) ] is empty, than it does not need to store anything in
> memory at all. I need to go to Idle now and experiment with this.

IMHO, the dictionary with 2-tuple keys is the way to
go.  I note also the response about using a graph. Such
a solution implies a highly-structured world and is
the sort of model used in adventure games. Your grid
model is like SimEarth and company in design.  It's
also basically similar to the class of simulations called
"cellular automata".

The two different approaches have their respective
advantages. In some ways, your grid is the simpler
of the two. It also provides a clean, open framework
for unrestricted play.  The graph approach provides
more opportunity to set up the situation, limit
choices, etc, and may be a more compact representation
of realistic worlds (closer to how we conceptualize
the world, in general).

And you definitely have a "sparse matrix" in this case,
this is why you didn't realize the size -- you only
consider the active squares when you think about it.

Go ahead and use 32767^2 -- it will give you plenty of
resolution -- but use a storage method that doesn't
consume space for empty squares. The dictionary suits
that.

world = {}
world[(x, y)] = ( tuple of properties )

Then

world.get( (x,y), default=( empty square properties ))

is the idiom I was trying to remember for retrieval
with default (I looked it up).

World will take up as much space as needed for each
tuple you specify and no more.  You also won't waste
a lot of time loading it.

Cheers,
Terry


-- 
------------------------------------------------------
Terry Hancock
hancock at anansispaceworks.com       
Anansi Spaceworks                 
http://www.anansispaceworks.com 
P.O. Box 60583                     
Pasadena, CA 91116-6583
------------------------------------------------------




More information about the Python-list mailing list