Making random spawn points fair?

inappropriateCode 08/22/2017. 9 answers, 4.496 views
game-design level-design

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.

5 Comments
10 Zibelas 07/28/2017
Spawn in a circle?
1 inappropriateCode 07/28/2017
@Zibelas Traditional approach, but violates requirement 3, and with lots of players this creates a huge map and empty interior.
4 Zibelas 07/28/2017
It depends on your type of game. (2D/ 3D, respawn/ last man standing, etc) Perfect spawn is in that case only possible on a ball shape world (more player, closer spawn but you can guaranty they have all the same distance). On a 2D world with fixed borders you have always less bordering players since you have no place to spawn them. If its a 3D game, you can have multiple layers.
1 RothX 07/28/2017
I think it would help to know what kind of game you are making. It sounds like some kind of warfare game, but what are the details? Is it a shooter? Do you start with all your weapons, or do you have to explore and find things? What is the victory condition? How long is a match expected to last?
3 Jan 'splite' K. 07/28/2017
Not for full answer, but i think everyone is trying for "fair & balanced spawn" which... is not fun. Look at excellent PUBG (and others Battle Royale) spawning: players can "spawn" (well, jump and land...) almost anywhere they want - if you want conflict and drama, you choose place where most player land / spawn. Hight risk hight reward, but only if player want it. You can land somewhere in woods, you got time to prepare yourself - low risk low reward but some players may prefer it (like me, for example ;) ). Its NOT random, its by players choice.

9 Answers


Philipp 07/28/2017.

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.

5 comments
14 Shashimee 07/28/2017
+1 for using the Hunger Games 1 film spawning system.
3 Philipp 07/28/2017
@Shashimee Actually I believe I have seen this method first in Anno 1602. I also believe that some of the early C&C games had that as an optional multiplayer game option (but I am not sure if I recall that correctly).
3 Zibelas 07/28/2017
@Philipp M.U.L.E. for the commodore 64 around 15 years older and let you pick as well your positions :)
Dent7777 07/28/2017
You then run into the issue where you are followed to your spawn point. This could, of course, be desired game mechanic, but it could also be extremely frustrating and not something you decide you want in your game. A good idea would be to have the characters spawn invisible and player-collision-free, and find their base before starting the game.
Kroltan 07/28/2017
That's the method used by the "Vampirism" and "Tree Tag" line of custom gamemodes on Warcraft 3. It works best since all players are allied (at least initially) and the opposing team is released later.

Theraot 07/28/2017.

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.

  1. 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.

  1. 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.

  1. 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.


Zibelas 07/28/2017.

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)


Aric Fowler 07/28/2017.

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.

1 comments
2 Avery 07/29/2017
Or make a map that, well, in center, you can get hunted or hunt much easier, and can also find loot easier, but again, you're much more possible to get hunted like this, and in non-center areas, make it so that players are less likely to find other users and loot, so if they want more loot they'll have to go to the center, if they want to survive longer, they'll have to stay where they are. So basically make the disadvantage of random spawns an advantage.

dnk drone.vs.drones 07/28/2017.

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

Diagram of spawning mechanisms

2 comments
Zanon 07/28/2017
Second image is a great option. It solves the problem of the first option where the player knows exactly where all other players are located.
Avery 07/29/2017
@Zanon though with first image players can (and likely will) move away before someone comes there. Second one will cause unfair spawns, some close to others. Maybe something like this where there are 2 circles and the difference between smaller and bigger one is where they spawn, so like second image, but less to the center.

MrCranky 07/28/2017.

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.

Aaron 07/28/2017.

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.


Anton Sherwood 07/29/2017.

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.


NotThatGuy 07/31/2017.

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.

HighResolutionMusic.com - Download Hi-Res Songs

1 BLACKPINK

Kiss And Make Up flac

BLACKPINK. 2018. Writer: Soke;Kny Factory;Billboard;Chelcee Grimes;Teddy Park;Marc Vincent;Dua Lipa.
2 Martin Garrix

Waiting For Tomorrow flac

Martin Garrix. 2018. Writer: Pierce Fulton;Mike Shinoda;Martijn Garritsen;Brad Delson.
3 Martin Garrix

Access flac

Martin Garrix. 2018. Writer: Martin Garrix.
4 John Legend

Written In The Stars flac

John Legend. 2018. Writer: Kiana Brown;Santoy;Kevin White;Mike Woods;MZMC;The Heavy Group;Rice N' Peas.
5 Martin Garrix

Yottabyte flac

Martin Garrix. 2018. Writer: Martin Garrix.
6 Alan Walker

Diamond Heart flac

Alan Walker. 2018. Writer: Alan Walker;Sophia Somajo;Mood Melodies;James Njie;Thomas Troelsen;Kristoffer Haugan;Edvard Normann;Anders Froen;Gunnar Greve;Yann Bargain;Victor Verpillat;Fredrik Borch Olsen.
7 Cardi B

Taki Taki flac

Cardi B. 2018. Writer: Bava;Juan Vasquez;Vicente Saavedra;Jordan Thorpe;DJ Snake;Ozuna;Cardi B;Selena Gomez.
8 Bradley Cooper

Shallow flac

Bradley Cooper. 2018. Writer: Andrew Wyatt;Anthony Rossomando;Mark Ronson;Lady Gaga.
9 Post Malone

Sunflower flac

Post Malone. 2018. Writer: Louis Bell;Billy Walsh;Carter Lang;Swae Lee;Post Malone.
10 Dyro

Latency flac

Dyro. 2018. Writer: Martin Garrix;Dyro.
11 Zara Larsson

Ruin My Life flac

Zara Larsson. 2018. Writer: Delacey;Michael Pollack;Stefan Johnson;Jordan Johnson;Sermstyle;Jackson Foote.
12 ZAYN

Fingers flac

ZAYN. 2018. Writer: Zayn Malik;Alex Oriet;David Phelan.
13 Halsey

Without Me flac

Halsey. 2018. Writer: Halsey;Delacey;Louis Bell;Amy Allen;Justin Timberlake;Timbaland;Scott Storch.
14 Lady Gaga

I'll Never Love Again flac

Lady Gaga. 2018. Writer: Benjamin Rice;Lady Gaga.
15 Sia

I'm Still Here flac

Sia. 2018. Writer: Sia.
16 Dewain Whitmore

Burn Out flac

Dewain Whitmore. 2018. Writer: Dewain Whitmore;Ilsey Juber;Emilio Behr;Martijn Garritsen.
17 Little Mix

Woman Like Me flac

Little Mix. 2018. Writer: Nicki Minaj;Steve Mac;Ed Sheeran;Jess Glynne.
18 Mako

Rise flac

Mako. 2018. Writer: Riot Music Team;Mako;Justin Tranter.
19 Blinders

Breach (Walk Alone) flac

Blinders. 2018. Writer: Dewain Whitmore;Ilsey Juber;Blinders;Martin Garrix.
20 Rita Ora

Let You Love Me flac

Rita Ora. 2018. Writer: Rita Ora.

Related questions

Hot questions

Language

Popular Tags