J'ai une grille de tuiles d'une taille finie connue qui forme une carte. Certaines tuiles à l'intérieur de la carte sont placées dans un ensemble appelé territoire. Ce territoire est connecté, mais on ne sait rien de sa forme. La plupart du temps, ce serait une goutte assez régulière, mais elle pourrait être très allongée dans une direction, et elle pourrait même avoir des trous. Je souhaite trouver la frontière (extérieure) du territoire.
Autrement dit, je veux une liste de toutes les tuiles qui touchent l'une des tuiles du territoire sans être elle-même sur le territoire. Quel est un moyen efficace de trouver cela?
Pour une difficulté supplémentaire, il arrive que mes tuiles soient des hexagones, mais je soupçonne que cela ne fait pas trop de différence, chaque tuile est toujours étiquetée avec une coordonnée entière x et y et, étant donné une tuile, je peux facilement trouver ses voisins. Voici quelques exemples: le noir est le territoire et le bleu la frontière que je veux trouver.
En soi, ce n'est pas un problème difficile, Un algorithme simple pour cela, en pseudo-python, est:
def find_border_of_territory(territory):
border = []
for tile in territory:
for neighbor in tile.neighbors():
if neighbor not in territory and neighbor not in border:
border.add(neighbor)
Cependant, c'est lent et j'aimerais quelque chose de mieux. J'ai une boucle O (n) sur le territoire, une autre boucle (courte, mais quand même) sur tous les voisins, puis je dois vérifier l'appartenance sur deux listes, dont l'une est de taille n. Cela donne une échelle redoutable de O (n ^ 2). Je peux réduire cela à O (n) en utilisant des ensembles au lieu de listes pour la frontière et le territoire afin que l'adhésion soit rapide à vérifier, mais ce n'est toujours pas génial. Je m'attends à ce qu'il y ait de nombreux cas où le territoire est grand mais la frontière est petite en raison d'une simple mise à l'échelle zone vs ligne. Par exemple, si le territoire est un hex de rayon 5, il est de taille 91 mais la frontière n'est que de taille 36.
Quelqu'un peut-il proposer quelque chose de mieux?
Éditer:
Pour répondre à certaines des questions ci-dessous. Le territoire peut varier en taille, de 20 à 100 environ. L'ensemble de tuiles formant le territoire est un attribut d'un objet, et c'est cet objet qui a besoin d'un ensemble de toutes les tuiles de bordure.
Initialement, le territoire est créé comme un bloc, puis gagne principalement des tuiles une par une. Dans ce cas, il est vrai que le moyen le plus rapide consiste simplement à conserver un ensemble de bordure et à le mettre à jour uniquement sur la tuile obtenue. Parfois, un grand changement dans le territoire peut se produire - il devra donc être recalculé complètement à ce moment-là.
Je suis maintenant d'avis que faire un simple algorithme de recherche de frontière est la meilleure solution. La seule complexité supplémentaire que cela soulève est de garantir que la frontière est recalculée à chaque fois qu'elle devrait l'être, mais pas plus. Je suis assez confiant que cela peut être fait de manière fiable dans mon cadre actuel.
En ce qui concerne le timing, dans mon code actuel, j'ai quelques routines qui doivent vérifier chaque tuile du territoire. Pas à chaque tour, mais à la création et parfois après. Cela prend plus de 50% du temps de fonctionnement de ma combinaison de code de test, même si c'est une très petite partie du programme complet. Je tenais donc à minimiser les répétitions. CEPENDANT, le code de test implique beaucoup plus de création d'objets qu'une exécution normale du programme (naturellement), donc je me rends compte que cela pourrait ne pas être très pertinent.
la source
Réponses:
Il est généralement préférable de trouver un algorithme avec une structure de données qui facilite l'algorithme.
Dans ce cas, votre territoire.
Le territoire doit être un ensemble non ordonné (hachage O (1)) de frontières et d'éléments.
Chaque fois que vous ajoutez un élément au territoire, vous parcourez les tuiles adjacentes et voyez si elles doivent être une tuile frontière; dans ce cas, ils sont une tuile frontière s'ils ne sont pas une tuile élément.
Chaque fois que vous soustrayez un élément du territoire, vous vous assurez que ses tuiles adjacentes sont toujours dans le territoire, et vous voyez si vous devez devenir une tuile frontière. Si vous avez besoin que cela soit rapide, demandez aux tuiles de bordure de suivre leur "nombre adjacent".
Cela nécessite O (1) lorsque vous ajoutez ou supprimez une tuile sur ou depuis un territoire. La visite de la frontière prend O (longueur de la frontière). Tant que vous voulez savoir «ce qu'est la frontière» beaucoup plus souvent que vous ajoutez / supprimez des éléments du territoire, cela devrait gagner.
la source
Si vous devez également trouver des bords de trous au milieu de votre territoire, alors votre linéaire dans la zone du territoire délimité est le meilleur que nous pouvons faire. Toute tuile à l'intérieur pourrait potentiellement être un trou que nous devons compter, nous devons donc examiner chaque tuile dans la zone délimitée par le contour du territoire au moins une fois pour être sûr d'avoir trouvé tous les trous.
Mais si vous ne cherchez qu'à trouver la bordure extérieure (pas les trous intérieurs), nous pouvons le faire un peu plus efficacement:
Trouvez un bord séparant votre territoire. Vous pouvez le faire en ...
(si vous connaissez au moins une tuile territoire et que vous avez exactement un blob territoire connecté sur votre carte)
... commençant à une tuile arbitraire sur votre territoire et se déplaçant vers le bord le plus proche de votre carte. Ce faisant, souvenez-vous du dernier bord où vous êtes passé d'une tuile de territoire à une tuile hors territoire. Une fois que vous avez atteint le bord de la carte, ce bord mémorisé est votre bord de départ.
Ce scan est linéaire dans le diamètre de la carte.
ou (si vous ne savez pas où se trouvent vos tuiles de territoire à l'avance, ou si votre carte peut contenir plusieurs territoires déconnectés)
... en commençant à un bord de votre carte, parcourez chaque ligne jusqu'à ce que vous touchiez une tuile de terrain. Le dernier bord que vous avez traversé d'un non-terrain à un terrain est votre bord de départ.
Ce balayage pourrait être au pire linéaire dans la zone de la carte (quadratique dans son diamètre), mais si vous avez des limites pour restreindre votre recherche (par exemple, vous savez que le territoire traverse presque toujours les rangées du milieu), vous pouvez améliorer ce pire- comportement de cas.
En commençant à votre bord de départ trouvé à l'étape 1, suivez-le autour du périmètre de votre terrain, en ajoutant chaque tuile non-terrain à l'extérieur à votre collection de bordures, jusqu'à ce que vous reveniez au bord de départ.
Cette étape de suivi des bords est linéaire dans le périmètre de votre contour de terrain, plutôt que dans sa zone. L'inconvénient est que le code est plus compliqué car vous devez tenir compte de chaque type de virage que le bord peut prendre et éviter de compter deux fois les carreaux de bordure aux entrées.
Si vos exemples sont représentatifs de la taille réelle de vos données à quelques ordres de grandeur, alors j'irais moi-même pour la recherche de zone naïve - elle sera toujours extrêmement rapide sur un si petit nombre de tuiles, et est beaucoup plus simple à écrire , comprendre et maintenir (conduisant généralement à moins de bugs!)
la source
Remarque : Le fait qu'une tuile soit ou non sur la frontière dépend uniquement d'elle et de ses voisins.
À cause de ça:
Il est facile d'exécuter cette requête paresseusement. Par exemple: vous n'avez pas besoin de rechercher la limite sur toute la carte, uniquement sur ce qui est visible.
Il est facile d'exécuter cette requête en parallèle. En fait, je pourrais imaginer un code de shader qui fait cela. Et si vous en avez besoin pour autre chose que la visualisation, vous pouvez rendre une texture et l'utiliser.
Si une tuile change, la limite ne change que localement, ce qui signifie que vous n'avez pas besoin de recalculer le tout.
Vous pouvez également pré-calculer la frontière. Autrement dit, si vous remplissez l'hex, vous pouvez décider si une tuile est une limite à ce moment. Cela signifie que:
N'utilisez pas de liste pour la limite. Utilisez un ensemble si vous le devez vraiment ( je ne sais pas pour quoi vous voulez la limite. ). Cependant, si vous définissez une tuile comme limite ou non comme attribut de la tuile, vous n'avez pas besoin d'aller dans une autre structure de données pour vérifier.
la source
Déplacez votre zone vers le haut d'une tuile, puis vers le haut à droite, puis vers le bas à droite, etc. Retirez ensuite la zone d'origine.
La fusion des six ensembles doit être O (n), trier O (n.log (n)), définir la différence O (n). Si les tuiles d'origine sont stockées dans un certain format trié, l'ensemble fusionné peut également être trié dans O (n).
Je ne pense pas qu'il existe un algorithme avec moins de O (n), car vous devez accéder à chaque tuile au moins une fois.
la source
Je viens d'écrire un article de blog sur la façon de procéder. Cela utilise la première méthode mentionnée par @DMGregory en commençant par une cellule de bord et en marchant autour du périmètre. C'est en C # au lieu de Python mais devrait être assez facile à adapter.
https://dillonshook.com/hex-city-borders/
la source
POSTE ORIGINAL:
Je ne peux pas commenter ce site, je vais donc essayer de répondre avec un algorithme de pseudocode.
Vous savez que chaque territoire a au plus six voisins qui font partie de la frontière. Pour chaque tuile du territoire, ajoutez les six tuiles voisines à une liste de bordures potentielles. Ensuite, soustrayez toutes les tuiles du territoire de la frontière et il ne vous reste que les tuiles de la frontière. Cela fonctionnera mieux si vous utilisez un ensemble non ordonné pour stocker chaque liste. J'espère que j'ai été utile.
EDIT Il existe des moyens beaucoup plus efficaces que la simple itération. Comme j'ai essayé de le dire dans ma réponse (maintenant supprimée) ci-dessous, vous pouvez obtenir O (1) dans les meilleurs cas et O (n) dans le pire des cas.
Ajout d'une tuile à un territoire O (1) - O (N):
Dans le cas d'aucun voisin, vous créez simplement un nouveau territoire.
Dans le cas d'un voisin, vous ajoutez la nouvelle tuile au territoire existant.
Dans le cas de 5 ou 6 voisins, vous savez que tout est connecté, vous ajoutez donc la nouvelle tuile au territoire existant. Ce sont toutes des opérations O (1), et la mise à jour des nouveaux territoires frontaliers est également O (1), car il s'agit d'une simple fusion d'un ensemble avec un autre.
Dans le cas de 2, 3 ou 4 territoires voisins, vous devrez peut-être fusionner jusqu'à 3 territoires uniques. Il s'agit de O (N) sur la taille du territoire combiné.
Retirer une tuile d'un territoire O (1) - O (N):
Avec zéro voisins, effacez le territoire. O (1)
Avec un voisin, retirez la tuile du territoire. O (1)
Avec deux voisins ou plus, jusqu'à 3 nouveaux territoires peuvent être créés. C'est O (N).
J'ai passé mon temps libre au cours des dernières semaines à développer un programme de démonstration qui est un simple jeu de territoire hexadécimal. Essayez d'augmenter vos revenus en plaçant les territoires côte à côte. 3 joueurs, Rouge, Vert et Bleu s'affrontent pour générer le plus de revenus en plaçant stratégiquement des tuiles sur un terrain de jeu limité.
Vous pouvez télécharger le jeu ici (au format .7z) hex.7z
Contrôle simple de la souris LMB place une tuile (ne peut être placée que là où elle est mise en surbrillance). Score en haut, revenu en bas. Voyez si vous pouvez trouver une stratégie efficace.
Le code peut être trouvé ici:
Eagle / EagleTest
Pour construire à partir du code source, vous avez besoin d'Eagle et d'Allegro 5. Les deux se construisent avec cmake. Le jeu Hex se construit actuellement avec le projet CB.
Renversez ces votes négatifs. :)
la source