Understanding the requirements
- 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.
- 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.
- 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.
- 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.
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.