[Adonthell-devel] More map view ideas, nothing definite yet ...

[Kai Sterker]

Am 03.04.2008 um 15:07 schrieb Kai Sterker:

> Some of today's brainstorming: hope it makes at least a little bit  
> of sense :-).

Nice try, but too many problems ... so here is another go :-).

Lets start simple, with what we need for rendering an object visible  
in a map view:

* Its "base point", i.e. the location at which it needs to be drawn.
* Its position and size, so that we know when it intersects with the  
map view.
* Its z position, for the order in which to draw overlapping objects.

All that information is available when placing objects on the map, we  
only need to get it into a structure that is efficient for rendering.

One additional thing: we need to be able to split horizontal, non- 
solid objects around vertical objects. Since vertical objects (like  
characters) may change their position, this needs to happen  
dynamically. Here's a picture showing what I mean:

In this case, the water tile is split just once, but imagine rocks or  
trees growing in the riverbed and you can easily see, that multiple  
splits might be required ... although in case of static objects, they  
could possibly be calculated in advance.

How do we find the location for the split(s)? We're drawing from the  
top, and the base point of flat tiles is the top left corner. So if  
we find a non-solid object s (we need a flag to indicate this), we  
need to check if s will intersect with vertical objects. For that, we  
need to check the range y + z to y + height + z if there exists an  
object o whose base point is in that range and in the bottom right  
corner of o (= it's a vertical object). We then split s at o.base_y -  
s.height (- s.y to get the position relative to the size of s).

We can draw the first part of s at once, but any subsequent parts  
need to be drawn after o is drawn. So we also need a way to remember  
such parts and when to draw them.

This seems to cry for something like the zone_info class from my  
previous mail (a little modified):

>   class zone_info
>   {
>     ...
>   private:
>     // the map object represented by this zone_info object
>     placeable *obj;
>
>     // base point of object, negative if outside zone, but crossing  
> border
>     s_int32 x, y;
>     // extension of object from base point (negative for vertical  
> objects)
>     s_int16 width, height;
      // define which part of the object to draw
      drawing_area part;
      // remove after rendering
      bool temporary;
>   };

Maybe better call it draw_info, but it could easily be instantiated  
for each section of our non_solid object s and added to the proper  
position of the map view structure (which would consist of draw_info  
objects). An additional flag makes sure it will be cleaned up once it  
has been rendered.

Now we still do not know how the map view structure itself should  
look like. The requirements would be:

* Need to easily find all objects part of the map view, especially  
those overlapping borders of the view.
* Need to efficiently determine the order in which to draw objects.

A grid-based approach we have now seems the easiest way to find  
overlapping objects. The drawing order could be established most  
easily by a pixel-based matrix, where objects are added according to  
their base point. If multiple objects have the same base point  
location, their z coordinate would determine rendering order. Given  
such a matrix, we'd only need to go from left to right, top to bottom  
to draw stuff. Since we'd only have a few dozen objects in a map view  
sized area, the matrix would be pretty sparse, so it would probably  
be best represented by ... tada! ... a quadtree. Now that's an area  
where I have exactly zero expertise, so some more reading is required.

The basic question is: does traversing the tree return objects in the  
order we need to draw them? I somehow doubt it. However, quadtrees  
seem to be quite efficient when it comes to figuring out which  
rectangles (our objects) are contained in another rectangle (our map  
view).

So would it make sense to have zones of our maps represented by  
quadtrees?
From those we'd figure out objects contained in a view and store  
them in an array according to their drawing order.


Now, something else comes into my mind: how about changing the grid- 
based map we have now to an octree instead? That could just as well  
be used to find the objects required for collision detection and it  
could also help finding the objects required for rendering without  
having to keep those in two different data structures. Here is why:

In our isometric view, 1 pixel of height translates into one pixel of  
depth. That is, an object 10px above the ground (z-axis) is  
translated 10px along the y-axis. So if we have a map view at  
position x,y and size l,w we now can find objects with height h that  
will be visible in our mapview by searching in our octree at h,  
position x,y-h and size l,w.

Again, this is a data structure I know nothing about, so it remains  
to be determined whether that second proposition could be done  
efficiently (especially since we do not know the maximum height h).  
OTOH, if we did know maximum (and minimum height) of a certain area,  
we could use the same method to find the required objects in our grid  
structure too.


More thinking required, but perhaps laying down my thoughts sparks  
some ideas in somebody else :-).

Kai