#9080 - eustace - Mon Jul 28, 2003 4:02 am
Some co-workers and I are gonna team up and spend some leisure time dev'ing for the gba. As I was laying out the design of the game's engine, I was playing with the idea of using (packed) R-trees for managing the world layout of each level. i.e. item, enemy, etc placement and possibly even the bg tilemap's representation. This would seem to give some efficient collision-detection methods for the item's tree, as well as a suitable (static) rep of a bg.
While the use of such a tree for the items may be intuitive, the reasoning for the use of one for bg's has to do w/ the fact that the many repititious tiles could be reduced to single tile objects representing a certain tile and the total area it occupies (within an area).
At any rate, I was just wondering what others thought regarding the efficiency and plausability of such schemes for the gba before I go any further. This is our first project of this type so we are at this time just exploring different ideas and limits.
thanks-->
#9418 - funkeejeffou - Mon Aug 04, 2003 1:29 pm
I've been working with trees(binary ones) and when dealing with this type of data, it always means a recursive code or at least a "recursivity" of code.
When you traverse a tree, your stack will be sollicited continouesly as your code will make a lot of push and pop instructions. The stack on the GBA is located at the end of IWRAM and is full descending, if you keep pushing on it, you'll override at a moment your own data(if there is data in IWRAM) or you'll get out of the IWRAM size limit(if you push more than 32Kb of variables). Of course, this is an extreme case.
But what I mean is that if you have a tree containing 3000 nodes, and that you find yourself in a "worst case" where the first leaf is reached after traversing 1500 nodes, and that for each node traversed you have to push 12 bytes of variables, then your code will have pushed 17,6 Kb of data on the stack before beginning any pop instructiun. So if you had 20 Kb of data in IWRAM, then some of your data will be overwritten (as 32Kb -20Kb = 12 Kb free and 17,6Kb>12Kb :-) and your program will certainly freeze or get crazy before freezing.
What I mean is that when dealing with trees on GBA, you must always look at the worst case concerning your tree and store data in IWRAM in consequence to it so that there won't be any overlap. In the old days where dos was used, the stack couldn't be greater than 64Kb, stack has always been a problem (except for windows programming as they use the hard disk to keep pushing, wich sucks for realtime speedy software).
As stack is in the fastest RAM (1 wait sate in read/write for 8bit/16bit/32bit variables), trees are efficient if they are well used, but require a lot of attention as stack can share the same memory location of you IWRAM data.
I don't know if I understood well your question but hope this helps.
#9423 - Touchstone - Mon Aug 04, 2003 3:49 pm
| funkeejeffou wrote: |
| When you traverse a tree, your stack will be sollicited continouesly as your code will make a lot of push and pop instructions. |
That's why you would choose data recursion instead of code recursion.
_________________
You can't beat our meat
#9438 - tom - Mon Aug 04, 2003 9:29 pm
hah, just place your stack in ewram, and you're set =)
#9440 - funkeejeffou - Mon Aug 04, 2003 9:59 pm
Yes, but I think that anybody who uses tree structures in a game's code will also want speed. As the ARM7TDMI registers are 32 bits long, and a waitstate in EWRAM is 6 cycle long for a 32 bits variable; you can image how the traversal of your tree will be affected. Better well balance the tree (no disproportionned subtree) and optimize the number of parameters to push so that you can keep the stack in IWRAM.
Of course that's my choice because my tree traversal must execute very quickly if I wanna have a descent framerate.
#9454 - tom - Tue Aug 05, 2003 10:38 am
funkeejeffou : i know, i know, i was just joking =)
#9459 - col - Tue Aug 05, 2003 1:34 pm
why not just walk the tree using an non-recursive traversal algorithm?
cheers
col
#9487 - eustace - Wed Aug 06, 2003 4:31 am
thanks guys for your insights - definitely some things to keep in mind (regarding recursive calls and the stack).
however, im not sure if you're familiar w/ the R-tree structure or not, but it's basically a height-balanced extended variant of the b-tree, of which they both are of the larger family of multi-way trees. the point is, being that r-tree's are aimed at spatial partitioning (usually very handy for databases, geographic representations [think mapquest] and such), any given tree will have a very shallow depth. for instance, a pentium 4 chip, with about 42 million transistors in its spatial 2d layout, could be represented by an r-tree of depth no greater than 5. so the real problem here lies in constructing the tree in the first place. the variant i mentioned before, the packed r-tree, would be ideal in this case since it's optimal for static objects known in advance (tile data & certain item/sprite placement, for instance).
as far as memory goes, due to the structure of the tree, there wouldn't be a need for much use of the stack (for 'push'ing levels). traversal would be directed by a simple "does the search x & y lie in in this quadrant (the current node's)?", if so, go to the next level and repeat. if not, im sure a scheme could be worked out where maybe only two 4k nodes (for the current level) were needed at a time - one for the current node and one for the neighbor. so you just "skip right" until you find the bounding rectangle, and continue downward if it's not a leaf. as col pointed out, an iterative - not recursive - algorithm would work fine.
at any rate, theyre a real pain to "pack" initially, so i may just avoid them for that reason alone... probably more trouble than it's worth. what are some other schemes you guys use for, say, collision-detection between objects. one alternative i've thought about using is just keeping a list of about the 16 closest characters, periodically scanning through the entire list and updating as needed - should keep the list accurate to within 1/4 second.
#9488 - tepples - Wed Aug 06, 2003 5:46 am
Sort the sprites by y coordinate of the top edge, and then for each sprite s, only consider the following sprites whose top is above s's bottom. This should work except for the most crowded playfields, where the sector method is indicated.
In the sector method, you divide the active map into a uniform mxn grid of sectors, where m and n are small (usually less than 10, and in any case significantly larger than the largest sprite). Every frame, add each sprite to each sector where it overlaps. Then scan each sector for overlapping sprites, and store your findings in a heap. There may be duplicate collisions where two sprites overlap in two sectors, so disregard the dupes as you process the heap.
_________________
-- Where is he?
-- Who?
-- You know, the human.
-- I think he moved to Tilwick.