Rendre les points d'apparition aléatoires équitables?

Si tous les joueurs sont générés à des positions aléatoires à la même distance des joueurs adjacents, le nombre de joueurs sera proportionnel à la probabilité que leurs positions d'apparition soient injustes. Plus les joueurs apparaissent près du centre de la carte, plus ils sont susceptibles de rencontrer d'autres joueurs et moins ils ont de chances de survivre, par rapport aux joueurs sur le bord de la carte. Supposons que tous les joueurs sont générés en même temps.

Existe-t-il un moyen de façonner les points d'apparition ou de modifier la carte de sorte que:

1. Tous les joueurs ont un nombre limité d'ennemis adjacents.
2. Tous les joueurs ont des chances égales de rencontrer des ennemis adjacents.
3. La taille de la carte ne doit pas augmenter proportionnellement au nombre de joueurs.
4. Ces limitations ne sont pas appliquées avec des espaces impraticables arbitraires.

La réponse ne doit pas être parfaite, mais bien évidemment meilleure que l'alternative. Hors de la boîte en pensant bienvenue.

Laissez les joueurs choisir eux-mêmes leur emplacement de départ.

Au début de la partie, faites apparaître tous les joueurs au centre de la carte, mais sans aucun moyen de nuire aux autres joueurs. Ils devront ensuite pulluler et acquérir les moyens de s'engager mutuellement (construire une base, ramasser une arme, rassembler des ressources, etc.)

Il y a soit un peu de chance, soit une connaissance des cartes, pour trouver tôt un bon point de départ (selon que vous utilisez des cartes procédurales ou faites à la main). Mais quand et où s'installer, c'est surtout une décision stratégique. Un déploiement précoce vous donne un avantage de temps, mais vous met dans une position dangereuse. Choisir soigneusement votre base vous met en retrait en début de partie, mais peut être un avantage décisif en milieu et en fin de partie.

Comprendre les exigences

1. Tous les joueurs ont un nombre limité d'ennemis adjacents.

Tout d'abord, nous parlons des points d'apparition des joueurs, pas de la position actuelle des joueurs à un moment donné du jeu. Il suffit de retirer cela du chemin.

Adjacent est bien défini lorsque nous parlons d'un graphique. Nous pouvons penser à une carte qui représente la navigabilité sur la carte - désormais "le graphique".

Si un nœud peut avoir au plus un point d'apparition, alors parler d'eux comme «adjacents» a du sens. Remarque: Je ne contraindrai pas les nœuds à avoir un seul point d'apparition au plus, pour des raisons qui apparaîtront plus tard.

Pour construire le graphique, nous devrons prendre en compte des éléments tels que les murs, les ponts, les échelles, les points de téléportation, ou même envisager l'espace de vol s'il peut y avoir un joueur qui peut voler. Chaque nœud représente un emplacement traversable; chaque connexion représente un mouvement possible.

Remarque: connaître la taille et la forme des nœuds et travailler avec des nœuds réellement adjacents. Ne considérez pas les nœuds comme un point. Ne considérez pas les connexions comme ayant une longueur. Utilisez également des nœuds convexes.

Le graphique aurait pu être précompilé (la carte a été créée par un concepteur); sinon, il peut être créé à la volée si la carte est générée aléatoirement.

2. Tous les joueurs ont des chances égales de rencontrer des ennemis adjacents.

Je suppose que les ennemis sont d'autres joueurs. Encore une fois, il suffit de supprimer cela.

En supposant que chaque joueur fasse une marche aléatoire, la probabilité de trouver un joueur à un point donné - sur un espace plat, sans obstacles - sera donnée par une fonction (gaussienne) de la distance jusqu'au point d'apparition - à partir de maintenant "le une fonction".

Puisque nous travaillons sur le graphique, nous annoterons plutôt les valeurs sur le graphique.

3. La taille de la carte ne doit pas augmenter proportionnellement au nombre de joueurs.

Si nous avions la contrainte d'avoir un seul point d'apparition par nœud, alors pour ajouter plus de joueurs, nous aurions besoin de nœuds plus petits. Si nous décidons du graphique avant de savoir combien de joueurs nous aurons, nous devrons peut-être subdiviser les nœuds pour le jeu en particulier.

4. Ces limitations ne sont pas appliquées avec des espaces impraticables arbitraires.

Je n'ai pas l'intention d'ajouter des obstacles pour résoudre le problème. Au contraire , je dois travailler autour des obstacles. S'ils n'étaient pas là, la mise en œuvre serait plus simple.

Solution

Nous essayons de placer N points de réapparition de manière à ce que les chances de rencontrer un autre joueur à tous ces points de réapparition soient égales.

Nous pouvons obtenir une mesure de l'erreur comme la somme des différences entre les chances et la moyenne des chances. Nous essayons de minimiser cela (en fait, nous voulons le mettre à 0).

Pour ce faire, nous devons connaître les chances de rencontrer un joueur sur chaque nœud du graphique.

Pour calculer cette chance, commencez par zéro. Puisque la chance de trouver un joueur sur un nœud donné, quand il n'y a pas de joueurs, est nulle. Et puis, pour chaque point d'apparition, parcourez le graphique en ajoutant à la chance annotée la valeur de la fonction pour le point d'apparition actuel.

Remarque 1: L'ajout ou le déplacement d'un point d'apparition affectera les chances de rencontrer un joueur pour toute la carte.

Remarque 2: Garder une trace de la façon dont chaque point d'apparition affecte la chance rendra les choses plus faciles.

Remarque 3: Étant donné que les nœuds ont une taille, la proximité de l'erreur = zéro dépend de la taille des nœuds. Vous pouvez être plus précis en travaillant avec des plages de valeurs (chances minimun et maximun, selon la position particulière des points d'apparition dans le nœud).

Placez les points d'apparition au hasard, puis commencez à les déplacer de telle sorte que l'erreur devienne plus petite (envisagez un mouvement possible, et si l'erreur diminue, conservez-le, sinon inversez-le). Et continuez ainsi jusqu'à ce que nous ne puissions pas nous améliorer davantage (trop d'itérations sans amélioration, ou l'erreur est nulle).

Remarque 4: Lorsque vous déplacez un point d'apparition, vous pouvez utiliser la chance de rencontrer un joueur (à l'exclusion du point d'apparition que vous allez déplacer) pour sélectionner au hasard une nouvelle position pour un point d'apparition telle que cette position qui a une chance de rencontrer un joueur plus proche de la moyenne est plus probable. Je vous rappelle que déplacer le point d'apparition affectera la moyenne.

Le comportement attendu est que les points d'apparition qui sont trop rapprochés se séparent et que les points d'apparition trop éloignés se rapprochent. Jusqu'à ce qu'ils atteignent l'équilibre.

Si à une itération donnée vous avez plusieurs points d'apparition sur un nœud (ce qui est peu probable, car ils devraient avoir tendance à s'écarter, mais possible si vous avez des nœuds suffisamment grands), divisez le nœud et continuez à résoudre. Toute division du nœud est valide.

La solution ci-dessus approchera error = zero, mais ne garantit pas d'atteindre zéro. Vous pouvez le faire jusqu'à ce qu'il atteigne un minimum local ... En théorie, vous pouvez ensuite diviser les nœuds pour le rendre exactement nul ... Pourtant, cela équivaut à modifier les coordonnées du point d'apparition!

Essayez un recuit simulé pour déplacer le point d'apparition dans le nœud. Bien que, honnêtement, cela ne vaut probablement pas la peine de s'embêter avec un tel niveau de détail.

Je tiens à préciser que le résultat d'une carte plane sans obstacles ne sera pas des points uniformément répartis. Au lieu de cela, si la carte a des bords (c'est-à-dire si elle ne s'enroule pas), alors il y aura plus de points d'apparition plus près des bords, c'est parce que les points au centre peuvent être atteints depuis plus de directions, augmentant les chances de rencontrer d'autres joueurs là-bas. Ainsi, les points plus éloignés près du centre pour compenser.

Cela dépend du type de jeu que vous souhaitez créer et de sa rapidité. La parfaite distribution également espacée est possible sur une sphère comme le monde (par exemple l'annihilation planétaire). Mais est-ce une option équitable dans votre jeu? Même si toutes les personnes frayent à égale distance, certaines frayes peuvent toujours avoir un meilleur avantage.

• Des armes plus proches / meilleures à portée / plus de ressources
• Meilleure couverture / plus caché / aperçu
• le `` flux '' des joueurs, certains endroits sont plus attrayants que d'autres (pensez à une carte forestière complète avec une seule maison à un endroit, peu importe où cette maison est, bonne chance que les gens la vérifient)

Votre carte est-elle fixe ou générée par la procédure? Et avez-vous déjà essayé de jouer à Age of Empires avec 8 personnes sur une carte à 2? Il n'est pas possible de mettre à l'échelle les joueurs à l'infini sans ajuster la taille de la carte. Même un placement de départ injuste peut apporter beaucoup de dynamique dans le jeu (voir la série Worms). Personne ne se plaignait si vous apparaissiez dans une grande grappe, tant que votre alliance avec un autre joueur durait ou si vous n'aviez pas les vers les plus survivants après le premier tour.

(J'ajouterai quelques exemples supplémentaires si j'en sais plus sur votre type de jeu)

Aller jusqu'à quelque chose qui n'a pas été suggéré jusqu'à présent: faites en sorte qu'il n'y ait pas de centre sur la carte. Ce que je veux dire par là, c'est que les bords de la carte se rejoignent sur les côtés opposés. Cela prendrait beaucoup de travail de programmation, mais dans la pratique, cela peut faire en sorte que le niveau se répète à l'infini si vous marchez dans une direction. Cela signifie qu'il n'y a pas de centre et qu'une position d'apparition aléatoire n'aura aucun avantage ou inconvénient.

Vous pouvez le faire en créant une carte plate carrée et en joignant chaque bord à une copie du bord opposé. Lorsqu'un joueur quitte le côté, il est téléporté à son insu sur le bord opposé. Bien sûr, théoriquement, vous ne pourriez pas voir les joueurs de l'autre côté de la frontière. Pour résoudre ce problème, créez des clones de ce joueur qui semblent se promener de l'autre côté de la frontière afin que vous puissiez les voir, et lorsque vous courez vers eux, vous vous téléportez et le joueur réel se tient là où se trouvait le mannequin.

Alternativement, la carte entière pourrait exister à l'extérieur d'une sphère, mais cela rend les coordonnées difficiles pour le frai.

Voici quelques solutions possibles:

• Apparition aléatoire sur la circonférence du cercle
• Apparition aléatoire sur les rayons (pas d'apparition pour fermer le centre)
• Ajouter un composant de temps d'apparition aléatoire

Fondamentalement, je pense que c'est un problème de distribution des graphes. En supposant une situation de match à mort (chaque autre joueur est un ennemi), vous devez modéliser vos cartes comme un graphique interconnecté et suivre le nœud du graphique le plus proche de chaque joueur. Tous les nœuds n'ont pas besoin d'être un point d'apparition, mais vous avez besoin du graphique complexe pour modéliser les distances entre les points d'apparition. Au moment de la réapparition, vous parcourez ensuite le graphique et marquez chaque nœud pouvant se reproduire selon que les nœuds à proximité ont des joueurs.

Le nœud idéal a alors:

• Aucun joueur actuellement dedans
• Plus de zéro joueur dans les nœuds à proximité (un petit nombre de liens à l'extérieur)

Imaginez que votre graphique a été régularisé et que vous dessinez des zones concentriques autour de chaque nœud. Vous pénalisez le nœud si les zones intérieures contiennent déjà des joueurs et récompensez les nœuds qui ont des joueurs à la bonne distance. Vous voulez encourager le frai assez près des autres joueurs pour qu'ils trouvent rapidement de l'intérêt, mais pas si près qu'ils se lancent avant d'avoir eu la chance de se repérer.

Vous aurez besoin d'augmenter la taille de la carte que le nombre de joueurs augmente, mais la knécessité de ne pas être 1 ou plus. Votre pire cas sera toujours que chaque nœud sur le graphique a au moins un joueur - auquel cas il n'y a pas de bons nœuds à utiliser, et vous devrez subir ce cas et engendrer un joueur sachant qu'il le fera atterrir juste au-dessus d'un autre. L'algorithme de score devrait toujours pondérer les nœuds afin que vous apparaissiez dans le nœud avec le moins d'autres joueurs.

Gardez à l'esprit que votre graphique de carte devra être soigneusement construit, en connaissant la carte, ses itinéraires, tous les points d' étranglement et la distance effective entre les points de noeud, et non la distance réelle . Comme dans, utilisez quelque chose comme le temps mesuré pour traverser les nœuds plutôt que la distance, pour prendre en compte les terrains plus difficiles. Vous devez également tenir compte de l'ouverture par rapport à la couverture; deux nœuds peuvent être physiquement éloignés l'un de l'autre, mais comme ils sont très ouverts, la génération d'un joueur à chaque nœud peut signifier qu'ils sont tout aussi vulnérables que si vous les aviez générés l'un à côté de l'autre.

Améliorations:

• Ajoutez une pénalité temporaire pour marquer si un joueur est apparu récemment dans ce noeud, pour empêcher les chokepoints de se former (un flux sans fin de joueurs venant de la même direction et se faisant prendre)
• Ajoutez un caractère aléatoire dans une plage (par exemple, choisissez les 3 meilleurs nœuds puis choisissez au hasard entre eux avec une probabilité égale) pour obtenir plus de variation.
• Ajoutez un poids initial au centre de la carte (ou les points les plus intéressants) lorsque personne n'a encore engendré, de sorte que vous apparaissez dans des endroits connus, même lorsque chaque nœud a un score de zéro car aucun autre joueur n'est présent.

Quelques autres ont déjà discuté des limites de vos exigences (la carte devra évoluer à un moment donné pour éviter le surpeuplement, etc.) et ont finalement éludé le fait qu'il n'y a probablement pas d'algorithme de placement "parfait". Lorsqu'il n'y a probablement pas d'algorithme "parfait", je regarde toujours vers l'heuristique. Vous avez plusieurs critères qui sont directement ou indirectement en désaccord les uns avec les autres, ainsi qu'un espace de recherche très compliqué. Trouver une solution optimale peut ne pas être faisable ou pratique, mais avec un peu de réglage, une approche statistique peut très bien fonctionner la majorité du temps.

Répondre à vos troisième et quatrième critères: "La carte ne devrait pas avoir à s'étendre."

Je m'assurerais au début que vous avez une surabondance de nœuds (c'est-à-dire: aussi dense qu'un maillage de navigation pour trouver un chemin). Cela rend le calcul de la distance aux autres joueurs plus cher (pas les nœuds directement voisins), mais ce n'est pas un processus qui se produira plus d'une fois par tour (je suppose). Un bonus de ceci est que vous pouvez utiliser une bibliothèque de navigation pré-roulée pour la plupart de vos opérations. De plus, cela respectera la traversée des obstacles d'une manière équitable où la distance euclidienne ne peut pas (les joueurs dans un labyrinthe peuvent être placés plus près les uns des autres que dans un champ ouvert)

Calculez l'heuristique pour les caractéristiques d'apparition souhaitées:

Après avoir placé tous les joueurs au hasard, calculez les performances des nœuds environnants en fonction de vos critères (distance par rapport aux autres joueurs, distance jusqu'au point d'apparition, etc.) Les poids de vos valeurs peuvent être modifiés et manipulés pour être non linéaires afin de régler exactement les performances vous voulez dans un cas idéal aseptisé (grille rectangulaire plate sans obstacles), et les performances devraient être similaires lorsque vous ajoutez le monde. De là, vous pouvez décider du nombre de nœuds à rechercher, quel est le seuil pour déplacer un point de départ et le nombre d'itérations que vous souhaitez effectuer avant de finaliser le spawn et de commencer la partie.

Si le terrain de jeu est un tore topologique (c'est-à-dire un rectangle où sortir «hors des limites» signifie entrer du côté opposé), cela est probablement une bonne réponse: le joueur japparaît x = (pjW/N) mod W, y = (qjH/N) mod H, où W,Hsont les dimensions du rectangle, Nest le nombre de joueurs, et p,qsont des nombres entiers à déterminer; ils sont distincts, (probablement) relativement premiers, et pas trop loin desqrt(N) . Les points d'apparition forment un motif de «papier peint» oblique.

Cela suppose que les joueurs n'apparaissent qu'au début de la partie. S'ils apparaissent plus tard, je suppose que vous voudriez les placer aussi loin que possible de la position actuelle de n'importe quel joueur - au sommet du diagramme de Voronoi défini par les autres joueurs.

Que diriez-vous:

Chaque joueur est entouré d'une boîte (ou cercle) non reproductrice .

Comme dans, il y a un carré d'une certaine taille qui apparaît autour de chaque joueur et suit ce joueur - aucun autre joueur ne peut apparaître dans cette case.

Ces cases n'affectent que le frai et pas tout autre mouvement pendant la partie.

Cela fonctionne avec le frai initial uniquement ou le frai continu.

(Les points indiquent les joueurs et le vert indique la zone d'apparition possible pour les nouveaux joueurs)

La taille de la carte ne doit pas augmenter proportionnellement au nombre de joueurs

Pour y faire face, vous pouvez faire l'une des deux choses suivantes: (ou les deux)

• Diminuez la taille des boîtes qui ne se reproduisent pas en fonction du nombre de joueurs.
• Autorisez jusqu'à X joueurs ennemis à apparaître dans chaque case.
  • Ce nombre peut augmenter au fur et à mesure (à partir de 0).
  • Variante 1: avoir une plus petite boîte sans réapparition et une plus grande boîte à réapparition limitée.
  • Variante 2: les probabilités de poids selon la proximité du nouveau spawn avec ce joueur (si à l'intérieur de la boîte) - peuvent être difficiles à mettre en œuvre efficacement.