Re: CF: object structure layout.

[Mark Wedel <mwedel@scruznet.com>]

Kjetil Torgrim Homme wrote:
> 
> [Mark Wedel]
> >    It is easy to do in O(p*m) time (n=players, m=other objects).  go
> >   through all the players, and then go through the map objects and
> >   see what is nearby.  But if p gets pretty large, this could be
> >   pretty slow - slower than just updating all objects on a map that
> >   has a player on it.
> 
> Clearly it will depend on the size of the map.  I think just
> _checking_ whether an object should be processed will not take that
> much less time than do all processing on it.  You also need to make
> sure that to objects adjacent to two players don't get processed twice
> (going to timestamps instead of speed_left will help this problem).
> However, if a more advanced scripting language is available for NPC's,
> the tradeoffs will change.  I say keep it simple until profiling shows
> gains to be had.

 I agree.    One advantage of localized updates is that very large maps would
not be as much a problem as they used to be (for example, you could have a
100x100 map, player starting at 0,0 with some monster of generator at 100,100. 
With localized updates, you could be sure that the creature doesn't start doing
anything until the player at least gets close.

 But in reality, you probably won't make such large maps, and if map tiling is
handled automatically, you could perhaps split that into 20x20 sections
(automatic map tiling would probably effectively make a virtual maps, some
things would move accross the exits seemlessly).

Steve Fink wrote:
> I guess I don't know the code well enough to guess what really needs to
> be optimized. But your scheme seems to do a lot of scanning of the f
> queue, then dequeueing and requeueing the ones within 5 ticks. Why not
> unify all those queues into a single queue with wait nodes separating
> them? So if you label actions as letters and wait nodes as numbers, the
> queue a-b-c-1-d-1-e-f-2-g would do actions a, b, and c on the next tick
> (dequeueing them) and dequeue the wait(1) node, then action d on the
> following tick, the e and f, then nothing (except decrementing the
> wait(2) node to a wait(1) node), then g.

 The number 5 was just a small number I chose for illustrative purposes.  In
reality, somethin around 20 would probably be about right (only have to examine
stuff once every 20 ticks, and few items would be so slow that they have more
than 20 tick action times (20 ticks = speed 0.05 or slower)

> 
> Except that this makes insertions O(n), so you'd want to keep a separate
> list of pointers to the wait nodes (in fact, you can take the wait nodes
> out of the main queue and keep them in the separate list, then do
> pointer comparisons to check for the wait nodes... but I digress.) Then
> insertions are O(k), where k is the number of contiguous "chunks" of
> events (equivalent to the number of queues in your scheme). (O(k) is
> deceptive, because it would actually take <5 pointer traversals for
> those first 5 chunks.) If that's a problem, you can reduce it to
> O(log(k)) by using an array in place of a linked list, putting
> timestamps (tickstamps?) in the array instead of wait counts, and
> calling bsearch() to find the insertion point. (Well, creating a new
> queue is still O(k), because you have to insert an element into the
> array, but that's a quick memcpy() on a small, cache-efficient list).

 But if you are going to have these different insertion marks with pointers to
where they are, why not just have these pointers be the queues themselves.  For
example, something like:

 void *queues[50]
 int queue_one=0;

 So the queueu you insert into is queue_one+tick_delay % 50.  Each tick, you
increase queue_one by one, and wrap at 50.

> 
> I would guess that the O(k) linear search would be fast enough. If not,
> maybe you can merge this scheme with yours by keeping a certain number
> of fixed queues (or pointers into the main queue) somehow. But you can't
> get any faster for dequeuing.

 In reality, the exact mechanism probably doesn't make a big difference -
systems are fast enough that list traversal isn't likely to be a big imposition
as long as the active and non active objects are separate.

 And the likely scenario is to not have global queues, and instead have the two
lists stored in the map object (for objects on that map - I'll have to think
about how to do objects in containers - a global queue may be needed for those,
because otherwise if a player leaves a map, you would have to search through the
entire map for the objects to to remove).  In reality, you only care about the
objects that have speed (objects with no speed could only be referanced from the
object and that would not pose any problem, but objects that do stuff need to
have some easier referance to see if they should be animated or not)

 But back to the lists per map:  Most maps don't have enough active objects that
having seperate lists is likely to make a big gain.  Some maps may have a coupl
hundred monsters - the things that add a lot of objects are things like spell
effects, but these tend to have fast enough speed that they go every tick or
every other tick, so multiple queues doesn't really help there.
-
[you can put yourself on the announcement list only or unsubscribe altogether
by sending an email stating your wishes to crossfire-request@ifi.uio.no]