J'ai une grille rectangulaire de taille variable, mais la moyenne de 500x500 avec un petit nombre de points X, y de l'intérieur (moins de 5). J'ai besoin de trouver un algorithme qui renvoie une paire X, y est la plus éloignée possible de l'un des autres points.
Contexte: Écran de l'application (grille) et un ensemble de x, points y (ennemis). Le joueur meurt et j'ai besoin d'un algorithme qui les répare aussi loin des ennemis de sorte qu'ils ne meurent pas immédiatement après la remontée.
ce que j'ai jusqu'à présent: L'algorithme que j'ai écrit des œuvres mais n'effectue pas ce grand nombre de téléphones plus lents. Je divisons essentiellement la grille en carrés (beaucoup comme un tac Tic Toe) et j'identifie chaque carré un numéro. Je vérifie ensuite chaque carré sur tous les ennemis et stockez ce que l'ennemi le plus proche était sur chaque carré. La place avec le plus grand nombre est la place qui a l'ennemi le plus proche le plus éloigné. J'ai également essayé de faire la moyenne des points existants et de faire quelque chose de similaire à cela et que la performance était acceptable, la fiabilité de la méthode n'était pas.
6 Réponses :
Ceci est similaire à ce que vous faites déjà, mais avec deux passes où le premier passage peut être assez brut. Première résolution de diminution. Divisez la grille 500x500 en grilles 10x10 chacune d'une valeur de 50x50. Pour chacun des 100 sous-diagrils résultants - Déterminez au moins un ennemi et localisez le sous-variété qui est le plus éloigné d'un sous-varigré qui contient un ennemi. À ce stade, il n'y a que 100 sous-diagrils à craindre. Une fois que vous avez trouvé le sous-gridé le plus éloigné d'une résolution d'augmentation de l'ennemi. Ce sous-gridé a 50x50 = 2500 carrés. Faites votre approche originale avec ces carrés. Le résultat est 50x50 + 100 = 2600 carrés à traiter plutôt que 500x500 = 250 000. (Ajustez les chiffres selon que nécessaire pour le cas dans lequel il n'y a pas 500x500 mais avec la même stratégie de base).
Voici une implémentation Python3. Il utilise deux fonctions:
1) 2) une exécution typique: (J'ai vérifié en utilisant le Full Travrett sur la grille globale que (271 499) est en fait optimale pour ces ennemis) Full Travrether (A, B, N, ENNEMIES) Cette fonction prend un ensemble d'ennemis, un coin de coin (A, B) et un int, n et trouve le point dans le carré NXN des positions dont le coin supérieur gauche est (A, B) et trouve le point de ce carré dont lequel a la Min-distance maximale à un ennemi. Les ennemis ne sont pas supposés être dans cette grille NXN (bien qu'ils puissent certainement être) FindSafoint (n, ennemis, maillage = 20) Cette fonction prend un ensemble de Les ennemis qui sont supposés être dans la grille NXN à partir de (0,0). mesh détermine la taille des sous-diagrids, défaut de 20. La grille globale est divisée en maillage x maillage Subgrids (ou légèrement plus petit le long des limites Si maille ne divise pas n ) que je pense comme territoires. J'appelle un territoire un territoire ennemi s'il a un ennemi dedans. Je crée l'ensemble des territoires ennemis et transmettez-le à FULLRESSEARCH avec le paramètre N divisé par maillage plutôt que n . La valeur de retour me donne le territoire qui est le plus éloigné de tout territoire ennemi. Un tel territoire peut être considéré comme assez sûr. Je recette ce territoire dans Full TravRearch pour trouver le point le plus sûr de ce territoire en tant que fonction de retour globale. Le point qui en résulte est optimal ou presque optimal et est calculé très rapidement. Voici le code (associé à une fonction ):
Voici une solution intéressante, mais je ne peux pas tester son efficacité. Pour chaque ennemi, effectuez une ligne de chiffres de chaque numéro, en commençant par une et augmentant par un pour chaque augmentation de la distance. Quatre lignes initiales proviendront des quatre bords et chaque fois que vous allez également une autre ligne, vous créez une autre ligne qui sort à un angle de 90 degrés, augmentant également le nombre de changement de distance. Si la ligne de numéro rencontre un numéro déjà créé qui est inférieur à celui-ci, il ne l'écrasera pas et cessera d'atteindre plus loin. Essentiellement, cela le rend afin que si les lignes trouvent un nombre inférieur à celui-ci, il ne vérifiera aucune autre marque de grille, éliminant la nécessité de vérifier la grille entière de tous les ennemis.
<<<<<<^^^^^^^
<<<<<<^^^^^^^
<<<<<<X>>>>>>
vvvvvvv>>>>>>
vvvvvvv>>>>>>
public void map(int posX, int posY)
{
//left up right down
makeLine(posX, posY, -1, 0, 0, -1);
makeLine(posX, posY, 0, 1, -1, 0);
makeLine(posX, posY, 1, 0, 0, 1);
makeLine(posX, posY, 0, -1, 1, 0);
grid[posX][posY] = 1000;
}
public void makeLine(int posX, int posY, int dirX, int dirY, int dir2X, int dir2Y)
{
int currentVal = 1;
posX += dirX;
posY += dirY;
while (0 <= posX && posX < maxX && posY < maxY && posY >= 0 && currentVal < grid[posX][posY])
{
int secondaryPosX = posX + dir2X;
int secondaryPosY = posY + dir2Y;
int secondaryVal = currentVal + 1;
makeSecondaryLine( secondaryPosX, secondaryPosY, dir2X, dir2Y, secondaryVal);
makeSecondaryLine( secondaryPosX, secondaryPosY, -dir2X, -dir2Y, secondaryVal);
grid[posX][posY] = currentVal;
posX += dirX;
posY += dirY;
currentVal++;
}
}
public void makeSecondaryLine(int secondaryPosX, int secondaryPosY, int dir2X, int dir2Y, int secondaryVal)
{
while (0 <= secondaryPosX && secondaryPosX < maxX && secondaryPosY < maxY &&
secondaryPosY >= 0 && secondaryVal < grid[secondaryPosX][secondaryPosY])
{
grid[secondaryPosX][secondaryPosY] = secondaryVal;
secondaryPosX += dir2X;
secondaryPosY += dir2Y;
secondaryVal++;
}
}
Je ne suis pas totalement sûr de ce que vous entendez par "faire une ligne de chiffres de chaque numéro" et "quatre lignes initiales proviendront des quatre bords". Pourriez-vous clarifier la réponse ou peut-être publier un pseudocode?
J'étais curieux de voir comment mon code effectue par rapport à cela, j'ai donc essayé de javascriptif votre code pour une comparaison rapide. Quelles valeurs utilisez-vous pour Maxx et Maxy?
Maxx et Maxy sont des tailles de la grille. Si la grille est 500x500 maxx est de 500 et maxy est de 500. J'ai utilisé une grille de 500 x 500. Vous exécutez également une carte avec chaque ennemi sur la grille, pas seulement l'un d'entre eux.
Ensuite, passez à travers la grille et trouvez la place avec le plus grand nombre.
La bonne chose à ce sujet est que vous pouvez également utiliser une grille de courser; De cette façon, vous devez choisir si vous voulez une précision ou une vitesse, ou quelque chose d'entre eux. (Il est difficile de le faire, car je dois remplir la grille avec des valeurs initiales entre chaque course.)
La version JavaScript prend environ 3 ms sur un bureau I5 à une résolution de 100x100, ce qui donne de bons résultats. En pleine résolution toutefois, il faut presque 100 ms.
Cela dépend aussi du nombre d'ennemis Julian sur la grille. S'il a un petit nombre d'ennemis, il serait certainement préférable d'utiliser une autre méthode, mais la bonne chose à propos de celui-ci est que la vitesse de celle-ci ne dépend pas vraiment autant sur le nombre d'ennemis, mais plutôt la taille de la grille. Je suis aussi toujours étudiant pour que je ne m'attendais pas vraiment à ce que ce soit aussi efficace.
Oui, le nombre limité d'ennemis favorise des solutions avec Per-ennemi au lieu de calculer les calculs par emplacement.
Cette méthode regarde tous les ennemis du point central, vérifie la direction dans laquelle ils se trouvent, trouve le secteur le plus vide, puis retourne un point sur une ligne au milieu de ce secteur, à 250 ans du centre. Le résultat n'est pas toujours parfait et le tache de sécurité n'est jamais au centre (bien que cela puisse être ajouté), mais peut-être que c'est assez bon.
L'algorithme fonctionne plus d'un million de fois par seconde sur mon bureau I5, mais un téléphone peut ne pas être aussi bon avec la trigonométrie. L'algorithme utilise 3 fonctions de trigonométrie par ennemi: Atan2 (), Cos () et Sin (). Ceux-ci auront probablement le plus d'impact sur la vitesse de l'exécution. Peut-être que vous pourriez remplacer le COS () et le péché () avec une table de recherche. P>
Exécutez l'extrait de code pour voir un exemple avec des ennemis positionnés au hasard. p>
p>
<BODY STYLE="margin: 0; border: 0; padding: 0"> <CANVAS ID="canvas" STYLE="width: 200px; height: 200px; background-color: #EEE;"CANVAS> </BODY>
Triangulate Les ennemis (il y a moins de 5?); et triangulez chaque coin de la grille avec la paire d'ennemis la plus proche. Le circonspect de l'un de ces triangles devrait être un endroit décent pour reproduire.
ci-dessous est un exemple en JavaScript. J'ai utilisé la méthode de la toile de la réponse de M69 pour la démonstration. Les points verts sont les candidats testés pour arriver à la suggestion de couleur bleue. Puisque nous triangulons les coins, ils ne sont pas offerts comme des solutions ici (peut-être que les solutions de proximité de manière aléatoire peuvent être passionnantes pour un joueur? Alternativement, testez également les coins ..). P>
p>
p>
<BODY STYLE="margin: 0; border: 0; padding: 0;"> <CANVAS ID="canvas" STYLE="width: 200px; height: 200px; background: radial-gradient(rgba(255,255,255,0) 0, rgba(255,255,255,.15) 30%, rgba(255,255,255,.3) 32%, rgba(255,255,255,0) 33%) 0 0, radial-gradient(rgba(255,255,255,0) 0, rgba(255,255,255,.1) 11%, rgba(255,255,255,.3) 13%, rgba(255,255,255,0) 14%) 0 0, radial-gradient(rgba(255,255,255,0) 0, rgba(255,255,255,.2) 17%, rgba(255,255,255,.43) 19%, rgba(255,255,255,0) 20%) 0 110px, radial-gradient(rgba(255,255,255,0) 0, rgba(255,255,255,.2) 11%, rgba(255,255,255,.4) 13%, rgba(255,255,255,0) 14%) -130px -170px, radial-gradient(rgba(255,255,255,0) 0, rgba(255,255,255,.2) 11%, rgba(255,255,255,.4) 13%, rgba(255,255,255,0) 14%) 130px 370px, radial-gradient(rgba(255,255,255,0) 0, rgba(255,255,255,.1) 11%, rgba(255,255,255,.2) 13%, rgba(255,255,255,0) 14%) 0 0, linear-gradient(45deg, #343702 0%, #184500 20%, #187546 30%, #006782 40%, #0b1284 50%, #760ea1 60%, #83096e 70%, #840b2a 80%, #b13e12 90%, #e27412 100%); background-size: 470px 470px, 970px 970px, 410px 410px, 610px 610px, 530px 530px, 730px 730px, 100% 100%; background-color: #840b2a;"></CANVAS> <!-- http://lea.verou.me/css3patterns/#rainbow-bokeh --> </BODY>
Peut-être que vous devriez ralentir un peu l'animation; De temps en temps, le choix du point de sécurité ne semble pas optimal, mais il faut plus de temps pour vraiment le juger, en particulier avec les points verts qui compliquent l'image.
C'est l'algorithme le plus simple que je puisse penser qui donne toujours de bons résultats. Il ne vérifie que 9 positions possibles: les coins, le milieu des côtés et le point central. La plupart du temps, le joueur se termine dans un coin, mais vous avez évidemment besoin de plus de positions que d'ennemis.
L'algorithme fonctionne dans 0,013 ms sur mon bureau I5. Si vous remplacez le MATH.POW () par MATH.ABS (), cela revient à 0,0088MS, bien que évidemment avec des résultats moins fiables. (Curieusement suffisant, c'est plus lent que mon autre réponse qui utilise des fonctions de trigonométrie.) P>
exécutant l'extrait de code (à plusieurs reprises) affichera le résultat avec des ennemis positionnés au hasard dans un élément de toile. P>
<BODY STYLE="margin: 0; border: 0; padding: 0;"> <CANVAS ID="canvas" STYLE="width: 200px; height: 200px; background-color: #EEE;"></CANVAS> </BODY>
Après avoir essayé toutes les réponses sur cette page, celle-ci était celle que j'ai fini par utiliser comme cela m'a donné des performances prévisibles. J'ai modifié les points prédéfinis de manière dynamique avec chaque jeu de jeu afin qu'ils «aspectent» au moins au moins à tous les niveaux. Merci!
@ Julian je suis content que vous l'avez trouvé utile.
Vous pouvez choisir un point aléatoire sur la grille, puis la déplacer itérativement des ennemis, voici mon implémentation en python: sortie:
Si vous ne l'avez pas déjà fait, essayez de remplacer Squareroot (Deltax ^ 2 + Deltay ^ 2) avec Deltax + Deltay, qui devrait améliorer un peu votre PEFORMANCE.
Une approche pourrait être de définir un seuil de distance minimum que le nouveau joueur doit être éloigné de tous les ennemis afin de respecter, puis générer des points aléatoires jusqu'à ce que l'un d'entre eux réponde à ce seuil. Ce n'est pas optimal mais ce serait rapide et pourrait être assez bon ».
La distance entre l'ennemi le plus proche est-elle tout-importante, ou peut-on être relativement proche si tous les autres sont loin?
@HUCK_CUSSLER C'est une bonne idée, veuillez le poster comme une réponse car elle pourrait être ce que je cherche. M69 Oui, c'est important car c'est un jeu rapide. Roy Sharaf, toujours pas de dés, merci!
Heuriste simple: essayez n points aléatoires et choisissez le meilleur.
La meilleure tactique pour l'ennemi est de s'organiser dans un rayon de cercle 125 * SQRT (2) autour du centre, puis serrez le filet lorsque le joueur reproche au piège.
@Julien S'il vous plaît voir ma réponse mise à jour pour une démonstration. À votre santé.