[Adonthell-devel] map structure

[Kai Sterker]

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.

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)

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.

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.


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?)


So much for the requirements. What are the consequences?

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). 

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.

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.

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.


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?

Kai

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