Making random spawn points fair?

Question

If all players are spawned at random positions the same distance from adjacent players, the number of players will be proportional to the likelihood of their spawn positions being unfair. The closer players spawn to the centre of the map, the more likely they are to encounter other players and the less likely they are to survive, compared with players on the edge of the map. Assume all players are spawned at the same time.

Is there a way to shape spawn points, or change the map, so that:

1. All players have a limited number of adjacent foes.
2. All players have equal chance of encountering adjacent foes.
3. Map size does not have to increase proportional to the number of players.
4. These limitations are not enforced with arbitrary impassable spaces.

The answer does not have to be perfect, just obviously better than the alternative. Out of the box thinking welcome.

Answer 1

Let the players pick their start locations themselves.

At the beginning of the game, spawn all players in the center of the map, but without any means of harming the other players. They will then have to swarm out and acquire the means to engage each other (build a base, pick up a weapon, gather resources, etc.)

There is either a bit of luck or map knowledge involved in finding a good start location early (depending on whether you use procedural or handmade maps). But when and where to settle is mostly a strategic decision. Deploying early gives you a time advantage, but puts you in a dangerous position. Picking your base carefully puts you behind in the early-game, but can be a decisive advantage in the mid- and late-game.

Answer 2

Understanding the requirements

1. All players have a limited number of adjacent foes.

First off, we are talking about the spawn points of the players, not the current position of the players at a given point in the game. Just getting that out of the way.

Adjacent is well defined when we talk about a graph. We can think of a map that represent navigability on the map - from now on "the graph".

If can node can have at most one spawn point, then talking of them being "adjacent" makes sense. Note: I will not constraint nodes to have one single spawn point at most, for reasons that will be apparent later.

To build the graph we will need to consider things such as walls, bridges, ladders, teleportation points, or even consider flight space if there could be player that can fly. Each node represents a traversable location; each connection represents a possible movement.

Note: know size and shape of the nodes, and work with actually adjacent nodes. Do not consider nodes a point. Do not consider connections as having length. Also, use convex nodes.

The graph could have been precompiled (the map was created by a designer); otherwise, it can be created on the fly if the map is randomly generated.

2. All players have equal chance of encountering adjacent foes.

I will assume foes are other players. Again, just getting that out of the way.

Assuming each player makes a random walk, the probability of finding a player at a given point - on a flat space, free of obstacles - will be given by a (Gaussian) function of the distance to the spawn point - from now on "the function".

Since we are working on the graph, we will instead annotate the values on the graph.

3. Map size does not have to increase proportional to the number of players.

If we had the constraint of having a single spawn point per node, then to add more player we would need smaller nodes. If we decide the graph before we know how many player we will have, we may have to subdivide nodes for the particular game.

4. These limitations are not enforced with arbitrary impassable spaces.

I do not intend to add obstacles to solve the problem. Au contraire, I need to work arround the obstacles. If they were not there, the implementation would be simpler.

---

Solution

We are trying to place N spawn points such that the chance of encountering another player at all those spawn points is equal.

We can get a measure of the error as the sum of the differences of the chances to the mean of the chances. We are trying to minimize that (in fact, we want to make it 0).

To do so, we need to know the chance of encountering a player on each node of the graph.

To compute that chance, start with zero. Since the chance of finding a player on any given node, when there are no players, is zero. And then, for each spawn point, walk the graph adding to the annotated chance the value of the function for the current spawn point.

Note 1: Adding or moving a spawn point will affect the chance of encountering a player for all the map.

Note 2: Keeping track of how much each spawn point affects the chance, will make things easier.

Note 3: Since nodes have size, how close you can get to error = zero depends on the size of the nodes. You can be more precise by working with ranges of values (minimun and maximun chance, depending on the particular position of the spawn points within the node).

Place spawn points at random, then start moving them in such way that error becomes smaller (consider a possible movement, and if causes the error to decrease keep it, otherwise revert it). And continue doing so until we cannot improve any further (too many iterations without improvement, or error is zero).

Note 4: When moving a spawn point, you can use the chance of encountering a player (excluding the spawn point you will move) to randomly select a new position for a spawn point such that position that have a chance of encountering a player closer to the mean are more likely. I remind you that moving the spawn point will affect the mean.

The expected behavior is that spawn point that are too close together move apart and spawn points that are too far apart come closer. Until they reach equilibrium.

If at any given iteration you have multiple spawn points on a node (which is unlikely, since they should tend to move apart, but possible if you have large enough nodes), split the node and continue solving. Any division of the node is valid.

---

The above solution will approach error = zero, but not guaranteed to reach zero. You can do is run it until it reaches a local minimum... In theory, you can then divide nodes to make it exactly zero... Yet, that is equivalent of tweaking the spawn point coordinates!

Try simulated annealing to move the spawn point within the node. Although, honestly, it probably is not worth it to bother with such level of detail.

---

I want to make it clear that the result for a flat map free of obstacles will not be uniformly distributed points. Instead, if the map has edges (that is, if it does not wrap around), then there will be more spawn point closer to the edges, this is because points at the center can be reached from more directions, increasing the chance of encountering other players there. Thus, points further apart near the center to compensate.

Answer 3

It depends on what kind of game you want to create and how fast paced it is. The perfect evenly spaced distribution is possible on a sphere like world (for example Planetary Annihilation). But is that a fair option in your game? Even if all people are spawning on equal distance, some spawns may still have better advantage.

• Closer/ better weapons in range/ more resources
• Better cover/ more hidden/ overview
• the 'flow' of the players, some places are more attractive than others (think of a full forest map with a single house at one place, regardless where that house is, good chance that people are checking it out)

Is your map a fixed one or a procedural generated one? And ever tried to play Age of Empires with 8 people on a 2 person map? It's not possible to scale the players infinite without making adjustment to the map size. Even an unfair start placement can bring a lot of dynamic in the game (see the Worms series). Nobody complained if you spawned right in a big cluster, as long as your one round alliance with another player lasted or you had not the most surviving worms after the first round.

(I will add a few more examples if I know more about your type of game)

Answer 4

Going for something not suggested so far: Make it so there is no centre of the map. What I mean by this is that the map edges join onto the opposite sides. This would take a lot of programming work, but in practise it can make the level repeat itself infinitely if you walk in one direction. This means that there is no centre, and a random spawn position will have no advantages or disadvantages.

You can do this by making a flat map which is square, and joining each edge to a copy of the opposite edge. When a player walks off the side, they are teleported without the player's knowledge to the opposite edge. Of course, theoretically you would not be able to see players on the other side of the boundary. To fix this, create clones of that player which appear to walk around on the other side of the boundary so that you can see them, and when you run towards them you teleport across and the actual player is stood where the dummy was.

Alternatively, the entire map could exist on the outside of a sphere, however this makes coordinates difficult for spawning.

Answer 5

Here are some possible solutions:

• Spawn randomly on the circumference of the circle
• Spawn randomly on radii (not spawning to close the center)
• Add a random spawn time component

Answer 6

Fundamentally I believe this is a graph distribution problem. Assuming a deathmatch situation (every other player is an enemy), you need to model your maps as an interconnected graph, and track which node on the graph each player is closest to. Not every node need be a spawn point, but you need the complex graph to model distances between spawn points. At spawn time, you're then iterating the graph and scoring each spawnable-node based on whether it nearby nodes have players.

The ideal node then has:

• No players currently in it
• More than zero players in nodes nearby (some small number of links away)

Imagine that your graph has been regularised, and you're drawing concentric zones around each node. You penalise the node if the inner zones already have players in them, and reward nodes that have players at the right distance away. You want to encourage spawning near enough to other players that they can find interest quickly, but not so near that they get jumped on before they've had a chance to get their bearings.

You will need to increase the map size as the number of players grows, but the k need not be 1 or greater. Your worst case is still going to be that every node on the graph has at least one player - in which case there are no good nodes to use, and you're going to have to suffer that case and spawn a player knowing that they will land right on top of another. The scoring algorithm should still weight the nodes so that you spawn in the node with the fewest other players.

Bear in mind that your map graph will have to be carefully built, with knowledge of the map, its routes, any chokepoints, and effective distance between node points, not actual distance. As in, use something like measured time to traverse between nodes rather than distance, to account for more difficult terrain. Also you need to account for open-ness vs cover; two nodes might be physically far apart, but because they are very open, spawning a player at each node might mean they are equally as vulnerable as if you'd spawned them right next to each other.

Refinements:

• Add a temporary penalty to score if a player has spawned in that node recently, to stop chokepoints from forming (an endless stream of players coming from the same direction and getting picked off)
• Add randomness within a range (e.g. pick the best 3 nodes and then randomly choose between them with equal probability) to get more variation.
• Add an initial weight to the centre of the map (or the most interesting points) when no-one has yet spawned, so that you spawn in known places, even when every node has a score of zero because no other players are present.

Answer 7

A few others have already discussed the limitations of your requirements (map will need to scale at some point to prevent overcrowding, etc.), and have ultimately eluded to the fact that there likely isn't a "perfect" placement algorithm. When there likely is no "perfect" algorithm, I always look towards heuristics. You have several criteria that are either directly or indirectly at odds with eachother, along with a very complicated search space. Finding an optimal solution may not be feasable or practical, but with a little tuning, a statistical approach can perform very well the majority of the time.

Addressing your third and fourth criteria: "The map shouldn't have to expand."

I would make sure at the beginning you have an over-abundance of nodes (ie: as dense as a navigation mesh for path-finding). This makes calculating the distance to other players more expensive (not directly neighboring nodes), but this is not a process that will happen more than once per round (I assume). A bonus of this is you can use a pre-rolled nav library for most of your operations. Additionally this will respect traversal around obstacles in a fair manner where euclidean distance may not (players in a maze might be placed closer together than in an open field)

Calculate heuristics for your desired spawn characteristics:

After randomly placing all the players, calculate the performance of the surrounding nodes based on your criteria (distance from other players, distance to spawn, etc.) The weights of your values can be tweaked, and manipulated to be nonlinear to tune exactly the performance you want in a sanitized ideal case (flat rectangular grid with no obstacles), and the performance should be similar when you add the world back in. From there you can decide how many nodes to search, what is the threshold for moving a starting point, and how many iterations you want to perform before finalizing the spawn and beginning the game.

Answer 8

If the playing field is a topological torus (i.e. a rectangle where going “out of bounds” means entering at the opposite side), this is likely to be a good answer: player j spawns at x = (pjW/N) mod W, y = (qjH/N) mod H, where W,H are the dimensions of the rectangle, N is the number of players, and p,q are integers to be determined; they are distinct, (probably) relatively prime, and not too far from sqrt(N). The spawn points form an oblique ‘wallpaper’ pattern.

That's supposing that the players spawn only at the beginning of the game. If they spawn later, I guess you'd want to put them as far as possible from any player's current position – at a vertex of the Voronoi diagram defined by the other players.

Answer 9

How about:

Each player is surrounded by a non-spawning box (or circle).

As in, there's a square of a certain size that spawns around every player and follows that player around - no other player can spawn within that square.

These squares only affect spawning and not any other movement during the game.

This works with either initial-only spawning or continuous spawning.

(Dots indicate players and green indicates possible spawn area for new players)

Map size does not have to increase proportional to the number of players

To deal with this, you can do one of two things: (or both)

• Decrease the size of the non-spawning boxes based on the number of players.
• Allow up to X enemy players to spawn in each box.
  • This number can increase as you go (starting at 0).
  • Variant 1: have a smaller no-spawn box and a larger limited-spawn box.
  • Variant 2: weight probabilities according to how close the new spawn is to this player (if inside the box) - might be hard to implement efficiently.