2 $Id: newmap.dxt,v 1.4 2002/04/07 09:51:28 ksterker Exp $
4 Copyright (C) 2001 Alexandre Courbot
5 Part of the Adonthell Project http://adonthell.linuxgames.com
7 This program is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License.
9 This program is distributed in the hope that it will be useful,
10 but WITHOUT ANY WARRANTY.
12 See the COPYING file for more details.
18 * @author Alexandre Courbot <alexandrecourbot@linuxgames.com>
19 * @brief Specifications for the new mapengine.
23 \page newmap Specifications for the new mapengine.
25 This document will precisely describe the specifications/internals of
26 the new map engine implementation that is supposed to be shipped with
27 versions >= 0.4 of the Adonthell engine.
29 \section p10spec Specification
30 What we want is a flexible, powerfull map engine that allows the
34 <li> Unlimited number of \e submaps, that is different areas that
35 can be connected to each others (ex. several rooms in a house),
36 <li> Precise, pixel-unit based %characters movments and %objects
38 <li> Unlimited number of possible \e levels, to allow things like
40 <li> Altitude management through \e levels. A %character must be
41 able to fall from a bridge to the ground. A %character must also be
42 able to naturally climb stairs, for example,
43 <li> No limit about the number of %objects that can be placed on the
44 maps, no matter if they are all at the same place,
45 <li> %Objects and %characters must have the possibility to be
46 animated. Furthermore, the ways of animations must be very flexible,
47 allowing from very-simple to very-complex animations,
48 <li> %Characters animations should be most flexible. In particular, a
49 %character can have an unlimited number of special animations (jumping,
50 falling,...) that may be unique to him.
51 <li> Finally, the rendering must be realistic, bug-free of course,
52 but should remain as fast as possible.
55 The above have been written with the ideas of speed, flexibility and
56 minimized ressource usage in mind. No pig-solution can pretend to be a
57 viable solution for the implementation.
59 ... All the problem will now be to stand on these specifications! :)
61 \section p10imp Implementation proposal
62 Of course, our implementation will have to be well structured to be
63 viable. Such demanding specifications implies that the proposed
64 solution remains simple in it's parts, even if complex in it's
65 whole. That's why this section is highly hierarchised. We'll try to
66 describe the implementation from the higher layer to the lowest one.
68 \subsection mapcoord_class The mapcoordinates class
69 Not much to say about this one. It represents the position of any
70 object on the map, with the tile it is on and an offset from this tile:
79 bool operator < (const mapcoords & mc);
80 bool operator <= (const mapcoords & mc);
81 bool operator > (const mapcoords & mc);
82 bool operator >= (const mapcoords & mc);
86 The operators let you easily compare two coordinates. A coordinate is
87 superior to another if it's \e y is superior, \b or it's \e x, \b or
88 it's \e oy, \b or it's \e ox (in this order). They should be mostly
89 used when you need to sort lists of objects - rendering, for example,
90 will need the objects to be sorted by coordinates in order to have a
93 \subsection p10landmap The landmap class
94 This class contains the entire map, as well as the elements
95 (%characters, %objects) that are on it. It may or may not contains the
96 \e graphical %data of these %objects - anyway it is of no importance
97 for it as it's job is only to make the world it represents live - and
98 in no way to render it.
100 At this level, we only need the submaps, (map)%characters and
101 (map)%objects this \e %landmap owns. So the structure of the
102 \e %landmap class is as simple as this:
107 vector<landsubmap*> submap;
108 vector<mapcharacter*> mapchar;
109 vector<mapobject*> mobj;
113 Using such a structure, we have the following advantages:
116 <li> The number of landsubmaps, mapcharacters and mapobjects are
117 unlimited, and the allocated memory will exactly reflect the actual
118 number of them used. We are using pointers here for several reasons:
120 <li> The vector container needs to perform copies when resized. As
121 we don't want our whole structures to be copied (which would be very
122 slow and would need a tricky copy-constructor) we are using arrays of
124 <li> Sometimes (depending on the implementation) the actual size of the vector is larger than the
125 number of elements that are inside it, to perform faster growings. As
126 our classes are rather large, using pointers we will ``waste'' less memory.
127 <li> Finally, and probably the most important, using pointers the
128 adress of the %objects in memory will remain the same, no matter
129 whether we resize the vector or not. As mapobjects and %mapcharacter
130 will further be referenced by their memory adress, using pointers here
131 is mandatory if we want to keep this flexibility.
133 On the other hand, we will be responsible for manually
134 allocating/freeing our %objects, which will require additionnal
136 <li> The flexibility is maximal, as we can dynamically add/remove
137 landsubmaps, mapobjects or mapcharacters. Beware, though, that the
138 resizing of a vector can be time consuming.
141 \subsection p10landsubmap The landsubmap class
142 This class will be quite simple too. Actually, we will define a
143 \e landsubmap as a vector of \e mapsquare_areas, which
144 are the \e layers of this submap. On a simple map, the layer 0
145 could for example be the ground, while the layer 1 will be a bridge:
146 that way characters can safely walk on and under the bridge, it's just
147 a matter of \e layer. All the problem will then be to define
148 \e when does the characters switch from layer 0 to layer 1 and to
149 layer 1 to layer 0 - but we will have a look at this later, so hang on
152 So our structure for \e landsubmap will be:
156 vector<mapsquare_area> area;
160 Although things have quite quite simple until now, I fear the next
161 sections will give you a little more headache.
163 \subsection p10mapsquare_area The mapsquare_area class
164 Serious matters starts now, as this class represents a bit more than
167 First, it seems sensible that all areas on the map aren't necessarly
168 the same size. Obviously, the ground will be larger than a bridge, so
169 the different areas can be differently sized. That's why their
170 position is precisely set by an \e offset, which sets which %mapsquare
171 this area starts on. ONLY for the \e first %mapsquare_area (0 indexed)
172 this offset parameter won't make sense, as others are placed
173 relatively to this one. Also, the area indexed \e n must ALWAYS be
174 higher than the one indexed \e n-1, for renderer performance reasons.
176 %Mapsquare_areas will also have (excepted, once again, for the layer
177 0) an altitude parameter. The layer will be drawn \e alt pixels higher
178 than the ground layer, \e alt being the altitude of that layer. Also,
179 having the altitude we can make characters fall from a layer to
180 another and, why not, jump from a lower layer to an higher one if the
181 %character can jump high enough.
183 Apart from that, the %mapsquare_area will also contain a
184 two-dimensional array of %mapsquares. Hang on for details about
190 vector<vector<mapsquare>> area;
199 \subsection p10mapsquare The mapsquare class
200 Although this class just represents a basic square of a level of a
201 map, it's structure is much more complex than what we've seen until
204 A %mapsquare contains informations about the following things:
206 <li>The %mapobjects that are on it. Their number is virtually unlimited.
207 <li>The %mapcharacters that are on it. Unlimited number of %mapcharacters
209 <li>The walkability of this square. Actually, this information is
210 indirectly determined from the %mapobjects that are on it (as
211 %mapobjects have their own walkability information).
214 The easiest way to handle such freedom in the number of %mapobjects
215 and %mapcharacters that can be placed on a %mapsquare is to use a
216 dynamic structure, the best candidate being a linked list.
218 That's at this level that we have to think about rendering
219 issues. Actually, there is only one, but huge issue: having in mind
220 that some %objects are totally flat (carpets) and that they must then
221 be drawn BEFORE %characters, while others (tree, houses) have an
222 "height" and therefore must be drawn before the %characters that are
223 in front of them, and after the characters that are behind them, how
224 can we correctly handle that without making things too much complex
225 and eating CPU time finding out what to draw before what? Having the
226 %data structure well organised can deadly accelerate things by having
227 simplier algorithms, and that's what we'll try to do with the
230 As we only have two particular cases with %mapobjects (flat ones and
231 non-flat ones), let's separate their %storage in memory: we'll have one
232 list (not especially linked, as you will see after) for flat %objects,
233 and another one for non-flat %objects. That way we can easily draw flat
236 <b>Handling flat %objects</b>
238 So, we have our list of flat %objects for this %mapsquare. But even if
239 these %objects are flat, some can be upper than others, for example two
240 carpets that superimposed on each others. Which one to draw first, the
241 red or the blue? The renderer will perform as follows: it will first
242 draw the first element of each %mapsquare, then perform another pass
243 to draw the second, and so on until all "layers" are done. This has
244 the following consequences:
246 <li>The renderer have to perform one pass per "layer" of flat
247 %objects. This is the price for having such freedom in %objects
249 <li>We can add an additionnal information to the %mapsquare_area,
250 about the number of layers of flat %objects it has. That way, the
251 renderer won't have to perform a pass for nothing when we have drawn
253 <li>We can't reasonnably use a linked list for these %objects, as the
254 renderer will perform the layer 0 of all mapsquares, then the layer
255 1, etc. We need a container that has constant access time. A vector
256 seems to be the best candidate here, as anyway it's size won't be
257 changed, or very occasionally, and the reallocations won't be too huge
258 (actually, they will rather be very small ones).
261 <b>Handling non-flat %objects</b>
263 With non-flat %objects it is ok to use linked lists, and the renderer
264 will only have to perform one pass to draw the entire thing, non-flat
265 %objects and %mapcharacters, provided the linked lists are correctly
266 organized. The details about this will be discussed into the renderer
269 \section p10dyn Map dynamic: how to make things move correctly
271 \subsection p10levchan Handling characters map level change
273 \section p10renderer Renderer details