Fair spawning of players on a 2D grid

Question

As new players enter a game, they are given a location on a large grid. The first player is given the location in the center.

Now, how should the second player be placed? Then, the third and so on?

New players should be placed reasonably near some other players, but not so close as to cause bunching.

My current thinking is to trace a clockwise spiral around the first player, gradually moving further and further out from that initial point. But I keep thinking this must have been done before and that a general solution must exist.

This is for a strategy resource game (similar to CoC or Throne Wars etc).

How do I do this?

Answer 1

I'll address the general problem and issues you'll face, regardless of what game-specific rules you have for spawning players. You'll want these three parts:

1. Something that generates a potential spawn point, let's call it GenerateSpawnPoint()
2. Something that checks whether a spawn point is valid, let's call it CheckSpawnPointIsValid(spawnPoint)
3. Make sure that you eventually make a correct guess, or handle things if you cannot make one

So the pseudocode is:

loop for some time:
    point = GenerateSpawnPoint() // #1
    if CheckSpawnPointIsValid(point): // #2
        SpawnPlayer(point) and end
if we have not spawned:
    do something else // #3

It may seem that guessing and checking repeatedly like this is inefficient, but most games have very complex rules for whether a spawn point is valid. Your game rule may dictate that players can't intersect each other, or over certain objects. Your map may have inaccessible areas. You may want to spawn close to some things, or further away from others. It doesn't take many of these rules to create quite a complex CheckSpawnPointIsValid() function, and certainly one that is too complex to guarantee your guesses are successful. Therefore unless you are spawning hundreds and thousands of players per game tick, this sort of loop should be ok, even if you iterate hundreds of times in this spawning loop (just make sure the loop terminates).

Another advantage with this approach is that it's very easy to make; your game probably already has routines to check whether spawn points are valid, as part of your normal gameplay.

GenerateSpawnPoint() can be as simple as creating a random point. Just be careful that it makes a good enough guess, such that the guess has a reasonably good chance of being valid. For instance, avoid using a completely random guess over your entire world dimensions if your map is very sparse. Your idea of using a spiral is good because points next to existing players are more likely to be valid spawn points; just be aware that your suggested algorithm will tend to spawn players close to others than further.

Finally, the reason why we should handle the extraordinary case where we don't manage to find a valid guess is that, for non-trivial game rules and map layouts, it's hard to guarantee that we'll find a valid point, in all cases. For example, you may (inadvertently) specify game rules that players should not spawn in sight of any existing players, but apply it on a wide-open small map (where every point is in sight). Therefore you should think about what should be done if you cannot find a valid spawn point - is it ok to try spawning again later, or spawning in a position that breaks some of the rules, or not spawning at all?

These are the general issues you should be keeping in mind.

Answer 2

I read up an answer on these board about this, I tried to search for the link it because it was more detailed, but I couldnt find it back. to give you a summary about it : it was about how AI decide where to build town in Civ game. I'm not sure what a CoC game looks like, but since its resources base it should be similar.

You just basicly build a basic town placement AI. When you generate a map, you give a startingValue integer to each "square" or hexagone, or however you split your map. You recalculate to adjust the value whenever a player makes a new town, or "spawn"

You have to determine what gives a good value to a starting location, and give it an score. to be fair, spawn to player at locations with similar score, even if the resources differs, as long as the total point is similar, it should be fair.

close to a gold mine = +5 points

distance to nearest enemy > 5 = +3

distance to nearest enemy < 10 (encourage aggression) = 5 point

on water's edge (port, fishing, etc ) +3

close to XXX luxury resources = 2 points

close to food resources = 8 points.

...

you can add a lot of options here. if you want to force players be to relatively close to each other, only spawn startingValue point ( thus making these valid for a new player) in the 15 radius-square closest to the 1st player, etc.

Now just decide how you want to spawn your player, and what you consider to be fair.

Ex : You have 3 player, you spawn them on locations with 10,11 and 11 points, even if you have 2 other location worth 15 points, since it wouldn't be fair to the third player.