Instanced dungeons for an MMORPG game server

Intro

0:00 Hello and welcome back to episode thirty-eight, where we're going to give each player who walks into a dungeon a copy of it of their own. Let's begin with a quick look at where we're going to be by the end of the episode.

0:12 Alice is in the Meadows, by a new gate, and bob logs in next to her, while Ember's log along the bottom says who joined. They both walk east, through the gate, into the Crypt, our first dungeon, and each of them gets a copy of the Crypt of their own, so in there, neither of them sees the other.

0:31 On the website of the series you can find more information about the project. The code for the project is open source on GitHub, tagged at each step of each episode so that you can follow along.

Last time

0:43 Now, before we get to today's work, let's quickly go over what we did last time. The script that starts a release moved onto the server, so that the runner we put there next can start a release too, and not just our deploy script. GitHub's Actions runner runs on our server, in Docker, and waits on GitHub for jobs with its labels. CI got a deploy job, which runs on that runner for each push to main, once the build, the sanitisers and the fuzzers pass. The job looked for the releases in the runner's own home folder at first, until the runner mounted the home folder of the server's user. And the runner refuses any job that isn't a deploy of main, as a pull request from a fork could send it one.

Today

1:26 Our worlds have two lands, the Meadows and the Ashlands, and everyone in a world shares them, which is what we want for open land, where players meet. In a dungeon, players want the monsters to themselves, so each player who goes in is going to get a copy of it of their own. MMOs call that an instance, but since episode thirty-six, an instance for us is a running server of a world, so in our code, a running land is going to be a copy. So first, the world server is going to run its lands as copies, with an id each. Then a land is going to have more than one gate, so that the Meadows can lead to the Ashlands and to our dungeon, the Crypt. A copy of the Crypt that nobody's in is going to stop, and go after a while. And a player in the Crypt is going to be saved outside it, so that a logout or a deploy doesn't bring them back to a new copy, with all its skeletons back. All right, let's get started, with the copies.

Lands as copies

2:22 We start with a new header, copies dot h, and its header guard. Chrono is for the time each step covers, c std int for the ids, and map for the copies, which we're going to keep by their ids. Content dot h has what fills a land, interest dot h has the cells that NPCs are kept in, and world dot h has our World, which runs a land. A copy is a land, running, with the land, by its place in our list of lands, and the World that runs it. It has its NPCs in their cells too, which the server kept in a list of their own until now. Copies holds all the copies of a world server, and for now, each land has one, which everyone in the world shares, like the worlds the server had. But each copy has an id, so that a land can have more than one. The constructor takes the world's seed, which makes each land's terrain, and the content, which fills the lands with monsters and NPCs. Join puts a player into their land's copy, and leave takes them out. Of gives the copy a player's in, or a null pointer for someone who isn't playing. Step steps each copy by a tick, and then takes the players through the gates, which the server did until now. All gives the copies by their ids, for the server to save and broadcast them, and players counts the players in all of them. In the private part, for gives the id of a land's copy, and travel takes players through the gates. Then the copies, in a map by their ids, and the id the next copy gets, starting from one. And where keeps the copy each player's in, by their ids, so that finding a player's copy is a look-up in a map, without going through each copy. In copies dot c c, after our header, chrono, c std int and map again, and i o stream, for the line in the log when a player goes through a gate. Iterator is for std s size, random for each World's seed, utility for std move, and vector for the players going through a gate. Monsters dot h and NPCs dot h spawn a land's monsters and NPCs, lands dot h has our list of lands, and terrain dot h makes a land's island. The constructor makes the copies, which the server's constructor and its start did until now. It goes through the lands by their places in the list. Std s size gives the list's size as a signed number, so comparing it with our int doesn't mix signed and unsigned numbers. Each land's copy goes into the map under the next id, with a World of its own, seeded from the random device, as before, on the land's terrain. The terrain comes from the world's seed plus the land's, and the land's wading depth, and the World gets the items and the skills from the content. Emplace returns where the copy went in, and whether it did, so first, then second, is the copy, which we keep a reference to. Then the land's monsters and NPCs are spawned into it, and its NPCs go into their cells, like the server's start did. Join finds the copy of the player's land, has its World take the player, and notes that copy as where they are. Leave looks up where the player is, and returns if they're nowhere. Otherwise, their copy's World lets them go, and they come out of where. Of looks them up in where, and returns their copy, or a null pointer. Players adds up the players in all the copies, like the server's players function did with its worlds. The world's registration with Consul carries that count, for the login server's list of worlds. Step steps each copy's World by the time it's given, and then calls travel. For goes through the copies, and returns the id of the first one of the land. Each land has a copy from the start, so it finds one, and the zero at the end, which no copy has as its id, isn't reached. Travel is the server's travel, moved here, and it goes through the copies. As before, leaving changes the map we go through, so first we note who's going. Taking a player out of a World while we go through that World's players would break the loop, so their ids go into a vector, and the moves come after. Each player in the gate of their copy's land goes through it. They leave their copy, come out past the other land's gate, the way they were facing, and the log says where they went. Then they join the copy of the land the gate leads to, which for now is that land's one copy, and where notes it. In server dot h, copies dot h comes in, for the copies the server is going to hold. Start takes nothing more than the port, as the copies spawn the monsters and NPCs now. Land of becomes world of, which gives the World of the copy the player's in, or a null pointer, as a land can have more than one World from now on. Travel goes, and broadcast land becomes broadcast copy, which takes the copy it broadcasts. And the list of worlds and the list of their NPCs' cells make way for the copies. In server dot c c, random, monsters dot h, NPCs dot h and terrain dot h go, as making the lands moved into copies dot c c. Create starts the server with nothing more than its port. The constructor makes the copies from the seed and the content, and the loop that made the worlds goes. The copies are made in the constructor's initialiser list, so they're ready before the server listens for anyone. Members are initialised in the order the class declares them, and the copies come right after the seed, so the list follows that order too. Players asks the copies how many players there are, as the loop over the worlds moved into copies, with the rest of the lands. Start loses the content, and the loop that spawned the monsters and NPCs into each World. Spawning moved into the copies, as a copy that's made later is going to need its monsters too, and copies spawns them as it makes each one. Land of went through the worlds, and returned the one with the player in it. The new function looks the player up, and if they're playing, returns a pointer into their copy, and a null pointer if they aren't. The copies sit in a map, which doesn't move them, so the pointer stays good while the copy exists. Then each place that called land of changes to the new name. The input that comes in over UDP needs it, and so does the check in hello, which refuses a player who's playing already. Hello then puts the player into the copies, which find their land's copy. Leave says in the log who left, and takes them out of the copies. Chat needs it for the player's name, and talking to an NPC and learning a skill need it for the NPCs in the player's land. Each land counts its NPCs from one, so talking and learning have to look in the World of the player's copy. In tick, the copies step by the tick's interval, and take the players through the gates. The loop over the worlds, and the call to the server's travel, make way for that one call. We count the players after the step, as the step can take some of them through a gate. Its empty braces fill each slot with zero to start with. The metric of players online counts them by land, and a land can have more than one copy now. So we count each copy's players into its land, in an array with a slot for each land, and set each land's count from that. And the server's travel goes, as moving a player between copies has to update where, which copies keeps private. That way, where and the copies' Worlds change together, in one class. Saving goes through each copy's players, and saves each player whose progress changed, like it did with the worlds' players, and broadcasting broadcasts each copy. Each copy goes out to the players in it, and nobody else. Broadcast copy takes the copy, and its World is the land it broadcasts, under the name land, so the rest of the function reads as before. The views get the copy's NPC cells, and each player's own part gets the seed and the place of the copy's land. Copies get a test of their own, in copies underscore test dot c c, with chrono for the tick, c std int for the ids, GoogleTest, our World and our lands. A tick is fifty milliseconds, like the server's, and the Meadows and the Ashlands get names for their places in the list. Copy of gives the id of the copy a player's in, by going through all the copies and checking whose World has the player, so that the tests check what of returns against what the Worlds hold. The first test checks that the copies start with a copy for each land. The second makes copies of its own, like each test does, and has alice and bob join the Meadows, and checks that they share a copy, which is the Meadows'. And the third puts alice in the middle of the Meadows' gate, and steps the copies once. A player in the middle of a gate goes through it on the next step, so one step is enough. Assert not equal stops the test there if of gives a null pointer, as the checks after it would read through it. She's in the Ashlands' copy then, and her player has the Ashlands as their land. Players counts one player in all the copies, so she's no longer in the Meadows' copy. In the server's CMake file, copies dot c c goes into the server's core library, and its test into the server's tests. And the README says that the world server runs its lands as copies, with one copy of each land for now.

11:29 The copies' tests don't need MySQL, Redis or Consul, so dash dash no deps runs the tests without starting them, and the three pass. Each land has its one copy, so the game plays as it did.

A land with two gates

11:44 For a second gate in the Meadows, the gates are going to need a list of their own. In lands dot h, a land had its gate, and the land it took you to, and those two fields go. So each land fits on a line, with its name, its seed and how deep its sea can be waded. A gate is a ring of stones in a land, which takes players to another. It has the land it stands in, where it stands, and the land it takes you to, both lands by their places in our list. K gates lists them, and for now it has the two we had, between the Meadows and the Ashlands, each ten metres north of its land's middle. A gate's way back is a gate in the land it leads to, which leads back to the land it stands in, and we're going to call that its twin. Gates lead back checks that each gate has one, and it's constexpr, so the compiler can run it. For each gate, it looks for a gate in the land it leads to, which leads back to the gate's own land. The static assert has the compiler run it, and stops the build with a message if it's false, so a gate without a twin can't get into a build. In gate takes a gate now, and twin gives a gate's twin. Arrival takes the gate a player goes through, and gives where they come out: past the middle of its twin, the way they were facing, so that they walk on out of it. In lands dot c c, algorithm comes in, for find if. In gate checks whether a player is within a metre of the gate's place, which is the gate's radius. Twin finds the first gate in the land this one leads to, which leads back, with ranges find if and a lambda that checks both lands. Gates lead back makes sure there's one, so we can use what find if returns without checking it. And arrival starts from the twin's place, and goes three metres past it, the way the player was facing, as it did from the land's gate. The yaw is the way the player faces, so its sine and cosine give the step along x and along z. In copies dot c c, travel goes through the gates. We note who's going, and through which gate, as a land can have more than one, so the travellers are pairs of a player's id and a pointer to their gate. For each player, we look through the gates in their copy's land, and the first one they're in sends them. Gates don't overlap, so a player is in one at most, and the break stops looking once we've found it. They come out past the gate's twin, in the land it leads to, which the log names, and they join that land's copy. On the client, in gate dot h, the gate's cubes are a ring of standing stones around each of the land's gates, with a slab in the middle in the colour of the sky where it takes you. In gate dot c c, gate cubes went round the land's gate. Now it goes through the gates, skips the ones in other lands, and puts a ring of stones around each of the others, from its place. Each of the stones goes around the gate's place, at an angle of its own, so that they make a circle. Each stone stands on the terrain, at its height there, and goes up by half its height, as a cube's position is its middle. The stones take the rock colour of the land they stand in, from its look, like the stones of the land's gate did before. We take the sky of the land the gate leads to, from that land's look. Its three numbers are red, green and blue, from zero to one, as the look keeps them for the shader, so color from normalized makes raylib's colour from them, at full opacity. The slab gets that colour, so that the slab tells you where a gate goes before you walk into it. The bots go into a gate on one trip in five, and a land can have more than one now. In wander dot h, random gate gives one of the land's gates, at random, as players go through each of them, and random trip's comment says the gate takes the bot to another land. In wander dot c c, c std def comes in for std size t, and vector for the places of the land's gates. Random gate takes the bot's random generator and its land, and collects the places of the gates that stand in that land, into a vector. With the gates we have so far, each land has one, so for now the bot picks the gate it went to before. The vector can't be empty, as each land has a gate, as the way back to the land before. Then it picks one, with a uniform distribution over their indices. In bot dot c c, a bot's trip goes to a random gate of its land, where it went to the land's gate before. In the terrain tests, has room at each gate went through the lands, and checked that each land's gate is on the island, and that a player who comes through lands on the island and out of the gate. It makes each island from seeds one to three plus the land's, as different worlds have different seeds. Now it goes through the gates instead of the lands. For each gate, it takes the gate's land, and makes that land's island from the seed, and the gate has to stand on that island. The players who come out at it are the ones who went through its twin. They have to come out of each of the land's gates, as landing in another gate would send them on at once. A second test checks that each gate's twin is in the land it leads to, and leads back. Then it checks where a player who goes through comes out, facing along z, for a yaw of zero: three metres past the twin's middle, the way they were facing. And the copies' test, with algorithm for ranges find, puts alice in a gate from the list. Our new helper finds the first gate whose to is the land, through a pointer to that member, and for the Ashlands, that's the Meadows' gate. And the README lists the gates with the lands, in a column of the table, says what a twin is, and that the static assert checks each gate has one. It says that the bots go into one of their land's gates at random too, so they spread over both lands. The bullet on gates keeps what players see: a ring of standing stones, around a slab in the colour of the sky beyond.

17:39 The terrain tests pass with the gates in their list, and with the two gates we have, the game plays as it did.

The Crypt

17:55 Now for the Crypt, so in lands dot h, a land says whether it's a dungeon. In a dungeon, each player who goes in gets a copy of the land of their own, without the one copy that everyone in the world shares. The Crypt is the third land, with two thousand added to the world's seed, nothing to wade into, and it's a dungeon. Its island is made like the others, so it has a shore and hills, which the client draws in the Crypt's own look. The client builds a land from the seed the server sends, so the Crypt needs nothing more on the client than its look. Two more gates go between the Meadows and the Crypt: one twelve metres east of the Meadows' middle, and its twin in the Crypt, ten metres north of its middle, like the Ashlands' one. A dungeon's copy is made as a player comes in through a gate, and a dungeon needs a gate of its own, which is the way out. So gates lead back checks that too: for each land, it looks for a gate that stands in it, and a dungeon without one fails, and the message says so. On the client, in atmosphere dot h, the Crypt gets a look. Its sky is a dark purple, with fog from twenty metres to ninety, so that it feels closed in, under a dim, cold light. Its ground goes from a dark sand through grey to a pale stone, and its trees are dark. Its sea is a green ooze, which glows a little, with an emission of point six. It goes into the list of looks, which the static assert under it checks has a look for each land. In the monsters' content, the Crypt gets a kind of its own, the Crypt Skeleton, at level three, with a hundred and twenty health, and a hundred and fifty experience for beating one. It hits for eleven, swings like the other skeletons, sees five metres, and stays within six of its home, in the skeleton's model, tinted a pale purple. And the Crypt gets twelve camps of them, spread over the island, with three skeletons to a camp where the ground allows, so each copy spawns up to thirty-six of its own. In copies dot h, vector and terrain dot h come in, for each land's terrain, which copies is going to keep. A copy gets an owner, whose copy of a dungeon it is, by their id. Nobody owns an open land's copy, which everyone in the world shares, and zero isn't a player's id. The class comment says it now: each open land has one copy from the start, and a dungeon has one for each player who goes in, from when they do. The constructor takes the content by value now, as copies of the Crypt are made after the constructor returns, so copies keeps the content. Join puts a player into the open land's copy, or for a dungeon, their own. For takes the player's id too, and makes a dungeon's copy for a player who hasn't one, so it isn't const any more. The content goes into a member, along with terrains, each land's terrain, made once, which each of the land's copies gets a copy of. Making an island takes a while, and a copy is made inside the tick, so making one there would hold up the tick for everyone in the world. So the copy copies the terrain that's there. In copies dot c c, terrain dot h goes, as the header has it. The constructor moves the content into its member, makes each land's terrain once, and makes a copy of each open land through for, with no player, so the Crypt has no copy until someone goes in. Join passes the player's id to for, along with their land. For works out whose copy the player needs: theirs in a dungeon, and nobody's in an open land. A copy of that land with that owner is the one, so a player who goes back into the Crypt goes back to their copy. Otherwise, there isn't one yet, and for makes it, under the next id, with what the constructor did for each land. It has a World on a copy of the land's terrain, its owner, its monsters and NPCs, and its NPCs' cells. A dungeon's copy says in the log whose it is, and for returns its id. Travel can make a copy now, while it goes through the map of copies. A new copy goes into the map as we go through it, which std map allows, as adding to a map doesn't move what's in it. And the players who arrive in it are out of its gate, so going on through the map with them in it does no harm. And travel passes the player's id to for, so going into the Crypt makes their copy. We want to see how many copies a server runs, so in metrics dot h, set copies sets how many copies of a land the server runs, in a family of gauges, like the players online. In metrics dot c c, the family is nanoMMO underscore copies, with its help text, and each land gets a gauge in the family, under its name as the land label. Set copies sets the gauge with the land's label to the count. In server dot c c, tick counts the copies of each land too, in a second array, next to the players, and sets each land's count. And the comment over sending chat says that everyone in the world hears it, in all its lands. In the copies' test, the Crypt gets its name, as the third land. The first two tests are about open lands now. The copies start with two, one for each open land, neither of them a dungeon's, and neither of them owned. And players share an open land, as before, with alice and bob in the Meadows. Gate to finds the gate for the new test, as the Meadows' gate is the first one that leads to the Crypt. The test puts alice and bob in the middle of the Meadows' gate to the Crypt, and steps the copies once. Both of them start in the gate, so both go through on that step, into a copy each that for makes for them. Each of them is in a copy of the Crypt, owned by them, and the two copies are different ones, so there are four copies: the Meadows, the Ashlands, and a Crypt each, with two players in all. And the README describes the Crypt, a dungeon of grey stone around a green ooze, and its gates, in the table. It says how the server runs its lands as copies, with a copy of the Crypt for each player who goes in, made as they go through its gate, and it lists the copies metric. It says the bots that go into the Crypt get a copy each too.

23:54 The copies' tests pass, the new one among them, so let's go into the Crypt.

24:09 Alice walks east, through the new gate, into the Crypt, and Ember's log says that it made player one a copy of the Crypt. Her copy has its dark purple sky, the green ooze and the dark trees, with its skeletons out in the fog. She walks back through the Crypt's gate, and comes out next to the gate in the Meadows, and when she goes in again, she's back in her copy, so the log has no new copy this time.

24:35 With forty bots playing on Ember in Compose for a minute and a half, let's ask the server for its metrics. It runs several copies of the Crypt, one for each bot that went in, along with a copy of each open land. Then we take the swarm of bots down, wait twenty seconds after they've gone, and ask the server for its metrics a second time. There are no players online, and the Crypt's copies are all still there. Each of them steps its World each tick with nobody in it, so a world that ran for a month would keep a copy for each player who ever went into the Crypt.

Copies that go

25:11 So a copy of the Crypt with nobody in it is going to stop, and go after a while. In copies dot h, a copy keeps how long it's had nobody in it. And the class gets k empty life, which is five minutes. After its last player leaves, a dungeon's copy stops, and waits this long for them before it goes, so that someone who steps out finds it as they left it. Step's comment says what it steps now: the copies with players in them, and the open lands' whether or not anyone's in them. And it drops the dungeons' copies that have been empty for k empty life. In copies dot c c, step goes through the copies with an iterator, as it's going to erase some of them, and erasing from a map gives back an iterator to the next copy. An open land's copy, or a dungeon's with someone in it, starts its empty time from zero again, and steps, as before. A dungeon's copy with nobody in it doesn't step, so its monsters stand where they are, and it adds the tick to its empty time. Until that's five minutes, it stays, and then the log says whose copy went, and it's erased. Nobody's in it, so no player's entry in where points at it. In server dot c c, broadcast copy returns at once for a copy with nobody in it. A dungeon's copy waits for its player with nobody to send it to, and serialising its monsters each tick would be for nobody. In the copies' test, content dot h and monsters dot h come in, for the content and for parsing monsters, and run for steps the copies tick by tick for a while. It takes whole seconds, and steps fifty milliseconds at a time, like the server's tick. Crypt with a skeleton is content with one kind of skeleton. It parses its monsters from text, like the server reads its monsters file, and the star takes what parse monsters returns, as the text is ours and parses. The kind has its level, health and experience, and its fight has the fields our content's skeletons have: how hard it hits, how often it swings, how far it sees, and how far from home it goes. Then one of them spawns in the Crypt, six metres east of its middle, away from where players come in. The first new test is about the five minutes a copy waits. It makes alice once, as a player standing in the gate, so that she can join twice. She goes into the Crypt, the test notes the id of her copy from copy of, and has her leave the game, and come back a second before her copy's five minutes are up. A single step of four minutes and fifty-nine seconds counts as that much empty time, as the copy adds whatever time it's given. She joins again in the Meadows' gate, steps into the Crypt, and finds the copy she left, which copy of says has the id we noted. Then she leaves again, and after five minutes, her copy is gone, and the Meadows and the Ashlands are what's left. The second has alice go into a Crypt with a skeleton. It takes a reference to her copy, and checks that the copy has one monster. It takes a reference to the skeleton too, which stays valid while the copy runs, and notes where the skeleton starts. It runs the copies for ten seconds, and checks that with her in it, the skeleton has wandered off. It rests between two and six seconds before each walk, so ten seconds with alice in the copy is long enough for it to move. Then she leaves, and the test notes where the skeleton stands. It runs the copy for ten seconds with nobody in it, and expects to find the skeleton where it was. And the README says what happens to a copy that has nobody in it.

28:36 The copies' tests pass, the two new ones among them, so a copy with nobody in it stops, and goes.

28:51 Forty bots played on Ember again for a minute and a half, and stopped, and five minutes after that, Ember's log says it dropped the bots' copies of the Crypt. The metrics say the server runs a copy of each open land, and no copies of the Crypt.

Saved outside the Crypt

29:05 A player who leaves the game in the Crypt is saved where they stood, in the Crypt. When they come back, their copy may be gone, so they'd get a new one, with all its skeletons back. And after a deploy, their copy ran in the instance before, so the next instance makes them a new one. So players in a dungeon are going to be saved outside it. In lands dot h, way out gives a dungeon's way out, which is its first gate. In lands dot c c, way out finds the first gate that stands in the dungeon, which gates lead back makes sure is there. In server dot c c, progress of turns a player into what we save. It starts from where they are and what they have, and the dead are saved in the middle, at full health, as before. The check for the dead changes its part of the progress and carries on, so that a later check can still move where they're saved. For a player in a dungeon, dead or alive, as the dead would come back in the middle of a copy that may be gone, we take its way out. We save them at the spot three metres south of its twin, as their x and z, with the land it leads to as theirs. Over it, the comment says why: a dungeon's copy may be gone by the time they're back, and after a deploy it is, as it ran in the instance before, so we keep them outside it. And hand over's comment says that those in a dungeon come out of it in the next instance, as its copy stays in this one. In the server tests, lands dot h comes in, for the gates and the arrival. It's a server test, with the databases and a server running for it, like the others in this file. The fixture made alice's account, and the test starts from where she left the game, standing in the Meadows' gate to the Crypt. The Crypt is the third land, and its gate is the first one that leads there, found in the list like in the copies' test. Her hash in Redis is named after the world and her id, and it's what the server loads when she says hello. So we write it there, with the gate's place as her x and z, and the Meadows as her land. Her experience is zero, and her health, weapon and skills are empty, so she comes back with what a new player has. Then she connects as a test player, with a token for her account. She comes back in the gate, and goes through it, into the Crypt. Run until runs the client and the server until the client's world says it's in the Crypt, or gives up after a while. What Redis keeps of her then is the Meadows, three metres out of the gate. The test works out that spot the way the server does, with arrival at the Crypt's gate, facing south. Alice leaves, which closes her connection, and the test waits for the server to let her go, as hello refuses an account that's still playing, and then she plays again. Her world says she's in the Meadows, and the test looks for her among its players, and checks that she's at that spot, outside the gate. And the README says where the players in a dungeon are saved, and why.

31:59 The server tests need MySQL and Redis, so without dash dash no deps, Compose starts them for the tests, and the new test passes.

32:15 Alice walks into the Crypt, in Ember on seven seven seven seven, and gets her copy. Then Ember's next instance starts next to it, on seven eight seven seven, and builds its lands, the Crypt's terrain among them, and registers with Consul. When the old Ember stops, it hands alice over, and she comes out of the Crypt in the new instance, three metres south of its gate in the Meadows.

Wrap-up

32:41 So, today the world server runs its lands as copies, with an id each. The gates have a list of their own, each with a twin that leads back, so the Meadows lead to the Ashlands and to the Crypt. Each player who goes into the Crypt gets a copy of it of their own, with its own skeletons, and the copies metric counts them. A copy of the Crypt with nobody in it stops, and goes after five minutes, and players in the Crypt are saved outside it, so that a logout or a deploy brings them back to the Meadows, by its gate.

Playing it

34:04 Let me know in the comments what you'd like to see next. And if you want to follow along with the series, subscribe to the channel. I hope you find this useful, and thanks for watching.