Re: [Adonthell-devel] map structure

[Alexandre Courbot]

> As little has been done in that direction, I'll have to raise this
> subject again. We want to have a single, continuous map where
> everything takes place. THe Waste's Edge world was small enough to
> keep all of it in memory. Maybe this would work with the next demo
> too, maybe not. However, it definately won't work with the final game.
> 
> So I suggest that we think about a way to load parts of the map as
> they are needed - in realtime. Because if we wait until later, we'll
> have to rewrite our code once more, including the editors we'll have
> by then. It's better to do it properly right from the beginning.

You're right. I wasn't sure about the method to use - totally separated
maps a la FF or continuous map a la Ultima, but even though the second
will be more complicated to implement, it will also probably be more
enjoyable for the player.

> Here are my thoughts on that issue. First of all, it's important to
> distinguish between the map and mapobjects. In this context, a map is
> simply the information where (and in which order) mapobjects are
> placed. So the map data itself is quite small. The Waste's Edge map is
> just 3222 bytes! By far larger are the mapobjects, the scenery,
> characters, items.(2-3 Megs)

Waste's Edge map is only 3222 bytes because it's compressed with gzip.
In a usable form, it already takes much, much more! :)

> So the first action would be separating map and mapobjects. As
> adjacent areas would most likely share some mapobjects, some sort of
> mapobject cache would make sense. When loading new areas, only few
> mapobjects should have to be loaded from disk. A larger part should be
> already cached. Each mapobject would have a reference count (either
> how many areas refer to it, or how often it is used in total). As the
> player moves along the map new areas are loaded, and old ones
> discarded. Loading should of course happen before discarding, so that
> as little allocation/deallocation of mapobjects takes place.

Most modern operating system offer a powerful caching system, but of
course what takes the more time in mapobjects loading is image decoding.
So having our own cache system would be an excellent idea.

The interesting thing about mapobjects, especially on the server side,
is that terrain occupation is separated from graphics. That to enable a
server to run without useless graphics. So I guess we can keep many
mapobjects in memory in the case of a server, which would be great
considering the much more important requirements.

> Another way to keep the mapobject fluctuation small without
> restrictions to map design is to keep the areas small. That way,
> loading new areas will happen more often, but the amount of data that
> is loaded is usually small, so it shouldn't hurt much.

Right. Moreover, it would make map creation easier, I think.

> Another important point is that this splitting of the map shouldn't
> concern map designers. It has to be completely transparent to them. So
> it needs to be automated, and for that it makes sense to split the map
> into regular chunks. Squares. As I suggested once before, at any time
> we had 9 areas in memory. One where the player currently sits, and one
> in each of the 8 directions around the player. Whenever the player
> nears the center of the outer area (or whatever we mark as 'border'),
> new areas in this direction are loaded, then the ones in the opposing
> direction are unloaded. That shouldn't take longer than 0.25s; if
> possible it should be faster. Maybe the framerate would drop for that
> time, but in general it shouldn't be noticed. (would it make sense to
> use a special thread for this purpose?)

I'm against using another thread. There are good reasons to think that
the map that will be loaded uses the same mapobjects as the one next to
it, plus maybe a few ones. So loading shouldn't hurt much. Using a
thread won't help anyway, as the player couldn't progress as long as the
map isn't completely loaded, so the result would be the same! It would
be dangerous otherwise. Imagine a player that moves very (very!) fast,
he could arrive at the new map area before it is completely loaded. I
prefer to play on security here.

> Coordinates:
> All areas would use a global coordinate system. I.e. Area 0,0 would
> have coordinates (0,0)-(16,16). Area 1,0 would have (17,0)-(32,16).
> And so on. I imagine that the mapeditor would center on 0,0 when
> starting a new map. From there you could start adding terrain in
> either direction(meaning negative coordinates are allowed). Otherwise
> editing could start at 2^16,2^16 (assuming 32 bit coordinates). 

We'd need a global coordinate system, sure. But maybe the maps
themselves could use relative coordinates, while every map has a global
coordinate - that way coordinates would be translated. Don't know if
this could be useful however! :)

> Splitting:
> When saving a map, the editor would automatically split it in parts
> and name them according to some scheme. Like <mapname><xxxx><yyyy>. x
> and y would probably be in hex notation.

Yes, but there's something that worries me a little bit here: what if a
mapobject is split between two maps? I guess we can handle this
correctly, provided the two maps are always loaded when the map object
is used (and this will probably always be the case). Need further
thoughts anyway.

> Overlapping mapobjects:
> Mapobjects that overlap areas shouldn't be a problem (I hope). I
> imagine they are placed down on a certain tile and stretch in whatever
> direction. They belong to the area that contains the tile they're
> placed on. As the map areas will be a single structure in memory,
> there is no difference to objects that don't overlap areas.

Mmm not exactly. Every square a mapobject is on has a reference to it
and his relative position from the square. But well, there is certainly
a clean way to handle this.

> Map structure in memory:
> Again I assume that the map in memory is some sort of array of
> maptiles. That of course means that as new areas are loaded and old
> ones are removed, there needs to be a way to insert new areas at the
> proper positions. That probably involves some moving around of array
> content. However, that should be pretty fast, as the array wouldn't be
> large.

How about the map file structure? You proposed to split it into multiple
files, but since they have no reason to exist without others (as they
are a whole), maybe it would be better to save the whole map into a
single, indexed file for fast access to map parts. This could even be
slightly faster, as you wouldn't need to open/close files all the time.

> So in the end we'd have the following
> 
> x+0,y+0                                    x+47,y+0
>   +--------------+--------------+--------------+
>   |              |              |              |
>   |       .......|..............|......        |
>   |      :       |              |      :       |
>   |      :       |              |      :       |
>   |      :       |              |      :       |
>   +--------------+--------------+--------------+
>   |      :       |              |      :       |
>   |      :       |              |      :       |
>   |      :       |     <P>      |      :       |
>   |      :       |              |      :       |
>   |      :       |              |      :       |
>   +--------------+--------------+--------------+
>   |      :       |              |      :       |
>   |      :       |              |      :       |
>   |      :.......|..............|......:       |
>   |              |              |              |
>   |              |              |              |
>   +--------------+--------------+--------------+
> x+0,y+47                                   x+47,y+47
> 
> The part of the map that is kept in memory is a single array, but
> composed of 9 areas. Whenever the player <P> crosses the dotted line,
> new areas are loaded. The area where the player was will be the new
> center of the map.
> 
> 
> What do you think?

That's cool! :) What I like is that if we turn multiplayer, this scheme
will perfectly fit. We could even do it for NPCs (well, of course as we
already discussed we can't update them all all the time). So I guess
we'll follow this direction!

> P.S. I could definately help with coding that stuff. As it wouldn't
> involve rendering as such, there shouldn't be any conflicts.

Great! I'm reading through my image synthesis lessons, which contain
interesting information for 3D collisions and rendering. So even though
these two parts are map related, we have no chance to conflict! :)

Alex.
-- 
http://www.gnurou.org