Fazer pontos de geração aleatórios justos?

inappropriateCode 09/12/2017. 9 answers, 4.496 views
game-design level-design

Se todos os jogadores forem gerados em posições aleatórias à mesma distância de jogadores adjacentes, o número de jogadores será proporcional à probabilidade de suas posições de geração serem injustas. Os jogadores mais próximos geram para o centro do mapa, mais provável que eles encontrem outros jogadores e menos chances de sobreviver, em comparação com jogadores na borda do mapa. Suponha que todos os jogadores sejam gerados ao mesmo tempo.

Existe uma maneira de moldar pontos de geração, ou alterar o mapa, para que:

  1. Todos os jogadores têm um número limitado de inimigos adjacentes.
  2. Todos os jogadores têm a mesma chance 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 aplicadas com espaços infranqueáveis ​​arbitrários.

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

5 Comments
10 Zibelas 07/28/2017
Spawn em um círculo?
1 inappropriateCode 07/28/2017
@Zibelas abordagem tradicional, mas viola o requisito 3, e com muitos jogadores isso cria um mapa enorme e um interior vazio.
4 Zibelas 07/28/2017
Depende do seu tipo de jogo. (2D / 3D, respawn / last man standing, etc.) O spawn perfeito é nesse caso apenas possível em um mundo de forma de bola (mais jogador, spawn mais próximo, mas você pode garantir que eles têm a mesma distância). Em um mundo 2D com fronteiras fixas, você sempre tem menos jogadores limítrofes, já que você não tem lugar para gerá-los. Se é um jogo em 3D, você pode ter várias camadas.
1 RothX 07/28/2017
Eu acho que ajudaria a saber que tipo de jogo você está fazendo. Parece um tipo de jogo de guerra, mas quais são os detalhes? É um atirador? Você começa com todas as suas armas, ou você tem que explorar e encontrar coisas? Qual é a condição de vitória? Por quanto tempo dura uma partida?
3 Jan 'splite' K. 07/28/2017
Não para uma resposta completa, mas acho que todos estão tentando por "spawn justo e equilibrado" que ... não é divertido. Olhe para a excelente criação de PUBG (e outros Battle Royale): os jogadores podem "gerar" (bem, pular e aterrar ...) quase em qualquer lugar que desejam - se você quer conflitos e drama, você escolhe o lugar onde a maioria dos jogadores pousa / spawn. Hight arrisca alta recompensa, mas apenas se o jogador quiser. Você pode pousar em algum lugar na floresta, você tem tempo para se preparar - baixa recompensa de baixo risco, mas alguns jogadores podem preferir (como eu, por exemplo);). Não é aleatório, é pela escolha dos jogadores.

9 Answers


Philipp 07/28/2017.

Deixe os jogadores escolherem seus próprios locais de partida.

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

Há um pouco de sorte ou conhecimento do mapa envolvido na busca de uma boa localização inicial antecipada (dependendo se você usa mapas processuais ou artesanais). Mas quando e onde se estabelecer é principalmente uma decisão estratégica. A implantação precoce dá-lhe uma vantagem de tempo, mas coloca você em uma posição perigosa. Escolher sua base com cuidado coloca você atrasado no início do jogo, mas pode ser uma vantagem decisiva no meio e no final do jogo.

5 comments
14 Shashimee 07/28/2017
+1 para usar o sistema de criação de filmes Hunger Games 1.
3 Philipp 07/28/2017
@Shashimee Na verdade, eu acredito ter visto esse método primeiro no Anno 1602. Eu também acredito que alguns dos primeiros jogos do C & C tiveram isso como uma opção de jogo multijogador opcional (mas não tenho certeza se eu lembro disso corretamente).
3 Zibelas 07/28/2017
@Philipp MULE para o comodoro 64 por volta de 15 anos e deixa você escolher também suas posições :)
Dent7777 07/28/2017
Você então aborda o problema onde você é seguido para o seu ponto de geração. Isso poderia, é claro, ser o mecânico do jogo desejado, mas também poderia ser extremamente frustrante e não algo que você decidir que deseja no seu jogo. Uma boa idéia seria ter os personagens invisíveis e livres de colisões para jogadores, e encontrar sua base antes de começar o jogo.
Kroltan 07/28/2017
Esse é o método usado pela linha "Vampirismo" e "Árvore Tag" de gamemodes personalizados no Warcraft 3. Ele funciona melhor, pois todos os jogadores estão aliados (pelo menos inicialmente) e a equipe adversária é lançada mais tarde.

Theraot 07/28/2017.

Compreender os requisitos

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

Em primeiro lugar, estamos falando dos pontos de geração dos jogadores, e não da posição atual dos jogadores em um determinado ponto do jogo. Just getting that out of the way.

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

Se o nó pode ter no máximo um ponto de geração, então, falar de eles sendo "adjacentes" faz sentido. Nota: Eu não impedirei os nós de ter um único ponto de geração ao máximo, por razões que serão aparentes mais tarde.

Para construir o gráfico, precisamos considerar coisas como paredes, pontes, escadas, pontos de teletransporte, ou mesmo considerar o espaço do vôo, se houver um jogador que possa voar. Cada nó representa uma localização perceptível; cada conexão representa um possível movimento.

Nota: conheça o tamanho e a forma dos nós e trabalhe com nós realmente adjacentes. Não considere os nós como um ponto. Não considere conexões como tendo o 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 pode ser criado on-line se o mapa for gerado aleatoriamente.

  1. Todos os jogadores têm a mesma chance de encontrar inimigos adjacentes.

Eu assumirei que os inimigos são outros jogadores. Again, just getting that out of the way.

Supondo que cada jogador faça uma caminhada aleatória, 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 ao ponto de geração - a partir de agora função".

Uma vez que estamos trabalhando no gráfico, anotaremos 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 geração por nó, então, para adicionar mais jogadores, precisaríamos de nós menores. Se decidimos o gráfico antes de sabermos quantos jogadores teremos, talvez possamos subdividir nós para o jogo em particular.

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

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


Solução

Estamos tentando colocar N pontos de geração de modo que a chance de encontrar outro jogador em todos esses pontos de geração é igual.

Podemos obter uma medida do erro como a soma das diferenças das chances para a média das chances. Estamos tentando minimizar isso (na verdade, queremos fazê-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. Uma vez que a chance de encontrar um jogador em qualquer nó dado, quando não há jogadores, é zero. E então, para cada ponto de geração, passe o gráfico adicionando à chance anotada o valor da função para o ponto de geração atual.

Nota 1: Adicionar ou mover um ponto de geração afetará a chance de encontrar um jogador para todo o mapa.

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

Nota 3: Uma vez que os nós têm tamanho, o quão próximo você pode chegar ao erro = zero depende do tamanho dos nós. Você pode ser mais preciso trabalhando com intervalos de valores (mínimo e chance máxima, dependendo da posição particular dos pontos de geração no nó).

Coloque os pontos de geração ao acaso e, em seguida, comece a movê-los de tal forma que o erro se torne menor (considere um possível movimento e, se o erro for diminuído, mantenha-o, caso contrário, reverte-o). E continuar a fazê-lo até que não possamos melhorar ainda mais (muitas iterações sem melhoria, ou o erro é zero).

Nota 4: Ao mover um ponto de geração, você pode usar a chance de encontrar um jogador (excluindo o ponto de geração que você se moverá) para selecionar aleatoriamente uma nova posição para um ponto de geração, tal que tenha a chance de encontrar um jogador mais perto de A média é mais provável. Lembro-lhe que mover o ponto de desova afectará a média.

O comportamento esperado é que o ponto de geração que está muito próximo juntos se separe e os pontos de geração que estão muito distantes se aproximam. Até chegarem ao equilíbrio.

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


A solução acima irá aproximar erro = zero, mas não garantido para chegar a zero. Você pode fazer é executá-lo até atingir um mínimo local ... Em teoria, você pode então dividir os nós para torná-lo exatamente zero ... No entanto, isso equivale a ajustar as coordenadas do ponto de geração!

Experimente o recozimento simulado para mover o ponto de geração no nó. Embora, honestamente, provavelmente não vale a pena incomodar com esse nível de detalhe.


Quero deixar claro que o resultado para um mapa plano sem obstáculos não será pontos uniformemente distribuídos. Em vez disso, se o mapa tiver arestas (ou seja, se não se envolver), haverá mais ponto de geração próximo das bordas, porque os pontos no centro podem ser alcançados por mais direções, aumentando a chance de encontrar outros jogadores lá. Assim, pontos mais distantes perto do centro para compensar.


Zibelas 07/28/2017.

Depende do tipo de jogo que você deseja criar e da rapidez com que seja. A distribuição perfeita uniformemente espaçada é possível em uma esfera como o mundo (por exemplo, Annihilation Planetary). Mas isso é uma opção justa no seu jogo? Mesmo que todas as pessoas estejam gerando distância igual, alguns engenhos ainda podem ter uma melhor vantagem.

  • Mais perto / melhores armas em alcance / mais recursos
  • Melhor cobertura / mais escondido / 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 daquela casa, boa chance de que as pessoas verifiquem)

O seu mapa é fixo ou um processo gerado? E já tentou jogar Age of Empires com 8 pessoas em um mapa de 2 pessoas? Não é possível escalar os jogadores infinitamente sem fazer ajustes no tamanho do mapa. Mesmo uma colocação de início injusta pode trazer muita dinâmica no jogo (veja a série Worms). Ninguém se queixou se você gerou direito em um grande cluster, enquanto sua aliança de uma rodada com outro jogador durou ou você não tinha os vermes mais sobreviventes após a primeira rodada.

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


Aric Fowler 07/28/2017.

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

Você pode fazer isso fazendo um mapa plano que é quadrado e juntando cada uma das bordas a uma cópia da borda oposta. Quando um jogador sai do lado, eles são teletransportados sem o conhecimento do jogador para a borda oposta. Claro, teoricamente, você não poderá ver os jogadores do outro lado do limite. Para consertar isso, crie clones desse jogador que parecem caminhar do outro lado do limite para que você possa vê-los, e quando você corre em direção a eles, você se desloca e o jogador atual está parado onde estava o manequim.

Alternativamente, o mapa inteiro poderia existir no exterior de uma esfera, no entanto, isso dificulta as coordenadas para a reprodução.

1 comments
2 Avery 07/29/2017
Ou faça um mapa que, bem, no centro, você possa ser caçado ou caçar muito mais fácil, e também pode encontrar o buraco mais fácil, mas, novamente, você é muito mais possível se caçar assim e, em áreas não centrais, fazer para que os jogadores tenham menos chances de encontrar outros usuários e saquear, então, se quiserem mais pilhagens, eles terão que ir ao centro, se quiserem sobreviver por mais tempo, eles terão que ficar onde estão. Então, basicamente, a desvantagem de gerar aleatórias é uma vantagem.

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

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

  • Spawn aleatoriamente na circunferência do círculo
  • Spawn aleatoriamente em raios (não gerando para fechar o centro)
  • Adicione um componente de tempo de geração aleatória

Diagrama de mecanismos de desova

2 comments
Zanon 07/28/2017
A segunda imagem é uma ótima opção. Resolve o problema da primeira opção onde o jogador sabe exatamente onde todos os outros jogadores estão localizados.
Avery 07/29/2017
@Zanon, porém, com a primeira imagem, os jogadores podem (e provavelmente) se afastarão antes que alguém venha lá. O segundo causará geramentos injustos, alguns próximos dos outros. Talvez algo parecido com isso, existem dois círculos e a diferença entre o menor e o maior é o lugar onde eles geram, assim como a segunda imagem, mas menos para o centro.

MrCranky 07/28/2017.

Fundamentalmente, acredito que este é um problema de distribuição de gráficos. Assumindo uma situação deathmatch (qualquer outro jogador é um inimigo), você precisa modelar seus mapas como um gráfico interconectado e acompanhar qual o nó no gráfico que cada jogador está mais próximo. Nem todo nó precisa ser um ponto de geração, mas você precisa do gráfico complexo para modelar distâncias entre os pontos de geração. No tempo de geração, você está então iterando o gráfico e marcando cada nó spawnable com base em se os nós próximos tiveram jogadores.

O nó ideal então tem:

  • Nenhum jogador atualmente nele
  • Mais de zero jogadores em nós próximos (alguns pequenos números de links)

Imagine que seu gráfico foi regularizado e você está desenhando zonas concêntricas ao redor de cada nó. Você penaliza o nó se as zonas internas já tiverem jogadores neles e recompensar os nós que têm jogadores à distância certa. Você deseja encorajar o nascimento próximo ao suficiente para outros jogadores, que eles possam encontrar interesse rapidamente, mas não tão perto de que eles tenham pulado antes de terem tido a chance de se identificar.

Você precisará aumentar o tamanho do mapa à medida que o número de jogadores crescer, mas o k não precisa ser igual ou superior a 1. O seu pior caso ainda será que cada nó no gráfico tem 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 eles vão pousar bem em cima de outro. O algoritmo de pontuação ainda deve pesar os nós para que você gera no nó com o menor número de outros jogadores.

Tenha em mente que seu gráfico de mapas terá que ser cuidadosamente construído, com conhecimento do mapa, suas rotas, pontos de choque e distância effective entre os pontos do nó, e não actual distância actual . Como em, use algo como o tempo medido para percorrer os nós em vez da distância, para explicar o terreno mais difícil. Além disso, você precisa dar conta de open-ness vs cover; dois nós podem estar fisicamente distantes, mas porque eles estão muito abertos, gerar um jogador em cada nó pode significar que eles são igualmente vulneráveis ​​como se você os tivesse gerado um ao lado do outro.

Refinamentos:

  • Adicione uma penalidade temporária para marcar se um jogador gerou nesse nó recentemente, para impedir que os chokepoints se formem (um fluxo interminável de jogadores que vêm da mesma direção e são retirados)
  • Adicione aleatoriedade dentro de um intervalo (por exemplo, escolha os melhores 3 nós e, em seguida, escolha aleatoriamente entre eles com a mesma probabilidade) para obter mais variação.
  • Adicione um peso inicial ao centro do mapa (ou os pontos mais interessantes) quando ninguém ainda gerou, de modo que você gera em lugares conhecidos, mesmo quando cada nó possui uma pontuação de zero porque nenhum outro jogador está presente.

Aaron 07/28/2017.

Alguns outros já discutiram as limitações de seus requisitos (o mapa precisará escalar em algum momento para evitar o superlotação, etc.) e, em última instância, eludiu o fato de que provavelmente não existe um algoritmo de posicionamento "perfeito". Quando provavelmente não há algoritmo "perfeito", sempre olho para heurísticas. Você tem vários critérios que estão direta ou indiretamente em desacordo com o outro, além de um espaço de busca muito complicado. Encontrar uma solução ótima pode não ser viável ou prático, mas com um pouco de ajuste, uma abordagem estatística pode ser muito boa na maioria das vezes.

Dirigindo seu terceiro e quarto critérios: "The map shouldn't have to expand."

Certifiquei-me de que, no início, você tenha uma abundância excessiva de nós (ou seja: tão denso quanto uma malha de navegação para busca de caminho). Isso torna o cálculo da distância para outros jogadores mais caro (não diretamente nos nós vizinhos), mas este não é um processo que acontecerá mais de uma vez por rodada (eu suponho). Um bônus disso é que você pode usar uma biblioteca de navegação pré-rolada para a maioria de suas operações. Além disso, isso irá respeitar o percurso em torno de obstáculos de forma justa, onde a distância euclidiana não pode (os jogadores em um labirinto podem ser colocados mais próximos do que em um campo aberto)

Calcule as heurísticas para as características de geração desejadas:

Depois de colocar aleatoriamente todos os jogadores, calcule o desempenho dos nós circundantes com base em seus critérios (distância dos outros jogadores, distância para spawn, etc.) Os pesos de seus valores podem ser ajustados e manipulados para serem não-lineares para sintonizar exatamente o desempenho você quer em um caso ideal higienizado (grade retangular plana sem obstáculos) e o desempenho deve ser semelhante quando você adiciona o mundo de volta. A partir daí, você pode decidir quantos nós procurar, qual o limiar para mover um ponto de partida , e quantas iterações você deseja executar antes de finalizar o spawn e começar o jogo.


Anton Sherwood 07/29/2017.

Se o campo de jogo é um toro topológico (ou seja, um retângulo onde "fora dos limites" significa entrar no lado oposto), isso provavelmente será uma boa resposta: o jogador j gera em x = (pjW/N) mod W, y = (qjH/N) mod H , onde W,H são as dimensões do retângulo, N é o número de jogadores, e p,q são números inteiros a serem determinados; eles são distintos, (provavelmente) relativamente primos, e não muito longe de sqrt(N) . Os pontos de geração formam um padrão de papel de parede oblíquo.

Isso é supondo que os jogadores só geram no início do jogo. Se eles gerarem 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 Voronoi definido pelos outros jogadores.


NotThatGuy 07/31/2017.

E se:

Cada jogador está rodeado por uma caixa não-desovadora (ou círculo).

Como em, há um quadrado de um certo tamanho que gera em torno de cada jogador e segue esse jogador ao redor - nenhum outro jogador pode gerar dentro desse quadrado.

Esses quadrados só afetam a desova e nenhum outro movimento durante o jogo.

Isso funciona com germinação única ou reprodução contínua.

(Pontos indicam jogadores e verde indica possível área de geraçã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 das duas coisas: (ou ambas)

  • Diminua o tamanho das caixas não geradoras com base no número de jogadores.
  • Permita que até X jogadores inimigos se multipliquem em cada caixa.
    • Esse número pode aumentar a medida que você for (a partir de 0).
    • Variante 1: tenha uma caixa menor sem germinação e uma caixa de germinação limitada maior.
    • Variante 2: probabilidades de peso de acordo com a proximidade da nova geração com este jogador (se dentro da caixa) - pode ser difícil de implementar de forma eficiente.

Related questions

Hot questions

Language

Popular Tags