Page 1 of 1
way of organizing objects that manipulate multiple sprites
Posted: Fri Feb 15, 2019 2:07 pm
by psycopathicteen
I was trying to think of a way to handle objects that consist of multiple sprites in patterns like waving sine waves. I didn't want to use linked lists, or having an object control a gazillion other objects, so I was thinking maybe there is a way to organize multiple tables of multiple sizes depending on how many sprites the object needs. Obviously there can't be more than 128 sprites onscreen, and because of that, there can't be more than 128 objects onscreen either, assuming each object has at least one sprite. I thought 32 would be a nice maximum sprites-per-object limit, so 128 lists of 32 sprites would be 4096 entries, which is definitely more space than needed. If I had a list of 128 1-slots, I can have 64 32-slots, which adds up to 2176 entries. If I had 128 2-slots, I can have 42 32-slots, which adds up to 1600 entries.
It then turned out that using 128 4-slots, and 25 32-slots came up the best at 1312 entries, so I subdivided both groups. I got these groups:
9 slots of 32
25 slots of 12
64 slots of 4
128 slots of 1
Then I discovered that one slot of every group can be reduced in size and still work withing the worst case scenario.
8 slots of 32
1 slot of 24
24 slots of 12
1 slot of 8
63 slots of 4
1 slot of 2
128 slots of 1
I got this down to 958 entries total.
edit:
Found out some tweaks can get me to 955:
Code: Select all
//minimum
8 slots of 32 //13
1 slot of 24 //12
23 slots of 12 //5
1 slot of 11 //5
1 slot of 8 //4
62 slots of 4 //2
1 slot of 3 //2
1 slot of 2 //1
127 slots of 1 //1
Re: way of organizing objects that manipulate multiple sprit
Posted: Fri Feb 15, 2019 10:05 pm
by Oziphantom
I would just use a packed buffer to allocate.
So you have 128 items, so an array of 128
you start at 0, and then you add sprites as you need.
So you add 32, and then a 4, 4, 8, 2, 1, 1, 1, 16 etc
so you need each object to holds it "index" and "length" into the buffer. When you remove an object you go to the end of the buffer and remove stuff that can git into the object you just removed gap, thus packing the structure back down. It has a flaw in that if you have a lot of small objects and a big object at the end, the big object won't be able to fit into the small space until a lot of objects are removed. You can either avoid this by careful level spawning control, or extending the buffer to hold upto 256 items, so you have enough overflow to handle it taking a long time for a big enough slot to open up and the pack step. This also gives you room to wait until an opportune frame to do the pack.
Re: way of organizing objects that manipulate multiple sprit
Posted: Sat Feb 16, 2019 9:45 am
by psycopathicteen
I think looking through a bunch of bytes for an open space big enough would be kind've slow.
Actually it just occurred to me that I don't need the 1-sized slots because I can just use the object slots themselves to store sprite information. So that will be 828 entries by removing the 127 1-slots.
Re: way of organizing objects that manipulate multiple sprit
Posted: Sat Feb 16, 2019 9:33 pm
by Oziphantom
you don't look.
Remove object X
Fill said space with last object, until can fill no more.
There is no hunting, you know the exact locations of both objects you are moving.
Re: way of organizing objects that manipulate multiple sprit
Posted: Sat Feb 16, 2019 10:04 pm
by psycopathicteen
I think it still could take pretty long to block move everything down, and also adjust every index.
With my method all you really have to do to find an array is determine which of the three size ranges it fits under, and pull an index number off of one of the three stacks, and when it's done, put the index value back on the corresponding stack.
Re: way of organizing objects that manipulate multiple sprit
Posted: Sat Feb 16, 2019 10:27 pm
by Oziphantom
you don't move everything down, you plug the hole,
so imagine you have
111111222222233334445555555666777788899999
And I remove object 55s data
11111122222223333444-------666777788899999
Then I move so I just made a slot of 7, the last item is 5, it fits so
1111112222222333344499999--6667777888
that gives me 2 left, 8 is 3 won't fit
End = End -5
Now when you want to allocate you just start at End
not a massive time sink. Unless you are adding and removing hundreds of items each frame to which then yes it will start to kill you and you have to them spend a lot more RAM pre allocated for things.
This will get you fragmentation, which is something you might need to deal with, or just allocating double the max space might get you through the level. you can also put in "defrag" operations that you trigger at known points in your level when you know it becomes an issue and there is not much else going on. Think "crossing a portal" in new games, or the "boss entry corridor" in Megaman. But it gives you a lot less RAM usage to hold your object, and a faster alloc, as you just get end + amount and done. The shift down can happen as and when you have enough frame time to do it, it doesn't have to happen "then and there" you just record this slot, this big needs patching, if it can be.
Your method is potentially faster, but you have a lot more RAM used, and you have a lot more indexes to update, and you have to look up which index, and which ram buffer to start allocating in, which may cost you more time than just allocating from a known end positions.
Re: way of organizing objects that manipulate multiple sprit
Posted: Sun Feb 17, 2019 12:46 pm
by psycopathicteen
You don't need to update a bunch of indexes. Just push and pull values from a software stack.
Code: Select all
allocate_array:
cpy #$0005
bcc allocate_small_array
cpy #$000d
bcc allocate_medium_array
ldx {large_array_stack_pointer}
lda {large_array_stack},x
inx #2
stx {large_array_stack_pointer}
tax
rts
allocate_medium_array:
ldx {medium_array_stack_pointer}
lda {medium_array_stack},x
inx #2
stx {medium_array_stack_pointer}
tax
rts
allocate_small_array:
ldx {small_array_stack_pointer}
lda {small_array_stack},x
inx #2
stx {small_array_stack_pointer}
tax
rts
////////////////////////////////////////////////////////////////
deallocate_array:
txa
cpy #$0005
bcc deallocate_small_array
cpy #$000d
bcc deallocate_medium_array
ldx {large_array_stack_pointer}
dex #2
sta {large_array_stack},x
stx {large_array_stack_pointer}
rts
deallocate_medium_array:
ldx {medium_array_stack_pointer}
dex #2
sta {medium_array_stack},x
stx {medium_array_stack_pointer}
rts
deallocate_small_array:
ldx {small_array_stack_pointer}
dex #2
sta {small_array_stack},x
stx {small_array_stack_pointer}
rts
Here's a shorter, but slightly slower way of doing this:
Code: Select all
array_size_group_lut:
db 0,0,0,0,0,2,2,2,2,2,2,2,2,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4,4
allocate_array:
lda array_size_group_lut,y
and #$00ff
tax
ldy {array_stack_pointer},x
tya
inc #2
sta {array_stack_pointer},x
ldx {array_stack},y
rts
deallocate_array:
lda array_size_group_lut,y
and #$00ff
tay
lda {array_stack_pointer},y
dec #2
sta {array_stack_pointer},y
tay
txa
sta {array_stack},y
rts
Re: way of organizing objects that manipulate multiple sprit
Posted: Sun Feb 17, 2019 11:18 pm
by Oziphantom
That only lets you free the last thing on the stack. And means you need to remove things in the exact reverse order.
Re: way of organizing objects that manipulate multiple sprit
Posted: Mon Feb 18, 2019 9:26 am
by psycopathicteen
The order doesn't matter.
This is how it is initially:
0123456789
If you need 3 arrays pull them from stack.
456789
If 0 clears first then 1 then 2 it looks like this:
2103456789
You'll still get the same amount of arrays you started with, just in a different order.