On Thu, Oct 02, 2008 at 12:37:04PM -0400, Mike Caron wrote: > James Paige wrote: > >On Thu, Oct 02, 2008 at 12:04:47PM -0400, Mike Caron wrote: > >>James Paige wrote: > >>>So I am going to start work on the rectangle interface... > >>> > >>>SUDDEN VOCABULARY CHANGE! > >>> > >>>Actually, I think I will start using the term "slice" as S'orlok coined > >>>for the FMF. I am not sure that my plan is exactly analogous to his > >>>slices, but I think it is pretty darn close, and it is less ambigious > >>>than "rectangle interfaces" > >>> > >>>So anyway, I need to maintain a tree of slices. FreeBasic is sadly > >>>missing a good data type for trees. Now I could hack together a tree of > >>>pointers, but you know how that makes me weep. Besides, I really want to > >>>make FreeBasic do my memory allocation with REDIM I don't want to do it > >>>myself. > >>> > >>>So I am thinking I will have a one dimentional array of slices. Each > >>>slice will have a property which indicates its parent, and a property > >>>which indicates how many children it has. This is a little > >>>bit like how the menu items are stored, with the difference that this > >>>will be a depeer tree than just one level. > >>> > >>>So I will sort this tree when elements are inserted or deleted. That > >>>does mean a lot of work-- but really this sorting will have to happen at > >>>some point no matter what, since we have to get z-order correct for > >>>drawing. So I think it is better to sort the tree when slices are added, > >>>removed, or moved, which will happen far less often than the drawing > >>>cycle. > >>> > >>>So the first element in this array will always be the root slice. It > >>>will have (by default) five child slices, map slice, scriptsprite > >>>slice, textbox slice, menu slice, scriptstring slice in that order. > >>> > >>>The camera code would be updated to move the x,y position of the map > >>>slice relative to the root slice > >>> > >>>The map slice will have six child slices, the map layer 0 slice, map > >>>layer 1 slice, npc&hero slice, map layer 2 slice, overhead backcompat > >>>slice, and the harm tile flash slice. > >>> > >>>The map layer slices will have a "type" property which indicates that > >>>they draw map tile layers > >>> > >>>The npc&hero slice will have two child slices, the npc slice and the > >>>hero slice, and their order will depend on the general map bitset that > >>>controls hero-vs-npc layering. > >>> > >>>To begin with, these slices can simply be of a type that instructs the > >>>slice drawing code to draw all the NPCs or heroes using pretty much > >>>exactly the same NPC and hero drawing code that exists now. > >>> > >>>In the future, these npc and hero slices could be changed to have child > >>>slices which would be generic sprite slices representing each NPC and > >>>hero. For example, The npc layer will have 300 child slices, one for > >>>each NPC reference. These slices will replace the .x and .y members of > >>>the current array of NPCInst, and all the current code to move NPCs > >>>would just reference these slices instead (to do this efficiently, the > >>>slice tree sorting code would have to notice and save the index of the > >>>NPC slice, so the child NPC sprite slices could be found quickly > >>>without needing a search each time) > >>> > >>>Anyway, everything that has an x/y position would be moved into the > >>>slice tree. Drawing of all layers would be unified, and easy to extend > >>>and manipulate. We could have generic plotscripting functions that > >>>re-order or re-parent slices. Existing commands, like the ones to move > >>>plot strings, or the ones to move custom menus, or the ones mike > >>>just implemented for scriptsprites would all remain the same to > >>>plotscripters, but internally their implementations would be moving > >>>slices relative to their natural parents. > >>> > >>>The slice tree sorter would update a table of indexes into the slice > >>>array that mark various important standard slices, so that other code > >>>can find these slices quickly without having to search the slice tree. > >>> > >>>Comments? > >>This seems like a pretty good plan. However, there is one thing that I > >>need to ask: > >> > >>Let's say I add sprite A, and get a handle to it. Since I put it on the > >>hero and NPC slice, it's somewhere in the middle of the pile. Now, let's > >>say I add another sprite, sprite B, which is on Layer 0. The resort then > >>puts sprite B before sprite A, and since numbers have the irritating > >>property of being consecutive, sprite A is no longer at the same ordinal > >>as it was before, giving it a new handle, and rendering my old handle > >>invalid. > >> > >>Or, am I missing something? > > > >No, that is a very valid point. The sorted-tree-in-a-linear-array > >approach has the disadvantage that you have to have a sceme to update > >your handles. That table of magical slices that gets updated when the > >tree storage re-sorts is basically a table of handles, they just happen > >to be handles used by the engine internally rather than handles used by > >plotscripts. > > > >However, I think that problem can be solved by indirecting plotscript > >slice handles through a similar table which will also be updated at sort > >time. > > > >If all this slice handle updating sounds daunting, fear not. There will > >be good ways to optimize the sort. For example, when a slice moves, only > >the parent slice needs to be re-sorted, which will be pretty easy to do > >since the tree is always sorted already. And after a sub-tree has > >changed size through the addition or deletion of a child, the rest of > >the handles can be updated by +1 or -1 to anything > the end of the > >slice that just got sorted. > > > >But honestly, this is all complicated. Would it be more complicated than > >a tree built from *shiver* pointers? > > > >I'm not sure. I guess I need to give some more thought to a pointer > >tree, so I can fairly compare the two options. > > Well, the main point against pointers is that you want to avoid passing > pointers to plotscripts, since that's just inviting trouble. However, a > way around it would be to store the pointers in a table, and pass the > index, much like existing solutions (the plotsprites, for example, are a > good example) > > One large problem we have to keep in mind, though, is that we'll be > going both up and down the tree: Drawing will be bottom up, while > manipulation is top down. So, for maximum efficiency, we should keep > references to both parents and (I can hear the gasp coming...) children. > > To do so is complex, yes, but it would make everything so much easier, > and not require sorting. How I would do it is like this: > > Type Slice > Parent as Slice Ptr > Children as Slice Ptr Ptr > NumChildren as Integer > 'whatever else > End Type > > So, by default, .Children is null, indicating that there's no children. > .Parent works as expected, pointing at the parent. For the root node, > this will be null. > > When we need to add a child to a slice, we do something like this: > > Function AddChildSlice(parent as Slice ptr) as slice ptr > 'check parent for null and validity > dim found as integer > for i as integer = 0 to parent->NumChildren - 1 > if parent->Children[i] = 0 then > found = YES > exit for > end if > next > > if not found then > GrowChildren(parent) 'add error checking here, in case of mem error > end if > > dim child as Slice ptr = new Slice > parent->Children[i] = child > child->Parent = parent > 'whatever else we need to do > > return child > end function > > The GrowChildren function, as it says on the tin, grows the number of > children a slice can have. > > So, to draw this tree, we recurse from the root node, and follow > children. To move a slice, we remove the child from the parent, change > the parent to a new parent, and add the child to the new parent. Easier > done than said, really.
Wow. that above code makes me shiver. Granted it will be bad either way, and no matter what implementation we choose, we will need to work hard to wrap the uglyness into functions so that some bright day when FreeBasic implements a real tree-suitable container datatype like other languages have we will be able to easily retrofit this mess to use the new simpler data type. > Type Slice > Parent as Slice Ptr > Children as Slice Ptr Ptr > NumChildren as Integer > 'whatever else > End Type About this part. Wouldn't it be easier to do: Type Slice Parent as Slice Ptr FirstChild as Slice Ptr NextSibling as Slice Ptr PrevSibling as Slice Ptr NumChildren as Integer 'whatever else End Type I think that would eliminate the need for GrowChildren() --- James Paige _______________________________________________ Ohrrpgce mailing list ohrrpgce@lists.motherhamster.org http://lists.motherhamster.org/listinfo.cgi/ohrrpgce-motherhamster.org
