Dungeon 170
The business people–me, with my business hat on–want to be able to better define levels in the game. The tech people–my other hat–get to figure out how to do this.
We’ve talked, the business people and tech people, about gae play, set pieces, puzzles, and so on. We’ve determined that it’s time to begin to provide ways to design levels rather than just let them be random.
Now, to tell the truth, which I generally do, I didn’t have this in mind when I started this project. I didn’t have 170 articles in mind, either. It just seemed like something fun to do, after the antique arcade games. So there has been no planning or designing to make it possible to define a dungeon level. They’re random. And the game doesn’t even think in terms of rooms and hallways. It thinks in terms of tiles, which if they are floor tiles you can walk on them, and if they’re wall tiles, you can’t.
Yesterday I tweeted about part of the problem, as I was thinking about it:
I have what seems to me to be an “interesting” problem in my long-running Dungeon series. A dungeon is an array of tiles. Randomly placed in the array are rectangular rooms.
Rooms are connected from room N to room N-1 by halls from center to center, either first H then V or first V then H. This means that a given all way can cut through any other room, two halls can be side by side, making a wide hallway, and so on.
Like this:
Complex map in top right of dungeon picture.
My problem is this. I would like to have complex puzzles, I call them “set pieces”, in the dungeon, for the player to solve. Maybe she has to find three switches, figure out what they do, and configure them a certain way to gain access to something valuable.
But the game program literally does not know what the dungeon layout is, and even if I were to place, say, a one-entrance set piece room first, the hallway logic could cut a second path right to it, by accident.
In a “real world” map like that, things would be arranged in convenient rooms for whatever the usage was. And doors would be built, paths walled up, based on knowledge of the big map. In my game, there does not exist “knowledge of the big map”.
I like that property, and want to maintain it. Yet I need to find suitable places to put puzzle items so that the puzzle will make sense.
I will think of something clever and elegant, if I can, or I’ll brute force program my way through it.
I don’t want to be given the clever and elegant solution, but I did want to talk about the problem. @ me if you wish.
I got a number of super replies. Here’s a link to the top of the thread, so that you can find them. I’ll mention some here as well.
Jose Raez suggested a graph approach, considering all the tile connections, and then analyzing them to learn enough about the dungeon to lay in puzzle objects. He pointed to one “invariant” that might help distinguish large areas from small, the number of connections that a tile has.
Andrew Traviss suggested having some kind of simple “agent” that explored the space and set up furnishings and puzzle. I particularly liked that suggestion because it’s kind of like how a band of people might explore and use a naturally-occurring cave system: look around and decide what rooms to use for what.
I don’t think I’ll do it, but I like the idea. We do have a simple version of that now, the Pathfinder, which can find its way from any cell to the WayDown exit from the current level. That same code could be used to find a path between any two cells, of course. Anyway, Andrew’s idea surprised me, and I like that when I’m looking for ideas.
Luca Minudel identified a number of issues relating to the problem. I think he thought I was “alluding” to those issues, but in fact, he identified them more clearly than I had them in mind. I was alluding to nothing, just fondling this new problem, turning it this way and that, to see if there was a crack in it that I could exploit.
Jez Higgins asked about adding constraints to room placement, so perhaps if a given room can’t connect to its designated neighbor, it would have to be repositioned. That’s a bit more thinking than my current layout code can do, but it’s interesting. It also led me to consider a specific constraint:
Could we block out a section of the dungeon and say “no paths can go through here”? Well, clearly we could. Would the dungeon still connect? In general, given the current algorithm, it might not. But the room-to-room connection does choose one of two paths, first horizontal then vertical, or first vertical the horizontal. If one of these were blocked, the other could be tried, and it would “usually” work.
We could even give up on that connection, continue with other connections, and then see whether the troublesome room was connected indirectly, which often happens. And, presumably, we’d be connecting the blocked-out area to the rest of the dungeon, and that might connect up the troublesome room.
And, if it just wouldn’t connect, we could drop the room, or reroll the whole dungeon.
A little drawing tells me that although my hallway algorithm can be thwarted by a blocked area, you can always connect all the rooms in the non-blocked area, unless the blocked area completely divides the space into two separate parts. (Like a wall all the way across in the middle.)
So it’s “clear” that with some work we could block out areas for special purposes and let the rest of the dungeon be random.
Those are a few of the comments and ideas that came along. I’m grateful for all the responses, and not just because it’s fun or makes me feel like someone out there is listening. When we’re working a problem, talking with someone else is a valuable way to settle the ideas better in our mind, and, or course, as happened here, the other people will offer ideas that we didn’t have, or that we wouldn’t have prioritized, so they move us to a better place.
So thanks to you all, whether I mentioned you here or not. I think I followed most of the repliers and hearted their messages.
So, with those ideas in hand …
What’s the Plan?
After discussion between my business hat and my technical hat, we’ve decided on a couple of things.
First, we’re going to focus a little bit on what GeePaw Hill calls the “Making App”, the parts of our system that help us build the product. In particular, we’ll start working toward some tools for defining a game level. I have almost no idea what is meant by that.
Second, as a first step, we’re going to build a specific first level. We’ll control the layout of the rooms and their connections, and we’ll control everything that is put into that level. We’ll consider it to be a “training” level for new players, which will introduce them to the features of the game. We’ll build up that level incrementally, and as we do it, we’ll enhance our “Making App” to make similar operations easy.
Now, there are at least three ways a Making App could be done.
- Programming Framework
- We’re all programmers here, so we could simply define objects and methods that make it easy to write a “script” in Lua that lays out everything in a dungeon. In a sense, we must do this, since the other two ways pretty much require this as their basis.
- Textual Definition
- This is the standard YAML or JSON or Tune Of Our Own Invention textual definition of a dungeon. Room coordinates, objects in the room, who knows?
- Little Language
- Textual definition languages usually run out of steam. Easy things are easy, reasonable things are hard, and difficult things are nearly impossible. Sooner or later, a textual definition turns into a programming language.
I think there’s a saying somewhere that sooner or later, every textual definition language turns into a real programming language. We’ve got a real programming language, and when we get there, we’ll use it. We won’t create a new one.
My estimate of what will happen is that we’ll start with the programming framework, then find ways to drive parts of it with tables of text or maybe other information. We’ll be doing it as we go.
And there’s in important point here:
We Did Not Plan For This!
It is part of my standard shtick to say that if we keep our program in good condition for what it does, with a design sufficient to what it does, that we’ll almost always be able to move it in whatever direction we need to.
Well, here we are. We have a decent design, with some areas that are less than ideal, but which, overall, is pretty OK. We built the whole thing around the idea of randomly-created dungeons, and here they are telling us that they want to lay out the rooms and everything in them explicitly.
Are we daunted? Only a little. Let’s get started.
What’s the First Cut?
We’ve agreed, the business (me) and technical folks (me) on a first “training” dungeon. We’ll work for a few iterations to create that, learning as we go. Here’s what we know right now.
The dungeon will consist of 12 rooms, 4 across and 3 down. They will completely fill the dungeon space with only a single tile’s spacing between them. The rooms will each have one or two doors. There will be some kind of actual door that can be opened or closed using objects to be discovered in the preceding rooms.
The rooms will be connected in a sort of spiral, leading the player around and around until she gets to the final room, where she will graduate to the next level. It will look like kind of this:
I wanted to be allowed to break the system for a few days, but I told me that we couldn’t do that, we had to keep up our practice of shipping a version every day. The version we ship doesn’t need to contain any new features, unless it does, but the learning level needs to be on a switch or something so that it won’t show up until we’re ready.
Let’s Design a Bit
The dungeon is 85 tiles wide by 64 tiles high. If there are three rows, we have 60 tiles to share among them, and if there are four columns, we have 80 tiles to share.
But have we been requiring rooms to have an odd number of tiles? I don’t remember. Let’s look. We create a random room this way:
r = Room:random(self.tileCountX,self.tileCountY, 4,13, self)
function Room:random(spaceX, spaceY, minSize, maxSize, runner)
local w = math.random(minSize,maxSize)
local h = math.random(minSize,maxSize)
local x = math.random(2,spaceX-w - 1) -- leave room for wall
local y = math.random(2,spaceY-h - 1) -- leave room for wall
return Room(x,y,w,h,runner, false)
end
function Room:init(x,y,w,h, runner, paint)
if paint == nil then paint = true end
self.x1 = x
self.y1 = y
self.x2 = x + w
self.y2 = y + h
self.runner = runner
if paint then
self:paint()
end
end
Looks like we don’t control to odd width or height. OK. We define a room by its lower left corner and its width and height. The room remembers its corners. It paves itself with all tiles of type “room”. Walls are provided separately.
Tiles are indexed from 1 to 86 in x, 1 to 65 in y. (I just noticed this. You’d kind of expect 1-85 and 1-64. I think we’ll ignore this odd fact for now.)
We have room for rooms of size 20x20, four across and three up (or down), with one tile in between. So their coordinates in x will be 2, 23, 44, 65, and in y will be 2, 23, 44. (I calculated this with arithmetic, so it’s probably wrong.
For our first experiment, I’m going to put in a createLearningRooms function, and call it instead of the createRandomRooms function.
function GameRunner:createLevel(count)
self.dungeonLevel = self.dungeonLevel + 1
if self.dungeonLevel > 4 then self.dungeonLevel = 4 end
TileLock=false
self:createTiles()
self:clearLevel()
--self:createRandomRooms(count)
self:createLearningRooms()
self:connectRooms()
...
Here’s my first cut at that method:
function GameRunner:createLearningRooms()
self.rooms = {}
local sx = 2
local sy = 2
local step = 21
for x = 1,4 do
for y = 1,4 do
r = Room(sx,sy, 20,20, self, true)
table.insert(self.rooms, r)
sy = sy + step
end
sx = sx + step
end
end
Should I have done a test for this? Perhaps. I didn’t. I’m going to run it.
Well, I should have done a test. My current cut, which works, looks like this:
function GameRunner:createLearningRooms()
self.rooms = {}
local sx = 2
local sy = 2
local step = 21
for col = 1,4 do
local x = sx + step*(col-1)
for row = 1,3 do
local y = sy + step*(row-1)
r = Room(x,y, 19, 19, self, true)
table.insert(self.rooms, r)
r:paint(#self.rooms)
end
end
end
Curiously, when we went w and h of 19 into the room creation, we get a room of size 20, because we set x2 = x1 + w, and so on. I don’t want to fiddle with that.
With the map hacked to show the whole thing, we see this when we start the program.
Clearly this won’t do. The rooms are way too large. We don’t really want the player to find herself in rooms so large that she can’t see the edges. So we’ve learned a little something. We can see about 18 tiles each side of the princess. That strkes a familiar note: I think that lighting is set to distance 9.
I also had to trace and turn off a number of the other “features” of the dungeon to make this work. Spikes can’t find anywhere to go. I should have built a completely separate method for creating a learning level.
And, finally, the rooms aren’t connected in the way we wanted, in a spiral ending on one of the middle ones.
But we’ve learned a lot here. Let’s revert and do something more sensible. We’ll call this a spike. It’d be better to have said that earlier, but well, here we are. We’ve learned, we’ve made a mess. We revert and go again, slightly smarter. Or at least less ignorant.
Regroup
OK, what’s the new plan?
First, the rooms should be smaller. Let’s stick with just 12, that should be plenty. Normal rooms are from 4 to 13 in width and height, which I think makes them 5 to 14. There are too many plus and minus ones in that code
Let’s make our rooms all be 12 wide and 8 high, and see if we like it.
Second, we want them to connect in a spiral. We can approach that in two ways. A, we could define them in a spiral and let the current path logic do it. B, we could define them in whatever order makes sense to us, and connect them explicitly.
I think we like the second way best, it’s more direct. We’ll define them left to right, bottom to top:
| 9 | 10 | 11 | 12 |
| 5 | 6 | 7 | 8 |
| 1 | 2 | 3 | 4 |
OK. New method, createLearningLevel. We’ll fill in all its contents as this big story goes forward.
function GameRunner:createLearningLevel()
self.dungeonLevel = 1
TileLock = false
self:createTiles()
self:clearLevel()
self:createLearningRooms()
self:connectLearningRooms()
self:placePlayerInRoom1()
self:createButtons()
self.playerCanMove = true
TileLock = true
end
I just read through createLevel and copied in the things I thought we needed. We’ll see if there isn’t a better way, but we’re still learning.
I think we still have to just paste this in for now:
function setup()
if CodeaUnit then
runCodeaUnitTests()
CodeaTestsVisible = true
end
local seed = math.random(1234567)
print("seed=",seed)
math.randomseed(seed)
showKeyboard()
TileLock = false
Bus = EventBus()
Runner = GameRunner()
--Runner:createLevel(12)
Runner:createLearningLevel()
TileLock = true
if false then
sprite(xxx)
end
...
I’d like to put this on a switch, but I’m not sure yet how to do that.
Now let’s code these new methods. I actually start out like this:
function GameRunner:createLearningRooms()
self.rooms = {}
local rooms = self.rooms
local r
r = Room(2,2, 11,7, self, true)
table.insert(rooms, r)
r = Room(15,2, 11,7, self, true)
table.insert(rooms, r)
r = Room(28,2, 11,7, self, true)
table.insert(rooms, r)
r = Room(41,2, 11,7, self, true)
table.insert(rooms, r)
r = Room(2,11, 11,7, self, true)
table.insert(rooms, r)
end
And I drew a picture, too. I’m pretty sure I understand the rules now.
Let’s see if we can do this in a loop now.
function GameRunner:createLearningRooms()
self.rooms = {}
local rooms = self.rooms
local r
local sx,sy = 2,2
local w = 11 -- makes room 12 wide
local h = 7 -- and 8 wide
local xStep = w +2
local yStep = h + 2
for y = 1,3 do
local yy = sy + yStep*(y-1)
for x = 1,4 do
local xx = sx + xStep*(x-1)
local r = Room(xx,yy, 2, h, self, true)
table.insert(rooms, r)
end
end
end
I have high hopes for this, but why didn’t I write a test for it?? My head is set wrong, because I know it’s hard to test the room / tile / runner logic.
Even worse, I’m turning off those slow tests. We’ll end this session soon and think about this. This is not good practice.
Trying to run this gives me a weird picture and a crash.
The crash is about the crawl. I need to do a bit more setup in my creation method. The picture makes it look like I’ve put the wrong width into my room call, and indeed, somehow I typed 2 instead of w. I just typed 2 twice trying to type w, so I know how it may have happened.
function GameRunner:createLearningRooms()
self.rooms = {}
local rooms = self.rooms
local r
local sx,sy = 2,2
local w = 11 -- makes room 12 wide
local h = 7 -- and 8 wide
local xStep = w +2
local yStep = h + 2
for y = 1,3 do
local yy = sy + yStep*(y-1)
for x = 1,4 do
local xx = sx + xStep*(x-1)
local r = Room(xx,yy, w, h, self, true)
table.insert(rooms, r)
end
end
end
And a bit more in the outer method:
function GameRunner:createLearningLevel()
self.dungeonLevel = 1
TileLock = false
self:createTiles()
self:clearLevel()
self:createLearningRooms()
self:connectLearningRooms()
self:placePlayerInRoom1()
self:createButtons()
self.cofloater:runCrawl(self:initialCrawl(self.dungeonLevel))
self:startTimers()
self.playerCanMove = true
TileLock = true
end
OK that looks like our expected layout. We have another diagnostic:
GameRunner:510: attempt to index a nil value (field 'monsters')
stack traceback:
GameRunner:510: in method 'startTimers'
GameRunner:95: in method 'createLearningLevel'
Main:17: in function 'setup'
We need to set a bunch of special collections. Obviously monsters is one of them.
This is odd. We’re sort of debugging our way to this new method instead of actually have code that tells us what to do. That’s not great. Let’s record our learning, at least:
function GameRunner:createLearningLevel()
self.dungeonLevel = 1
TileLock = false
self:createTiles()
self:clearLevel()
self:createLearningRooms()
self:connectLearningRooms()
self.monsters = {}
self:placePlayerInRoom1()
self:createButtons()
self.cofloater:runCrawl(self:initialCrawl(self.dungeonLevel))
self:startTimers()
self.playerCanMove = true
TileLock = true
end
That should say:
self.monsters = Monsters()
Monsters have a smart collection that helps run them. Now the pic is this:
We have no wall tiles, and no hallways. Let’s do the hallways. The current connectRooms is this:
function GameRunner:connectRooms()
local dungeon = self:getDungeon()
for i,r in ipairs(self.rooms) do
if i > 1 then
r:connect(dungeon, self.rooms[i-1])
end
end
end
We can do something similar. We write it out longhand, as agreed:
function GameRunner:connectLearningRooms()
local dungeon = self:getDungeon()
local rooms = self.rooms
rooms[2]:connect(dungeon, rooms[1])
rooms[3]:connect(dungeon, rooms[2])
rooms[4]:connect(dungeon, rooms[3])
rooms[8]:connect(dungeon, rooms[4])
rooms[12]:connect(dungeon, rooms[8])
rooms[11]:connect(dungeon, rooms[12])
rooms[10]:connect(dungeon, rooms[11])
rooms[9]:connect(dungeon, rooms[10])
rooms[5]:connect(dungeon, rooms[9])
rooms[6]:connect(dungeon, rooms[5])
rooms[7]:connect(dungeon, rooms[6])
end
We get this pic:
The mini-map looks just as we intended. The big map doesn’t have any wall tiles yet. We haven’t called for them.
function GameRunner:createLearningLevel()
self.dungeonLevel = 1
TileLock = false
self:createTiles()
self:clearLevel()
self:createLearningRooms()
self:connectLearningRooms()
self.monsters = Monsters()
self:placePlayerInRoom1()
self:convertEdgesToWalls()
self:createButtons()
self.cofloater:runCrawl(self:initialCrawl(self.dungeonLevel))
self:startTimers()
self.playerCanMove = true
TileLock = true
end
The convertEdgesToWalls is the method that fills in the walls.
This looks about right. Just for fun, I’ll place back the monsters and such:
function GameRunner:createLearningLevel()
self.dungeonLevel = 1
TileLock = false
self:createTiles()
self:clearLevel()
self:createLearningRooms()
self:connectLearningRooms()
self:convertEdgesToWalls()
self.monsters = Monsters()
self:placePlayerInRoom1()
self:placeWayDown()
--self:placeSpikes(5)
--self:placeLever()
self:setupMonsters(6)
self.keys = self:createThings(Key,5)
self:createThings(Chest,5)
self:createLoots(10)
self:createDecor(30)
self:createButtons()
self.cofloater:runCrawl(self:initialCrawl(self.dungeonLevel))
self:startTimers()
self.playerCanMove = true
TileLock = true
end
A quick tour tells me everything works pretty well.
For now, having demonstrated this to the Product Owner (me), I’ll turn off the call to the learning level, until we decide what we want to do with it.
function setup()
if CodeaUnit then
runCodeaUnitTests()
CodeaTestsVisible = true
end
local seed = math.random(1234567)
print("seed=",seed)
math.randomseed(seed)
showKeyboard()
TileLock = false
Bus = EventBus()
Runner = GameRunner()
Runner:createLevel(12)
--Runner:createLearningLevel()
TileLock = true
if false then
sprite(xxx)
end
end
Test one more time, with all the tests turned back on. Looks good.
Commit: new learning level layout works. Not terribly easy to use.
Let’s have a quick retrospective and see what we’ve learned.
Retro
Defining the rooms was a bit tedious but could be simplified if need be. It looks like this:
function GameRunner:createLearningRooms()
self.rooms = {}
local rooms = self.rooms
local r
local sx,sy = 2,2
local w = 11 -- makes room 12 wide
local h = 7 -- and 8 wide
local xStep = w +2
local yStep = h + 2
for y = 1,3 do
local yy = sy + yStep*(y-1)
for x = 1,4 do
local xx = sx + xStep*(x-1)
local r = Room(xx,yy, w, h, self, true)
table.insert(rooms, r)
end
end
end
Because the layout was so regular, we did it in a loop. It could have been driven from a table, specifying the coordinates for each room.
I think we’ll need to draw some proposed layouts and think about how we might represent them. I predict that with a few exceptions, we’ll soon want to go back to random layouts, but to provide some way, as yet undetermined, to specify a few rooms.
Or, possibly, we’d like to provide a set piece of some kind, and tell the game to place it in any room whose size is at least yay by yay. We need to do some game design on this, but it’s clear we can do whatever we need. The current issue is that we don’t know what we need.
The room definition notation is weird. The rooms are one wider and higher than their w and h would suggest. We might want to sort that out just to keep things easier to understand.
There are some settings, like the timers and the crawl, that are required for any dungeon, and those should be factored out to be separate, and the different dungeon strategies should be independent of those aspects.
There should be some kind of table telling us how many of everything to create, and perhaps even able to control the specifics of what is hidden in a chest, and so on.
In the learning level, we should probably plan to provide just a few monsters. The first ones you meet should probably be entirely peaceful, even if attacked. Then there should be one that you can corner and attack and have a battle with. Then maybe there is an angry one that attacks right away. We may or may not wish to tell them about the Mimic. It’s rather a nice surprise.
I noticed in the learning level that the WayDown is not in the middle room, it’s in the room diagonally opposite the starting room. That’s because the standard WayDown placing logic looks for the furthest room from the start. We’ll need a way to control that directly for our custom layouts.
Finally, it’s even more obvious than ever that we should be building the dungeon outside of GameRunner. It has enough to do without all these creation and setup methods. We should work toward a DungeonMaker class of some kind, before we go much further.
Post-finally, I mentioned “strategy” above, and that reminds me that a strategy plug-in or similar approach is probably the way to go, allowing us to select among dungeon creation approaches simply.
And post-post-finally, that reminds me of the need for a feature toggle.
A very common way of putting new code into a product but not releasing it yet to users is with a “feature toggle”, a flag that if set, allows the new stuff and if not, does not. In Codea, we might want to do that with one of its parameter switches, which can be turned on and off. One issue with that is that, presently, when I want to run the game again, I hit reset, and that would reset the parameter switches.
So we’ll have to invent a little something to deal with our feature toggle. Codea does have a way of saving data in the project. Maybe we’ll use that.
Summing up, we’ve created a planned layout, even though we never planned for a planned layout, and we’ve seen that such things won’t turn out to be technically difficult. We still need to build up some kind of notation for defining all this stuff. That will come. I bet we make some progress on it this week.
See you next time!