Dungeon 40
Lighting? Better lighting? In a DUNGEON??? Are you serious?
The probably otherwise perfectly likeable Bruce Onder tweeted:
@RonJeffries I can’t think of something simpler or more grok-able than your impl so far.
However, I think it might be nice to improve the tinting a bit.
Right now, the princess can see through walls and around corners.
Raycasting could help with that.
I am of mixed feelings about this idea. On the one hand, you do get clues about the dungeon from the current lighting, especially in the mini-map.
In the picture above, the princess went up the right-hand hallway, but both the mini-map and the detailed view show the left hand hallway as well. So Bruce is right to want this feature.
But then one does a little research into ray-casting and shadow casting, and finds that the algorithms to do them can get to be quite intricate. The shadow casting algorithm of choice is usually implemented recursively, and it’s not obvious how it works. Someone thought hard about that algorithm, and I’m guessing it didn’t just fly from their fingertips in that fashion one likes to imagine.
There are other approaches, and in fact I plan to start with a simple idea that I had while dozing this morning before getting up, but I anticipate that this could get tricky. Since I foresee that it’ll be tricky, I realize that I need to test-drive it. And since I kind of know how the system works–at least I’m the local expert–I think the tests will be a pain to set up.
On the gripping hand, however, it might go really well, and then I’ll feel really good about myself and grateful for the idea.
Let’s find out.
My Cunning Plan
My cunning plan is simple at base. All I really need to accomplish is a reasonable lighting of the scene, enough to ensure that hidden paths don’t show when they shouldn’t.
In the picture above, I’ve set all the tiles that will be tinted to some level of visibility to completely visible. We see the problem: the hallway above the princess is illuminated, as is the wall above that, and they should be hidden.
I have a plan. Let me explain. No, there is too much. Let me sum up:
- Plan Summary
- I propose to draw a series of imaginary lines emanating from the player, at a suitably small angular difference. I’ll trace each of those lines until it either gets past the light limit, or hits a wall. Everything up to that point will be illuminated. Everything beyond, will not.
I think we’ll encounter some interesting things unwinding the code that’s in there now to mark things seen, but I feel that it is fairly well isolated. And if not, maybe we’ll refactor first. Or maybe we’ll rip it out.
The first thing is to draw the “lines”.
We’re on a plain of 64x64 tiles, and our lighting radius is 7. At a radius of 7, things are invisible:
function Tile:getLargeScaleTint()
if not DisplayToggle then return color(255) end
local d = self.runner:playerDistance(self)
local t = math.max(255-d*255/7,0)
if t > 0 then self.seen = true end
return color(t,t,t,255)
end
That t thing there goes to zero at distance = 7 and stays there.
It occurs to me that we could fetch this information as early as possible in
tile:drawand exit early if the color is zero. That might speed up our draw cycle a bit. And we do draw the whole dungeon twice, once in small scale and once in large, mostly colored black. So this might be a worthy optimization to think about, though we have no evidence that it’s needed.
Anyway we need lines in a tiled space. We want to draw imaginary radial lines around the player’s tile, checking each tile touched to see if it blocks light. If it does, we allow it to be seen but stop looking beyond.
How do we draw “lines” through 64x64 tiles? I believe the official algorithm for lines through tiled pixels is Bresenham. See, for example Bresenham’s Line Algorithm.
I’ve found a lua version of the algorithm and I see no reason to build it from scratch. I think I’ll work with it in a separate project, however, to fit it into our scheme and to make it easier to test and visualize.
Here’s what I’ve done. The algorithm I found takes a “map” parameter, which is a “bitmap”, addressed by integer coordinates. It has a single function: drawLine, that calls map:set` on each of the coordinates it wants on the line. I embedded it in a simple program that draws a floor of tiles and lets you draw lines in it.
I called it this way:
TheFloor = Floor(20,15)
Bresenham:drawLine(TheFloor, 10,8, 1,15)
Bresenham:drawLine(TheFloor, 10,8, 4,4)
Bresenham:drawLine(TheFloor, 10,8, 20,1)
Bresenham:drawLine(TheFloor, 10,8, 20,15)
Bresenham:drawLine(TheFloor, 10,8, 20,8)
Bresenham:drawLine(TheFloor, 10,8, 10,1)
And it drew this:
That looks good enough to me. I don’t see an interesting way to test it, so, given that it’s a published algorithm, I’m going to import it and use it. Here’s the function, in case you care:
Bresenham = class()
function Bresenham:drawLine(map, x1, y1, x2, y2, c)
local dx, sx = math.abs(x2-x1), x1<x2 and 1 or -1
local dy, sy = math.abs(y2-y1), y1<y2 and 1 or -1
local err = math.floor((dx>dy and dx or -dy)/2)
while(true) do
map:set(x1, y1, c or 0xFFFFFFFF)
if (x1==x2 and y1==y2) then break end
if (err > -dx) then
err, x1 = err-dy, x1+sx
if (x1==x2 and y1==y2) then
map:set(x1, y1, c)
break
end
end
if (err < dy) then
err, y1 = err+dx, y1+sy
end
end
end
Now we have the small matter of …
Plugging It In
Supposing that we plug this in somehow, it will just call set on all the cells along one of our proposed sight lines. I imagine I’ll set up to have maybe three or four per quadrant, whatever it takes to look good. But what we want to do is to progress outward along those lines, looking for walls, and lighting things up until we hit a wall, which we’ll illuminate and then stop.
So I think I’d like the function to give us a table of coordinates to check, each time we call drawLine, which we can then iterate over. It would be possible to set up drawLine as some kind of Lua iterator, but that’s very fancy for my taste, especially when we don’t have anything in hand that’s working.
In aid of getting the drawLine to do that, I think I’ll do a test or two.
_:test("Bres returns table", function()
local t = Bresenham:drawLine(15,15,16,16)
_:expect(#t).is(2)
end)
This looks like a line I can predict. :)
Running the test, we’ll explode immediately because it expects different parameters.
11: Bres returns table -- Bresenham:9: attempt to perform arithmetic on a nil value (local 'y2')
Yes. To fix:
function Bresenham:drawLine(x1, y1, x2, y2, c)
local coords = {}
local dx, sx = math.abs(x2-x1), x1<x2 and 1 or -1
local dy, sy = math.abs(y2-y1), y1<y2 and 1 or -1
local err = math.floor((dx>dy and dx or -dy)/2)
while(true) do
table.insert(coords, vec2(x1,y1))
if (x1==x2 and y1==y2) then break end
if (err > -dx) then
err, x1 = err-dy, x1+sx
if (x1==x2 and y1==y2) then
table.insert(coords,vec2(x1,y1))
break
end
end
if (err < dy) then
err, y1 = err+dx, y1+sy
end
end
return coords
end
I really expect this to work. However:
11: Bres returns table -- Actual: 3, Expected: 2
That’s interesting. I tested in the graphic version and saw this for a similar test:
But for a two-step line, I see this:
So I imagine we have an extra coordinate. I’ll print just to see.
1 (15.000000, 15.000000)
2 (15.000000, 16.000000)
3 (16.000000, 16.000000)
OK, it does that. I’m OK with that but I do want a better test.
_:test("Bres returns table", function()
local t = Bresenham:drawLine(15,15,17,17)
_:expect(#t).is(3)
_:expect(t).has(vec2(15,15))
_:expect(t).has(vec2(16,16))
_:expect(t).has(vec2(17,17))
end)
This in fact passes. Good enough, we’re getting a table back. Now what?
I think what should happen is that when the player enters a new tile, we should calculate what’s visible right then and there. We’ll begin by setting the visible cells to a full white tint, then put in the gradient after this works. We want to see the shadowing clearly as we go forward.
And we should clear everyone’s tint to zero whenever the player moves. That will ensure that we have a fresh display of shadows from the current position.
This is rather a bit different from the current scheme that tints as it goes. And I expect that we’ll lose the mini map for a while. So when that happens, I won’t be surprised.
We’ll add a tint to tile:
function Tile:init(x,y,kind, runner)
self.position = vec2(x,y)
self.kind = kind
self.runner = runner
self.sprites = {room=asset.builtin.Blocks.Brick_Grey, wall=asset.builtin.Blocks.Dirt, edge=asset.builtin.Blocks.Greystone}
self.contents = {}
self.seen = false
self:clearTint()
end
function Tile:clearTint()
self.tintColor = 0
end
function Tile:setTint(aColor)
self.tintColor = aColor
end
And we’ll use it where we currently use the calculated tint, changing:
function Tile:draw(tiny)
pushMatrix()
pushStyle()
spriteMode(CORNER)
tint(self:getTint(tiny))
local sp = self:getSprite()
local center = self:graphicCorner()
sprite(sp, center.x,center.y, self.runner.tileSize)
for k,c in pairs(self.contents) do
c:draw()
end
popStyle()
popMatrix()
end
To:
function Tile:draw(tiny)
pushMatrix()
pushStyle()
spriteMode(CORNER)
tint(self.tintColor)
local sp = self:getSprite()
local center = self:graphicCorner()
sprite(sp, center.x,center.y, self.runner.tileSize)
for k,c in pairs(self.contents) do
c:draw()
end
popStyle()
popMatrix()
end
At this point I expect black screen except for the princess, and that’s what I get.
Now we need some help from GameRunner, to clear all the tiles. (This isn’t the first time I’ve wished that the Tiles knew where they all were. Let’s remember that, but right now we’re on a mission.
function GameRunner:clearTiles()
for i,row in ipairs(self.tiles) do
for j,tile in ipairs(row) do
tile:clearTint()
end
end
end
Now when we move the player, we want to clear all tiles, and then light up the ones around us. First cut:
function Player:moveBy(aStep)
self.runner:clearTiles()
self.tile = self.tile:legalNeighbor(self,aStep)
self.tile:illuminate()
end
Tiles don’t know illuminate, yet, so:
function Tile:illuminate()
for dx = -7,7 do
for dy = -7,7 do
local tilePos = self:pos() + vec2(dx,dy)
local tile = self.runner:getTile(tilePos)
tile:setTint(color(255))
end
end
end
I am surprised at first to see a black screen again, but of course the princess hasn’t moved yet. Once she moves, I see this:
Before I forget, let’s illuminate where we set her down:
function Player:init(tile, runner)
self.alive = true
self.tile = tile
self.tile:illuminate()
self.tile:addContents(self)
self.runner = runner
self.keys = 0
end
Now if illuminate were smarter, we’d have what we want.
Honestly, even as likely as it is that I’ll run into trouble doing this, I don’t see a productive way to test it. I’ll just go ahead.
Let’s try radial probes of radius 7, and every pi/8 around the circle.
How about this:
function Tile:illuminateLine(distance,angle)
local endPt = vec2(distance,0):rotate(angle)
local pts = Bresenham:drawLine(0,0,endPt.x,endPt.y)
for offset in ipairs(pts) do
local pos = self:pos() + offset
local tile = self.runner:getTile(pos)
tile:setTint(255)
if tile.kind == TileWall then break end
end
end
That turns out to need some repair. Here’s my present version:
function Tile:illuminate()
for theta = 0,2*math.pi, math.pi/32 do
self:illuminateLine(7, theta)
end
end
function Tile:illuminateLine(distance,angle)
local endPt = vec2(distance,0):rotate(angle)
endPt.x = math.floor(endPt.x + 0.5)
endPt.y = math.floor(endPt.y + 0.5)
--print(self:pos(), endPt)
local pts = Bresenham:drawLine(0,0,endPt.x,endPt.y)
print("pts ", #pts)
for i,offset in ipairs(pts) do
local pos = self:pos() + offset
--print(pos)
local tile = self.runner:getTile(pos)
tile:setTint(color(255))
if tile.kind == TileWall then break end
end
end
Note that I’ve pumped up the angle to pi/32, which means 64 lines around the circle. The picture we get is this:
The black holes are in fact floor tiles that we cannot see. You’d kind of expect to see at least one floor tile down a hallway, and I’m not at all clear on why we don’t.
Insert Long Delay
Various things have happened in the delay above, including a pleasant brunch with my wife.
In addition, I’ve drawn a number of pictures with the sample program, and have convinced myself that the Bresenham, rotated by a fixed theta, leaves holes where we definitely do not want them. I’ve done another experiment, drawing lines from the center tile to the 52 edge tiles at x and y at -7 and 7, and that looks to give good coverage:
I’ll change the code in the dungeon program to do what I did in that sample. That code looked like this:
for x = 0,7 do
paint(x,7)
paint(x,-7)
paint(-x,7)
paint(-x,-7)
end
for y = 0,6 do
paint(-7,y)
paint(7,y)
paint(-7,-y)
paint(7,-y)
end
end
function paint(x,y)
local target = vec2(10,8) + vec2(x,y)
Bresenham:drawLine(TheFloor, 10,8, target.x, target.y)
end
The second loop goes only zero to 6 because the first loop covers the corners. I think I should be able to just plug this in pretty easily.
function Tile:illuminate()
for x = 0,7 do
self:illuminateLine(x,7)
self:illuminateLine(x,-7)
self:illuminateLine(-x,7)
self:illuminateLine(-x,-7)
end
for y = 0,6 do
self:illuminateLine(-7,y)
self:illuminateLine(7,y)
self:illuminateLine(-7,-y)
self:illuminateLine(7,-y)
end
end
function Tile:illuminateLine(dx,dy)
local pts = Bresenham:drawLine(0,0,dx,dy)
for i,offset in ipairs(pts) do
local pos = self:pos() + offset
local tile = self.runner:getTile(pos)
tile:setTint(color(255))
if tile.kind == TileWall then break end
end
end
This does go in quite readily. However it still doesn’t really look right. I think I want to factor the distance back into the picture:
function Tile:illuminateLine(dx,dy)
local pts = Bresenham:drawLine(0,0,dx,dy)
for i,offset in ipairs(pts) do
local pos = self:pos() + offset
local d = self:pos():dist(pos)
if d > 7 then break end
local t = math.max(255-d*255/7,0)
if t > 0 then self.seen = true end
local tile = self.runner:getTile(pos)
tile:setTint(color(t,t,t))
if tile.kind == TileWall then break end
end
end
This puts the tint back but it still doesn’t always paint the walls as I think it should:
I suspect that my idea is working as I intended, and that we’re up against limitations of the idea. Let’s try to get the mini-map back and wrap this up. I think that we can now plug in a smarter illuminate method and improve our results.
For now, I want to get back to the functionality we had last time, which will be a bit improved because at least we won’t see double hallways and such.
I need to be sure to set seen when a tile is seen:
function Tile:setTint(aColor)
self.tintColor = aColor
if aColor.r > 0 then self.seen = true end
end
That plus a little care with tint, and we’re nearly good:
function Tile:draw(tiny)
pushMatrix()
pushStyle()
spriteMode(CORNER)
tint(self:getTint(tiny))
local sp = self:getSprite()
local center = self:graphicCorner()
sprite(sp, center.x,center.y, self.runner.tileSize)
for k,c in pairs(self.contents) do
c:draw()
end
popStyle()
popMatrix()
end
function Tile:getTint(tiny)
--if true and self.runner:playerDistance(self) < 7 then return color(255) end
if tiny then
return self:getTinyScaleTint()
else
return self:getLargeScaleTint()
end
end
function Tile:getTinyScaleTint()
if self.seen and self.kind == TileRoom then
return color(255)
else
return color(0)
end
end
function Tile:getLargeScaleTint()
if not DisplayToggle then return color(255) end
return self.tintColor
end
This code is a bit convoluted, mostly due to the oddness of DisplayToggle. I’ll have to sort that out.
But my main concern is to see whether something better can be readily done with illumination. I’ll have to do more reading, and I’m afraid I’m going to have to figure out shadow casting. The hardest part of that is that I’m sure it’ll need testing, and I don’t see quite how to do that other than visually, which really isn’t testing at all.
So thanks, Bruce. And see you next time!