Public Commander Keen Forum

Curious, so all your sprites are active all the time?

Well... it's kind of complicated how it works.

Sprites that are offscreen are completely ignored, EXCEPT that the main drawing loop still makes one cycle for them; it just skips all the drawing and behavior code.

But the main speed-killer is the redraw-test code, which makes sure tiles get redrawn over each sprite every frame. This runs through every sprite (skipping the off-screen ones but still making one cycle for each) and checks if it overlaps the given tile, but the kicker is that it must do this for every single on-screen tile, since there's no way to know where a sprite is but to run through them one by one anyway.

So you essentially have (20*13)*(# of sprites) in additional FOR loop cycles per frame. With just one sprite that's 260 cycles (simply the number of on-screen tiles); but with a typical level (say 30 sprites) that number can easily get into the 5000-15000 cycles range. That's way too many. QB45's FOR loops are just way too freaking slow.

I know there must be a way to optimize this, but I'm missing it. Any ideas?

This is what I've learned from a partial Keen 1 disassembly:

The refresh manager (or whatever you want to call it) keeps track of a matrix representing every tile in the viewport (in your case that would be 20x13 tiles, I presume). Each slot in the matrix indicates if a tile needs to be updated (drawn).

Every actor that is drawn marks the respective slots in this matrix to indicate they require an update. That's basically using width and height of the sprite image and setting all the slots it overlaps with to a 1 in the matrix.

When the refresh manager updates the tiles, it sets the slots in the matrix back to 0, so they won't be updated again. Since you usually draw sprites AFTER drawing the tiles, that should work without a problem. I think updating and drawing actors in Keen 1 is done in the same loop, this means that this algorithm should always "erase" sprites from the screen by default. After that, the actor's update code can place/draw the sprite at the new location and mark the new tiles in the matrix.

That should speed things up significantly.

Indeed, Keen games keep track of sprite size and position quite carefully so they do not have to check all onscreen tiles for refresh, this is one thing that makes the faster than comparable games of the era. And of course the games also have the whole 'foreground' thing that means some tiles are always skipped over.