Adonthell 0.4
|
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 */