Algorithms for Spawning in Multiplayer games

#1
Hi!

I've been thinking a lot about how video games such as Call of Duty or (any multiplayer game) might determine where to re-spawn you if you are killed in a match. I'm not sure what statistical or machine learning techniques could be applied. This is all very crude, but let me give you a typical scenario.

-In the multiplayer game, there are two teams (e.g. Red team vs Blue team). The objective is to shoot and kill members of the other team. The team with the highest score at the end of a 10 minute match wins. There is no score cap.

-Every time you die in the match, your character is re-spawned to a spawn point, after a brief delay (usually 10 seconds).

My question hinges around how to best choose that spawn point given the state of the game when you die (and potentially in that 10 second delay).

Some thoughts:

-You don't want to be re-spawned to a spawn point that is near a dense group of players from the other team. It can be viewed as unfair (e.g. if you happen to spawn right behind a dense area of enemies you will have the drop on them. On the other hand, if you spawn right in front of them, you're toast)

-You don't want to be re-spawned to a point so far away that it takes a long time to reach a semi-dense (i.e. action heavy) portion of the map. The map can be somewhat big and the match is timed, so you can potentially waste a lot of time doing nothing. [I've had this experience]

I'm not looking for an answer per se, just would appreciate any help in framing this into a statistical or machine learning problem.

I don't know too much about machine learning, but this smells suspiciously like SVM. Likewise, the nature of the game also sounds like it could lend itself to a continuous time, discrete-space stochastic process.


Happy to hear any thoughts!
 
#2
I guess you could try to minimise some objective function for each spawn point, that function being somehow weighted by density of enemies such that it penalises both being too near and too far.

Not sure ML techniques would be useful though. For instance a SVM is a supervised technique - you'd need user feedback to 'tell' the algorithm whether it got the respawn location right.

Be interesting to know how they are actually programmed.
 
#3
Thanks for the reply!

I'm still unsure how they actually do it after researching.

So far, I've taken your approach on an objective function and started to program something really crude.

-I have a grid from 0 to 10 (on X, and Y) which serves as the multiplayer map.
-I uniformly generate 3 blue dots (i.e. team members) and 3 red dots - each point has an x and y coordinate pair and this represents their location on the map.
- I've also fixed the location of the spawn points to static x-y coordinates. There are 6 of them.

In order to spawn say a new blue team member, I look at the individual euclidean distances of each red team member alive at that time to each spawn point. (So if there are 3 red players, I calculate distances for each of them to each of the 6 spawn points). I then simply sum up the distances. Right now, I'm selecting the spawn point that's associated with the maximal distance over all red team members.

Need to think about how I might factor in a penalty.

this has been a fun distraction from actual work :)