light

o  940727:	Light Revisited.
OK, so my initial idea doesn't pan out the way we'd like it to. But upon looking at it again this morning, I think I have a way out. A little calculus in the right places can be fun! Yes, I said calculus. Remember the limit theorem and integrals? Good. I knew you did! Here's the deal.
A room can be described as a rectangle with length L and width W. The average amount of light that a moblie light source will contribute to a room, is a curve which describes the path the light source takes as it moves through the room. Since we are not actually USING coordinates within rooms, the path is simply a straight line from the enterance to the centre, and another line from the centre to the exit.

Now, if the room is square (as probably 75% of the rooms in any mud are), the two line segments are of equal length. We can then see that a single line, which is the length of the room, will suffice if we ignore the overlap (as we would, since it would really be an irregular curve with varying speeds of movement). Even if the room is not square, it can be represented by a line if the enterance and exits chosen are on opposite walls. This line would be either the length or width. If the enterance is on a wall adjacent to the exit, the total distance covered is twice the average of the two halves.

Problem 1: We do not know what exit the player will select, before they actually leave the room. This means that in a long hallway (10x100), if they enter on the 10' fall and leave on the 100' wall, the total distance is 55'. But if they enter on the 100' and leave on the opposite 100', the distance is only 10'. Likewise, travelling down the hall is 100' distance. If we assume the average, we will greatly enhance those people travelling across the hallway, but peanalize those walking down it. To do this would discourage the use of non-square rooms and would be a mistake in my opinion.

Now, assuming problem 1 is addressed in some fashion, we can state that the area of the room lit will be the area covered by light as we walk over both straight line segments. Since the light is being emitted from a point source, it will cover a radius which varies with it's strength. We will ignore things like reflection for our purposes, since we are building a mud, not a ray tracer.

Since this light varies in intensity over the range of full brightness at the source, to zero brightness at the periphery, our chance of spotting an object/monster varies as well. Note that in our game, those characters with infravision can spot monsters without light if they emit heat, but object do not radiate heat (as a rule). Also, light will prevent infravision from working, so you can use one or the other, but not both. This is good, else our formulae would be much more complex.

Now, if I'm not mistaken, we can define three categories of space within the room. The area which is encased in darkness and is not affected by our point light source, the area from the edges of darkness to our optimal vision level of light, and the area from that optimum brightness to the full brightness of the light source. Any light which is ambient can be added to our light level, thus making the darkness area NULL, and increasing the other two areas. Any fixed light source can be expressed as a percentage chance of seeing, based on a "normal" vision level, and the percentage of the room's area lit by it. This percentage can be added to the result of our formula and does not affect the formula itself.

NOTE: I *was* mistaken. There is another zone which is the range from the light source to the maximum tolerable light level that your character can still have a non-zero percentage chance to see in. It works like a bell curve...

	100% |           ,-+-,
	     |         .'  |   \
	     |        /    |      \
	     |      .'     |         \
	     |     /       |            +
	     |   .'        |            |    \
	     |  /          |            |         \
	  0% --+-----------+------------+-------------+----
	       0       optimum       source       tolerance
Let me try and draw a picture of what we have so far:
	-------- Width/2 ---------      +        ------- Width/2 ------
	|                        |               |                    |

	/-------------------------------------------------------------\  ---
	|           |.....|//////|#######|#######|//////|.....|       |    |
	|           |.....|//////|#######|#######|//////|.....|       |    |
	|           |.....|//////|#######|#######|//////|.....|       |    |
	|           |.....|//////|#######|#######|//////|.....|       |
	|           |.....|//////|#######|#######|//////|.....|       |  Length
	|           |.....|//////|#######|#######|//////|.....|       |
	|           |.....|//////|#######|#######|//////|.....|       |    |
	|           |.....|//////|#######|#######|//////|.....|       |    |
	|           |.....|//////|#######|#######|//////|.....|       |    |
	\-----------|--------------------|--------------------|-------/  ---
                    |     |      |       |       |      |     |
                    |     |      |       |       |      |     |
	         darkness |    light     |     light    |  darkness
                          |    source    |     source   |
                        vision        maximum         vision
                        level        tolerance         level
Alright then, if we make a compromise on the length vs. width issue, we can say the length of the path will be:
Path Length = (Enterance Width / 2) + ((Enterance Width + Adjacent Length) / 4)

So, the actual figures in our 10x100 room would be:

		Enter	Exit	Path
		N, S	N, S	5 + 5 = 10
		E, W	E, W	50 + 50 = 100
		N, S	E, W	5 + 50 = 55
		E, W	N, S	50 + 5 = 55
Our estimate is:
		N, S	?	5 + (50 + 5)/2 = 5 + 27.5 = 32.5 = 33
		E, W	?	50 + (50 + 5)/2 = 50 + 27.5 = 77.5 = 78
Why bother? Well, it does get a little bit closer to the correct values, and it tends to spread the errors out rather evenly. You see that the error is 22.5 for all possible exit combinations, which is better than being perfect on half and over 40 off on the others.
Now that THAT is out of the way, let's get down to work. The formula for light distribution will be a sum of integrals, with the light level being the varying factor.

At any given point, the chance we can see an object is the difference between the light level at that point, and the optimal vision level for our character.

	f(x) = { x <= 0     : 0
	         0 < x <= v : x/v
	         v < x      : v/x
where x is the light level at a point, and v is the optimal vision level for the character in question.
Now, remembering that we are in a finite mud environement, let's see if we can make some iterative code.

			Indoors			Outdoors

	Ambiant		Constant		Sun or
						Phase of Moon(s)
						* (1- Cloud %)
Fixed Source	% of room illuminated is added at creation time.
	(Example:  a 100 lumen source would be 100 at 10 feet,
						50 at 20 feet,
						25 at 30 feet,
						12 at 40 feet,
						 6 at 50 feet,
						 3 at 60 feet,
						 1 at 70 feet.
Thus we know a formula for determining the radius of sectors illuminated for a given light source level is: r(x) = log2(x). Likewise, once we have the radius, the number of squares affected is easy to compute. The inner ring is full brightness. Each outer ring has less brightness, and thus illuminates less of the space than the innermost.
			ring(1) = 1 * 1		= 1
			ring(2) = 4 * .5	= 2
			ring(3) = 8 * .25	= 2
			ring(4) = 12 * .125	= 1.5
			ring(5) = 16 * .0625	= 1
			ring(6) = 20 * .03125	= .625
			...
			ring(7) = 24 * 1/64	= .375
			ring(8) = 28 * 1/128	= .21875
			ring(9) = 32 * 1/256	= .125
			ring(10) = 36 * 1/512	= .0703125
			ring(11) = 40 * 1/1024	= .0390625
			ring(12) = 44 * 1/2048	= .021484375
			ring(13) = 48 * 1/4K	= .01171875
			ring(14) = 52 * 1/8K	= .006347656
			ring(15) = 56 * 1/16K	= .003417968
			ring(16) = 60 * 1/32K	= .001831054
So, the formula for a given ring's illumination is
ring(x) = { x = 1: 1,
x > 1: 4(x-1) / (2^(x-1))
Also, for moving light sources, we use a strip rather than a ring....
strip(x,L) = { x = 1: L,
x > 1: L / (2^(x-2))
The total area illuminated would then be the sum of all rings for which the illumnation level at that distance is greater than 0 lumens. In our example, this is 6 rings, so the total effective area illuminated at full brightness is 8.125 sectors. If the room in question were 10x10, this would be roughly 8% of the room.
pointsource(x) = lim x -> +INF sum( ring(x) ) This seems too small, but think about it. We are saying that there are 61/100 sectors which have some amount of illumination from the fixed-light source. But only 1 of those sectors is at full brightness, only 12 are even above 1/4 brightness, the majority of 48 sectors are 1/8 or dimmer. So the odds on spotting an object that falls into full brightness are 100% times 1/100 of the room, or 1%. The odds on spotting the object in 1/2 brightness are 4/100 * 50% = 2%.... we keep going until the light level drops below 1%. The outer ring is 20 sectors * 1/32 which is less than 1%. So, we take this 8% total and multiply it by the character's visual skill.

This gives us another possible avenue for optimization. Look at this fact. A given brightness of light will ALWAYS produce the same number of rings. Furthermore, since the size of each ring is fixed, the size of the area illuminated will also be a fixed function of the light's brightness. Although our PERCEIVED illumination area will change due to our vision level, the actual number of lumens is constant.

So, our light sources COULD be given in terms of the number of rings they illuminate. True, this is another way to make the data more coarse, since now instead of having numbers from 64 to 127, we now have the number 6 doing the same job.
64, 32, 16, 8, 4, 2, 1

This would make the calculations a little simpler though. The radius calculation would no longer be needed. The number of illumination levels is now limited to 32 with long integers, thus also making it possible to table the other calculations and hardcode them into the light function.

Another simplification! In looking at the light formula, if we pretend that more light is always better, we can say that if you take the total number of lumens produced by the light (IE: add up all the sectors with non-zero lumen counts) and average this by the total number of sectors in the room, you get the same percentage as using the ring method.

Therefore, if we can come up with a way to quickly figure out how much you CAN'T see in too-bright areas, we are down to a simple table lookup: pointsource(100)= 899.79 lumens (evaluated to ring 16).
pointsource(100)/ roomsize(100,100)= 900 / 10000 = 9%

This requires multiplication and additions out to the resolution of ringsize we want. In the above, 16 multiplications of 100 * the number of sectors in the ring, and the summation of all of them. The other side is a constant multiplication of width * height.

If we adopted the coarse light resolution of treating each number as a power of two (IE 1 == 1, 2 == 2, 3 == 4, 4 == 8....), the entire multiplication sum can be reduced to a single table lookup. This is very fast, but also not flexible. We might want/need the resolution of using lumens to make it interesting.