Tornar pontos aleatórios de desova justos?

22

Se todos os jogadores forem gerados em posições aleatórias à mesma distância dos jogadores adjacentes, o número de jogadores será proporcional à probabilidade de suas posições de geração serem injustas. Quanto mais jogadores aparecerem no centro do mapa, maior a probabilidade de encontrar outros jogadores e menor a probabilidade de sobreviver, em comparação com os jogadores na borda do mapa. Suponha que todos os jogadores sejam gerados ao mesmo tempo.

Existe uma maneira de moldar pontos de spawn ou alterar o mapa, de modo que:

  1. Todos os jogadores têm um número limitado de inimigos adjacentes.
  2. Todos os jogadores têm chances iguais de encontrar inimigos adjacentes.
  3. O tamanho do mapa não precisa aumentar proporcionalmente ao número de jogadores.
  4. Essas limitações não são impostas com espaços intransitáveis ​​arbitrários.

A resposta não precisa ser perfeita, apenas obviamente melhor que a alternativa. Fora da caixa, pensando bem-vindo.

inadequadoCode
fonte
10
Desovar em um círculo?
Zibelas 28/07
1
@Zibelas Abordagem tradicional, mas viola o requisito 3, e com muitos jogadores, isso cria um mapa enorme e um interior vazio.
inappropriateCode
4
Depende do seu tipo de jogo. (2D / 3D, respawn / último homem em pé, etc) Nesse caso, o spawn perfeito só é possível em um mundo em forma de bola (mais jogadores, spawn mais próximo, mas você pode garantir que eles tenham a mesma distância). Em um mundo 2D com bordas fixas, você sempre tem menos jogadores limítrofes, já que não tem lugar para gerá-los. Se for um jogo em 3D, você pode ter várias camadas.
Zibelas 28/07
1
Eu acho que ajudaria a saber que tipo de jogo você está fazendo. Parece algum tipo de jogo de guerra, mas quais são os detalhes? É um jogo de tiro? Você começa com todas as suas armas ou precisa explorar e encontrar coisas? Qual é a condição da vitória? Quanto tempo dura uma partida?
RothX 28/07/19
3
Não é para uma resposta completa, mas acho que todo mundo está tentando "desovar justo e equilibrado", o que ... não é divertido. Veja a excelente geração de PUBG (e outros Battle Royale): os jogadores podem "desovar" (bem, pular e pousar ...) quase onde quiserem - se você quiser conflito e drama, escolha o local onde a maioria dos jogadores aterrará. Alto risco, alta recompensa, mas apenas se o jogador quiser. Você pode pousar em algum lugar na floresta, você tem tempo para se preparar - baixo risco, baixa recompensa, mas alguns jogadores podem preferir (como eu, por exemplo;)). NÃO é aleatório, é por escolha dos jogadores.
Jan 'splite' K.

Respostas:

27

Deixe os jogadores escolherem seus locais de partida.

No início do jogo, crie todos os jogadores no centro do mapa, mas sem nenhum meio de prejudicar os outros jogadores. Eles terão que se aglomerar e adquirir os meios para se envolverem (construir uma base, pegar uma arma, reunir recursos etc.)

Existe um pouco de sorte ou conhecimento de mapa envolvido na localização precoce de uma boa localização (dependendo de você usar mapas procedurais ou feitos à mão). Mas quando e onde se estabelecer é principalmente uma decisão estratégica. A implantação antecipada oferece uma vantagem de tempo, mas coloca você em uma posição perigosa. Escolher sua base cuidadosamente o coloca para trás no início do jogo, mas pode ser uma vantagem decisiva no meio e no final do jogo.

Philipp
fonte
3
@Shashimee Na verdade, acredito ter visto esse método pela primeira vez em Anno 1602. Também acredito que alguns dos primeiros jogos da C&C tiveram isso como uma opção opcional para vários jogadores (mas não tenho certeza se me lembro corretamente).
Philipp
3
@Philipp MULE para o Commodore 64 cerca de 15 anos mais velho e deixar você escolher bem suas posições :)
Zibelas
Você então encontra o problema em que é seguido até o ponto de desova. É claro que isso poderia ser a mecânica do jogo desejada, mas também poderia ser extremamente frustrante e não algo que você decide que deseja no seu jogo. Uma boa idéia seria fazer com que os personagens aparecessem invisíveis e livres de colisão de jogadores e encontrassem sua base antes de iniciar o jogo.
Dent7777
Esse é o método usado pela linha "Vampirism" e "Tree Tag" de modos de jogo personalizados no Warcraft 3. Funciona melhor porque todos os jogadores são aliados (pelo menos inicialmente) e a equipe adversária é lançada mais tarde.
Kroltan
Isso também tem a vantagem de se sentir menos injusto. Se você gerar aleatoriamente e morrer rapidamente ou sofrer penalidades, isso pode parecer injusto, mesmo que seja bastante justo. Se você está escolhendo onde você gera mortes ou multas pode parecer menos injusto e punitivo, porque escolher pontos de reprodução é uma habilidade em si e algo em que você pode melhorar. Dito isto, se escolher pontos de desova é realmente difícil, também pode parecer injusto, porque jogadores com habilidades mais altas se sairiam melhor nisso.
Anubian Noob
9

Compreendendo os requisitos

  1. Todos os jogadores têm um número limitado de inimigos adjacentes.

Primeiro, estamos falando sobre os pontos de reprodução dos jogadores, não sobre a posição atual dos jogadores em um determinado ponto do jogo. Apenas tirando isso do caminho.

Adjacente é bem definido quando falamos de um gráfico. Podemos pensar em um mapa que representa a navegabilidade no mapa - a partir de agora "o gráfico".

Se o nó can pode ter no máximo um ponto de desova, então falar sobre eles serem "adjacentes" faz sentido. Nota: Não restringirei os nós a terem no máximo um único ponto de desova, por motivos que serão aparentes posteriormente.

Para construir o gráfico, precisaremos considerar coisas como paredes, pontes, escadas, pontos de teletransporte ou até mesmo espaço de voo, se houver um jogador que possa voar. Cada nó representa um local que pode ser percorrido; cada conexão representa um movimento possível.

Nota: saiba o tamanho e a forma dos nós e trabalhe com nós realmente adjacentes. Não considere os nós um ponto. Não considere as conexões como tendo comprimento. Além disso, use nós convexos.

O gráfico poderia ter sido pré-compilado (o mapa foi criado por um designer); caso contrário, ele poderá ser criado rapidamente se o mapa for gerado aleatoriamente.

  1. Todos os jogadores têm chances iguais de encontrar inimigos adjacentes.

Vou assumir que os inimigos são outros jogadores. Novamente, apenas tirando isso do caminho.

Supondo que cada jogador faça um passeio aleatório, a probabilidade de encontrar um jogador em um determinado ponto - em um espaço plano, livre de obstáculos - será dada por uma função (gaussiana) da distância até o ponto de desova - a partir de agora "o função".

Como estamos trabalhando no gráfico, anotamos os valores no gráfico.

  1. O tamanho do mapa não precisa aumentar proporcionalmente ao número de jogadores.

Se tivéssemos a restrição de ter um único ponto de reprodução por nó, para adicionar mais jogadores, precisaríamos de nós menores. Se decidirmos o gráfico antes de sabermos quantos jogadores teremos, talvez tenhamos que subdividir nós para o jogo em particular.

  1. Essas limitações não são impostas com espaços intransitáveis ​​arbitrários.

Não pretendo adicionar obstáculos para resolver o problema. Ao contrário , preciso trabalhar em torno dos obstáculos. Se eles não estivessem lá, a implementação seria mais simples.


Solução

Estamos tentando colocar N pontos de desova, de modo que a chance de encontrar outro jogador em todos esses pontos de desova seja igual.

Podemos obter uma medida do erro como a soma das diferenças das chances com a média das chances. Estamos tentando minimizar isso (na verdade, queremos torná-lo 0).

Para fazer isso, precisamos saber a chance de encontrar um jogador em cada nó do gráfico.

Para calcular essa chance, comece com zero. Como a chance de encontrar um jogador em qualquer nó, quando não há jogadores, é zero. E então, para cada ponto de desova, siga o gráfico adicionando à chance anotada o valor da função para o atual ponto de desova.

Nota 1: Adicionar ou mover um ponto de desova afetará a chance de encontrar um jogador em todo o mapa.

Nota 2: Manter o controle de quanto cada ponto de desova afeta a chance, facilitará as coisas.

Nota 3: Como os nós têm tamanho, o quão perto você pode chegar ao erro = zero depende do tamanho dos nós. Você pode ser mais preciso trabalhando com faixas de valores (chance mínima e máxima, dependendo da posição específica dos pontos de reprodução dentro do nó).

Coloque os pontos de reprodução aleatoriamente e comece a movê-los de maneira que o erro se torne menor (considere um movimento possível e, se o erro diminuir, mantenha-o, caso contrário, reverta-o). E continue fazendo isso até que não possamos melhorar mais (muitas iterações sem melhoria ou o erro é zero).

Nota 4: Ao mover um ponto de desova, você pode usar a chance de encontrar um jogador (excluindo o ponto de desova que você moverá) para selecionar aleatoriamente uma nova posição para um ponto de desova, para que a posição que tenha a chance de encontrar um jogador mais próximo a média é mais provável. Lembro que mover o ponto de desova afetará a média.

O comportamento esperado é que os pontos de desova muito próximos se afastem e os pontos de desova muito próximos se aproximem. Até que eles atinjam o equilíbrio.

Se, em qualquer iteração, você tiver vários pontos de geração em um nó (o que é improvável, pois eles tendem a se separar, mas possível se você tiver nós grandes o suficiente), divida o nó e continue resolvendo. Qualquer divisão do nó é válida.


A solução acima abordará error = zero, mas não é garantido que chegue a zero. Você pode executá-lo até atingir o mínimo local ... Em teoria, você pode dividir os nós para torná-lo exatamente zero ... No entanto, isso equivale a ajustar as coordenadas do ponto de reprodução!

Tente recozimento simulado para mover o ponto de desova dentro do nó. Embora, honestamente, provavelmente não valha a pena se preocupar com esse nível de detalhe.


Quero deixar claro que o resultado de um mapa plano livre de obstáculos não será distribuído de maneira uniforme. Em vez disso, se o mapa tiver arestas (ou seja, se não contornar), haverá mais pontos de desova mais próximos, porque os pontos no centro podem ser alcançados de mais direções, aumentando a chance de encontrar outros jogadores lá. Assim, pontos mais afastados perto do centro para compensar.

Theraot
fonte
6

Depende do tipo de jogo que você deseja criar e da velocidade do jogo. A distribuição perfeita e uniformemente espaçada é possível em uma esfera como o mundo (por exemplo, Aniquilação Planetária). Mas isso é uma opção justa no seu jogo? Mesmo que todas as pessoas estejam desovando em distâncias iguais, algumas desova ainda podem ter uma vantagem melhor.

  • Armas mais próximas / melhores ao alcance / mais recursos
  • Melhor cobertura / mais oculto / visão geral
  • o 'fluxo' dos jogadores, alguns lugares são mais atraentes do que outros (pense em um mapa florestal completo com uma única casa em um só lugar, independentemente de onde esteja, boas chances de que as pessoas estejam verificando)

O seu mapa é fixo ou gerado processualmente? E já tentou jogar Age of Empires com 8 pessoas em um mapa de 2 pessoas? Não é possível escalar infinitamente os jogadores sem fazer ajustes no tamanho do mapa. Até mesmo um posicionamento inicial injusto pode trazer muita dinâmica ao jogo (veja a série Worms). Ninguém reclamou se você gerou certo em um grande cluster, desde que sua aliança de uma rodada com outro jogador durasse ou você não tivesse os vermes mais sobreviventes após a primeira rodada.

(Vou adicionar mais alguns exemplos se souber mais sobre o seu tipo de jogo)

Zibelas
fonte
5

Buscando algo que não foi sugerido até agora: faça com que não haja centro do mapa. O que quero dizer com isso é que as bordas do mapa se juntam aos lados opostos. Isso exigiria muito trabalho de programação, mas, na prática, pode fazer com que o nível se repita infinitamente se você caminhar em uma direção. Isso significa que não há centro e uma posição aleatória de reprodução não terá vantagens ou desvantagens.

Você pode fazer isso criando um mapa plano quadrado e juntando cada aresta a uma cópia da aresta oposta. Quando um jogador sai do lado, ele é teleportado sem o conhecimento do jogador para a borda oposta. Obviamente, teoricamente você não seria capaz de ver jogadores do outro lado da fronteira. Para consertar isso, crie clones desse jogador que parecem andar do outro lado do limite para que você possa vê-los, e quando você corre em direção a eles, você se teletransporta e o jogador real fica onde o manequim estava.

Como alternativa, o mapa inteiro pode existir do lado de fora de uma esfera, no entanto, isso dificulta as coordenadas de desova.

Aric
fonte
2
Ou faça um mapa que, bem, no centro, você possa ser caçado ou caçar muito mais facilmente, e também possa encontrar saques mais fáceis, mas, novamente, é muito mais possível ser caçado assim, e em áreas não centrais, faça para que os jogadores tenham menos probabilidade de encontrar outros usuários e saques, por isso, se quiserem mais saques, terão que ir ao centro, se quiserem sobreviver por mais tempo, terão que ficar onde estão. Então, basicamente, faça da desvantagem de desova aleatória uma vantagem.
Ave
4

Aqui estão algumas soluções possíveis:

  • Gera aleatoriamente na circunferência do círculo
  • Cria aleatoriamente em raios (não gera para fechar o centro)
  • Adicionar um componente de tempo de reprodução aleatório

Diagrama dos mecanismos de desova

dnk drone.vs.drones
fonte
A segunda imagem é uma ótima opção. Ele resolve o problema da primeira opção em que o jogador sabe exatamente onde todos os outros jogadores estão localizados.
Zanon
@Zanon, embora os jogadores de primeira imagem possam (e provavelmente irão) se afastar antes que alguém chegue lá. O segundo causará desastres injustos, alguns próximos a outros. Talvez algo parecido com este, onde existem 2 círculos, e a diferença entre um menor e maior seja o local onde eles geram, assim como a segunda imagem, mas menos para o centro.
Ave
1

Fundamentalmente, acredito que este é um problema de distribuição de gráficos. Assumindo uma situação de deathmatch (todos os outros jogadores são inimigos), você precisa modelar seus mapas como um gráfico interconectado e acompanhar em qual nó do gráfico cada jogador está mais próximo. Nem todos os nós precisam ser um ponto de desova, mas você precisa do gráfico complexo para modelar as distâncias entre os pontos de desova. No momento da reprodução, você está iterando o gráfico e pontuando cada nó reproduzível com base no fato de os nós próximos terem jogadores.

O nó ideal possui:

  • Nenhum jogador atualmente nele
  • Mais de zero jogadores em nós próximos (um pequeno número de links de distância)

Imagine que seu gráfico tenha sido regularizado e você esteja desenhando zonas concêntricas em torno de cada nó. Você penaliza o nó se as zonas internas já tiverem jogadores e recompensa os nós que possuem jogadores à distância certa. Você deseja incentivar a desova perto o suficiente de outros jogadores para que eles possam encontrar interesse rapidamente, mas não tão perto que eles sejam atacados antes que eles tenham a chance de se orientar.

Você vai precisar de aumentar o tamanho do mapa como o número de jogadores aumenta, mas a knecessidade não ser 1 ou maior. Seu pior caso ainda é que todos os nós no gráfico tenham pelo menos um jogador - nesse caso, não há bons nós para usar, e você terá que sofrer esse caso e gerar um jogador sabendo que terra bem em cima de outro. O algoritmo de pontuação ainda deve ponderar os nós para que você apareça no nó com o menor número de outros jogadores.

Lembre-se de que o gráfico do seu mapa deverá ser cuidadosamente construído, com conhecimento do mapa, suas rotas, pontos de estrangulamento e distância efetiva entre os pontos dos nós, e não a distância real . Por exemplo, use algo como o tempo medido para percorrer os nós em vez da distância, para dar conta de terrenos mais difíceis. Além disso, você precisa considerar abertura versus cobertura; dois nós podem estar fisicamente separados, mas, por serem muito abertos, gerar um jogador em cada nó pode significar que eles são igualmente tão vulneráveis ​​quanto se você os tivesse gerado um ao lado do outro.

Refinamentos:

  • Adicione uma penalidade temporária para marcar se um jogador tiver gerado nesse nó recentemente, para impedir a formação de pontos de estrangulamento (um fluxo interminável de jogadores vindo da mesma direção e sendo eliminados)
  • Adicione aleatoriedade dentro de um intervalo (por exemplo, escolha os 3 melhores nós e escolha aleatoriamente entre eles com igual probabilidade) para obter mais variações.
  • Adicione um peso inicial ao centro do mapa (ou aos pontos mais interessantes) quando ninguém aparecer ainda, para que você apareça em locais conhecidos, mesmo quando cada nó tiver uma pontuação zero, porque nenhum outro jogador está presente.
MrCranky
fonte
0

Alguns outros já discutiram as limitações de seus requisitos (o mapa precisará ser escalonado em algum momento para evitar a superlotação, etc.) e acabaram escapando ao fato de que provavelmente não existe um algoritmo de posicionamento "perfeito". Quando provavelmente não existe um algoritmo "perfeito", eu sempre olho para as heurísticas. Você tem vários critérios que estão direta ou indiretamente em desacordo entre si, além de um espaço de pesquisa muito complicado. Encontrar uma solução ideal pode não ser viável ou prático, mas com um pouco de ajuste, uma abordagem estatística pode funcionar muito bem na maioria das vezes.

Abordando seu terceiro e quarto critérios: "O mapa não precisa ser expandido".

Eu garantiria que, no início, você tenha uma abundância excessiva de nós (ou seja, tão densa quanto uma malha de navegação para encontrar caminhos). Isso torna o cálculo da distância para outros jogadores mais caro (não os nós vizinhos diretamente), mas esse não é um processo que acontecerá mais de uma vez por rodada (presumo). Um bônus disso é que você pode usar uma biblioteca de navegação pré-configurada para a maioria de suas operações. Além disso, isso respeitará a travessia de obstáculos de uma maneira justa, onde a distância euclidiana não pode (jogadores em um labirinto podem ser colocados mais próximos do que em um campo aberto)

Calcule heurísticas para as características de desova desejadas:

Depois de colocar todos os jogadores aleatoriamente, calcule o desempenho dos nós ao redor com base em seus critérios (distância de outros jogadores, distância para gerar, etc.) Os pesos dos seus valores podem ser ajustados e manipulados para não serem lineares para ajustar exatamente o desempenho você deseja um caso ideal higienizado (grade retangular plana sem obstáculos), e o desempenho deve ser semelhante ao adicionar o mundo novamente. A partir daí, você pode decidir quantos nós procurar, qual é o limite para mover um ponto de partida , e quantas iterações você deseja executar antes de finalizar a reprodução e iniciar o jogo.

Aaron
fonte
0

Se o campo de jogo for um toro topológico (isto é, um retângulo onde sair “fora dos limites” significa entrar no lado oposto), é provável que seja uma boa resposta: o jogador japarece x = (pjW/N) mod W, y = (qjH/N) mod H, onde W,Hestão as dimensões do retângulo, Né o número de jogadores e p,qnúmeros inteiros a serem determinados; eles são distintos, (provavelmente) relativamente primos e não muito distantes sqrt(N). Os pontos de reprodução formam um padrão oblíquo de 'papel de parede'.

Isso supõe que os jogadores aparecem apenas no início do jogo. Se eles aparecerem mais tarde, acho que você gostaria de colocá-los o mais longe possível da posição atual de qualquer jogador - em um vértice do diagrama de Voronoi definido pelos outros jogadores.

Anton Sherwood
fonte
0

E se:

Cada jogador é cercado por uma caixa que não gera (ou círculo).

Por exemplo, há um quadrado de um certo tamanho que gera em torno de todos os jogadores e o segue - nenhum outro jogador pode aparecer dentro desse quadrado.

Esses quadrados afetam apenas a desova e não qualquer outro movimento durante o jogo.

Isso funciona tanto com a desova inicial quanto com a desova contínua.

(Pontos indicam jogadores e verde indica possível área de reprodução para novos jogadores)

O tamanho do mapa não precisa aumentar proporcionalmente ao número de jogadores

Para lidar com isso, você pode fazer uma de duas coisas: (ou ambas)

  • Diminua o tamanho das caixas que não geram, com base no número de jogadores.
  • Permita que até X jogadores inimigos desovem em cada caixa.
    • Esse número pode aumentar à medida que você avança (começando em 0).
    • Variante 1: tenha uma caixa menor de não desova e uma caixa maior de desova limitada.
    • Variante 2: probabilidades de peso de acordo com a proximidade da nova semente com este jogador (se dentro da caixa) - pode ser difícil de implementar com eficiência.
NotThatGuy
fonte