MMO NPCs in C++: data-driven, low bandwidth

Intro

0:00 Hello and welcome back to episode twenty-four, where we're going to put the first NPCs in our world, the guards and merchants who stand around in an MMO's towns. Let's begin with a quick look at where we're going to be by the end of the episode.

0:14 Three NPCs stand around the middle of the Meadows, a guard by the road to the gate, and a merchant and a healer facing each other across it. Until they have models, each one is a ball of its own colour and size, with its name over it in green.

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:42 Now, before we get to today's work, let's quickly go over what we did last time. Our players got a chat, where a line that one player types reaches everyone in their world, in both lands, and the server sends each tick's lines to each player over TCP, as a line that's lost is gone. The client got a chat window, where the game's keys wait while you type, after a first try where typing a line walked us around and swung the sword. The server cleans each line before anyone sees it, as anyone can write a client, and a token bucket for each player keeps a single player from flooding everyone's chat. And our bots talk now and then, while the dashboard counts the lines, said or refused.

Today

1:23 Today, we're going to start by turning our monsters into data, with tables of their kinds and of where they spawn, in place of code. Our NPCs then get tables of their own, for what each kind looks like and where each one stands, and a small type of their own on the server, apart from the monsters. NPCs don't move or change, so the server is going to send them once a second, and the client is going to keep them between the worlds that bring them, even when one of those is lost. Last, the client is going to draw them as coloured balls with their names over them. All right, let's get started with what NPCs are in an MMO.

NPCs in an MMO

1:59 An NPC, short for non-player character, is someone in the world that no player controls, such as a guard who stands at a town's gate. A merchant buys and sells, a quest giver hands out quests, and there are trainers, healers, bankers and so on, depending on the game. A big MMO has thousands of them, which makes them content, written by the people who build the world, and added or moved far more often than the code changes. So most MMO servers keep them as data, which the server reads when it starts, and a new NPC in a town doesn't need a new build of the server.

2:33 The usual way to lay that data out is in two parts, where a kind says what the NPCs of that kind have in common, such as a name, a look and a level. A spawn then says where one of them stands, by its kind, its map and its place. That way, a hundred guards around a city share one row for what a guard is, and a change to the guard changes all of them. TrinityCore, an open source server for World of Warcraft, lays it out like this, with a creature template table for the kinds, and a creature table for the spawns. We're going to start with tables in our C++ code, like the lands from episode twenty-two, and they can move into MySQL later, with a migration, when we'd like to change them without building the server again.

Monsters as data

3:16 Our skeletons are the kind of thing those tables are for. The skeleton function says in code what a skeleton is, with its health, its damage and its swing. Where skeletons stand is a list of places at the top of server dot c c, with the number of camps next to it. So in monsters dot h, we include array, for the tables, and a monster kind is a struct for what the monsters of a kind have in common. The name is a const char pointer, as a constexpr table can't hold a std string, which allocates its memory while the program runs. Then it has a level and the most health a monster of the kind can have, and the experience, which is what a player gets for killing one. The damage of a blow comes next, with the length of a swing, in milliseconds, and the hit time, how far into its swing the blow lands. K skeleton holds the skeleton's numbers from the function we had, level one, fifty health and fifty experience, five damage, and a swing of nine hundred milliseconds, which hits at six hundred and fifty. Each field is named as we set it, with designated initialisers, so a kind reads like a row with its column names. A monster spawn is a monster with a fixed home, in metres from the middle of its land, where the server puts it each time it starts. It points at its kind, so that the skeleton's numbers are written once, and each spawn refers to them. The address of a constexpr variable is a constant too, so the table can stay constexpr. Then it says which land, by its place in k lands, and its x and z. K monster spawns lists the three skeletons around the middle, at the places we had in the server. The first three rows are for land zero, the Meadows, and the next three put skeletons at those places in land one, the Ashlands, as the server spawned the three in each land. Each row names its fields as well, so a row reads as its kind, its land, and where it stands, and one more skeleton somewhere is one more row. Monster camps is for camps of monsters, in places that the land's seed picks with the camps function, so an entry has no place of its own. It has a kind, a land, and a count of camps, and each land gets eight camps of skeletons, as before. A camp of another kind in the Ashlands would be one more row in this table. The skeleton function becomes monster of, which makes a monster of a kind, at a place. And spawn monsters puts a land's monsters into its world from both tables. The index is the land's place in k lands, which is how the tables name a land. In monsters dot c c, array comes in too, for k camp layout, which moves over from server dot c c with a new name, as a camp can be of any kind now. Over it, we write where each camp's three monsters stand, from the middle of the camp. Monster of fills in a monster from its kind, at the place it's given. Each field comes from the kind, by name: the name and the level, the most health and the experience, and then what it fights with, the damage and the swing's two times. The world's spawn then fills in the monster's home and its health, like before. Spawn monsters goes through the spawns, and spawns the ones for this land, with monster of, from the kind that the spawn points at. Then it takes the land's terrain, for the camps, and goes through them, skipping the entries for other lands with continue. For an entry of this land, camps picks as many places as the entry says, from the land's terrain, like before. At each place of the layout around a camp, it spawns a monster of the camp's kind, where the ground is walkable. In server dot c c, the list of skeletons, the number of camps and the camp's layout go, and start goes through the lands by their index, for the tables. Each land's monsters come from spawn monsters, with the index as an int, which is what the tables hold.

7:06 Our tests made their skeletons with the skeleton function, so in monsters test dot c c, each test gets its skeleton from the new function and the skeleton's kind, at the place it had. The skeleton that rests and then walks starts in the middle of the board, while the one that stays near home and on the board starts in a corner. Its line grows past eighty characters, so it breaks after the equals sign, where clang format puts the break. The skeleton that runs at the players it sees starts in the middle too, and the one that spots living players near its home starts three metres to the left. World test makes skeletons too, for the tests of how they spawn, fight and come back. Spawns monsters with ids of their own spawns two of them, and checks that they get ids one and two, and that the first one's home is where it spawned. Both of those lines break after the equals sign as well, like the one in the corner. Swings at the nearest monster in reach has a near one and a far one, both within the player's reach, so the player's swing has to pick the one that's nearer, while the far one keeps all of its health. Kills monsters for their experience makes a skeleton that's weak, with ten health, which comes back after it dies. And the last test has a skeleton kill a player, who comes back in the middle. As we haven't changed anything about a skeleton, the tests we have already are how we check that, without writing new ones.

8:26 We run the server's tests for the monsters and the world, with a filter of two patterns, split by a colon, and they all pass, so the skeletons we make from the tables are what they were.

An NPC of its own

8:46 We could make an NPC a monster that stands still, with a flag, as a monster has a name, a place and a level already, and the server sends it to the players. A monster carries a lot that an NPC doesn't need, though, such as its health and the experience a player gets for it. It has a home, a place it's walking to, a rest and a player it's hunting, along with its damage, its swing and when it comes back to life. Each of those would need a check for NPCs, so that no player can hit a merchant, and no merchant wanders off after a player. An NPC is a name, a place and a look, for now, so it gets a small type of its own, with ids of its own, apart from the monsters. That way, the code that runs the monsters doesn't see NPCs at all.

9:28 We start in the proto file, where an NPC gets a message of its own, next to the monster's. An NPC has an id and a name, its place on the land and which way it faces. Then comes its look, starting with a colour, as four bytes in a single number, for red, green, blue and alpha, which is how raylib's get colour reads a colour from a number. And it has a radius, in metres, which is how big the client draws its ball. The look goes out with each NPC, so the client needs no table of kinds of its own, and a new kind on the server shows up on the clients without a new client. Above the message goes a comment on what an NPC is, someone who stands in one place, and doesn't fight, and who comes once a second, with its look, a ball of that colour and radius. The world gets the NPCs near you as a repeated field, number twelve, after last time's chat. On the server, in world dot h, the NPC struct comes after the monster's, for someone who stands in one place, such as a guard. NPCs don't move or fight, so they have none of a monster's health or of what it thinks with. It has a name, x, z and a yaw, a colour, as red, green, blue and alpha, and a radius, in metres, which is the size of its ball until NPCs have models. The world gets a second spawn, for NPCs, as an overload, since C++ picks the function by the type of its argument, and NPCs get ids of their own, apart from the monsters'. NPCs returns them, as a const reference to a map, like players and monsters, and the world keeps them in a map by id, with the next id to give out, starting at one. In world dot c c, spawn takes the next id, moves the NPC into the map, and returns the id. It does none of the monster spawn's work, as an NPC has no home to come back to, no health to fill up, and no rest before it walks.

11:18 The NPCs' tables get a header of their own, NPCs dot h, next to the monsters, with array, cstdint, and world dot h, for the NPC struct. An NPC kind is what the NPCs of a kind look like, and its comment says why the look is in the server's table: the server sends it with each NPC, so the client needs no table of its own. A kind has a name, a colour, white unless the kind says otherwise, and a radius, which is half a metre by default. A guard is a blue ball, a little bigger than the default. Its colour is written in hex, two digits each for red, green, blue and alpha, where f f for alpha makes the ball opaque. A merchant is a gold one, and a healer is green, and a bit smaller, with a radius of four tenths of a metre. The Ashlands get an ash warden, in the orange of their lava, and the biggest of them all. An NPC spawn says where an NPC stands, in metres from the middle of its land, and which way it faces. It points at its kind, like the monsters' spawns, and has the land, by its place in k lands, its x and z, and the yaw, in radians. K NPC spawns has three NPCs for each land, six rows in all, with the Meadows first. The guard stands a few metres to the left of the road, near the gate, while the merchant stands six metres out to the left of the middle, and the healer six metres out to the right. A yaw of one point five seven is about a quarter turn, so the merchant faces along x, towards the healer, who turns a quarter the other way. In the Ashlands, the ash warden takes the guard's place, on the other side of the road, and the merchant and the healer stand where they do in the Meadows. Then we go back up, to say over the table where they stand, around the middle of each land, where the players start: a guard by the road to the gate, facing the players, and a merchant and a healer facing each other across it. Spawn NPCs spawns a land's NPCs from the table, where the ground is walkable, and the index is the land's place in k lands. Spawn NPCs is a function of its own, next to spawn monsters, so that the server's start reads as a list of what each land gets, without the details of each. In NPCs dot c c, which starts with its own header, iostream comes in, for the error stream, where the server writes its warnings. Spawn NPCs goes through the spawns, and skips the ones for other lands. It takes a reference to the spawn's kind, and checks that the ground is walkable where the NPC stands. A seed of its own can put the sea or a tree where the table says, as each world has a seed, while the table stays as it is. So the server says which NPC it left out, and where, as an NPC that's missing would be hard to explain otherwise, and it goes on to the next one. Otherwise, the land spawns an NPC with the kind's name, the spawn's place and yaw, and the kind's look. Spawn returns the NPC's id, which we don't need here, as the server finds the NPCs through their land. The server's library gets NPCs dot c c, next to monsters dot c c.

Once a second

14:21 Players and monsters move, so they go out in each world, twenty times a second, and the server puts them into their cells of the island on each tick, as we did in episode twenty. NPCs don't move, and nothing about them changes while the server runs, so they can go out with the full world, once a second, like the names and the levels. And the server can put them into their cells once, when it spawns them. The client then has to keep them between the full worlds, as it drops anyone who isn't in a world that arrives whole. And as a full world can be lost over UDP, the client is going to keep each NPC for a few seconds after it last heard of it.

14:59 Each of the Meadows' NPCs takes between thirty-two and forty bytes in a world, with its name and its look, so the three of them come to one hundred and ten bytes. Sent with each world, twenty times a second, they'd be two point two kilobytes a second for each player near them, for NPCs that don't change. Once a second, they're one hundred and ten bytes a second, which is twenty times less. With three hundred bots on my machine, most of them near the middle, the server sent about four hundred and eighty kilobytes a second of NPCs when they went with each world, against about twenty-four when they go once a second.

15:32 In interest dot h, cells is the ids of what's in each cell, as a map from a cell to its ids, with a using declaration, as we're going to pass one around. Cells of is a template, since players, monsters and NPCs are three types that each have an x and a z, and it sorts a map of any of them by id into cells. A template goes in the header, where the compiler can see its body for each type it's used with. For each unit, its id goes into the list of the cell it's in. A view is what the players in a cell get, and it has the NPCs near it too, in a list of ids of their own. So the server can put the NPCs' pieces into a cell's world by their ids, like the players' and the monsters'. Views takes the NPCs already in their cells, where it takes players and monsters as they are. Players and monsters move, so they go into their cells each time, while NPCs stand still, so the server puts them in theirs once, when they spawn. In interest dot c c, gather goes in the unnamed namespace, and adds the ids in one cell to a list, if the cell has any. Views had that code twice already, once for the players and once for the monsters. It takes the cells by const reference, and the list by reference, as gather adds to the list we pass it. Views sorts the players into cells with cells of, and the monsters too, in place of the two loops that did it by hand. The loops over the cells around each player's cell stay as they were, two cells each way. For each of those cells, views gathers the players and the monsters, and then the NPCs, from the cells that the server worked out when they spawned.

17:08 Each unit goes to the players as a piece, a world with that unit in it, serialized once a tick. So in parts dot h, a piece is now a player, a monster or an NPC in a world of its own, serialized, and piece gets an overload for an NPC. In parts dot c c, it makes a world, adds the NPC to its list, and serializes it, like the other two. In server dot h, we include interest dot h, for cells, and the server keeps each land's NPCs in their cells, in a vector by land. In server dot c c, NPCs dot h comes in, and to protocol gets an overload for an NPC, which copies its id, its name, its place, its yaw and its look into the message. A player's or a monster's name is cleared on the worlds in between, while an NPC's message keeps all of its fields, as it goes out in the full worlds and no others. In start, each land spawns its monsters, then its NPCs, and its NPCs go into their cells right after, which is the one time the server sorts them. In broadcast, the comment over full says that names and levels change now and then, while NPCs don't, so they go out once a second, and the clients keep them in between. In broadcast land, NPCs get a map of pieces, next to the players' and the monsters', and on a full world, each NPC of the land is serialized into its piece, with its look. On the other nineteen worlds of each second, the server doesn't serialize the NPCs at all. Views gets the land's NPCs in their cells, and on a full world, each cell's world gets the pieces of the NPCs near it, after the players and the monsters.

18:38 Our interest test puts three players and a monster around the island, and checks what each cell gets. We add two NPCs, one near the first player, and one a hundred metres past the far player, out of its view. Views gets them in their cells, from cells of, the way the server does it. The first player's cell gets the NPC near it, while the far player's gets none, as a hundred metres is three cells away, past the two cells each way that a player sees.

19:07 We run the interest test on its own, with a filter, and it passes, so each player gets the NPCs near them, and none of the others.

On the client

19:22 On the client, parts puts the pieces of a world back together, and once a whole world has arrived, it drops the players and monsters that weren't in it, which is how someone who walks out of view goes. NPCs come in one world a second, so on that rule, they'd go again with the next world, a twentieth of a second later. Instead, parts keeps each NPC with the time that the server sent its world, which each world carries already, from the server's clock, so that a full world that's lost over UDP doesn't make them blink out for a second. It drops an NPC once three seconds of worlds have gone by without it, such as when you walk away from it. And a new land starts with none, so that the Meadows' NPCs don't stand around in the Ashlands until the first full world arrives.

20:07 In parts dot h, chrono comes in, and k NPC timeout is three seconds, as chrono seconds. NPCs come once a second, so a client keeps each for this long after it last heard of it, and one lost datagram doesn't make them blink out. Three seconds lets two full worlds in a row go missing, while an NPC we walk away from goes a few seconds later, out in the fog. In the private part of parts, a heard NPC is the NPC's message, with when the world it last came in was sent, in microseconds, like the world's own sent. Parts keeps them in a map by id, next to the players and the monsters. In parts dot c c, chrono comes in here too, for the timeout. Add takes each part of a world as it arrives, and keeps the newest world's time, which is what we're going to measure the NPCs against. Once the client is through a gate, its parts come from another land, and each land has NPCs of its own, which may have the last one's ids. So a part from another land clears the NPCs, before the land changes. Each NPC in the part goes into the map, with the time its world was sent, in place of what we had for that id. Then erase if drops the NPCs that we last heard of more than three seconds before the newest world, as microseconds, which chrono compares with a timeout in seconds for us. And the world that parts puts together gets the NPCs it keeps, so the rest of the client sees them as if each world had brought them.

21:35 Then a test at the end of parts test dot c c, which keeps NPCs between the worlds that send them, until they're gone. K second is a million microseconds, with digit separators, so that the zeros are easy to count. A full world, at one second, has a player from make world, and an NPC with id one, named Guard, and it goes into parts, like a world off the network. The next world comes at three seconds, with no NPCs in it, as the next full world, a second later, was lost. Two seconds after we last heard of it, the guard is still there, by name, while at five seconds, four seconds after, it's gone.

22:14 We run the protocol tests for parts, where our new test sits next to the ones for splitting worlds and putting them back together, and they all pass.

Coloured balls

22:32 The client draws the world as figures, which the animator makes. So in animator dot h, a figure gets a flag for an NPC, next to the one for a monster, and a raylib colour, white by default, and a radius. Together, they're an NPC's look until NPCs have models, a ball of this colour and radius, in metres. The animator keeps the last frame's figures in a map for each, as players, monsters and NPCs each have ids of their own, so they're kept apart, with a third map, for NPCs. In animator dot c c, follow eases each player and monster towards where the server says it is, and blends its animations, which a ball doesn't need. So stand makes an NPC's figure, from the one we had for it last frame, if there was one, so that its clip's time carries on from there, and a new figure otherwise. It copies the id and the name, and marks it as an NPC. Get colour turns the number into a raylib colour, reading its four bytes as red, green, blue and alpha, and the radius comes as it is, in metres. It puts the figure where the server says, facing its yaw, and main lifts it onto the ground, like the other figures, from the terrain's height. The comment over stand says why it's this short: NPCs stand still, so each is where the server says, and its clip's time is all that goes on. In update, NPCs get a map for this frame, next to the players' and the monsters'. Each NPC in the world gets its figure from stand, which goes into the map and into the list to draw, after the players and the monsters. At the end, this frame's map replaces the last, which is where NPCs that went drop out too, along with the players who left and the monsters that went.

24:11 In renderer dot h, the renderer gets a model next to the cube, for the ball that each NPC is drawn as, scaled to its radius and tinted its colour. A single model means one mesh on the GPU, however many NPCs there are, as each draw passes its own scale and colour. In renderer dot c c, the constructor makes the sphere with raylib's gen mesh sphere, with a radius of one, so that scaling it by an NPC's radius gives the right size. It has sixteen rings and sixteen slices, which look round at the sizes we draw. The ball uses the cube's shader, which lights it, and fogs it, like the rest of the island, and the destructor unloads it, next to the cube. In draw figure, an NPC is drawn before anything else is looked at, as it has no model of its own to look for. We take the figure's place, and the ball's middle is its origin, so it's raised from there to rest on the ground. Draw model e x draws the ball a radius above the figure's place, with no turn, as turning a ball would change nothing on screen. The ball is scaled by its radius on all three axes, and tinted its colour, and nothing else gets drawn for it.

25:19 Last, the nameplates, in nameplates dot c c, where k NPC name is a light green, for the NPCs' names, next to the monsters' red. Above says how far over a figure's feet its nameplate goes, in metres, which for an NPC is the top of its ball, two radii up, and forty centimetres more, while monsters and players keep the heights they had. Where we work out the nameplate's place on screen, the height now comes from above. An NPC gets a branch of its own, as NPCs don't fight, so they have a name and no level or health. For an NPC, the nameplate measures its name first, into an im vec two, which is ImGui's pair of floats for a size or a place on screen. It measures with calc text size, which takes the size of the text, the largest float as the widest it may be, and a wrap width of zero, so that a long name stays on one line. Half the width to the left of the point centres the name, and its height up puts it over the point, where draw shadowed text writes it in green, with the shadow under it, like the other names. Then continue goes on to the next figure, before the health bar and the level that players and monsters get.

26:25 Let's build it and run it, with netem dropping one packet in ten between the client and the server, so that now and then, a full world with the NPCs in it is lost. Once alice is in, the guard, the merchant and the healer stand in front of her, in blue, gold and green, with their names over them. As she walks up the road towards the gate, the balls stay put, while full worlds go missing here and there. Turning the camera around them shows that they rest on the ground, lit and fogged like the rest of the island.

Docs

26:56 Last, the README, where the opening paragraph mentions the NPCs, and the section on the monsters points at the tables in monsters dot h. A new section on NPCs says where they stand in each land, and what they look like, and that monsters and NPCs are data now, where a new kind, or one more of them somewhere, is a line in a table. It says how an NPC differs from a monster, with no health and nothing to think with, and that NPCs aren't saved, as the tables put them back whenever a server starts. Then it goes through how the server puts them into their cells once, and sends them once a second, with their look, and how the client keeps each one for three seconds. The section ends on what an NPC that walks a round would need, which is to go out with each world, like a monster, or in a message of its own whenever it changes.

Wrap-up

27:43 So, today our monsters became data, with a kind for the skeleton, and tables of where monsters spawn and camp in each land. And our NPCs got tables of their own, for what each kind looks like and where each NPC stands. On the server, an NPC is a small type of its own, with ids of its own, apart from the monsters, which goes into its cell once, and out to the players once a second, with its look. The client keeps each NPC for three seconds after it last heard of it, so that a lost world doesn't make them blink out, and draws them as coloured balls with green names, until they have models.

Playing it

29:12 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.