Keen Game Engine (for lack of a better name): VGA Keen DEMO

Here is where to post about the latest Commander Keen fangame or modification you've finished, a new website you've made, or another Keen-related creation.
User avatar
Levellass
S-Triazine
Posts: 5261
Joined: Tue Sep 23, 2008 6:40

Post by Levellass » Sun Oct 16, 2016 3:27

Curious, so all your sprites are active all the time?
What you really need, not what you think you ought to want.

User avatar
keenmaster486
Vorticon Elite
Posts: 503
Joined: Sun Mar 20, 2016 18:29
Location: Tranquility Base
Contact:

Post by keenmaster486 » Sun Oct 16, 2016 6:24

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?
I flermmed the plootash just like you asked.
Very silly indeed: https://audaxeundum.wordpress.com/

User avatar
K1n9_Duk3
Vorticon Elite
Posts: 531
Joined: Mon Aug 25, 2008 9:30
Location: Germany
Contact:

Post by K1n9_Duk3 » Sun Oct 16, 2016 9:24

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.
Hail to the K1n9, baby!
http://k1n9duk3.shikadi.net

User avatar
Levellass
S-Triazine
Posts: 5261
Joined: Tue Sep 23, 2008 6:40

Post by Levellass » Sat Oct 29, 2016 2:02

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.
What you really need, not what you think you ought to want.

Post Reply