On Thu, Oct 02, 2008 at 12:58:22PM -0400, Mike Caron wrote: > James Paige wrote: > >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() > > That would work too, at the expense of slightly more complex code. > Actually, in this case, you likely wouldn't need NumChildren any more, > since to append a new child, you navigate to the first child, and then > navigate to the end of the linked list. Or, hell, append it in the front > for all it matters.
keeping NumChildren could just be an optimization so that if you wanted to know the count, the work could be done at add/remove time rather than at request-time > It occurs to me that we're duplicating work ;) > http://www.w3.org/TR/2003/WD-DOM-Level-3-Core-20030226/DOM3-Core.html#core infinity cool-points for the first person to re-implement the OHRRPGCE in javascript. infinity+1 cool-points for the first person to implement a W3C compliant web browser in HamsterSpeak --- James _______________________________________________ Ohrrpgce mailing list ohrrpgce@lists.motherhamster.org http://lists.motherhamster.org/listinfo.cgi/ohrrpgce-motherhamster.org
