Saturday, November 04, 2006

XeO3: Faster and faster....

The thing I love most about fully open development is that no matter how clever you think you've been, and how well you think you've written something, someone almost always comes along and improves it! It's not that I'm bad at what I do, or that the other person is way smarter; no, it's simply that a fresh pair of eyes and a different brain can pickup on small things you've missed. This is especially true if you've been staring at the same few lines for months trying to improve it. You're brain gets into a rut, and you just can't get past what you see. Open internet development gets rid of this by allowing anyone on the web to help. Sometimes the codes so obscure that no one can understand it - but thats fine, your no worse off... But other times, its a nice small snippet that someone points out something and you slap your forehead and say "why didn't I think of that!!"

Heres a case in point.... Some time back I was struggling to find a faster way to fire bullets, and it took me several days to come up with what I thought was the perfect solution - and to be fair to me, it was pretty spiffy. So I happily posted it for everyone to see and use. Heres the original...

FreeList db 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,$ff
; Usage:- AllocBullet [x|y] Specify the X or Y register that hold the bullet to free
AllocBullet macro
ld\0 FreeIndex ; 3 ldx FreeIndex
lda FreeList,\0 ; 4 lda FreeList
bmi !NoneFree ; 2 bmi !NoneFree
in\0 ; 2 inx
st\0 FreeIndex ; 3 stx FreeIndex
ta\0 ; 2 tax
dec BullInUse,\0 ; - dont count this... its not in the new one.
ta\0 ; 2 = 18 tax X=next free bullet (or $ff for none left).
; (best case=12) Negative flag SET on none left

Now, this was a pretty fantastic improvement over the original which was just a loop through "N" bullets. It was fast, it didn't matter how many bullets you had to allocate from, the time was linear. Great! Then along came TNT (who incedently is doing a cool remake of paradriod), who quickly pointed out that if I reversed the stack it would be even quicker - like this:-

AllocBullet macro
ld\0 FreeIndex ; 3
bmi !NoneFree ; 2 (best case=6)
lda FreeList,\0 ; 4
de\0 ; 2
st\0 FreeIndex ; 4
ta\0 ; 2 = 17

Now I had fiddled with the routine for some time, but had missed this simple switch, and this is the great thing about open internet development. My game goes faster, and I hardly had to lift a finger! While it appears to be a small change, allocations happen all the time, so if you can knock of a cycle, or make it early out quicker, then its all good.

Anyway.... the reason for all this is that I've been retro fitting all my allocators with TNT's new version, and it reminded me why I'm doing all this in the first place: Open Internet Development is good, for a retro scene - its vital!


Anonymous said...

Have you considered using a linked list instead? I don't know how it evens out with freeing bullets (or if you do anything fancy with the list) but it may save a few cycles.

To allocate a bullet (6/12 cycles):
ldx free_first
beq .empty
lda free_link,x
sta free_first

And to free one (11 cycles):
lda free_first
sta free_link,x
stx free_first

That's how I handle actor allocations at any rate.


Anonymous said...

Wait a second, you're using the first part of the free list to keep track of active bullets so simply decreasing the index is enough to keep track of them? And freeing is a matter of swapping entries to the end of the list.

Ignore my previous post.. ;)