/*
   $Id$

   Copyright (C) 2001   Alexandre Courbot
   Part of the Adonthell Project http://adonthell.linuxgames.com

   This program is free software; you can redistribute it and/or modify
   it under the terms of the GNU General Public License.
   This program is distributed in the hope that it will be useful,
   but WITHOUT ANY WARRANTY.

   See the COPYING file for more details.
*/

/** 
 * @file newmap.dxt
 *
 * @author Alexandre Courbot <alexandrecourbot@linuxgames.com>
 * @brief Specifications for the new mapengine.
 */

/*! 
\page newmap Specifications for the new mapengine.

This document will precisely describe the specifications/internals of
the new map engine implementation that is supposed to be shipped with
versions >= 0.4 of the Adonthell engine.

\section p10spec Specification
What we want is a flexible, powerfull map engine that allows the
following things:

<ul>
<li> Unlimited number of \e submaps, that is different areas that
can be connected to each others (ex. several rooms in a house),
<li> Precise, pixel-unit based %characters movments and %objects
placement,
<li> Unlimited number of possible \e levels, to allow things like
bridges and so on,
<li> Altitude management through \e levels. A %character must be
able to fall from a bridge to the ground. A %character must also be
able to naturally climb stairs, for example,
<li> No limit about the number of %objects that can be placed on the
maps, no matter if they are all at the same place,
<li> %Objects and %characters must have the possibility to be
animated. Furthermore, the ways of animations must be very flexible,
allowing from very-simple to very-complex animations,
<li> %Characters animations should be most flexible. In particular, a
%character can have an unlimited number of special animations (jumping,
falling,...) that may be unique to him.
<li> Finally, the rendering must be realistic, bug-free of course,
but should remain as fast as possible.
</ul>

The above have been written with the ideas of speed, flexibility and
minimized ressource usage in mind. No pig-solution can pretend to be a
viable solution for the implementation.

... All the problem will now be to stand on these specifications! :)

\section p10imp Implementation proposal
Of course, our implementation will have to be well structured to be
viable. Such demanding specifications implies that the proposed
solution remains simple in it's parts, even if complex in it's
whole. That's why this section is highly hierarchised. We'll try to
describe the implementation from the higher layer to the lowest one.

\subsection mapcoord_class The mapcoordinates class
Not much to say about this one. It represents the position of any
object on the map, with the tile it is on and an offset from this tile:

\verbatim
class mapcoordinates
{
public:
    u_int16 x, y;
    u_int16 ox, oy;

    bool operator < (const mapcoords & mc); 
    bool operator <= (const mapcoords & mc); 
    bool operator > (const mapcoords & mc); 
    bool operator >= (const mapcoords & mc); 
}; 
\endverbatim

The operators let you easily compare two coordinates. A coordinate is
superior to another if it's \e y is superior, \b or it's \e x, \b or
it's \e oy, \b or it's \e ox (in this order). They should be mostly
used when you need to sort lists of objects - rendering, for example,
will need the objects to be sorted by coordinates in order to have a
good and fast result.

\subsection p10landmap The landmap class
This class contains the entire map, as well as the elements
(%characters, %objects) that are on it. It may or may not contains the
\e graphical %data of these %objects - anyway it is of no importance
for it as it's job is only to make the world it represents live - and
in no way to render it.

At this level, we only need the submaps, (map)%characters and
(map)%objects this \e %landmap owns. So the structure of the
\e %landmap class is as simple as this:

\verbatim
class landmap
{
    vector<landsubmap*> submap;
    vector<mapcharacter*> mapchar;
    vector<mapobject*> mobj;
};
\endverbatim

Using such a structure, we have the following advantages:

<ol>
<li> The number of landsubmaps, mapcharacters and mapobjects are
unlimited, and the allocated memory will exactly reflect the actual
number of them used. We are using pointers here for several reasons:
  <ol>
  <li> The vector container needs to perform copies when resized. As
we don't want our whole structures to be copied (which would be very
slow and would need a tricky copy-constructor) we are using arrays of
pointers.
  <li> Sometimes (depending on the implementation) the actual size of the vector is larger than the
number of elements that are inside it, to perform faster growings. As
our classes are rather large, using pointers we will ``waste'' less memory.
  <li> Finally, and probably the most important, using pointers the
adress of the %objects in memory will remain the same, no matter
whether we resize the vector or not. As mapobjects and %mapcharacter
will further be referenced by their memory adress, using pointers here
is mandatory if we want to keep this flexibility.
  </ol>
  On the other hand, we will be responsible for manually
allocating/freeing our %objects, which will require additionnal
attention.
<li> The flexibility is maximal, as we can dynamically add/remove
landsubmaps, mapobjects or mapcharacters. Beware, though, that the
resizing of a vector can be time consuming.
</ol>

\subsection p10landsubmap The landsubmap class
This class will be quite simple too. Actually, we will define a
\e landsubmap as a vector of \e mapsquare_areas, which
are the \e layers of this submap. On a simple map, the layer 0
could for example be the ground, while the layer 1 will be a bridge:
that way characters can safely walk on and under the bridge, it's just
a matter of \e layer. All the problem will then be to define
\e when does the characters switch from layer 0 to layer 1 and to
layer 1 to layer 0 - but we will have a look at this later, so hang on
;).

So our structure for \e landsubmap will be:
\verbatim
class landsubmap
{
    vector<mapsquare_area> area;
};
\endverbatim

Although things have quite quite simple until now, I fear the next
sections will give you a little more headache.

\subsection p10mapsquare_area The mapsquare_area class
Serious matters starts now, as this class represents a bit more than
arrays of things.

First, it seems sensible that all areas on the map aren't necessarly
the same size. Obviously, the ground will be larger than a bridge, so
the different areas can be differently sized. That's why their
position is precisely set by an \e offset, which sets which %mapsquare
this area starts on. ONLY for the \e first %mapsquare_area (0 indexed)
this offset parameter won't make sense, as others are placed
relatively to this one. Also, the area indexed \e n must ALWAYS be
higher than the one indexed \e n-1, for renderer performance reasons.

%Mapsquare_areas will also have (excepted, once again, for the layer
0) an altitude parameter. The layer will be drawn \e alt pixels higher
than the ground layer, \e alt being the altitude of that layer. Also,
having the altitude we can make characters fall from a layer to
another and, why not, jump from a lower layer to an higher one if the
%character can jump high enough.

Apart from that, the %mapsquare_area will also contain a
two-dimensional array of %mapsquares. Hang on for details about
%mapsquares.

\verbatim
class mapsquare_area
{
    vector<vector<mapsquare>> area;

    u_int16 xoffset;
    u_int16 yoffset;
    
    u_int16 altitude;
};
\endverbatim

\subsection p10mapsquare The mapsquare class
Although this class just represents a basic square of a level of a
map, it's structure is much more complex than what we've seen until
now.

A %mapsquare contains informations about the following things:
<ul>
<li>The %mapobjects that are on it. Their number is virtually unlimited.
<li>The %mapcharacters that are on it. Unlimited number of %mapcharacters
too.
<li>The walkability of this square. Actually, this information is
indirectly determined from the %mapobjects that are on it (as
%mapobjects have their own walkability information).
</ul>

The easiest way to handle such freedom in the number of %mapobjects
and %mapcharacters that can be placed on a %mapsquare is to use a
dynamic structure, the best candidate being a linked list.

That's at this level that we have to think about rendering
issues. Actually, there is only one, but huge issue: having in mind
that some %objects are totally flat (carpets) and that they must then
be drawn BEFORE %characters, while others (tree, houses) have an
"height" and therefore must be drawn before the %characters that are
in front of them, and after the characters that are behind them, how
can we correctly handle that without making things too much complex
and eating CPU time finding out what to draw before what? Having the
%data structure well organised can deadly accelerate things by having
simplier algorithms, and that's what we'll try to do with the
%mapsquare class.

As we only have two particular cases with %mapobjects (flat ones and
non-flat ones), let's separate their %storage in memory: we'll have one
list (not especially linked, as you will see after) for flat %objects,
and another one for non-flat %objects. That way we can easily draw flat
%objects before all.

<b>Handling flat %objects</b>

So, we have our list of flat %objects for this %mapsquare. But even if
these %objects are flat, some can be upper than others, for example two
carpets that superimposed on each others. Which one to draw first, the
red or the blue? The renderer will perform as follows: it will first
draw the first element of each %mapsquare, then perform another pass
to draw the second, and so on until all "layers" are done. This has
the following consequences:
<ul>
<li>The renderer have to perform one pass per "layer" of flat
%objects. This is the price for having such freedom in %objects
placement. 
<li>We can add an additionnal information to the %mapsquare_area,
about the number of layers of flat %objects it has. That way, the
renderer won't have to perform a pass for nothing when we have drawn
all the layers.
<li>We can't reasonnably use a linked list for these %objects, as the
renderer will perform the layer 0 of all mapsquares, then the layer
1, etc. We need a container that has constant access time. A vector
seems to be the best candidate here, as anyway it's size won't be
changed, or very occasionally, and the reallocations won't be too huge
(actually, they will rather be very small ones).
</ul>

<b>Handling non-flat %objects</b>

With non-flat %objects it is ok to use linked lists, and the renderer
will only have to perform one pass to draw the entire thing, non-flat
%objects and %mapcharacters, provided the linked lists are correctly
organized. The details about this will be discussed into the renderer
section.

\section p10dyn Map dynamic: how to make things move correctly

\subsection p10levchan Handling characters map level change

\section p10renderer Renderer details

*/