Adonthell
0.4
Main Page
Related Pages
Classes
Files
File List
File Members
newmap.dxt
Go to the documentation of this file.
1
/*
2
$Id: newmap.dxt,v 1.4 2002/04/07 09:51:28 ksterker Exp $
3
4
Copyright (C) 2001 Alexandre Courbot
5
Part of the Adonthell Project http://adonthell.linuxgames.com
6
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.
11
12
See the COPYING file for more details.
13
*/
14
15
/**
16
* @file newmap.dxt
17
*
18
* @author Alexandre Courbot <alexandrecourbot@linuxgames.com>
19
* @brief Specifications for the new mapengine.
20
*/
21
22
/*!
23
\page newmap Specifications for the new mapengine.
24
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.
28
29
\section p10spec Specification
30
What we want is a flexible, powerfull map engine that allows the
31
following things:
32
33
<ul>
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
37
placement,
38
<li> Unlimited number of possible \e levels, to allow things like
39
bridges and so on,
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.
53
</ul>
54
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.
58
59
... All the problem will now be to stand on these specifications! :)
60
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.
67
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:
71
72
\verbatim
73
class mapcoordinates
74
{
75
public:
76
u_int16 x, y;
77
u_int16 ox, oy;
78
79
bool operator < (const mapcoords & mc);
80
bool operator <= (const mapcoords & mc);
81
bool operator > (const mapcoords & mc);
82
bool operator >= (const mapcoords & mc);
83
};
84
\endverbatim
85
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
91
good and fast result.
92
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.
99
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:
103
104
\verbatim
105
class landmap
106
{
107
vector<landsubmap*> submap;
108
vector<mapcharacter*> mapchar;
109
vector<mapobject*> mobj;
110
};
111
\endverbatim
112
113
Using such a structure, we have the following advantages:
114
115
<ol>
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:
119
<ol>
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
123
pointers.
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.
132
</ol>
133
On the other hand, we will be responsible for manually
134
allocating/freeing our %objects, which will require additionnal
135
attention.
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.
139
</ol>
140
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
150
;).
151
152
So our structure for \e landsubmap will be:
153
\verbatim
154
class landsubmap
155
{
156
vector<mapsquare_area> area;
157
};
158
\endverbatim
159
160
Although things have quite quite simple until now, I fear the next
161
sections will give you a little more headache.
162
163
\subsection p10mapsquare_area The mapsquare_area class
164
Serious matters starts now, as this class represents a bit more than
165
arrays of things.
166
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.
175
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.
182
183
Apart from that, the %mapsquare_area will also contain a
184
two-dimensional array of %mapsquares. Hang on for details about
185
%mapsquares.
186
187
\verbatim
188
class mapsquare_area
189
{
190
vector<vector<mapsquare>> area;
191
192
u_int16 xoffset;
193
u_int16 yoffset;
194
195
u_int16 altitude;
196
};
197
\endverbatim
198
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
202
now.
203
204
A %mapsquare contains informations about the following things:
205
<ul>
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
208
too.
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).
212
</ul>
213
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.
217
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
228
%mapsquare class.
229
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
234
%objects before all.
235
236
<b>Handling flat %objects</b>
237
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:
245
<ul>
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
248
placement.
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
252
all the layers.
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).
259
</ul>
260
261
<b>Handling non-flat %objects</b>
262
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
267
section.
268
269
\section p10dyn Map dynamic: how to make things move correctly
270
271
\subsection p10levchan Handling characters map level change
272
273
\section p10renderer Renderer details
274
275
*/
newmap.dxt
Generated by
1.8.1.1