Dungeon 311

Let’s work on the Spike aimed at creating DungeonObjects. Uh oh: Something too clever has been done here!

The purpose of a “Spike” is to quickly drive through a problem, so as to learn what the problem is, how we want to solve it, and what the solution code should look like. I often go into a Spike situation thinking that I know pretty much what I want, and I usually come out with something else. And, with rare exceptions, I come out with a much better understanding and better solution than when I went in.

There are exceptions. Once in a while, our understanding of the problem is so vague, or the problem some complicated, that the Spike just tells us that we don’t know yet. If that does happen, maybe we need to sit with the problem a bit, and quite likely we need to slice off a sub-problem and deal with that.

But that’s not the case today. Today I have a better idea of what I’m up to, and even some ideas about how to do it.

Let’s review.

Named Parameter Tables

The basic problem is to accept some kind of imaginary Level Designer input, which we’ll never really code up, and to inject it into dungeon creation, so as to populate a level with the desired distribution of Decor, Monsters, whatever. And the core of my proposed solution is that, given some basic information about, say, the kinds of Decor, the kinds of Loot, the kinds of pain, and the sort of room tiles that we want the Decor to inhabit, we spin through that information and create an array of tables, each element describing one desired Decor, and we spin through that array, creating and distributing the Decor items.

The central idea is that the array element will be a dictionary, with the key being the name of the Decor parameter, and the value being the particular value for the desired Decor, roughly:

{ kind="Skeleton2", loot=someLoot, pain=someDamage, tile=someTile}

The input to this process will be simple parallel arrays, each containing a particular element of the final dictionary, i.e. all the kinds, or all the loots, and we’ll just (there’s that word) zip them together and we’re good to go.

Parallel arrays, as Jeff Grigg reminded me, are a curse. But we have to start somewhere, and since I’d very much like to avoid a lot of parsing, I think we’ll go with the arrays, and get rid of them as quickly as we can.

Let’s see what we have in our Spike so far:

Spike Code

We have two tests, one that was rather irritating to write, and one that wasn’t:

        _:test("zip without replacement", function()
            local control = {"a", "b", "c", "d", "e", "f"}
            local without = { "y", "y", "z"}
            local kinds = makeTables("kind", control)
            local d = dump(kinds)
            --print(d)
            local expected = [[kind: a$$kind: b$$kind: c$$kind: d$$kind: e$$kind: f$$]]
            _:expect(d).is(expected)
            local zipin = {"u", "v", "w", "x", "y", "z"}
            local zipped = zip("loot", kinds, zipin)
            _:expect(#zipped, "wrong number of elements").is(#zipin)
            local zipexp = [[kind: a$loot: u$$kind: b$loot: v$$kind: c$loot: w$$kind: d$loot: x$$kind: e$loot: y$$kind: f$loot: z$$]]
            local zipdump = dump(zipped)
            --print(zipdump)
            _:expect(zipdump).is(zipexp)
        end)
        
        _:test("one zip step", function()
            local kind = {kind="a", pain="intense"}
            local loot = "aLoot"
            local zipped = cloneWithNewKeyedValue(kind, "loot", loot)
            _:expect(zipped.kind).is("a")
            _:expect(zipped.pain).is("intense")
            _:expect(zipped.loot).is("aLoot")
        end)

The functions I’m writing all need to go through one or more arrays of elements and “zip” them together, according to various simple rules. The first test tried to check the whole resulting array, and that required me to invent a way of dumping the elements to strings and then compare the strings. Really irritating.

The second test just tests an inner function that takes a dictionary and inserts a key-value pair into it. That function will be used inside a loop when all is said and done.

The code so far includes a few functions. That second test tests these two functions:

function cloneWithNewKeyedValue(keyedTable, key, value)
    local result = clone(keyedTable)
    result[key] = value
    return result
end

function clone(keyedTable)
    local result = {}
    for k,v in pairs(keyedTable) do
        result[k] = v
    end
    return result
end

We need to do the shallow copy of the input keyed table, because Lua passes tables by reference, and we would otherwise be changing the input parameter table. I think in my use here, that would be OK, but as a rule, it seems a bad idea. So we make the shallow copy in clone.

Then I have two versions of zip, one using FP functions and one not:

function zipFP(key, keyedTableArray, valueArray)
    assert(#keyedTableArray==#valueArray, "tables must have same length")
    local i = 0
    return ar.map(keyedTableArray, function(t1Entry)
        i = i + 1
        return cloneWithNewKeyedValue(t1Entry, key, valueArray[i])
    end)
end

function zip(key, keyedTableArray, valueArray)
    assert(#keyedTableArray==#valueArray, "tables must have same length")
    local result = {}
    for i,keyedTable in ipairs(keyedTableArray) do
        local element = cloneWithNewKeyedValue(keyedTable, key, valueArray[i])
        table.insert(result,element)
    end
    return result
end

Here, what we’re doing is to take an array of dictionaries, keyedValueArray, a key (string), and a value array, and produce a new array containing copies of the original dictionaries, with the new key-value inserted.

I think the order of the parameters there is more than a bit naff, since the key goes with the value array. Let’s change that rat now.

            local zipped = zip(kinds, "loot", zipin)

function zipFP(keyedTableArray, key, valueArray)

function zip(keyedTableArray, key, valueArray)

Commit: reorder zip parameters. (I do have this spike under version control, as I expect it to run for a while and I expect to make mistakes.)

Finally, I have a makeTables function:

function makeTables(key,tab)
    local result = {}
    for i,v in ipairs(tab) do
        local entry = {}
        entry[key]=v
        table.insert(result, entry)
    end
    return result
end

This, too, is not a great name. The function takes a simple array and produces an array of dictionaries, with each dictionary having the key as the input key parameter and the value, the corresponding array element.

I think we can rewrite that function using our FP functions.

function makeTables(key,tab)
    local f = function(element)
        local entry = {}
        entry[key] = element
        return entry
    end
    return ar.map(tab, f)
end

It’s unfortunate that we can’t just return

{ key=element }

But the key we want isn’t “key”, it is whatever value key holds. If there’s a one-line way to say that in Lua, I don’t know it. Anyway I prefer that to the longhand way, for expressivity, though some may disagree. I have a sort of long-range objective of using the FP methods until I get totally used to them.

Digression on FP

Note what I had to do with the index in the zip function:

function zip(keyedTableArray, key, valueArray)
    assert(#keyedTableArray==#valueArray, "tables must have same length")
    local i = 0
    return ar.map(keyedTableArray, function(t1Entry)
        i = i + 1
        return cloneWithNewKeyedValue(t1Entry, key, valueArray[i])
    end)
end

An ordinary Lua loop over an array includes the index and the value. But my fp functions do not:

fp.map = function(t,f)
    local result = {}
    for k,v in pairs(t) do
        result[k] = f(v)
    end
    return result
end

It seemed to me that that form followed other languages’ FP implementations, but sometimes, at least as I’m using them, I want to work with both the key and the value of a table. It is tempting to change my FP implementation to provide that ability. I could imagine leaving, say, map alone, and building map2 that would pass in both key and value:

fp.map2 = function(t,f)
    local result = {}
    for k,v in pairs(t) do
        result[k] = f(k,v)
    end
    return result
end

Or, I could just change it to always do that, which would require my users (me) to change their code. Or, possibly, I could reverse the order, returning the index after the value, which would mean that your function could include that parameter if you wanted it, but functions written the old way would continue to work.

Something for the future, but since we own FP as well as Dungeon, we do well to consider whether our various libraries are sufficiently helpful.

But we digress.

Focus

Let’s focus a bit. We’re here to convert some arrays of parameters into an array of dictionaries, each dictionary containing the parameters for just one object creation. We have a function that will suffice to convert the first array to an array of dictionaries, and another that will zip in a second array, giving its elements a provided name in the dictionary. For safety, we’re shallow-copying at each step.

That’s enough to do the job for a fully-specified set of arrays, but I have more in mind.

I also envision functions to map a table of elements and a table of counts into an array with repeated elements:

{ a, b, c } with
{ 3, 2, 3 } gives
{ a, a, a, b, b, c, c, c }

Further, I can imagine even more capable kinds of input combinations, such as allowing the array to be filled out with sufficient trailing default values to get to the desired size, or an array-like thing that we can draw from, with or without replacement, to give the designer probabilistic control over the values provided. While we want to allow for exact control over what goes into the dungeon, we are sure that more commonly we’ll want to specify something simpler, along the lines of:

Provide 20 Monsters, 1/3 Ankle Biters and 2/3 Ghosts.

And have the DungeonBuilder just roll up 20 monsters probabilistically.

We want to explore the Level Design problem enough so that we’re sure we can solve any reasonable need, but since we don’t really have Level Designers on staff, and we’re not really building an actual game, as far as I know, we don’t need to provide everything, so much as show that we can. (And, because we’re probably going to follow up with (ScopeMaster_)[https:twitter.com/ScopeMaster_), we may want to be able to state these ideas clearly, and even to have a sense of how long it might take to do them.)

So … let’s write a test that sketches how we might create Decor right now. I’ll leave out the pain control, because we haven’t written that yet, and just do Decor type vs Loot and tile.

        _:test("sketch Decor creation", function()
            local decors = {"chest", "box", "vase"}
            local loots = { "l1", "l2", "l3" }
            local tiles = { "tile1", "tile2", "tile3"}
            local decorTable = makeTables("kind", decors)
            local withLoots = zip(decorTable, "loot", loots)
            local withTiles = zip(withLoots, "tile", tiles)
            local middle = withTiles[2]
            _:expect(middle.kind).is("box")
            _:expect(middle.loot).is("l2")
            _:expect(middle.tile).is("tile2")
        end)

That test actually runs now. But the larger learning is this: it’s not terribly convenient to write. Seems a bit irritating to have to do it step by step like that. A fluent interface might be better. What if we could say this:

        _:test("sketch fluent Decor creation", function()
            local decors = {"chest", "box", "vase"}
            local loots = { "l1", "l2", "l3" }
            local tiles = { "tile1", "tile2", "tile3"}
            local withTiles = makeTables("kind", decors):zip("loot", loots):zip("tile", tiles)
            local middle = withTiles[2]
            _:expect(middle.kind).is("box")
            _:expect(middle.loot).is("l2")
            _:expect(middle.tile).is("tile2")
        end)

That would be nifty.

Let me try an evil hack:

function zip(keyedTableArray, key, valueArray)
    assert(#keyedTableArray==#valueArray, "tables must have same length")
    local i = 0
    local result = ar.map(keyedTableArray, function(t1Entry)
        i = i + 1
        return cloneWithNewKeyedValue(t1Entry, key, valueArray[i])
    end)
    local meta = {}
    meta.zip = zip
    meta.__index = function(t,k)
        return meta[k]
    end
    setmetatable(result,meta)
    return result
end

function makeTables(key,tab)
    local f = function(element)
        local entry = {}
        entry[key] = element
        return entry
    end
    local result = ar.map(tab, f)
    local meta = {}
    meta.zip = zip
    meta.__index = function(t,k)
        return meta[k]
    end
    setmetatable(result,meta)
    return result
end

What I’ve done here is to provide my result tables with a metatable that specifies a function for zip and that specifies that if the base table doesn’t have a given key, return the value from the metatable. So when we look for zip in the base table, we seek and find the zip function in the metatable, and call it.

So the code in the test actually works.

As written, however, it is almost certainly too clever to live, although it is perfectly legitimate Lua and a decent example of how one might create a fluent interface to some tables. However, in the current style chez Ron, I think we’d do better to embed this kind of thing in an object rather than tables with metatables.

We’ll need to think about that. And it is time for Sunday brekkers, so let’s wrap up.

Wrapping Up

We actually made some interesting progress today. We’ve seen that what we have is sufficient for the basic case of making our parameter dictionaries from our imagined starting arrays.

We’ve seen an interesting, although perhaps too clever approach to a fluent interface, which would certainly be useful to the level-designing programmer. We should explore doing a similar thing with objects.

Spikes are for learning, and we’ve definitely learned some things. Material for thought.

For estimation purposes, we have to sessions now consisting of little more than “design” for how to do the Level Design thing. It’s design with code, however, which will pay off when we get to the writing of the real thing.

See you next time!