Jakob's Blog Personal insights into technologies

Gamedev #2: Multiplayer and procedural map generation

Today, we define the basics of multiplayer in Paddlers and I walk you through the necessary steps to generate pseudo-random maps using procedural techniques.

In previous posts, I have written about the single-player experience which happens inside a single village on a stream of water.

The multi-player game mechanics should take place on a global map where all villages are marked. But at the time of writing, I have not implemented any of that. Naturally, the exact map design is not carved in stone, yet.

Table of content in this post

Multiplayer game mechanics

The most important question right now is what the map should facilitate. What will be going on on the map? Depending on the answer to that question, there are different requirements for the map structure.

Actions on the map

Multiplayer in Paddlers will be mostly about interactions with neighboring villages. There have to be plenty of villages generated in the world.

At the start, each player controls one such settlement. Other villages can be discovered on the map and benefits await for interacting with them, as I will explain in more detail soon.

Some villages are under control of AI players. These are simply building up their villages at a medium to slow pace. AI players are mostly passive but sometimes they find their own belief system and decide to challenge their neighbors’ faith with their own.

When a player becomes inactive, his or her village(s) will be controlled by the AI as well. This is to avoid players getting stranded in the middle of completely dead villages.

Farming and grinding

To grow an empire, resources are required. And players will have to put in some effort to efficiently gather them if they want to dominate their neighbors. One mechanic to accelerate the income of resources is through invitations.

In Paddlers, players can invite ducks from AI villages to visit their village, which means they will float through the player’s town. If the visitors are satisfied after their visit, they will leave behind a reward.

Hence, players will often scroll through the map and see in which town there are idle ducks. The more they can invite (and satisfy), the more resources are coming in!

Furthermore, it will be possible to convince visiting Paddlers to stay and join the settlement to increase the population.

Unclear at the moment is how invitations will work between two non-AI players. Currently, I am facing some game design issues there and I yet have to figure out how to resolve them.

Expanding

Later in the game, players will want to grow their cult’s influence. Gloriously, with the best of intentions, populations following the wrong belief-system will be freed from their nescience!

Players will send missionaries to other villages. They will try to weaken the prevalent religion in a town and push their own religion instead. Eventually, this might lead to the conversion of an entire village, which is exactly how conquests are executed in Paddlers.

By providing preferable conditions to the local Paddlers, players can defend their town and make conversions much less likely. The details of this are not clear, yet, and will not be further discussed for now.

Post-MVP features

Some features are already planned but they will not make it into the MVP. They are likely subject to change but I want to list them quickly anyway.

The map layout

Given all the possible actions listed above, let me define the map structure that I have chosen to facilitate them.

Base structure

The map will consist of a wide green land, flooded by many little streams. On the waterside reside the players’ settlements.

Please, have a look at this mockup to get a better idea of what I am describing.

Image: Draft of map Mockup of a possible map design created in Inkscape

Imagine the map to expand indefinitely towards the left and the right side. The streams should help players to orient themselves on the map, thus, preferably they are shaped uniquely.

The grid, on the other hand, helps to keep distance-calculations simple. This is nice to have because the distance between villages will determine the time it takes to reach another village, which players might want to compute or estimate in their heads.

Village distribution

The villages density will be quite an important factor in the game. There should be enough close villages around each village to keep the game interactive. But too many villages too close could also result in a rapid pace such that a player could be rushed down during a normal working day when he or she has no time to log in.

To properly address this requirement, careful balancing will be needed. Thus, I want to go for a flexible way of generating maps that allows me to easily change village density in the balance-testing phase. Hand-crafted village distributions are off the table. Instead, village positions on the map must be generated dynamically.

On the other side of things, the map should also be realistic. And since each village has a stream of water flowing right through the center, village positions on the map should exclusively be on streams.

Procedural map generation

Eventually, I decided to go with procedural map generation for the streams and villages. This leads to unique and hopefully beautifully shaped streams with flexible villages density.

Basics of procedural map generation

When I am talking about procedural map generation, I am referring to any algorithm which takes a small input seed, for example, a 32-bit number, and generates a pseudo-random map from it. Ideally, even the slightest change in the seed changes the look of the map completely.

The geometry of a Paddlers map

As in the mockup above, a main-river spans the entire map horizontally. The shape of the main-river is static and will be the same for all generated maps, serving as a stable root for the remainder of the generation.

Smaller streams are flowing vertically into the river. These are being generated and therefore must be defined mathematically. To have nice curves that are described by only a few numbers, I decided to go with quadratic Bézier curves. The same are frequently used in vector graphics and they are therefore easy to draw.

Deterministically generating a random-looking map

To have different maps available for different servers, my map generator takes a single integer as seed. This is then fed into a linear congruential generator (LCG) to generate a stream of pseudo-random numbers. This output stream decides each further step of the map generation.

One stream of water at the time, the control points for the Bézier curves are generated. A couple of rules define in which area the control points are allowed to be:

Following these rules, the LCG output is used to pick a random position for each of the control points until the stream has the defined length. The code for this would be too boring, so here is just an example output.

Image: Example of map skeleton Generated empty map example This image has been rendered in the browser by the WASM frontend of the game itself, using Lyon to generate the curves from the control points. The white rhomboids visualize the randomly generated control points which define the stream curves.

After generating the map once, all control points are stored in the database. The frontend will receive these points on demand and can render the curves using vector graphics libraries.

Village positions

One last crucial step remains. Where will the villages be placed?

To compute possible village positions on the game server, I calculate the Bézier curves in the backend code, using the control points stored on the database. The goal is then to find all squares which are crossed by a stream enough, whatever that means.

To keep it simple, I just sample some points on the curves and compare the distance to the next square center. Whenever such a point is relatively close to the center of a square, this square is a legal position for a settlement.

With this technique and some parameter fine-tuning, a fully populated map looks like this:

Image: Generated map example with all possible village positions Pre-alpha footage of Paddlers

In the real game, not all villages will be created instantly. As more players join, more settlements are created and the map fills up slowly. Eventually, it will look something like in the examples above. But until then, there will more space between villages, as demonstrated in this last example:

Image: Generated map example Pre-alpha footage of Paddlers

Closing word

In this article, I introduced the fundamental multiplayer game mechanics in Paddlers. Further, the process to generate maps procedurally has been described.

In my next post, I finally want to talk about some technical aspects. Stay tuned!

Next post in series: Gamedev #3: Fun with Rust and distributed systems