Hi all,

As you might know i work at SOLAR OS and HE RTS game from time to time. Both share an interesting optimization problem (but to be honest more the OS than the game)...

I will use the OS for examples from now on:

Well, I aim to do the fastest real-realtime OS on Earth :D (in my dreams)
Well, it is faster than Menuet (:P)

However lately tests on a CELERON at 500Mhz (128k cache) showed unacceptable low frame rates (~10FPS)

This is mainly because i curently draw everything every time in system RAM backbuffer and then at the end (after painting mouse) I memcpy all system backbuffer to video LFB.

Needless to say that both full screen clear with desktop color and all windows drawing (some translucent) and the finally batch memcpy use up a lot of CPU power every frame.

Besides optimising memcpy and memfill functions (using prefetch and/or MMX algo form here)...

I was thinking IF i can not find a decent dirty rectangles algo that will speed this stuff up at least when big parts of screen are not updating.

For your understanding I will show here that the current OS screen redraw is message/callback based: Aka system executor sends a ACT_PAINT message to THE crt Active Desktop and this Desktop draws itself ;then sends same message to ALL of its Children Windows and they draw themselfes and then they send same message to their childrens ... etc etc

As i see it now is that i sould somehow colect info from each window if its content was updated lately (in a realtime/ games OS there are some windows that are updating every frame anyway) and then send messages to each window with the rectangle that needs to be updated.

What botheres me is that this mechanism is obviously useless and even more time consuming IF many changes are done to screen at the same time... so in this cases i will have to fall back to curent method of painting.

I will have to see what windows are located under a changed (translucent?) window and intersect the rectangles and get a new rectangle that will have to updated also... something like that (puzzeled)

Another thing i have in mind are non rectangular windows (like circles and stuff) Intersecting rectangles can be fast and fun but dealing with all sorts of user defined shapes intersections can again be time consuming...

So what are your people's ideeas about algorithmic optimizations of this issues?

Any ideeas about such algorithms are wellcome
Posted on 2003-05-05 22:25:33 by BogdanOntanu
Solar OS seems pretty interesting. Can you post the link of the RTS ?

Some years ago, I was confronted on the problem of redrawing parts of screens (on 8 bits games).
First, I recommend you the following trick:

just keep an array of every line of the screen.
When a line has to be refreshed, you just have to change the flag, and redraw the line when necessary.

About the minimal redraw, I would have created a linked list of parts to redraw of the screen.
Ideally, this linked list should be sorted by Y increasing order.

You can also combine the 2 ideas, and store a linked list of all horizontal lines to redraw for every Y (this also works for circle and non rectangular windows).

JC
Posted on 2003-05-07 08:57:38 by MCoder
Hi

Thank you for interesting ideeas, i will try to check all and then try and implement some of them, see if i get any speed improvements

The RTS is on my WWW home

www.hostileencouner.com
and the os at :
www.hostileencounter.com/sol_os/
Posted on 2003-05-10 22:55:01 by BogdanOntanu
I played a little bit of that Hostile Encounter game. I must say I was very impressed. :alright:

But even on easy setting the AI was royally slaughtering me left and right. It would send wave after wave of robots, and just when I thought I had enough defenses to withstand it, it would send tanks in to pummel me to death. So I gave up. :( ;)
Posted on 2003-05-11 00:16:50 by iblis
Then i must add extra easy to AI

Really it is not that inteligent, you must get used to its patterns of actions and will kill him easy
Hummans via internet or LAN play are the great challange !!!!

How was the speed, as the above algo questions ar speed realated actually
Posted on 2003-05-11 00:26:15 by BogdanOntanu
I can beat it using the money cheat. But without the cheats I can't seem harvest enough energy to build stuff before the AI comes to kill me with its army of robots. I should probably learn to use the hotkeys.

The speed was more than fine. Even with 30 bajillion spider-bots on the screen there was no slow-down. I think for a scrolling game like that you shouldn't worry about dirty rectangles. But for the OS you definitely should.
Posted on 2003-05-11 03:44:57 by iblis
Thank you for interesting ideeas, i will try to check all and then try and implement some of them, see if i get any speed improvements


Simply implement the first suggestion (tagging lines to be refreshed).
This works in every case, and is very easy to implement.

I'll check your game when the download will be finished (2 hours on my 56k, argh).

JC
Posted on 2003-05-11 08:27:40 by MCoder
Bogdan: there is another technique which could be applied to your game, if you want to redraw optimally the screen.
Simply cut the screen into tiles, like 8*8 or 16*16 or 32*32, just keep one byte for every tile.
When a sprite is drawn, simply tag the tiles that need to be refreshed.
Of course, I hope you use a double (or triple) buffering !

About the game: it's totally unplayable on my P4 2.26 ! It's much too fast !
I tried to play with 30fps, and the game is still very hard !
Since the game engine seems pretty finished, you should try to adjust the gameplay. Be careful: you can find the levels easy, because you know the game well, but this is not the case of the beginners !

JC
Posted on 2003-05-13 05:46:58 by MCoder
Much too fast ? OMG, how i wished to hear such things :)
This means i can allocate more time to AI

But please setup a game on The Arena (256x256 map for 8 players) and put ALL players Computers ==> YES you CAN dothat <=== ,

Make the game FFA (Free Fight All) and the let them battle all aginst all....you can just disable fog of war using Del key cheat and then watch the whole game as a spectator...

Just take care to move yourself towards winning player using F11/F12 before your crt player is killed...

This way ALL 8 AI's will be running and tons of units will be produced by each AI player...
Thell me if it is still that fast then :D


Unfortunately my optimization target is P2/400/500 and not the mighty P4 / 2.6
That is why the FPS speed limit was introduced in options screens: to make game playable on super fast machines.

Playable means User Interface --- NOT the AI opponents :P,--- well AI will run at the same FPS as game and not faster . Also choosing Easy AI from Options will slow them down a little and make them attack with less units.

But you are true i know games's units properties and features quite well so its a lot easyer for me. As i have said it before i looks like i need and extra easy AI option (read dumb)


Yes, i use double buffering (sometimes we have even used 3 buffers) but you must understand that both the Game and keep the buffer in system memory for doing translucency without hardware accel.

And this makes them very memory read/write intensive.

1st Problem:
--------------------
Is of course the copy from memory system located backbuffer to video RAM.
-Here i must use some above dirty rectangles techniques and indeed they seem quite straight forward.

2nd Problem:
-----------------------
Is the every frame repaint of the system backbuffer.

- sometimes in the game there are so many units moving all over the screen that a dirty rectangle looks like overkill to me.
-many units (like the Lords hunter) have animations while they sit and wait for targets, su they must e updated anyway. Same goes for working buildings

3rd Problem:
--------------------
Is how to propagate / collect updates in an unknown chain of objects placed on unknow number of layers

- Game has no problem here as we only have a few well known layers: terrain, doads,Buildings, Ground units, Ait units, spells/explosions

-but OS can have ANY layout of any number of windows some translucent some not, some updated some (???) not.

- knowing what "is under me" as an object requires multipe window intersections and tests , while simple drawing from Desktop to top most windows has none of this problems



Anyway when i touch this issues and make tests to check if algo optimizations are worth the effort i will let you all know my findings ...
Posted on 2003-05-13 10:33:12 by BogdanOntanu