Adonthell 0.4

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.

Specification

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

  • Unlimited number of submaps, that is different areas that can be connected to each others (ex. several rooms in a house),
  • Precise, pixel-unit based characters movments and objects placement,
  • Unlimited number of possible levels, to allow things like bridges and so on,
  • Altitude management through 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,
  • No limit about the number of objects that can be placed on the maps, no matter if they are all at the same place,
  • 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,
  • 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.
  • Finally, the rendering must be realistic, bug-free of course, but should remain as fast as possible.

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! :)

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.

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:

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); 
}; 

The operators let you easily compare two coordinates. A coordinate is superior to another if it's y is superior, or it's x, or it's oy, or it's 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.

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 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 landmap owns. So the structure of the landmap class is as simple as this:

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

Using such a structure, we have the following advantages:

  1. 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:
    1. 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.
    2. 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.
    3. 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.
    On the other hand, we will be responsible for manually allocating/freeing our objects, which will require additionnal attention.
  2. 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.

The landsubmap class

This class will be quite simple too. Actually, we will define a landsubmap as a vector of mapsquare_areas, which are the 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 layer. All the problem will then be to define 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 landsubmap will be:

class landsubmap
{
    vector<mapsquare_area> area;
};

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

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 offset, which sets which mapsquare this area starts on. ONLY for the first mapsquare_area (0 indexed) this offset parameter won't make sense, as others are placed relatively to this one. Also, the area indexed n must ALWAYS be higher than the one indexed 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 alt pixels higher than the ground layer, 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.

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

    u_int16 xoffset;
    u_int16 yoffset;
    
    u_int16 altitude;
};

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:

  • The mapobjects that are on it. Their number is virtually unlimited.
  • The mapcharacters that are on it. Unlimited number of mapcharacters too.
  • 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).

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.

Handling flat objects

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:

  • The renderer have to perform one pass per "layer" of flat objects. This is the price for having such freedom in objects placement.
  • 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.
  • 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).

Handling non-flat objects

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.

Map dynamic: how to make things move correctly

Handling characters map level change

Renderer details