Dungeon 227--Undecided

Bill Wake found an interesting site about hexes (not the magical kind) and now I’m not sure what I want to do.

On our Friday Night Coding Slack, where we meet on Zoom every Tuesday night, Bill Wake pointed to this link from Amit Patel, about programming hex maps. I’ve mentioned the Red Blob Games site before. It’s just packed full of outstanding information, ideas, and algorithms.

If you’re interested in the general topic of hexagonal grids, I commend that whole article to you. You’ll learn more, or at least different things, there than here. Now I am left with a problem.

My initial reaction to reading that page, expressed eloquently on our Slack, was

“That’s quite good, makes me want to give up.”

In terms of understanding hex grids, it would be hard to beat that article. And in terms of finding algorithms to use in my usual try something and improve it fashion, well, now my mind is tainted, and I’m not likely to find anything as good as what’s there.

Now, that’s OK. We can’t always find brilliant examples of what we’re trying to do, and I find that we can almost always start with something simple and evolve it into something quite strong enough to do the job for us. There are surely exceptions, especially in the area of pure algorithms: you and I aren’t likely to code up a better sort than we can find in the literature. On the other hand, the fact that a route optimization is NP complete doesn’t mean that a quick and dirty fill algorithm won’t help your monster find the WayDown. In the small, that works just fine. Searching the complete road system of the USA well, probably not.

Some of the ideas on Amit’s site are interesting in themselves, and it’s tempting to try some of the hex-indexing approaches there, and to do some pathfinding or something. We’d surely learn some stuff about hexes, and about what kind of weird things happen to an old guy TDDing in Codea.

On the other hand, I really came here to explore the notion of Tiles and Boundaries, in the context of my existing D2 Dung program. It had not entered my mind to use hex tiles in that game, or any game, but I was kind of wondering if a better notion of Tile and friends might improve the Dung code, and whether it could be plugged in simply enough to be done in small steps.

In a reasonable world, I’d have started with square tiles and none of this would have happened. But hexes have more boundaries and that seemed interesting.

Looking forward, I see at least these possibilities:

1. Ditch the hex tiles spike soon, possibly do a square tiles spike, or (this might be amusing) convert this spike smoothly to squares.
2. Push forward on hex tiles just for the sake of working with some of these cool ideas.
3. After #1 or #2, convert Dung to hex tiles just to see what happens.
4. Do a new game on hex tiles.

Or, of course, something else entirely. But I don’t have a something else entirely idea that appeals to me.

I should mention here the suggestion from “UberGoober” on the Codea forum, who challenged me to make my game actually interesting to play. I declined that nomination, because that’s a lot of work and I don’t see much prospect for the kind of learning that I like to write about. I also declined it because I don’t know how to make the game interesting and foresee that it would be masses of work.

I don’t think UberGoober was impressed by my answer. Honestly, I wasn’t either, but the above is my current view. Somewhere between don’t wanna and can’t anyway, I’m focused on how we create and evolve code, not on making a game people would actually play. I apologize for my position, but there it is.

Anyway, the question here today, and I should get an answer and move on real soon now is:

What Shall We Do Next?

OK, I choose this, at least for today. We’ll adopt one of Amit’s hex indexing approaches, and see about building up some fun stuff, maybe pathfinding and visibility. And then, if it seems interesting, maybe rig up at least a simple game that plays on hexagons.

I’ve not studied the Red Blob page, just read through most of it once, so I am in a fairly decent state of blissful ignorance about things, so I’m sure to make some interesting mistakes. In a real situation in my past, I might have studied the page in detail and worked through examples of much of it, to get a solid understanding of the ideas, and only then started programming.

That’s not my way now. I don’t recommend this, but I enjoy going into a thing less than fully prepared, learning as I go, and discovering what goes wrong and how to get out of trouble. I do that because it’s fun, of course, but also because in Real Programming, we usually are unaware of the pitfalls until it is too late, so our only hope is to find ways to incrementally get ourselves out of trouble. It’s my hope that these articles give the reader hope, hope that when things go bad, they’ll be able to smoothly improve the situation and get back into a good situation.

Hope is not a strategy, we’re told, but hope is a decent place to start making a strategy, for if there is no hope, we need not bother.

Wow, that got dark. Anyway, let’s look at indexing my Hexes.

Indexing

I think the cube notion of hex indexing is quite elegant. When we look at a hex map, we can see three “directions”, and of course if you look at a cube corner on, it looks like a hexagon. This picture from Red Blob shows what I think I’ll try to do:

The rules of cube coordinates are that the three x,y,z coordinates always sum to zero. This means that whenever you move from one hex to an adjacent one, two of the coordinates change. As Amit puts it:

Each direction on the hex grid is a combination of two directions on the cube grid. For example, northwest on the hex grid lies between the +y and -z, so every step northwest involves adding 1 to y and subtracting 1 from z.

So that will be interesting. Let’s decide that we’re going to build a hexagonal batch of hexes, which is kind of the natural growth pattern, starting with the (0,0,0) hex in the middle. I’m not sure quite how we’ll grow the pattern, around and around I suppose, but I think for now we have more basic issues to deal with.

Our Coord object has two values, x and y. We’ll need three. And we’d better implement the constraint that they sum to zero, because we’ve got a good chance of building them wrong. (There might be an issue with fractional coordinates, but we’ll worry about that later. The nice thing about this scheme is that the hex’s coordinates are all integral.)

Our conversion to screen coordinates will be wrong. Our hex drawing is probably nearly OK.

Let’s open this guy up and see what we can do. I’ll begin by looking at the tests, one at a time, and seeing what to do about them. Replacing seems likely. Here’s the first one:

        _: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)

This creates a rectangular array of Hexes. That’s right out, we’re going to create a grid with cubical coordinates.

I am sore tempted to blow all these tests away. They are certainly going to be seriously wrong. I’ll “ignore” them for now, because they probably contain ideas that we’ll want. Then I’ll start with scratch tests, guided by the (formerly) existing ones.

OK, the Coord needs some tests. I think we’ll give it the ability to move in directions, despite GeePaw’s suggestion yesterday that that’s not desirable. We’ll try to see what he was at. Do read that thread, it’s quite good.

So, Coordinate. Begin with a test.

        _:test("Coordinate Creation", function()
            local coord = Coord(0,0,0)
            _:expect(coord:valid()).is(true)
        end)

I didn’t see much point in checking x y and z, I don’t think even I can get that wrong, so I posited a valid method. Test fails, permitting me to code this:

Coord = class()

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

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

function Coord:valid()
    return 0 == self.x + self.y + self.z
end

I expect this to work. And it does. I truly HATE seeing the ignored ones printing out and it interferes with reading the good ones. I comment them out.

OK that works. I was going to test an invalid one but I have a better idea. CodeaUnit does allow checking that a call throws an error, and I’d like our Coords to check validity viciously. So let’s do this:

        _:test("Coordinate Creation", function()
            local coord = Coord(0,0,0)
            _:expect(coord:valid()).is(true)
            local f = function() Coord(1,1,1) end
            _:expect(f()).throws("Invalid Coord")
        end)

I think that’s the right syntax. Since I don’t like exceptions, I don’t do this much. Test should fail. And it does:

1: Coordinate Creation  -- Actual: nil, Expected: Invalid Coord

Now to throw:

function Coord:init(x,y,z)
    self.x = x
    self.y = y
    self.z = z
    if self:invalid() then error("Invalid Coordinates") end
end

function Coord:invalid()
    return 0 ~= self.x + self.y + self.z
end

That tells me I didn’t do the test correctly. You don’t call the function in expect, you let CodeaUnit do it:

        _:test("Coordinate Creation", function()
            local coord = Coord(0,0,0)
            _:expect(coord:invalid()).is(false)
            local f = function() Coord(1,1,1) end
            _:expect(f).throws("Invalid Coord")
        end)

OK, sweet. We can create hexes with valid Coords now. We still don’t know how to create our nice pattern, but let’s move in a different direction today. Let’s create a few valid hexes, and then give them a screenPos method and draw them.

Again, begin with a Test:

        _:test("Screen Positions", function()
            _:expect(Coord(0,0,0):screenPos()).is(vec2(0,0))
        end)

That seems legit. We’re doing to start in the middle of our raft of hexes, at the 0-0-0 one and move in all directions. So it should have the abstract screen position of 0,0. Recall that it is up to the screen drawing code to translate and scale.

It’s easy to make this test run:

function Coord:screenPos()
    local x = 0
    local y = 0
    return vec2(x,y)
end

That works. Why the x and y? Because I know that when I return a constant like vec2(0,0), a common mistake I make is to then compute the necessary x and y, and forget to plug the answers into the return line.

OK. We could figure this out, but let’s see whether Amit has done some work for us.

Well, he has and he hasn’t. He shows Hex to Pixel for Axial coordinates, but not for cubical.

function pointy_hex_to_pixel(hex):
    var x = size * (sqrt(3) * hex.q  +  sqrt(3)/2 * hex.r)
    var y = size * (                         3./2 * hex.r)
    return Point(x, y)

However, he also tells us how to convert cubical to axial:

function cube_to_axial(cube):
    var q = cube.x
    var r = cube.z
    return Hex(q, r)

function axial_to_cube(hex):
    var x = hex.q
    var z = hex.r
    var y = -x-z
    return Cube(x, y, z)

So that’s interesting. But I need a test. Let’s create a coord that is one away from 0-0-0, and calculate the results we expect.

        _:test("Screen Positions", function()
            _:expect(Coord(0,0,0):screenPos()).is(vec2(0,0))
            local oneUp = Coord(1,0,-1):screenPos()
            _:expect(oneUp.x).is(0.866, 0.01)
            _:expect(oneUp.y).is(1.5, 0.01)
        end)

I’m pretty sure we’re good here. I looked at one of my old diagrams rather than doing the math. Seemed safer. Now to convert Amit’s code. Futzing, I get this:

function Coord:screenPos()
    local q = self.x
    local r = self.z
    local x = (math.sqrt(3)*q + math.sqrt(3)/2*r)
    local y = 1.5*r
    return vec2(x,y)
end

There are some 1 + things in there that I don’t understand. I want my hex centered at 0,0. I think he may be centering on the corner. Anyway the answer needs to be what I have. The test nearly runs, except:

2: Screen Positions  -- Actual: -1.5, Expected: 1.5

The scheme that Amit uses has z pointing downward, so that moving up in the picture reduces z coordinates. This is perhaps due to the fact that python thinks 0,0 is at the top left of the screen. Codea thinks it is at bottom left.

So I think what I’ll do is negate the y coordinate. I think once that’s done everything should be “just fine”. Here’s the algorithm fancied up a bit:

-- algorithm from Red Blob https://www.redblobgames.com/grids/hexagons/
-- adjusted for our coords
--local cos30 = 0.8660254038 = sqrt(3)/2
--local sin30 = 0.5
--local sqrt(3) = 1.7320508076
function Coord:screenPos()
    local q = self.x
    local r = self.z
    local x = (1.7320508076*q + 0.8660254038*r) -- sqrt(3), sqrt(3)/2
    local y = -1.5*r -- we invert z axis for z upward
    return vec2(x,y)
end

Tests are green, time to commit: “Converting to Cubical Coords per Red Blob Games”.

Whew, I feel better now. Let’s draw a couple of hexagons and see what happens.

First, I need to create Hexes with the new coordinates.

I really should write a test for this but what is it going to do? Forgive me, but I’m going to convert the code and then see what to test.

I remove the HexArray class as completely out of date.

The first bit of Hex seems obvious:

Hex = class()

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

It has an accessor for coord, and it forwards screenPos to its coord. And it has this method:

function Hex:boundaryLine(angleIndex)
    local bTop = vec2(0.8660254038, 0.5)
    local bBot = vec2(0.8660254038, -0.5)
    local angs = {0,60,120,180,240,300}
    local ang = math.rad(angs[1+angleIndex%6])
    local vTop = bTop:rotate(ang)
    local vBot = bBot:rotate(ang)
    return {vTop.x, vTop.y, vBot.x, vBot.y}
end

That returns the boundary lines (surprise!) in zero-based coordinates. Because of something wrong with my mind, I looked up the angles. I’ll leave it for now but that should be fixed up in due time.

I think if we were to create a few Hexes in Main, they should draw correctly. Let’s find out.

function draw()
    if CodeaUnit then showCodeaUnitTests() end
    pushMatrix()
    pushStyle()
    ellipseMode(CENTER)
    rectMode(CENTER)
    stroke(color(255))
    strokeWidth(1.0/50.0)
    noFill()
    translate(WIDTH/2, HEIGHT/2)
    scale(50)
    local h1 = Hex(0,0,0)
    local h2 = Hex(1,0,-1)
    local hexes = {h1,h2}
    for i,hex in ipairs(hexes) do
        pushMatrix()
        local coord = hex:screenPos()
        local cx = coord.x
        local cy = coord.y
        translate(cx,cy)
        for rot = 0,5 do
            local bl = hex:boundaryLine(rot)
            line(table.unpack(bl))
        end
        popMatrix()
    end
    popStyle()
    popMatrix()
end

That should draw two adjacent hexes at the middle of the screen. And it does!

Just to be sure where the center is …

function draw()
    if CodeaUnit then showCodeaUnitTests() end
    pushMatrix()
    pushStyle()
    ellipseMode(CENTER)
    rectMode(CENTER)
    stroke(color(255))
    strokeWidth(1.0/50.0)
    fill(255)
    translate(WIDTH/2, HEIGHT/2)
    ellipse(0,0, 20,20)
    scale(50)
    local h1 = Hex(0,0,0)
    local h2 = Hex(1,0,-1)
    local hexes = {h1,h2}
    for i,hex in ipairs(hexes) do
        pushMatrix()
        local coord = hex:screenPos()
        local cx = coord.x
        local cy = coord.y
        translate(cx,cy)
        for rot = 0,5 do
            local bl = hex:boundaryLine(rot)
            line(table.unpack(bl))
        end
        popMatrix()
    end
    popStyle()
    popMatrix()
end

And we get a big dot right where we expect it:

Time to commit: two hexes draw as intended.

And let’s sum up.

Summary

So that went well. We converted our own rectangular coordinate notion to cubical, and lifted and adapted the screen conversion code to allow us to draw them in our desired fashion.

We have just a few tests in place, and should surely have a few more, but I feel confident in what we have, and I hope that you do as well. Tomorrow will tell the tale.

Well, tomorrow is Saturday, I suppose I might take tomorrow off, but probably not.

Formally speaking, what happened here could be called refactoring, because seen from the outside, our Hex behaves as it did before: it can be created and knows how to return enough information to be drawn. (I think it should know how to draw itself. We’ll consider the alternatives next time.)

But the work, to me, seemed more like “replace algorithm” than “smoothly move things never breaking anything until all of a sudden Voila! we notice that we have a new design”. And it’s that latter form of refactoring that I prefer.

I didn’t get to name “refactoring”, so let’s face it, if the results are the same before and after, it’s refactoring. It just might be kind of abrupt.

I think that so far, we’ve not violated the spirit of GeePaw’s muse, and with any luck, we never will. We’ll have to see what happens.

I hope you’ll follow along. See you then!