This could either be extremely difficult, or extremely easy. Depending on how far you go it tends to get more complicated. You may also be thinking that this should be in the Direct3D section - after all, lighting is a huge part of 3D games; well, I've seen many 2D games use this technique - with a little memory access it would actually be extremely easy to modify this for use in DirectDraw.

1: Writing a simple lighting algorithm.

We'll start our engine at being extremely simple, then as we progress it'll get more complex. For this tutorial we'll be dealing only with point lights, those that have a position and range, but no direction or cone, but once you've done point lights, the rest is fairly easy.

First, a bit of theory. A point light has a center and a range - therefore we'll only be lighting those areas that fall within this circle of influence. Also, as you travel further away from the source the light decreases - it fades out. This effect is called Attenuation; remember this - it will keep on cropping up. So, given that information it should be fairly easy to write the first stage.

1a: Structures.
We will be needing several data-types to hold information whilst we are rendering the lighting; we'll need a datatype describing the points (vertices) and a datatype describing a light. We'll be using these ones:

'//A simple color wrapper
Private Type RGB255
    r As Byte
    g As Byte
    b As Byte
End Type

'//This emulates the Direct3D 0.0 to 1.0 colour values
Private Type RGB0010
    r As Single
    g As Single
    b As Single
End Type

'//A generic Tile
Private Type Tile
    X(0 To 3) As Long '//X & Y are simple 2D coordinates
    Y(0 To 3) As Long '//there are 0-3 to simulate a tile with 4 corners...
    Z(0 To 3) As Long '//Height
    Color(0 To 3) As RGB255 '//The colour that windows/VB uses
    D3DColor(0 To 3) As RGB0010 '//The colour that the algorithm uses
End Type

'//The light structure
Private Type Light
    X As Long '//Coordinates
    Y As Long
    Z As Long
    sColor As RGB255 '//Start colour
    eColor As RGB255 '//End Colour
    Range As Long
    Active As Boolean '//Do we ignore this light?
End Type

'//The variables
Dim LandTile(199, 199) As Tile
Dim LList() As Light '//Open Ended Array
Dim NLights As Long '//Number of lights

These structures may seem a little odd, so I'll go through them. We need two types of RGB colour value. There is the normal 0-255 colour value you'll be used to in windows; and there is the 0.0 - 1.0 colours that Direct3D uses. The algorithm works with the Direct3D values, if you try to use the larger values you'll get overflow errors when you use big variations or colour and large distances... The rest should be fairly self explanatory...

1b: Distances.
We need to know how far it is from one point to another. This is crucial to our algorithm. We'll be using 3D pythagorus - it's not greatly important how it works, but the result will be the distance between the two points that are put in....

At the end of all that, "D" will be the distance between the light's position and the vertex's position. The coordinates part will be explained a little later....

1c: Attenuation.
After distance, attenuation is the most important factor. we work out the attenuation based on the difference between the start colour and the end colour; effectively generating a gradient. If the end colour is set to black it will appear to be fading away - but if it's set to a different colour, the start colour will merge into the end colour - allowing for many weird lighting effects.

above is the code that calculates the colour and the attenuation. all of the LList( ).*color.* values have the "/255" because it will convert a 0-255 value into a 0.0 to 1.0 value, which is required if the formula is to work. A breakdown of the formula:

(LList(T).sColor.r / 255) - (LList(T).eColor.r / 255)
=> This is basically "(Start colour - end colour)", we're left with the difference between the start and finish colour.
(Result) / LList(T).Range
=> This uses the result from the previous part and divides it by the range. This then results in "for every 1m you go, it changes by this much" - a gradient.
(LList(T).sColor.r / 255) - (D * Atten)
=> The first part converts the 0-255 value into a 0.0 to 1.0 value. The next part works out what the colour is based on the distance along the gradient slope. if you use the same sentence as above: "If you've gone D meters along you are at this colour value" it then takes away this value from the start value.

Done; you now have, stored in "r", the colour value for that vertex from that light. To get the other colours you just repeat this, substituting the "r"'s for "g"'s or "b"'s...

1d: the final colour
This is the final part of the formula. Assuming you have more than one light - which is very likely; how do you know that the red value you have is not less than the amount of red already there. We'll need to blend the colours - which in this case is incredibly simple. we'll only change the master value if the temporary "r" value is greater than the current "r" value. Here's the code for all 3 components:

Done. You now have all the information, algorithms and formulas that you will require...

1e: The trimmings
I'll now tidy up the code, and show you how the shell of the algorithm looks...

Simple really :)

2: Modifying it to accept face orientation
The model above is okay; for a simple game it would do. But for a little extra work a big difference can be gained. What if the tile you are lighting isn't facing the light - what if the light is behind it. In the previous model it wouldn't make any difference at all. But in real life the tile shouldn't get any light. Basically, we want to adapt our algorithm so that it shades each tile based on the direction it's pointing in - if it's pointing away then there is no light.

This has the added advantage of making the shading much better - should you have a cone shaped mountain; the side facing away will be dark (what we want), the side facing the light will be very bright, and anything betweem will be either slightly darker or slightly lighter.

The theory behind this is a little more complex than the previous incarnation of the lighting algorithm, but you still need to understand the previous one. You'll also need to understand what a vertex normal is; I've seen lots of posts on message boards about these, so I think this'll be our first stop.

A vertex normal is a vector perpendicular to the surface or the vertex. A vertex or face normal can tell you which direction it's pointing - which is exactly what we need for this part of our algorithm. For our algorithm we'll use a face normal - where the face is the tile. To work out what the face normal we'll use the Cross product. How this works isn't greatly important either, it takes two vectors, and the resulting vector is the normal. The two vectors we'll use are from the vertex 0 to vertex 1, and from vertex 0 to vertex 2; these two vectors basically describe the surfaces. So, to clear all this up; to calculate a vector between two points we use the formula:

As for the cross product. There is a function built into the DirectX type library for doing this; but we'll do it the long hand way:

At this point we would be able to get the vertex/face normal. For convenience we'll just copy this normal to each vertex. This will require us to modify one of the datatypes that we created earlier, and create a new one.

The next stage; we need the direction from the light to the vertex. This is fairly simple, and is done in the same way as the first stage of getting the vertex normal:

We also want to normalize the two vectors at this point. At the moment it is quite likely that you're light direction vector and your vertex normal are both of non-1 lengths (ie, a lengh other than 1). There is another function built into the DirectX type library for normalising a vector; but I'll show it to you long hand:

Okay; we're about ready to work some stuff out now. You've met the Cross product already, now meet the Dot product. The dot product returns a value between -1 and +1, which is the scaling factor of our colour. This code will get the intensity of our light:

We now just multiply all the channels by the "Intensity" value, which, if you think about it, works as a scaler. for example, if the intensity is 1.0 (the face faces the light) then the colour = colour * 1.0 = colour. Whereas, if the intensity were 0.5 the colour would be halved. The only thing you need to bare in mind; if the returned value is <=0 it gets no light at all; as this means that the surface is facing away from the light.

Sorted. Should you now run the program; you'll see that it only shades faces fully that are facing the light....

3: Modifying it for shadows
Now things start getting interesting. Assuming that we're writing a Direct3D lighting engine we're now at a point where we will be doing better than it's own engine - as it doesn't have support for shadows (Not without clever tricks).

There is one huge limitation to this technique when implemented with Direct3D - it's not very accurate; but when combined with the previous iteration of the engine it shouldn't be very noticable. Because Direct3D blends a colour across the surface, the ray of light going to a vertex only has to miss the shadow-caster by a fraction of a meter in order to make 1/4 or the surface appear in full light.... You can get around this quite easily by using medium-high resolution lightmaps, which look much nicer anyway...

To calculate whether a vertex is in shadow is basically the same as ray-tracing. We will basically trace a line from the light's position to the vertices position; should this line intersect with another tile we will know that we dont need to calculate any light. Before we really get started here you need to bare in mind that this technique is extremely slow; so should only be considered for pre-rendered lighting, NOT runtime/realtime lighting. If you have a good knowledge of Assembler you may well be able to make this go fast, but in pure VB you will be lucky to get reasonable speeds when compiling the light map. The algorithm we'll use isn't necessarily the best available, and the methods used aren't necessarily the fastest - should you want to use this method you can work that part out !

The time it takes to work out is proportional to the number of triangles in a model, and the distance between the light and the vertex. Should you be attempting to calculate the lighting for a ray going half-way across the level you may well need to process several thousand triangles.

Lets get started. First, we want to look at the ray-tracing algorithm; thinks to 'Rolly' for this - the original author.

Not too scary really, is it. We pass the function the three points of our triangle (triP1, triP2, triP3) and the points defining our line (startpos, endpos) and the accuracy. The accuracy is incredibly important - the smaller the number the more accurate the shadows are; for lightmaps this is quite important; as per-vertex shadowing is quite inaccurate anyway, calculating it very accurately isn't greatly important. Also, the accuracy determines the speed that this thing takes to render. The final thing to note is that the function returns true if the ray intersects with a triangle and false if it doesn't...

In order to use the above function we require two support functions: VectorScale and VectorAdd, as well as the core processing function, Test_Triangle. The two support functions are shown below:

Finally; the Test_Triangle procedure:

This basically takes a triangle, and a point and checks if the point is within the triangle. The point was worked out by the previous function - it's a value somewhere along the line between startpos and endpos based on the accuracy value. The theory behind this formula can be found from many of the big game development sites (http://www.faqs.org/ has a good entry in the comp.Graphics.Algorithms FAQ).

You'll also notice that this procedure requires several more functions for it to work - mostly vector manipulation. VectorSubtract, VectorCrossProduct, VectorLength and VectorDotProduct. Dot product and Cross product where demonstrated above; VectorLength and VectorSubtract are shown below:

okay; so now you can test a triangle if it intersects with a line between the light and the vertex. We now need to plug this into our existing algorithm. This is where we need to decide which triangles to test. The method shown below is probably the slowest that you can do, but in order to keep this article fairly simple we'll leave it like this. Should you have time I strongly suggest that you modify this - about 80% of the triangles tested will be well out of the line.

All we're going to do is run through the rectangle defined by the light position and the vertex position. Like So:

That segment of code goes after you scale the colours for face orientation, and before you compile the final colours....
Bare in mind that on my fast computer (700Mhz Athlon) it took 7 secs to do a complicated scene before shadowing and nearly 20minutes to do the same scene with shadowing....

Should you want to do the runtime method; you'll basically need to use the following methods outlined:
1. Lock the surface
2. Go through every pixel and get a 0-255 colour value for each component Red, Green and Blue
3. Get the data from the pre-made lightmap (or generate it now) and get a value of 0.0 to 1.0 for each colour component
4. Multiply the value you read from the surface by the 0.0-1.0 value you have for the lighting. If you think about it, a value of 1.0 (full light) will not affect the colour (colour*1# = colour), but if the value is 0.5 you will get half the colour (colour*0.5 = colour/2)...
5. Put the modified values back into the surface.

This, I'm sure, is how Direct3D does it's lighting when textures are used. Because it's the same, you'll have the same lighting problems. Think about it, if the pixel has green light on it (the multipliers will be 0.0, 1.0, 0.0) and the pixel colour is blue or red the overall colour will be black. As there is no green 1.0 * 0 = 0, as there is no red light, 255 * 0.0 = 0 and there is no blue light, 255 * 0.0 = 0 you're final colour will be black - not very pretty. There are three ways around this.
1. Ambient lighting - in the lighting program alter all light values so that they dont go below a certain level, ie dark grey, this way you're textures may well become very very dark, but they wont ever go black.
2. Lighter Textures - if you make you're green grass a very light green (use the brightness option in your paint program) then there will always be some of every component - therefore a light will always have some affect, even if it's very small...
3. Saturation, this is basically where if a value is above of below a boundary it is automatically set to another value. For example, a saturation of 75% would mean that all value >=75% would be set to 100%. The same can be done on the lower boundaries. You could write a simple algorithm to look at each channel (r,g,b) in every pixel (of your texture) and if it were below a certain value you could set it to a new lower boundary. For example, if you want the textures to always have 100 of a channel, you look through every channel and should it be less than 100 you alter it to be 100.... simple really...

5: Using Lighting in 3D - a brief guide
Lighting in Direct3D is easy. It was designed with lighting in mind after all...

However, you'll have to use either D3DLVERTEX's (where you can specify the colour) or the D3DTLVERTEX's (only if you're doing a 2D game). In either case you'll have to store you're lighting as a 0.0 to 1.0 value in your data file (or convert it at runtime) - as the "Dx.CreateColorRGB()" function takes colour values on a 0.0 to 1.0 scale.

Another advantage or using Direct3D is that it interpolates the colours across a triangle. therefore the lighting information doesn't need to be at such a high resolution, which saves on storage space and processing time....

Should you want to use lightmaps you'll need to store the lightmap as a texture, load it in as a texture and then use texture blending to apply it to your model. There are two major limitations to this method:
1. Filesize. Fancy storing a 2000x2000 bitmap for each level? Not pretty.
2. Texture sizes; you'll need to keep the textures to the power of two - 512,1024,2048,4096. The higher they get the more memory required, and the less hardware will support it. Bare in mind that Voodoo3 cards cant hold textures greater than 256x256 in size...

I just mentioned storing 2000x2000 bitmaps. You could use a compressed format, such as JPEG. But unless you're not bothered about clarity JPEG is a bad choice. JPEG compression is "Lossy" - therefore you're not going to get quite what you put in back....