Dungeon 225 - Squirrel!

An idea from the Zoom Ensemble last night has caught my attention. Let’s explore it.

We were looking at Bryan’s new dungeon program. He has restarted to try out some different ideas and a different angle on the “product”. As always happens, the people not doing the work had all kinds of good ideas about what Bryan should do, since we wouldn’t have to do it. Along the way, we did help solve a problem in his existing code based on an issue that at least a coupe of us had already run into in our own code.

We have all made the same mistake. When we have something like a dungeon, dimensioned in x and y, if we ever refer to it in terms of row and column, we almost invariably put row where the x should be and column where the y should be an hilarity ensues. Why? I think it’s because of how we speak. We speak in terms of row-column, we speak of x-y … and those are reversed.

Anyway, we got to talking about the walls and doors of the dungeon, and I was on some rant about how there was no difference between a wall and a door, and for that matter, there were really wall-doors in between any two adjacent tiles. You know how I get, or you don’t, consider yourself lucky.

This morning, I wrote this into our Slack channel.

Slack Idea

Related random notion. Imagine a tile. It has coordinates. If I had my druthers it would have tile coordinates, that is 0, 1, 2, not 0, 5, 10 in graphics. There’d be a central scaling factor to covert tile coords to graphical. But I digress. Imagine that the tile has 4 (assuming it’s a square, 6 if it is a hex) Boundaries. These boundaries are indexed, probably N E S W 0, 1, 2,3 but maybe just indexed “North”, “South” or North, South if North is some kind of object.

So all Tiles have Boundaries on all sides. We’re trying not to know what the sides are but in our hearts we know they are N S E W in some way. Boundaries have properties, including some info on how they are drawn. Perhaps some are drawn as a heavy solid line, some as a line with a square in the middle of it, some as a very thin line. Another property of a Boundary is, I’m not sure here, for now let’s say “Pass/Stop”. If the Boundary is Pass, the player can go through it. If Stop, then not. It is possible that there is a way (hint: key) to change some boundaries from Stop to Pass.

A Boundary will generally (always?) belong to two tiles, i.e. the one below and the one above or the one to the right and the one to the left. And the boundary needs to know, I fear, whether it is horizontal or vertical, i.e. EW or NS, so that it can draw itself properly. Maybe it just has a line that happens to be NS or EW and doesn’t really know H or V. That would be neat.

And entity on a tile picks a direction to go. A direction, probably is always a vector, one of four: <-1,0>, <1.0>, <0,1>, <0,1>. No one knows which if those is N W S or E but the button that points up creates <0,-1>, and the button that points left creates <-1,0>. (This makes me think that Boundaries are indexed by those four vectors, because:)

When we try to move in the direction <x,y>, we ask the boundary on the current cell to give us the Tile coordinate to move to, given that our current Tile coordinate is <tx,ty>. The boundary is like “Am I open? If so, return Tile coordinate plus direction coordinate, else return Tile coordinate.

So far, no one knows anything about N, S, E, W, nor can even tell the difference between H and V.

That seems so interesting that I might even try it. Maybe with hexes, just for grins.

For extra credit, there could be a TeleportingBoundary that, if it is Open, tells you, not Tile xy + Direction xy, but some other really different <TTX,TTY> that beams you elsewhere in the dungeon. “You have fallen into a deep pit and find yourself in a new dark part of the dungeon.”

This scheme builds a lot of objects, I think approximately 3 times the number of tiles, if tiles are square. 4 if hex. The objects are rather highly linked, since each Tile has four Boundaries, and each Boundary … well, maybe not. Maybe it doesn’t have its Tiles. It’s always going to be given any coordinates it needs. So the linkage only goes one way, from Tile to Boundaries. Not so bad. As you were.

Well, That’s the Idea.

So I’m thinking today that I might start trying out that idea, and writing about it, not necessarily in that order.

When I’m working on a program, I mostly focus on improving the design locally, identifying duplication and so on, and slowly refactoring to keep moving the design toward “good”. I like to push the limits of what can be done by small refactoring steps rather than big replacements or rewrites.

However, I also try always to be thinking about what a “perfect” design for the thing in hand might be. I try to be sensitive to the tiny things I have to do that get in the way, but also to the larger and larger scheme of things.

An example in the current Dungeon program is the Player and the Monster. They both inherit from Entity, which tries to absorb most of the common elements of their behavior. But I don’t find that situation to be entirely satisfactory. It seems to me that a Monster and a Player should be exactly the same, except in how they decide to move. The Monster has an algorithm to move him, the Player is moved by button presses. Otherwise, they’re the same. (Well, except …)

Point is, I try to have a growing understanding of what a “perfect” design would have been for what I’m doing, and when I refactor, I try to push the design in that direction. Sometimes I get all the way. More often, I don’t, but usually I make things better. Sometimes, well, sometimes the Monster bites you, and you make things worse. That’s why we have revert.

OK, but what about these Tiles and Boundaries?

I suppose I could refactor the existing program in the direction of the Tile-Boundary notion, but at this point it’s just a notion, and I’d like to understand it better. And besides, I’m bored with the existing program. So I think what I’d like to do is try the Tile-Boundary idea in a new program. And, sure, just to make it interesting, let’s try hexagonal tiles.

One more thing that may not be clear from all this musing. I have in mind that the Tiles and Boundaries will not have any real notion of direction. No North-Sound or Right-Left. It’s just that two tiles have a boundary in common, and that’s about it. The reason for that is twofold. First, I don’t want to fall into the trap of breaking out directions, and second, I have a vague intuition that it’s possible to do without.

Let’s get started.

D3

I start with a new Codea program, named D3, including CodeaUnit and nothing else.

Now I have to think a bit about Hex Tiles, and about some tests. I don’t want to worry much about graphics, but I do want to be able to draw the things, for fun, and because it will make problems more visible. And there will be problems: there always are.

Hex-based maps are interesting. They have discernible rows, but not columns so much as two sort of diagonal columns.

When I think of indexing that sort of thing, it’s easy to see how to handle the row numbers, but it seems that there’s a different number of hexes in the even rows than in the odd rows.

Ow. There I go thinking in rows and columns, and you know we’re going to start talking about x and y real soon now. Must try to use only one of those notions in the code.

What should the data structure be for our setup? Certainly each Tile will want to know where it is, if only so that it can draw itself. Let’s assume that they’ll have x and y, both ranging from 1 upward. (I’ll use 1 because Codea indexes start at 1. If this were some other language, zero might be better.)

Looking at the picture above, it’s obvious that the x coordinate of the next y up or down is one-half the width of the hex. It’s not obvious what the y coordinate is, some kind of trig function that we can figure out, but that I, at least, don’t have in my head. Also I don’t care.

OK, let’s see if we can at least begin with a test. Let’s create a collection of Hexes (renaming Tile), with a range of x values and y values, such that …

You know what, I was going to make the rows and columns different lengths, but instead, let’s just let the length be the same and there will be an extra tile hanging off the right hand end.

Oops, there I go with row and column again. The x count of hexes will be the same for each y value, not dependent on parity.

Begin with a Test

Well, this turned out to be interesting:

        _:test("Array of Array of Hexes", function()
            local hexes = createHexes(15,10)
            _:expect(hexes:xCount()).is(15)
            _:expect(hexes:yCount()).is(10)
        end)

I found myself deciding to have a plain function to create the hexes … but that the thing created is an object that knows how many hexes (or whatever is in there) there are in x and y.

This, of course, can be created trivially, so that’s what we’ll do:

function createHexes(xCount, yCount)
    return HexArray(xCount, yCount)
end

HexArray = class()

function HexArray:init(xCount, yCount)
    self.xC = xCount
    self.yC = yCount
end

function HexArray:xCount()
    return self.xC
end

function HexArray:yCount()
    return self.yC
end

Test runs.

This is different from what I’ve done historically. Last night, I accused Bryan’s code of suffering from “primitive obsession”, the tendency to keep information directly in primitive objects like strings and numbers and arrays. I fall into that same trap often, especially with collections, which, too often, I just create as tables. This time I’ve got an actual class, HexArray.

Let’s see if that helps. And let’s see if naming it “Array” turns out to lead us astray.

What is amusing so far is that this HexArray has no Hexes in it. It just says it has them. Liar. Well, I don’t know what a Hex is, but I do think we’re going to have a 2D array of them, and I think in Lua we do that with a table of tables. Let’s posit that a hex knows its x and y, though I’d rather they didn’t. But we need something to test.

I extended the test this way:

        _:test("Array of Array of Hexes", function()
            local hexes = createHexes(15,10)
            _:expect(hexes:xCount()).is(15)
            _:expect(hexes:yCount()).is(10)
            _:expect(hexes:get(5,5):coords()).is(Coord(5,5))
            _:expect(hexes:get(7,9):coords()).is(Coord(7,9))
        end)

I’m positing a get method on HexArray, a coords method on Hex, and a new object, Coord, with x and y values. At least that’s what I’m thinking.

This will take a bit of code. A smaller test might be better but let’s see if I can stretch this far.

OK, this went well. Here’s all the operational code now:

function createHexes(xCount, yCount)
    return HexArray(xCount, yCount)
end

Coord = class()

function Coord:init(x,y)
    self.x = x
    self.y = y
end

function Coord:__eq(aCoord)
    return aCoord:is_a(Coord) and self.x == aCoord.x and self.y == aCoord.y
end

HexArray = class()

function HexArray:init(xCount, yCount)
    self.xC = xCount
    self.yC = yCount
    self.contents = {}
    for x = 1,xCount do
        self.contents[x] = {}
        for y = 1,yCount do
            self.contents[x][y] = Hex(x,y)
        end
    end
end

function HexArray:xCount()
    return self.xC
end

function HexArray:yCount()
    return self.yC
end

function HexArray:get(x,y)
    return self.contents[x][y]
end

Hex = class()

function Hex:init(x,y)
    self.coord = Coord(x,y)
end

function Hex:coords()
    return self.coord
end

The Coord class has an x and a y, and so far only knows how to answer whether it is equal to another Coord. To do that I had to use two meta-methods. I had to implement --eq on Coord, and inside I used the is_a method to be sure I was comparing with another Coord.

The new Hex class contains a Coord and can return it.

And the Hexes class creates a two-dimensional array of Hex objects.

I made two mistakes in doing the above. I tried isA instead of is_a, because of a googling mistake, and I forgot to initialize ‘self.contents = {}’.

Not bad. I impress myself.

Let’s work on drawing these babies. And let’s do as much as we can with tests.

Our Hexes just know a coordinate, which just knows an integer x and y. We’ll have to fetch those out, I have no doubt. (No poem intended.)

Should I say something about why I picked the notion of Coord instead of putting x and y in the Hex? I’m just in a mood to make everything into objects. We may change that later or then again maybe not.

To draw an actual picture of an array of hexes, we’ll want to provide some information, or at least have something rigged up in the drawing transformations, to give us an offset on the screen for our array, and a size at which to draw. A 1 pixel Hex isn’t going to be very useful.

I think I’ll just let the little devils work in numbers for now and see if I can pick it all up with graphical scaling.

So let’s see. I’m considering the bottom-most row, number 1, and all the odd row … there I go again with rows and columns.

I consider the lowest y coordinate batch, with y = 1, and the other odd values of y, to start at x + 0.5, offset by half a Hex. The even y ones will position at just plain x.

What about the y coordinates? Let’s defer doing the math and just use y as is. The real value is some trig value less than 1.

Now how do we draw a hexagon of size 1 (radius 1/2?) at some point?

A Little Trick

Let me share with you a little trick, drawing a nearly perfect hexagon on grid paper. Take a look at this:

For the sides that are parallel to the axes, draw lines 8 long. For the diagonals, go toward the other side 7 and out 4. Connect the dots.

How perfect is that? The diagonals’ lengths are the square root of 7^2 + 4^2 or 49 + 16 or 65. That amounts to

8.0622577483

Close enough to 8? That’s my story and I’m sticking to it.

Looking at that picture makes me think that the graphical y coordinate is 1.5 times the Hex’s y coordinate.

Let’s begin by drawing just the centers of our hexes. With a test:

        _:test("Graphical Coords", function()
            local hexes = createHexes(15,10)
            local h11 = hexes:get(1,1)
            local h21 = hexes:get(2,1)
            local h11pos = h11:screenPos()
            local h21pos = h21:screenPos()
            _:expect(h11pos.x).is(0)
            _:expect(h21pos.x).is(1)    
        end)

That’s the easy part the bottom row coordinates go 0, 1, etc.

To make that work:

function Hex:screenPos()
    return self.coord:screenPos()
end

function Coord:screenPos()
    local x = self.x - 1
    if self.y%2 == 0 then
        x = x + 0.5
    end
    y = 0
    return vec2(x,y)
end

You may notice there that I coded past what I tested, with that check for the value of y. Bad Ron no biscuit. Better expand the test. I’ll do some Y as well.

Arrgh, my test is wrong and so is my code. The first row should be offset by 1/2 in x. The y = 1, 3, 5 rows should be offset. Fix the test then the code:

        _:test("Graphical Coords", function()
            local hexes = createHexes(15,10)
            local h11 = hexes:get(1,1)
            local h21 = hexes:get(2,1)
            local h12 = hexes:get(1,2)
            local h22 = hexes:get(2,2)
            local h11pos = h11:screenPos()
            local h21pos = h21:screenPos()
            local h12pos = h12:screenPos()
            local h22pos = h22:screenPos()
            _:expect(h11pos.x).is(0.5)
            _:expect(h21pos.x).is(1.5)
            _:expect(h11pos.y).is(0)
            _:expect(h21pos.y).is(0)
            _:expect(h12pos).is(vec2(0,1.5))
            _:expect(h22pos).is(vec2(1, 1.5))
        end)

And the new code:

function Coord:screenPos()
    local x = self.x - 1
    if self.y%2 == 1 then
        x = x + 0.5
    end
    local y = (self.y-1)*1.5
    return vec2(x,y)
end

Those are the figures I want. Notice that I’m working with fractional coordinates, which of course won’t display well. Let’s create some hexes and draw something. I plan to draw dots at the centers first.

Drawing

Hm so that didn’t go quite as I planned. Here’s the code for drawing after a few cuts:

function setup()
    if CodeaUnit then 
        codeaTestsVisible(true)
        runCodeaUnitTests() 
    end
    Hexes = createHexes(10,15)
end

~~~lua
function draw()
    if CodeaUnit then showCodeaUnitTests() end
    pushMatrix()
    pushStyle()
    ellipseMode(CENTER)
    stroke(color(255))
    fill(color(255))
    translate(500,100)
    scale(50)
    for x = 1,10 do
        for y = 1,15 do
            local hex = Hexes:get(x,y)
            local coord = hex:screenPos()
            rect(coord.x, coord.y, 1.1, 1.1 )
        end
    end
    popStyle()
    popMatrix()
end

And here’s the picture:

What is this telling me? Well, one thing it’s suggesting to me is that my scheme of using tiny values and then scaling only in the graphics may be problematical. Those fuzzy things are filled rectangles, very small, scaled up. The drawing and filling for rect is weird at that tiny scale. I started with ellipse to draw circles, and it was even worse.

And the spacing looks suspect as well. I’m not sure but I think the rows are spaced too far apart.

Let’s see if we can draw some lines instead of those rectangles.

    for x = 1,10 do
        for y = 1,15 do
            local hex = Hexes:get(x,y)
            local coord = hex:screenPos()
            local cx = coord.x
            local cy = coord.y
            line(cx-0.3,cy-0.3, cx+0.3, cy+0.3)
            line(cx-0.3,cy+0.3, cx+0.3, cy-0.3)
        end
    end

Now we get this, which is at least sort of intelligible:

I’m sure the rows are too far apart. And after all, if the x’s are 1 apart, the rows should be less. So it’s probably not 1.5, it’s probably 0.75. Fix the tests and code:

        _:test("Graphical Coords", function()
            local hexes = createHexes(15,10)
            local h11 = hexes:get(1,1)
            local h21 = hexes:get(2,1)
            local h12 = hexes:get(1,2)
            local h22 = hexes:get(2,2)
            local h11pos = h11:screenPos()
            local h21pos = h21:screenPos()
            local h12pos = h12:screenPos()
            local h22pos = h22:screenPos()
            _:expect(h11pos.x).is(0.5)
            _:expect(h21pos.x).is(1.5)
            _:expect(h11pos.y).is(0)
            _:expect(h21pos.y).is(0)
            _:expect(h12pos).is(vec2(0,0.75))
            _:expect(h22pos).is(vec2(1, 0.75))
        end)

function Coord:screenPos()
    local x = self.x - 1
    if self.y%2 == 1 then
        x = x + 0.5
    end
    local y = (self.y-1)*0.75
    return vec2(x,y)
end

That gives us this picture, which looks more reasonable:

Now let’s see about drawing some actual hexagons. I’ll have to work out how to do this. OK, how about this:

The corners of our desired hexes are at 60 degree angles. The top-most corner is at 12 o’clock, or an angle of 90 degrees. If we start with a vector (0,1) and rotate it and draw lines between the points … we should get a hexagon.

And my guess is that we really want the vector to be only (0,0.5) because we’re on 0.75 centers up and down. I’ll punch that in and see what I get:

    for x = 1,10 do
        for y = 1,15 do
            local hex = Hexes:get(x,y)
            local coord = hex:screenPos()
            local cx = coord.x
            local cy = coord.y
            local prev = vec2(0, 0.5)
            for rot = 1,6 do
                local next = prev:rotate(math.rad(60))
                line(cx+prev.x, cy+prev.y, cx+next.x, cy+next.y)
                prev = next
            end
        end
    end

That gives me a very promising picture indeed:

Scaling the lines thinner gives this:

I can see that the spacing isn’t right. Of course I was working from my drawing, which is an approximation. That could be the problem. But even so, we seem to be on the right track. It’s noon here chez Ron, so let’s wrap this up.

That’s a Wrap

Thinking big picture first, we started thinking in terms of a collection of Hex objects, and the Hex objects basically know nothing but a Coord object (should we name that Coordinate? probably.) The Coord object knows how to translate itself to a “graphical position” which is just an elementary calculation on its x and y values, resulting in tiny fractional values.

We are assuming, for now, that we can manage everything else by scaling up those tiny values and drawing at arbitrary positions.

Now my x and y offset values for the graphical position are clearly only approximate. If we assume “unit” hexagons, then the corners are at a radius of 0.5, and that means that the flat sides in x direction are less than 1.0 apart. We’ll have to do the real trig to work all that out. But those are just constants and once we know them, we’ll know them.

What is perhaps the nicest outcome so far is that even the graphical coordinates are covered by tests. I don’t usually get close to that result, since I tend to think “no way to test that” and then just draw and look at the picture. So I’m giving myself a little pat on the back there.

Anyway, this is just a tiny start, but I like how it’s going. I think we’ll play with this for a few days, and see what we come up with. I doubt we’ll convert the Dung program to hexes … maybe we’ll start something new. I don’t know. I’m just doing etudes here.

Questions via Twitter welcome if you have ‘em. See you next time!