James Paige wrote:
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
I was thinking about that... But, truthfully, 95% of the time I would
want to know how many children there are, I simply want to enumerate
over them anyway. But, I suppose it doesn't hurt.
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
Let me check in my Networking module for HamsterSpeak then!
... Actually, that would be kickass, if a bit impractical.
_______________________________________________
Ohrrpgce mailing list
ohrrpgce@lists.motherhamster.org
http://lists.motherhamster.org/listinfo.cgi/ohrrpgce-motherhamster.org
