[CF-Devel] O(n^2) hit-map

Mark Wedel mwedel at scruz.net
Thu Jan 4 01:53:09 CST 2001


 For the most part, stacking with insert_ob_in_map doesn't really need to worry
about stacking.

 And you are correct in that we could stack things by things like spells,
objects/monsters, floors, and then the stuff below floors.  That would work a
little better.

 But as I think about it, another problem area is still with the update_map_look
logic - it will probably still have to go through all the objects on the space,
and I think it still does it pretty stupidly (basically, anytime something is
inserted in the space, it re-does what the map should look like).  So fixing
insert_ob... doesn't really help out that out much.

 One of the things I do want to do is change that so that instead the map has a
flag for each space if it needs to update the look of the space.  Then when
weare about to send a space on the map to the player, we see if that is set, and
if so, update the look then.  That at least will reduce the number of looks to
at most once per tick, and doesn't have us update the look for spaces outside
the players view (which can be many of those).  However, I think that function
also does other think, like update the flags (blocked on so on).  But that can
probably get done more intelligently (if were adding an object, see if it has
any flags that are not set, and if so, set them.  IF removing an object, we
would still need to search the entire stack until we get another object with the
same flag (I'm thinking of the P_ flags, like blocksview, alive, etc). 
Fortunately, I don't think the fireballs have any of those set, and that is
really where the performance gets costly.)

 I was putting off the update of the map view to once a tick for version 2.0. 
But that may be easier to do, and may improve the performance a bit right now -
that at least removes one major calculation.

 One of the current issues is that the insert ob stuff tries to put players and
monsters on top so they are more visible, as they are more important objects. 
But since there are now visibility flags, that may not be as important, as when
it figures out the spaces, it would figure out what should be most visible at
that point.

    
    


More information about the crossfire mailing list