[Adonthell-devel] Re: Flaws in the current map implementation

[Kai Sterker]

On Thu, Apr 3, 2008 at 12:27 PM, Kai Sterker <address@hidden> wrote:

>  We'd also be free to decide which data structure would be best for
>  rendering. The grid makes sense for path finding and collision
>  detection, but maybe there's something more suitable to render
>  objects.

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

Base point of

  * flat objects:    * vertical objects:

    o--+               +--+
    |  |               |  |
    +--+               +--o

Data structure ('o' represents single object):

  o->o->o->...
  v  v  v
  o  o  o
  ...

  Each object has pointers to next object to the left and to the
bottom, in the order they need to be rendered.

Data structure implementation:

  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;

    // points to object of = y, >= x
    zone_info *right;
    // points to object of > y, <= x
    zone_info *down;
  };

Rendering algorithm:

  // from top left corner, find our way to the mapview start
  zone_info *zi = zone::head
  while max (zi->x, zi->x + zi->width) < mapview.x: zi = zi->right;
  while max (zi->y, zi->y + zi->height) < mapview.y: zi = zi->down;

  while min (zi->y, zi->y + zi->height) < mapview.y + mapview.height:
    zone_info *tmp = zi;
    while min (zi->x, zi->x + zi->width) < mapview.x + mapview.width:
      render tmp->obj
      tmp = tmp->right

    // next line
    zi = zi->down

Consequences:

* there will be as many 'lines' as there are different y values. this
is to prevent "merging" of lines which would lead to infinite loop.

* some unresolved issues. Consider some flat objects:

  o-----+   o---+
  |     --->|   |
  +--|--+   |   |
 ....|......|   |........
 :   v      +-|-+
 : o----+     v
 : |    --->o---+
 : +----+   +---+
 :

We may miss objects that are further into a line and extend into the
view if previous objects don't.

* Similar problem for vertical objects, but at the right and bottom
sides of the map view.


Alternative:

Maybe use map view itself as a cache of objects to be rendered.
Initialize once (costly as we go over complete zone to pick all
objects intersecting with the map view. Then only do incremental
changes along the edges as the view moves. But what about characters,
which move too?

Kai

P.S: I'll be on the road the next couple days. Notebook is with me,
but net access might not be around. Ideas are welcome ... missing the
great discussions we used to have here :-(.