• Main Page
  • Related Pages
  • Classes
  • Files
  • File List
  • File Members

newmap.dxt

Go to the documentation of this file.
00001 /*
00002    $Id: newmap.dxt,v 1.4 2002/04/07 09:51:28 ksterker Exp $
00003 
00004    Copyright (C) 2001   Alexandre Courbot
00005    Part of the Adonthell Project http://adonthell.linuxgames.com
00006 
00007    This program is free software; you can redistribute it and/or modify
00008    it under the terms of the GNU General Public License.
00009    This program is distributed in the hope that it will be useful,
00010    but WITHOUT ANY WARRANTY.
00011 
00012    See the COPYING file for more details.
00013 */
00014 
00015 /** 
00016  * @file newmap.dxt
00017  *
00018  * @author Alexandre Courbot <alexandrecourbot@linuxgames.com>
00019  * @brief Specifications for the new mapengine.
00020  */
00021 
00022 /*! 
00023 \page newmap Specifications for the new mapengine.
00024 
00025 This document will precisely describe the specifications/internals of
00026 the new map engine implementation that is supposed to be shipped with
00027 versions >= 0.4 of the Adonthell engine.
00028 
00029 \section p10spec Specification
00030 What we want is a flexible, powerfull map engine that allows the
00031 following things:
00032 
00033 <ul>
00034 <li> Unlimited number of \e submaps, that is different areas that
00035 can be connected to each others (ex. several rooms in a house),
00036 <li> Precise, pixel-unit based %characters movments and %objects
00037 placement,
00038 <li> Unlimited number of possible \e levels, to allow things like
00039 bridges and so on,
00040 <li> Altitude management through \e levels. A %character must be
00041 able to fall from a bridge to the ground. A %character must also be
00042 able to naturally climb stairs, for example,
00043 <li> No limit about the number of %objects that can be placed on the
00044 maps, no matter if they are all at the same place,
00045 <li> %Objects and %characters must have the possibility to be
00046 animated. Furthermore, the ways of animations must be very flexible,
00047 allowing from very-simple to very-complex animations,
00048 <li> %Characters animations should be most flexible. In particular, a
00049 %character can have an unlimited number of special animations (jumping,
00050 falling,...) that may be unique to him.
00051 <li> Finally, the rendering must be realistic, bug-free of course,
00052 but should remain as fast as possible.
00053 </ul>
00054 
00055 The above have been written with the ideas of speed, flexibility and
00056 minimized ressource usage in mind. No pig-solution can pretend to be a
00057 viable solution for the implementation.
00058 
00059 ... All the problem will now be to stand on these specifications! :)
00060 
00061 \section p10imp Implementation proposal
00062 Of course, our implementation will have to be well structured to be
00063 viable. Such demanding specifications implies that the proposed
00064 solution remains simple in it's parts, even if complex in it's
00065 whole. That's why this section is highly hierarchised. We'll try to
00066 describe the implementation from the higher layer to the lowest one.
00067 
00068 \subsection mapcoord_class The mapcoordinates class
00069 Not much to say about this one. It represents the position of any
00070 object on the map, with the tile it is on and an offset from this tile:
00071 
00072 \verbatim
00073 class mapcoordinates
00074 {
00075 public:
00076     u_int16 x, y;
00077     u_int16 ox, oy;
00078 
00079     bool operator < (const mapcoords & mc); 
00080     bool operator <= (const mapcoords & mc); 
00081     bool operator > (const mapcoords & mc); 
00082     bool operator >= (const mapcoords & mc); 
00083 }; 
00084 \endverbatim
00085 
00086 The operators let you easily compare two coordinates. A coordinate is
00087 superior to another if it's \e y is superior, \b or it's \e x, \b or
00088 it's \e oy, \b or it's \e ox (in this order). They should be mostly
00089 used when you need to sort lists of objects - rendering, for example,
00090 will need the objects to be sorted by coordinates in order to have a
00091 good and fast result.
00092 
00093 \subsection p10landmap The landmap class
00094 This class contains the entire map, as well as the elements
00095 (%characters, %objects) that are on it. It may or may not contains the
00096 \e graphical %data of these %objects - anyway it is of no importance
00097 for it as it's job is only to make the world it represents live - and
00098 in no way to render it.
00099 
00100 At this level, we only need the submaps, (map)%characters and
00101 (map)%objects this \e %landmap owns. So the structure of the
00102 \e %landmap class is as simple as this:
00103 
00104 \verbatim
00105 class landmap
00106 {
00107     vector<landsubmap*> submap;
00108     vector<mapcharacter*> mapchar;
00109     vector<mapobject*> mobj;
00110 };
00111 \endverbatim
00112 
00113 Using such a structure, we have the following advantages:
00114 
00115 <ol>
00116 <li> The number of landsubmaps, mapcharacters and mapobjects are
00117 unlimited, and the allocated memory will exactly reflect the actual
00118 number of them used. We are using pointers here for several reasons:
00119   <ol>
00120   <li> The vector container needs to perform copies when resized. As
00121 we don't want our whole structures to be copied (which would be very
00122 slow and would need a tricky copy-constructor) we are using arrays of
00123 pointers.
00124   <li> Sometimes (depending on the implementation) the actual size of the vector is larger than the
00125 number of elements that are inside it, to perform faster growings. As
00126 our classes are rather large, using pointers we will ``waste'' less memory.
00127   <li> Finally, and probably the most important, using pointers the
00128 adress of the %objects in memory will remain the same, no matter
00129 whether we resize the vector or not. As mapobjects and %mapcharacter
00130 will further be referenced by their memory adress, using pointers here
00131 is mandatory if we want to keep this flexibility.
00132   </ol>
00133   On the other hand, we will be responsible for manually
00134 allocating/freeing our %objects, which will require additionnal
00135 attention.
00136 <li> The flexibility is maximal, as we can dynamically add/remove
00137 landsubmaps, mapobjects or mapcharacters. Beware, though, that the
00138 resizing of a vector can be time consuming.
00139 </ol>
00140 
00141 \subsection p10landsubmap The landsubmap class
00142 This class will be quite simple too. Actually, we will define a
00143 \e landsubmap as a vector of \e mapsquare_areas, which
00144 are the \e layers of this submap. On a simple map, the layer 0
00145 could for example be the ground, while the layer 1 will be a bridge:
00146 that way characters can safely walk on and under the bridge, it's just
00147 a matter of \e layer. All the problem will then be to define
00148 \e when does the characters switch from layer 0 to layer 1 and to
00149 layer 1 to layer 0 - but we will have a look at this later, so hang on
00150 ;).
00151 
00152 So our structure for \e landsubmap will be:
00153 \verbatim
00154 class landsubmap
00155 {
00156     vector<mapsquare_area> area;
00157 };
00158 \endverbatim
00159 
00160 Although things have quite quite simple until now, I fear the next
00161 sections will give you a little more headache.
00162 
00163 \subsection p10mapsquare_area The mapsquare_area class
00164 Serious matters starts now, as this class represents a bit more than
00165 arrays of things.
00166 
00167 First, it seems sensible that all areas on the map aren't necessarly
00168 the same size. Obviously, the ground will be larger than a bridge, so
00169 the different areas can be differently sized. That's why their
00170 position is precisely set by an \e offset, which sets which %mapsquare
00171 this area starts on. ONLY for the \e first %mapsquare_area (0 indexed)
00172 this offset parameter won't make sense, as others are placed
00173 relatively to this one. Also, the area indexed \e n must ALWAYS be
00174 higher than the one indexed \e n-1, for renderer performance reasons.
00175 
00176 %Mapsquare_areas will also have (excepted, once again, for the layer
00177 0) an altitude parameter. The layer will be drawn \e alt pixels higher
00178 than the ground layer, \e alt being the altitude of that layer. Also,
00179 having the altitude we can make characters fall from a layer to
00180 another and, why not, jump from a lower layer to an higher one if the
00181 %character can jump high enough.
00182 
00183 Apart from that, the %mapsquare_area will also contain a
00184 two-dimensional array of %mapsquares. Hang on for details about
00185 %mapsquares.
00186 
00187 \verbatim
00188 class mapsquare_area
00189 {
00190     vector<vector<mapsquare>> area;
00191 
00192     u_int16 xoffset;
00193     u_int16 yoffset;
00194     
00195     u_int16 altitude;
00196 };
00197 \endverbatim
00198 
00199 \subsection p10mapsquare The mapsquare class
00200 Although this class just represents a basic square of a level of a
00201 map, it's structure is much more complex than what we've seen until
00202 now.
00203 
00204 A %mapsquare contains informations about the following things:
00205 <ul>
00206 <li>The %mapobjects that are on it. Their number is virtually unlimited.
00207 <li>The %mapcharacters that are on it. Unlimited number of %mapcharacters
00208 too.
00209 <li>The walkability of this square. Actually, this information is
00210 indirectly determined from the %mapobjects that are on it (as
00211 %mapobjects have their own walkability information).
00212 </ul>
00213 
00214 The easiest way to handle such freedom in the number of %mapobjects
00215 and %mapcharacters that can be placed on a %mapsquare is to use a
00216 dynamic structure, the best candidate being a linked list.
00217 
00218 That's at this level that we have to think about rendering
00219 issues. Actually, there is only one, but huge issue: having in mind
00220 that some %objects are totally flat (carpets) and that they must then
00221 be drawn BEFORE %characters, while others (tree, houses) have an
00222 "height" and therefore must be drawn before the %characters that are
00223 in front of them, and after the characters that are behind them, how
00224 can we correctly handle that without making things too much complex
00225 and eating CPU time finding out what to draw before what? Having the
00226 %data structure well organised can deadly accelerate things by having
00227 simplier algorithms, and that's what we'll try to do with the
00228 %mapsquare class.
00229 
00230 As we only have two particular cases with %mapobjects (flat ones and
00231 non-flat ones), let's separate their %storage in memory: we'll have one
00232 list (not especially linked, as you will see after) for flat %objects,
00233 and another one for non-flat %objects. That way we can easily draw flat
00234 %objects before all.
00235 
00236 <b>Handling flat %objects</b>
00237 
00238 So, we have our list of flat %objects for this %mapsquare. But even if
00239 these %objects are flat, some can be upper than others, for example two
00240 carpets that superimposed on each others. Which one to draw first, the
00241 red or the blue? The renderer will perform as follows: it will first
00242 draw the first element of each %mapsquare, then perform another pass
00243 to draw the second, and so on until all "layers" are done. This has
00244 the following consequences:
00245 <ul>
00246 <li>The renderer have to perform one pass per "layer" of flat
00247 %objects. This is the price for having such freedom in %objects
00248 placement. 
00249 <li>We can add an additionnal information to the %mapsquare_area,
00250 about the number of layers of flat %objects it has. That way, the
00251 renderer won't have to perform a pass for nothing when we have drawn
00252 all the layers.
00253 <li>We can't reasonnably use a linked list for these %objects, as the
00254 renderer will perform the layer 0 of all mapsquares, then the layer
00255 1, etc. We need a container that has constant access time. A vector
00256 seems to be the best candidate here, as anyway it's size won't be
00257 changed, or very occasionally, and the reallocations won't be too huge
00258 (actually, they will rather be very small ones).
00259 </ul>
00260 
00261 <b>Handling non-flat %objects</b>
00262 
00263 With non-flat %objects it is ok to use linked lists, and the renderer
00264 will only have to perform one pass to draw the entire thing, non-flat
00265 %objects and %mapcharacters, provided the linked lists are correctly
00266 organized. The details about this will be discussed into the renderer
00267 section.
00268 
00269 \section p10dyn Map dynamic: how to make things move correctly
00270 
00271 \subsection p10levchan Handling characters map level change
00272 
00273 \section p10renderer Renderer details
00274 
00275 */

Generated on Mon Sep 12 2011 for Adonthell by  doxygen 1.7.1