Re: Cheap tricks for map data structure

At Thu, 19 Feb 2009 13:22:58 -0800 (PST), Gelatinous Mutant Coconut wrote:

But an array of Cell objects is more manageable, more elegant...
simpler in the long term :).

I really can't agree with that, but I guess it's because I only use
fast, low-level programming languages that would let me get away with
such an inefficiency only when my resources are already constrained,
so I can't get away with it anyways.

I don't really see how a 2D array of Cell objects, each containing the
information necessary to produce the tile in question, is much more
inefficient than a a 2D array of either stacks of tile detail objects,
or arrays used to hold a fixed amount of tile detail objects per
cell.

Wouldn't the most straightforward implementation of a Cell class just
be a container for some fixed number of variables per tile, one of
which might be a pointer to a list of some kind? Is that really
different in any meaningful way?

Am I missing something?

Yes, please check what is the memory overhead of an object in your
language of choice, and what is the computational cost of creating it,
then multiply it by the number of map squares you plan to have on a
single level.

We've already had people here who had to increase the default memory
settings of the Java virtual machine, for example, just to be able to
run their games. And these defaults are not skimpy.

Having a separate object for each map square also encourages you to pass
a reference to that object to functions that would normally expect
a reference to a map and coordinates. This makes you store the coordinates
of the square inside the square object, and probably also a reference to
the map object itself, because without it the coordinates are meaningless
(of course, you could do another overkill and just store the references
to neighboring cells instead). That's a lot of unnecessary data in the
most common object class in your whole program. In addition, there are
cycles in it, so the garbage collector may have lots of fun. If there is
no garbage collector, then all the fun is yours instead, and static
analyzers based on the concept of 'ownership' responsibilities won't help
you.

All this is easily replaced by a simple map class that may contain
a several arrays of bytes for layers of terrain, a hash table of
coordinates to items and a quad tree of monsters -- if you decide
that such data structures fit your data models best. And if you decide
that they don't fit it, then you store your items in binary trees sorted
by coordinates, your monsters in a priority queue sorted by the next
scheduled action, and your map you compute on the fly from a random seed
and a fractal. Or whatever other solution you find the best in that
particular stage of development.

--
Radomir Dopieralski, http://sheep.art.pl
.

Relevant Pages

  • Re: Dangling pointers and saving references to file in C.
    ... But I wouldn't consider keeping absolute indices into an array a good ... Adeo manages reference serialization (which is what we're talking ... a map is loaded, after the entire map is loaded, the engine does a ...
    (rec.games.roguelike.development)
  • Re: Lat/Lon waypoints for GPS
    ... on the above sector in the map. ... until the required image is on screen and it's reference number shows. ... When the download screen appears, simply click on "Download MrSid image". ... You can use the MrSid viewer from LizardTech to view and magnify the images ...
    (uk.rec.sailing)
  • Re: Clojure hash table accessors in CL
    ... This is really stupid because the map actually gives you a reference (pointer ... This whole idiotic business of returning the reference to the value out of the ... Say, what would happen if you were to capture that storage location, manipulate ... The assignment is stomping on heap ...
    (comp.lang.lisp)
  • Re: Why doesnt Integer have a setValue(int i), and is there a way of changing its value.
    ... With immutable keys, ... The alternative to immutability would ... > Now, I assume that the second Integer added to the Map, will return an int ... a *copy* of the reference contained by b was passed to the ...
    (comp.lang.java.programmer)
  • Re: how does your language... make a map?
    ... from terrain import Terrain ... from monster import Monster ... you can access the contents of the map squares ...
    (rec.games.roguelike.development)