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

[Bengt Richter]

On Fri, 23 Aug 2002 05:43:47 -0700, Terry Hancock <hancock at anansispaceworks.com> wrote:

>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.
>
Don't you need to find things within _areas_ of the world, rather than just at specific
known points? E.g., I think you could even use floating point coordinates if you wanted to, if you had
a relational data base of things with coordinates and wrote, e.g.,

    select x,y,thing from world where x between 400.0 and 600.0 and y beween 200.0 and 300.0

or maybe better, select using half-open tiles. I believe some (postgreSQL?) databases support
optimized indexing for this kind of query. (It's probably good for relatively static stuff,
but I would guess you might want to keep track of moving players & such some other way to
avoid index update overhead -- though I'd be happy to be surprised by finding the latter to be low).
I haven't used a db in this way, but it would seem suited. Also GIS stuff.

You could also build your own quad-tree structures using plain old Python. Or maybe use a
dictionary of Voronoi neighbors?

Regards,
Bengt Richter