One simple thing you could do while retaining your current algorithm : use a system memory buffer, as sysmem is faster to read from than vid. The sysmem backbuffer->vidmem blit may cancel any advantage however -- you'll just have to test it.

As for a different approach to the problem, the following routine is educated speculation, since I haven't yet written something like this myself. But possibly if multipass (draw your sprites, then darken the non-vision areas) shadows are too slow, you might try a combined approach.

For each sprite, determine if its fully visible or fully invisible. if either of those special cases, either draw normally or don't draw at all, respectively. If its a case with mixed shadows, things get tricky. If you're doing DirectDraw blitting, this method will NOT work, since it relies on custom framebuffer drawing. It sounds like you're drawing with your own code though, so blended bliting is a piece of cake.

You'd have to create a copy of your regular blitter but for each pixel (or every 2nd pixel), determine a lightness value for it. This would be slow, but it would save you a read from vid mem, which probably would make it faster. To implement this, you could create an RLE shadowmap array for the whole screen for each frame of animation. This would probably be the thorniest part of the implementation. Then when drawing your pixels, also go through your shadowmap. You still have to calculate the blended source+light level result, but it removes all the visiblity code from your inner loop.

What saves you here is that your shadowmap will be very small, since the majority of the screen will condense into just a few bytes in the map thanks to the RLE compression. (if you go with byte-sized array elements, you could get 256pixels per run. If you combine your count and data bytes into a word and restrict your shadow levels to <=6bits, you could get 1024pixels per run... meaning about 2k for an entire 640x480 screen assuming a large mix of shadow/noshadow onscreen) This means that the shadowmap can stay in the cache, which means that the checks against it can be very fast. Not only that, but in the blitter itself you're only going to be reading from the shadowmap once for every light level change, which usually should be infrequent.

in C++ psuedocode, something like :

void Sprite::blit() {  if fully_visible do normal_blit();  if fully_invisible return;  else {     do clipping     for height of sprite       locate start of this line in RLE run, and retrieve RLE run and data values.       for width of sprite         get current light level from a CPU register containing the RLE run value         blend your source pixel with it         write your color to the destination         width++; RLErun--;         check if RLErun == 0, if so retrieve next run length and data byte from shadowmap.         }     height++;}

I can't promise that this would be fast, nor practical. But its one way I can think of that would allow arbitrary shadows and light without a 2nd pass like you're doing.

------------------
- Remnant
- (Steve Schmitt)

Is there anyone who can help me with a Starcraft-like shadow and fog-of-war algorithm?
I'm working at a 2D strategy game and I'm trying to make the shadows and the fog-of-war look transparent (like in Starcraft, not AOE).
The simplest algorithm I use is dividing by two the color of the pixels wich are covered by shadows.
A kind of alpha transparency.
It's made in asm, it's fast, but for a lot of shadows (100 units on screen) + fog-of-war it's getting too slow. Far too slow.
I think that's because I have to read from the destination surface the color of the current pixel, make a shift with it, and write it back to the same surface.
It performs a reading and then a writing with the video memory (if I only write something there it's very fast).
Reading a pixel from that video-memory surface kills me...

For fast fog-of-war, just use what Warcraft uses, patches of alternating
black dots. So you have two patterns: one solid black pattern and one
black dot pattern. You can create a simple black dot patch by drawing
several 45 degree angle black lines next to each other. Make the pixels
around the black dots your transparent color, so if you are using DirectX,
you can use BltFast and a transparent source colorkey to quickly draw the
shadow tile over the background tile.

Nemo