Dung

Some pals are Zoom-mobbing on a dungeon program that one of us was working on. I’m gonna try one in Codea.

I’ve titled this series consciously, because I am expecting some kind of disaster with this effort. I’ll return to Invaders and Asteroids, at least for some summing up articles, in due time.

Like the blurb says, a gang of us have started meeting on Zoom, and we’re working on a dungeon program that one of us has got a start on. We’ve most of us never really mobbed before, and we haven’t seen the code before, and we have no idea what we’re doing. So that’s fun.

There’s a lot of prior art on making what I think is called a Roguelike dungeon game, Rogue, I gather, being an early example. And in this series I plan to follow that art, and I plan to write almost everything from scratch in Codea Lua. I’m going to try hard to use TDD wherever I can, and as always I’ll show my work–and my mistakes–as we go along.

We’ll start with the dungeon creation. A dungeon winds up being a bunch of rectangular rooms, on a rectangular grid, joined together by hallways. The creation, as I understand it, consists of these phases:

1. Draw a bunch of randomly-sized rectangles, all within a small area of the space;
2. Separate the rectangles so that they are not overlapping;
3. Designate some of them as interesting;
4. Create a non-overlapping path between them;
5. Simplify that path to have no loops;
6. Put some loops back in;
7. Create hallways as needed to connect everything.

That’s my understanding, and it wouldn’t surprise me if that’s already wrong. Along the way, the cool kids use:

• A separation algorithm to spread the rectangles out but not too far;
• Delaunay triangulation to connect them;
• Some kind of path simplification to remove loops;
• Apparently random ad-hocery to put some loops back in.

With that done, and a bit more, you’ve got a graph of rectangles representing rooms and hallways and if you can only draw that and put your player in it, you’ve got a game.

I do plan to look up the Delaunay and other algorithms, but my intention is not to grab code but to write it all, hopefully with TDD.

I can see no way this cunning plan can go wrong. Shall we get started?

Random Rectangles

Apparently you start with a bunch of rectangles all falling within some small area. There’s a lot of talk about using a circle, but I see no reason offhand not to use a rectangle. The rectangles will have a random center point and random size, not too large and not too small.

I’m not sure what to do about scaling, but my success with scaling Invaders leads me to ignore it for now, but to give my rectangles integer coordinates, width and height, all larger than zero, so that they’ll readily stay on the screen without scaling or translation, at least at first. I recall in one of the articles I read that the algorithm scaled all the points down into the range 0-1, but I’m not going to worry about that for now.

As I do this, I’ll TDD what I can, and I’ll be drawing the results to the screen as well, so that you–and, more importantly, I–can see what’s going on.

So let’s use the middle half of the screen, that is from 1/4 to 3/4 of height and width and put our centers there.

My current thinking is to move to classes very early on in this effort. I’ve seen some of the code people write for this app without classes, and it quickly gets gnarly.

My initial tests, quickly renamed from the CodeaUnitBase that I use, are these:

function testCodeaUnitFunctionality()
    CodeaUnit.detailed = true

    _:describe("Dung Tests", function()

        _:before(function()
        end)

        _:after(function()
        end)

        _:test("HOOKUP", function()
            _:expect("Foo", "testing fooness").is("Bar")
        end)
        
        _:test("Floating point epsilon", function()
            _:expect(1.45).is(1.5, 0.1)
        end)

    end)
end

They run as expected, one passing, one not. I’ll fix the bug:

            _:expect("Bar", "testing fooness").is("Bar")

And we’re green. Except that I haven’t put the coloring into the CUBase yet:

I’ll work on that outside these articles, if I do it at all. Now I’ll remove both those hookup tests and see what I can think of for a first real test.

We want random integer coordinates between WIDTH/4 and 3*WIDTH/4, similarly for height. That’s expressed in Codea as math.random(WIDTH/4,3*WIDTH/4) so it’s hard to get it wrong. I know I’m supposed to TDD, but I see no useful test.

I’m going to code some rectangles and draw them. I start here:

-- Dung
-- RJ 20201102

function setup()
    runCodeaUnitTests()
    Rooms = {}
    createRooms(20)
end

function draw()
    showCodeaUnitTests()
    for i,r in ipairs(rooms) do
        r:draw()
    end
end

I decided that the createRooms function takes a parameter, the number of rooms to create. That gives me something truly dull to test, but it will at least get me over into the Test tab. And immediately I see why it’s worth doing even for something this trivial:

        _:test("create 25 rooms", function()
            local rooms = createRooms(25)
            _:expect(#rooms).is(25)
        end)

My setup code above assumes that createRooms is going to store the rooms in the Rooms global. As soon as I started to test that I realized that I don’t want to hammer the global, and therefore createRooms needs to return a table. I’ll fix Main while I’m at it.

-- Dung
-- RJ 20201102

function setup()
    runCodeaUnitTests()
    Rooms = createRooms(20)
end

function draw()
    showCodeaUnitTests()
    for i,r in ipairs(Rooms) do
        r:draw()
    end
end

This will not run because there is no createRooms function.

Main:6: attempt to call a nil value (global 'createRooms')
stack traceback:
	Main:6: in function 'setup'

No surprise there. Let’s code it.

function createRooms(n)
    local r = {}
    for i = 1,n do
        table.insert(r,Room())
    end
end

I’ve asked for something called Room() and I have in mind a class. I’ll create a trivial one:

-- Room
-- RJ 20201102

Room = class()

function Room:init()
end

function Room:draw()
end

I rather expect the test to pass now. As usual, I am mistaken:

1: create 25 rooms -- Tests:18: attempt to get length of a nil value (local 'rooms')

Forgot to return the table, innit?

function createRooms(n)
    local r = {}
    for i = 1,n do
        table.insert(r,Room())
    end
    return r
end

1 Passed, 0 Ignored, 0 Failed

Yay, success. Oddly enough, that test caused me to avoid at least one mistake that would have led to some interesting debugging when it came down to drawing these little beggars.

I can feel a lot of parameters coming on here, but let’s begin by just creating x and y and drawing some standard size.

function Room:init()
    self.x = math.random(WIDTH/4,3*WIDTH/4)
    self.y = math.random(HEIGHT/4,3*HEIGHT/4)
end

function Room:draw()
    pushMatrix()
    translate(self.x,self.y)
    rect(x,y, 5,5)
    popMatrix()
end

I’m not going to TDD this part. Will discuss in a moment. I expect now to see 20 small rectangles in center screen. Or nothing, depending on how the colors are set. But that’s not what happens. This is:

1: create 25 rooms -- Room:7: bad argument #1 to 'random' (number has no integer representation)

The divide returns a float. We do not prefer a float.

function Room:init()
    self.x = math.random(WIDTH//4,3*WIDTH//4)
    self.y = math.random(HEIGHT//4,3*HEIGHT//4)
end

Our existing TDD test detected that error. Neat.

Then this:

Room:14: bad argument #1 to 'rect' (number expected, got nil)
stack traceback:
	[C]: in function 'rect'
	Room:14: in method 'draw'
	Main:12: in function 'draw'

Forgot the self:

function Room:draw()
    pushMatrix()
    translate(self.x,self.y)
    rect(self.x,self.y, 5,5)
    popMatrix()
end

That one, the TDD test didn’t find. I make the rectangle sizes larger and fill them for better visibility:

function Room:draw()
    pushMatrix()
    fill(255)
    translate(self.x,self.y)
    rect(self.x,self.y, 15,15)
    popMatrix()
end

The picture is not as I expect: The rectangles are clearly going off to the right. Also I am a fool, because if you’re going to translate you don’t also set the coordinate in the rectangle call:

function Room:draw()
    pushMatrix()
    fill(255)
    translate(self.x,self.y)
    rect(0,0, 15,15)
    popMatrix()
end

And we’re good:

I think it’s time to hook this baby up to Working Copy and commit.

That went smoothly except that my iMac is still horked, I believe by Catalina 10.15.7 and is basically running backward. I’ve no idea what is up with it. I did get a new iPhone but I don’t quite see why that would bring down my Mac.

Anyway, we’re good here for now. And if need be I can use my unupdated laptop to build the site. Maybe

It is 0802 and I’m at a stopping point having just committed the code. I’ll perform my daily ablutions and head to the store for a bit of food shopping and a chai.

It is now 0943 and time to do whatever’s next. I’m pleased that my trivial test found a bug, but I don’t see how I could test for the mistake where I both translated to x,y and drew at x,y. That shows up on screen but has no functional effect that I can figure.

Now to give these rectangles some width and height. I’m going to use rectMode(CENTER), which means the rectangles will be positioned with center at their x,y, and drawn with a provided width and height.

What should those be? Let’s imagine each dungeon being within our standard WIDTH and HEIGHT for now, although we’ll have to do something about that for small screens or large dungeons. For now, we’ll do that. Thinking of those values as roughly 1000, we might want our rectangles to be no larger than a tenth of the screen dimensions. I’ll try that:

function Room:init()
    self.x = math.random(WIDTH//4,3*WIDTH//4)
    self.y = math.random(HEIGHT//4,3*HEIGHT//4)
    self.w = math.random(WIDTH//20,WIDTH//10)
    self.h = math.random(HEIGHT//20,WIDTH//10)
end

And we’ll draw like this, after a bit of fiddling that I’ll explain below:

function Room:init()
    self.x = math.random(WIDTH//4,3*WIDTH//4)
    self.y = math.random(HEIGHT//4,3*HEIGHT//4)
    self.w = math.random(WIDTH//20,WIDTH//10)
    self.h = math.random(HEIGHT//20,WIDTH//10)
end

function Room:draw()
    pushMatrix()
    fill(255)
    stroke(255)
    strokeWidth(0)
    translate(self.x,self.y)
    rect(0,0, 10,10)
    fill(0,255,0,25)
    stroke(0,255,0)
    strokeWidth(2)
    rect(0,0, self.w, self.h)
    popMatrix()
end

function draw()
    showCodeaUnitTests()
    pushMatrix()
    pushStyle()
    rectMode(CENTER)
    for i,r in ipairs(Rooms) do
        r:draw()
    end
    popStyle()
    popMatrix()
end

The result looks like that. I fiddled with the fill color and stroke color and stroke width until I liked the look of it. Stroke width of 1 makes the lines around the rectangles almost invisible. And, as you can see, I left the centers displayed in white: I think that’ll come in handy soon.

We do have overlap and if we make more rooms we’ll have more overlap. Here are 50 rooms:

So that’s good. The next step may be more difficult.

Separation

Our mission is to separate the rooms, kind of spreading them apart until there is no overlap. One article I read did that in a clever way, by associating a physical body with each rectangle and letting the physics simulation in their system jostle them apart. A more common way is to use the flocking separation approach, which basically means that each bird (or rectangle) looks at its nearby neighbors, and steers away from them.

We don’t want them to separate forever, so somehow we need to set up a process that will settle down. Presumably this will be iterative.

I think our definition of “nearby neighbors” might be just “his rectangle intersects with mine”. We do have a routine in Invaders that answers that question, so that might be fine.

This is definitely an algorithm, so let’s see about TDDing it. I guess I’ll do rectangles intersect, then if I want to veer away from a rectangle foo, I’ll adjust my position by the distance between our centers. That might work. It should at least be interesting.

I am immediately stymied. My rooms are all created randomly. That’s no way to run a railroad. I need to break out creating a random room from creating one of known dimensions. Let’s do this:

Room = class()

-- class methods

function Room:random()
    local x = math.random(WIDTH//4,3*WIDTH//4)
    local y = math.random(HEIGHT//4,3*HEIGHT//4)
    local w = math.random(WIDTH//20,WIDTH//10)
    local h = math.random(HEIGHT//20,WIDTH//10)
    return Room(x,y,w,h)
end

-- instance methods

function Room:init(x,y,w,h)
    self.x = x
    self.y = y
    self.w = w
    self.h = h
end

Now I know I’m creating them directly with Room(). Would it be too tricky to let Room() create random rooms and Room(x,y,w,h) create specific ones? I’m going to try that instead of this.

function Room:init(x,y,w,h)
    self.x = x or math.random(WIDTH//4,3*WIDTH//4)
    self.y = y or math.random(HEIGHT//4,3*HEIGHT//4)
    self.w = w or math.random(WIDTH//20,WIDTH//10)
    self.h = h or math.random(HEIGHT//20,WIDTH//10)
end

This is pretty idiomatic Lua, I think, so let’s go with it and see. It at least avoids a class method. Now for that test:

        _:test("rooms intersect", function()
            local r1,r2
            r1 = Room(100,100, 20, 20)
            r2 = Room(120,1000, 20,20)
            _:expect(r1:intersects(r2)).is(true)
        end)

This will go red for there being no intersects:

2: rooms intersect -- Tests:25: attempt to call a nil value (method 'intersects')

And we’ll fake it till we make it:

function Room:intersects(aRoom)
    return true
end

Trivially correct. Now another:

        _:test("rooms intersect", function()
            local r1,r2,r3
            r1 = Room(100,100, 20, 20)
            r2 = Room(120,1000, 20,20)
            _:expect(r1:intersects(r2)).is(true)
            r3 = Room(130,130, 20,20)
            _:expect(r1:intersects(r3), "room3").is(false)
        end)

This of course fails, since all intersects are true:

2: rooms intersect room3 -- Actual: true, Expected: false

Now I could figure this out or I could steal it. I’m feeling “steal it from Invaders”. Here’s that code:

function rectanglesIntersect(bl1,w1,h1, bl2,w2,h2)
   local tr1 = bl1 + vec2(w1,h1) - vec2(1,1)
   local tr2 = bl2 + vec2(w2,h2) - vec2(1,1)
   if bl1.y > tr2.y or bl2.y > tr1.y then return false end
   if bl1.x > tr2.x or bl2.x > tr1.x then return false end
   return true
end

What the heck are bl1 and tr1 and those about? Ah, surely bottomLeft and topRight. Yeah, OK. Let’s use that as a template for our method rather than directly copy it. I don’t like it much. But it has worked for ages in invaders.

OK, I found the bug in the test where I put 1000 meaning 100, and now the test is:

        _:test("rooms intersect", function()
            local r1,r2,r3
            r1 = Room(100,100, 20, 20)
            r2 = Room(120,100, 20,20)
            _:expect(r1:intersects(r2)).is(true)
            r3 = Room(130,130, 20,20)
            _:expect(r1:intersects(r3), "room3").is(false)
        end)

And the code is:

function Room:intersects(aRoom)
    return intersectCorners(self:corners(), aRoom:corners())
end

function Room:corners()
    return {self.x - self.w//2, self.y - self.h//2, self.x + self.w//2, self.y + self.h//2}
end

function intersectCorners(corners1, corners2)
    x1lo, y1lo, x1hi, y1hi = unpack(corners1)
    x2lo, y2lo, x2hi, y2hi = unpack(corners2)
    if y1lo > y2hi or y2lo > y1hi then return false end
    if x1lo > x2hi or x2lo > x1hi then return false end
    return true
end

Because I’m using rectMode CENTER, I need to compute both corners of the rectangle. I’m assuming for the moment that integer division by 2 will give me a reasonable width and height, though the odd-even thing is going to be a bit problematical. We probably need to round or something, but this will do for now

I played with converting this function to use vec2 but the conversion back and forth seemed more trouble than it was worth, so I did it by returning a table and unpacking. It might be possible to remove the table brackets and pass 8 parameters. Shall we try it?

Let’s do. First a commit to revert to: intersect in progress.

This doesn’t work:

function Room:intersects(aRoom)
    return intersectCorners(self:corners(), aRoom:corners())
end

function Room:corners()
    return self.x - self.w//2, self.y - self.h//2, self.x + self.w//2, self.y + self.h//2
end

function intersectCorners(x1lo, y1lo, x1hi, y1hi, x2lo, y2lo, x2hi, y2hi)
    print(x1lo," ",y1lo," ",x1hi," ",y1hi)
    print(x2lo," ",y2lo," ",x2hi," ",y2hi)
    if y1lo > y2hi or y2lo > y1hi then return false end
    if x1lo > x2hi or x2lo > x1hi then return false end
    return true
end

The second parameter batch comes in as 110,nil,nil,nil.

Something doesn’t work with multiple args, though I’m not sure what. No point chasing it, we have a perfectly good way to which I’ll now revert.

Right. Tests green again. Let’s check a few more rectangles to see how well this function works.

            r4 = Room(119,100,20,20)
            _:expect(r1:intersects(r4), "room4").is(true)

OK, that works. Looking at the whole test, we might have questions:

        _:test("rooms intersect", function()
            local r1,r2,r3,r4
            r1 = Room(100,100, 20, 20)
            r2 = Room(120,100, 20,20)
            _:expect(r1:intersects(r2)).is(true)
            r3 = Room(130,130, 20,20)
            _:expect(r1:intersects(r3), "room3").is(false)
            r4 = Room(119,100,20,20)
            _:expect(r1:intersects(r4), "room4").is(true)
        end)

No, that’s good. The rooms r1 and r2 should intersect, since they include the 120,100 point. Let’s move over one and test that for false:

            r5 = Room(121,100,20,20)
            _:expect(r1:intersects(r5), "room5").is(false)

The tests pass. I think our intersect works well, at least for even sizes of rectangle. Odd sizes will be … odd.

Imagine a rectangle with center 100,100 and w and h = 5. When we go to compare it with another rectangle, we’ll compute this one’s lower left as 98,98 and its upper right as 102,102. That will be pessimistic. We could use the ceiling of the w//2 and h//2, which would make our check values be 97,97 and 103,103, which is larger than it really is. More nearly correct, though, in that we’ll detect a collision when we shouldn’t rather than miss one. I think I’ll do a test for that, but what should it be? Where will Codea actually put those lines? I have no useful idea.

        _:test("odd size rooms intersect", function()
            local r1,r2
            r1 = Room(100,100,5,5)
            r2 = Room(102,100,10,10)
            _:expect(r1:intersects(r2)).is(true)
        end)

To my surprise, that test passes.

Oh. My brain isn’t thinking in terms of rectMode CENTER yet, so I’ve been making up coordinates as if it was rectMode CORNER. This calls my previous test into question, but first let’s fix this one:

        _:test("odd size rooms intersect", function()
            local r1,r2
            r1 = Room(100,100,5,5) -- 98-102
            r2 = Room(104,104,5,5) -- 102-106
            _:expect(r1:intersects(r2)).is(true)
        end)

This comes out true because the compares, like r1 high against r2 low compares 102 vs 102. And the comparison we do is > to return a false, so these two appear to overlap. Which I suppose is what I want but it doesn’t settle my mind on the rounding issue. If I change the r2 to 105, the test should fail, and does. Now to put in the ceil thing:

function Room:corners()
    return {self.x - math.ceil(self.w/2), self.y - math.ceil(self.h/2),
     self.x + math.ceil(self.w/2), self.y + math.ceil(self.h/2)}
end

Note that I had to change the // to / so that the ceil had a fraction to work with. We need to remove some duplication.

function Room:intersects(aRoom)
    return intersectCorners(self:corners(), aRoom:corners())
end

function Room:corners()
    local hw = self:halfWidth()
    local hh = self:halfHeight()
    return {self.x - hw, self.y - hh, self.x + hw, self.y + hh}
end

function Room:halfWidth()
    return math.ceil(self.w/2)
end

function Room:halfHeight()
    return math.ceil(self.h/2)
end

Tests still green. And it’s past lunch time due to my late second-stage start. I’m going to put a fail into the first intersection test to remind me to check it more carefully.

        _:test("rooms intersect", function()
            _:expect(2, "check all these for proper CENTER handling").is(3)
            local r1,r2,r3,r4, r5
            r1 = Room(100,100, 20, 20)
            r2 = Room(120,100, 20,20)
            _:expect(r1:intersects(r2)).is(true)
            r3 = Room(130,130, 20,20)
            _:expect(r1:intersects(r3), "room3").is(false)
            r4 = Room(119,100,20,20)
            _:expect(r1:intersects(r4), "room4").is(true)
            r5 = Room(121,100,20,20)
            _:expect(r1:intersects(r5), "room5").is(false)
        end)

That fails nicely:

2: rooms intersect check all these for proper CENTER handling -- Actual: 2, Expected: 3

Commit: rectangle intersect nearly good.

Let’s briefly sum up.

Briefly Summing Up

We have our random rectangle drawing working on screen, and a rectangle intersection checker which probably works but needs a bit more testing.

The next step will be to do the separation trick. I think that may cause us to need to deal with screen scaling to keep things on screen, but we’ll see what happens.

So far so good. Not much to see here. See you next time!