[Top][All Lists]
[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
[Adonthell-devel] More map view ideas, nothing definite yet ...
From: |
Kai Sterker |
Subject: |
[Adonthell-devel] More map view ideas, nothing definite yet ... |
Date: |
Wed, 16 Apr 2008 17:41:36 +0200 |
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
- [Adonthell-devel] Flaws in the current map implementation, Kai Sterker, 2008/04/01
- [Adonthell-devel] Re: Flaws in the current map implementation, Kai Sterker, 2008/04/02
- [Adonthell-devel] Re: Flaws in the current map implementation, Kai Sterker, 2008/04/03
- [Adonthell-devel] More map view ideas, nothing definite yet ...,
Kai Sterker <=
- Re: [Adonthell-devel] More map view ideas, something definite finally?, Kai Sterker, 2008/04/16
- Re: [Adonthell-devel] More map view ideas, something definite finally?, James Nash, 2008/04/16
- Re: [Adonthell-devel] More map view ideas, something definite finally?, Kai Sterker, 2008/04/16