Comment accélérer la finition A * lorsque la destination est impraticable?

31

Je fais un jeu 2D simple basé sur des tuiles, qui utilise l'algorithme de recherche de chemin A * ("A star"). J'ai tout fonctionne bien, mais j'ai un problème de performances avec la recherche. Autrement dit, lorsque je clique sur une vignette infranchissable, l'algorithme parcourt apparemment toute la carte pour trouver un itinéraire vers la vignette infranchissable - même si je me tiens à côté d'elle.

Comment puis-je contourner cela? Je suppose que je pourrais réduire le cheminement vers la zone d'écran, mais peut-être que je manque quelque chose d'évident ici?

user2499946
la source
2
Savez-vous quelles tuiles sont infranchissables ou le savez-vous simplement grâce à l'algorithme AStar?
user000user
Comment stockez-vous votre graphique de navigation?
Anko
Si vous stockez des nœuds traversés dans des listes, vous souhaiterez peut-être utiliser des tas binaires pour améliorer la vitesse.
ChrisC
Si c'est tout simplement trop lent, j'ai une série d'optimisations à suggérer - ou essayez-vous d'éviter complètement les recherches?
Steven
1
Cette question aurait probablement été mieux adaptée à l' informatique .
Raphael

Réponses:

45

Quelques idées pour éviter les recherches qui aboutissent à des chemins échoués:

ID de l'île

L'une des façons les moins chères de terminer efficacement les recherches A * plus rapidement est de ne faire aucune recherche. Si les zones sont vraiment infranchissables par tous les agents, inondez chaque zone avec un identifiant d'îlot unique en charge (ou dans le pipeline). Lors de la recherche de chemin, vérifiez si l' ID d'îlot de l'origine du chemin correspond à l' ID d'îlot de la destination. S'ils ne correspondent pas, la recherche est inutile - les deux points se trouvent sur des îles distinctes et non connectées. Cela n'aide que s'il existe des nœuds vraiment infranchissables pour tous les agents.

Limite de la limite supérieure

Je limite la limite supérieure du nombre maximal de nœuds pouvant être recherchés. Cela aide les recherches infranchissables à s'exécuter pour toujours, mais cela signifie que certaines recherches passables qui sont très longues peuvent être perdues. Ce nombre doit être réglé, et il ne résout pas vraiment le problème, mais il atténue les coûts associés aux longues recherches.

Si vous constatez que cela prend trop de temps, les techniques suivantes sont utiles:

Rendre les itérations asynchrones et limites

Laissez la recherche s'exécuter dans un thread séparé ou un peu à chaque image afin que le jeu ne s'arrête pas en attendant la recherche. Affichez une animation représentant un personnage se grattant la tête ou tapant des pieds, ou tout ce qui est approprié en attendant la fin de la recherche. Pour ce faire efficacement, je garderais l'état de la recherche en tant qu'objet séparé et permettrait à plusieurs états d'exister. Lorsqu'un chemin est demandé, saisissez un objet d'état libre et ajoutez-le à la file d'attente des objets d'état actifs. Dans votre mise à jour d'orientation, retirez l'élément actif de l'avant de la file d'attente et exécutez A * jusqu'à ce que A. soit terminé ou B. une certaine limite d'itérations soit exécutée. S'il est terminé, remettez l'objet d'état dans la liste des objets d'état libres. S'il n'est pas terminé, mettez-le à la fin des «recherches actives» et passez à la suivante.

Choisissez les bonnes structures de données

Assurez-vous d'utiliser les bonnes structures de données. Voici comment fonctionne mon StateObject. Tous mes nœuds sont pré-alloués à un nombre fini - disons 1024 ou 2048 - pour des raisons de performances. J'utilise un pool de nœuds qui accélère l'allocation des nœuds et cela me permet également de stocker des index au lieu de pointeurs dans mes structures de données qui sont des u16 (ou u8 si j'ai 255 nœuds max, ce que je fais sur certains jeux). Pour mon identification, j'utilise une file d'attente prioritaire pour la liste ouverte, stockant des pointeurs vers des objets Node. Il est implémenté comme un tas binaire, et je trie les valeurs à virgule flottante sous forme d'entiers car elles sont toujours positives et ma plateforme a des comparaisons à virgule flottante lentes. J'utilise une table de hachage pour ma carte fermée pour garder une trace des nœuds que j'ai visités. Il stocke les NodeIDs, pas les Nodes, pour économiser sur les tailles de cache.

Cachez ce que vous pouvez

Lorsque vous visitez un nœud pour la première fois et calculez la distance jusqu'à la destination, mettez-le en cache dans le nœud stocké dans l'objet État. Si vous revisitez le nœud, utilisez le résultat mis en cache au lieu de le calculer à nouveau. Dans mon cas, cela évite d'avoir à faire une racine carrée sur des nœuds revisités. Vous pouvez trouver qu'il existe d'autres valeurs que vous pouvez précalculer et mettre en cache.

D'autres domaines que vous pourriez étudier: utilisez la recherche de chemin bidirectionnelle pour rechercher à partir de l'une ou l'autre extrémité. Je ne l'ai pas fait, mais comme d'autres l'ont noté, cela pourrait aider, mais ce n'est pas sans mises en garde. L'autre chose sur ma liste à essayer est la recherche de chemin hiérarchique ou la recherche de chemin de clustering. Il existe une description intéressante dans la documentation HavokAI décrivant ici leur concept de clustering, qui est différent des implémentations HPA * décrites ici .

Bonne chance et dites-nous ce que vous trouvez.

Steven
la source
S'il existe différents agents avec des règles différentes, mais pas trop, cela peut toujours être généralisé assez efficacement en utilisant un vecteur d'ID, un par classe d'agent.
MSalters
4
+1 Pour avoir reconnu que le problème est probablement des zones délimitées (pas seulement des carreaux infranchissables), et que ce type de problème peut être résolu plus facilement avec des calculs de temps de chargement précoces.
Slipp D. Thompson du
Remplir ou remplir BFS chaque zone.
wolfdawn
Les ID d'îlot n'ont pas besoin d'être statiques. Il existe un algorithme simple qui conviendrait au cas où il serait nécessaire de pouvoir joindre deux îles distinctes, mais il ne peut pas diviser une île par la suite. Les pages 8 à 20 de ces diapositives expliquent cet algorithme particulier: cs.columbia.edu/~bert/courses/3137/Lecture22.pdf
kasperd
@kasperd, bien sûr, rien n'empêche les ID d'îles d'être recalculés, fusionnés lors de l'exécution. Le fait est que les identifiants d'îlot vous permettent de confirmer rapidement l'existence d'un chemin entre deux nœuds sans effectuer de recherche astar.
Steven
26

AStar est un algorithme de planification complet , ce qui signifie que s'il existe un chemin vers le nœud, AStar est garanti de le trouver. Par conséquent, il doit vérifier chaque chemin hors du nœud de départ avant de pouvoir décider que le nœud cible est inaccessible. C'est très indésirable lorsque vous avez trop de nœuds.

Façons d'atténuer cela:

  • Si vous savez a priori qu'un nœud est inaccessible (par exemple, il n'a pas de voisins ou qu'il est marqué UnPassable), retournez No Pathsans jamais appeler AStar.

  • Limitez le nombre de nœuds qu'AStar étendra avant de se terminer. Vérifiez l'ensemble ouvert. Si jamais il devient trop gros, terminez et revenez No Path. Cependant, cela limitera l'exhaustivité d'AStar; il ne peut donc planifier que des trajets d'une longueur maximale.

  • Limitez le temps nécessaire à AStar pour trouver un chemin. S'il manque de temps, quittez et revenez No Path. Cela limite l'exhaustivité comme la stratégie précédente, mais évolue avec la vitesse de l'ordinateur. Notez que pour de nombreux jeux, cela n'est pas souhaitable, car les joueurs avec des ordinateurs plus rapides ou plus lents verront le jeu différemment.

mklingen
la source
13
Je voudrais souligner que changer les mécanismes de votre jeu en fonction de la vitesse du processeur (oui, la recherche d'itinéraire est un mécanisme de jeu) peut s'avérer être une mauvaise idée car cela peut rendre le jeu assez imprévisible et dans certains cas, même injouable sur les ordinateurs dans 10 ans. Je préfère donc limiter A * en plafonnant l'ensemble ouvert plutôt que par le temps CPU.
Philipp
@Philipp. Modification de la réponse pour refléter cela.
mklingen
1
Notez que vous pouvez déterminer (raisonnablement efficace, O (nœuds)) pour un graphique donné la distance maximale entre deux nœuds. Il s'agit du problème de chemin le plus long et il vous fournit une limite supérieure correcte pour le nombre de nœuds à vérifier.
MSalters
2
@MSalters Comment faites-vous cela dans O (n)? Et qu'est-ce qui est «raisonnablement efficace»? Si ce n'est que pour des paires de nœuds, ne faites-vous pas simplement duplication de travail?
Steven
Selon Wikipedia, le problème de chemin le plus long est malheureusement NP-difficile.
Desty
21
  1. Exécutez une recherche double A * à partir du nœud cible en sens inverse et en même temps dans la même boucle et abandonnez les deux recherches dès que l'une est trouvée insoluble

Si la cible n'a que 6 tuiles accessibles autour d'elle et que l'origine a 1002 tuiles accessibles, la recherche s'arrêtera à 6 (doubles) itérations.

Dès qu'une recherche trouve les nœuds visités de l'autre, vous pouvez également limiter la portée de la recherche aux nœuds visités de l'autre et terminer plus rapidement.

Stéphane Hockenhull
la source
2
L'implémentation d'une recherche bidirectionnelle en étoile A ne se limite pas à ce que votre déclaration implique, y compris la vérification que l'heuristique reste admissible dans ces circonstances. (Liens: homepages.dcc.ufmg.br/~chaimo/public/ENIA11.pdf )
Pieter Geerkens
4
@StephaneHockenhull: Après avoir implémenté un A- * bidirectionnel sur une carte du terrain avec des coûts asymétriques, je vous assure qu'ignorer le blah-blah académique entraînera une sélection de chemin défectueuse et des calculs de coûts incorrects.
Pieter Geerkens
1
@MooingDuck: Le nombre total de nœuds est inchangé, et chaque nœud ne sera toujours visité qu'une seule fois, donc le pire des cas de division de carte exactement en deux est identique à A- * unidirectionnel.
Pieter Geerkens
1
@PieterGeerkens: Dans le classique A *, seulement la moitié des nœuds sont accessibles, et donc visités. Si la carte est divisée exactement en deux, alors lorsque vous effectuez une recherche bidirectionnelle, vous touchez (presque) chaque nœud. Certainement un cas de pointe cependant
Mooing Duck
1
@MooingDuck: J'ai mal parlé; les pires cas sont des graphiques différents, mais ont le même comportement - le pire des cas pour unidirectionnel est un nœud de but complètement isolé, nécessitant que tous les nœuds soient visités.
Pieter Geerkens
12

En supposant que le problème est que la destination est inaccessible. Et que le maillage de navigation n'est pas dynamique. La façon la plus simple de le faire est d'avoir un graphique de navigation beaucoup plus clairsemé (suffisamment clairsemé pour qu'une exécution complète soit relativement rapide) et d'utiliser le graphique détaillé uniquement si le cheminement est possible.

ClassicThunder
la source
6
C'est bon. En regroupant les tuiles en "régions" et en vérifiant d'abord si la région dans laquelle se trouve votre tuile peut être connectée à la région dans laquelle se trouve l'autre tuile, vous pouvez jeter les négatifs beaucoup plus rapidement.
Konerak
2
Correct - relève généralement de la LPD *
Steven
@Steven Merci j'étais sûr que je n'étais pas la première personne à penser à une telle approche mais je ne savais pas comment elle s'appelait. Permet de tirer parti de la recherche préexistante beaucoup plus facilement.
ClassicThunder
3

Utilisez plusieurs algorithmes avec des caractéristiques différentes

A * a de belles caractéristiques. En particulier, il trouve toujours le chemin le plus court, s'il en existe un. Malheureusement, vous avez également trouvé de mauvaises caractéristiques. Dans ce cas, il doit rechercher de manière exhaustive tous les chemins possibles avant d'admettre qu'aucune solution n'existe.

Le "défaut" que vous découvrez dans A * est qu'il ignore la topologie. Vous pouvez avoir un monde 2D, mais il ne le sait pas. Pour tout ce qu'il sait, dans le coin le plus éloigné de votre monde se trouve un escalier qui le ramène sous le monde à sa destination.

Envisagez de créer un deuxième algorithme qui connaît la topologie. Dans un premier temps, vous pourriez remplir le monde de «nœuds» tous les 10 ou 100 espaces, puis conserver un graphique de connectivité entre ces nœuds. Cet algorithme rechercherait le chemin en trouvant des nœuds accessibles près du début et de la fin, puis en essayant de trouver un chemin entre eux sur le graphique, s'il en existe un.

Une façon simple de le faire serait d'affecter chaque tuile à un nœud. Il est trivial de montrer que vous n'avez besoin d'affecter qu'un seul nœud à chaque tuile (vous ne pouvez jamais avoir accès à deux nœuds qui ne sont pas connectés dans le graphique). Ensuite, les bords du graphique sont définis comme étant n'importe où deux tuiles avec des nœuds différents sont adjacentes.

Ce graphique a un inconvénient: il ne trouve pas le chemin optimal. Il trouve simplement un chemin. Cependant, il vous a maintenant montré que A * peut trouver un chemin optimal.

Il fournit également une heuristique pour améliorer vos sous-estimations nécessaires pour faire fonctionner A *, car vous en savez maintenant plus sur votre paysage. Vous êtes moins susceptible d'avoir à explorer pleinement une impasse avant de découvrir que vous aviez besoin de prendre du recul pour aller de l'avant.

Cort Ammon - Rétablir Monica
la source
J'ai des raisons de croire que des algorithmes comme ceux de Google Maps fonctionnent de manière similaire (bien que plus avancée).
Cort Ammon - Rétablir Monica le
Faux. A * connaît très bien la topologie, via le choix de l'heuristique admissible.
MSalters
Concernant Google, lors de mon travail précédent, nous avons analysé les performances de Google Maps et constaté qu'il ne pouvait pas s'agir d'un A *. Nous pensons qu'ils utilisent ArcFlags ou d'autres algorithmes similaires qui reposent sur le prétraitement des cartes.
MSalters
@MSalters: C'est une ligne fine intéressante à tracer. Je soutiens que A * n'est pas au courant de la topologie car elle ne concerne que les voisins les plus proches. Je dirais qu'il est plus juste de dire que l'algorithme générant l'heuristique admissible connaît la topologie, plutôt que A * lui-même. Prenons un cas où il y a un diamant. A * prend un chemin pendant un moment, avant de reculer pour essayer l'autre côté du diamant. Il n'y a aucun moyen d'aviser A * que la seule "sortie" de cette branche se fait via un nœud déjà visité (sauvegarde du calcul) avec l'heuristique.
Cort Ammon - Rétablir Monica le
1
Je ne peux pas parler pour Google Maps, mais Bing Map utilise une étoile A bidirectionnelle parallèle avec repères et inégalité triangulaire (ALT), avec des distances pré-calculées à partir (et vers) d'un petit nombre de points de repère et de chaque nœud.
Pieter Geerkens
2

Quelques idées supplémentaires en plus des réponses ci-dessus:

  1. Mettre en cache les résultats d'une recherche A *. Enregistrez les données de chemin de la cellule A à la cellule B et réutilisez-les si possible. Ceci est plus applicable dans les cartes statiques et vous devrez travailler davantage avec les cartes dynamiques.

  2. Mettez en cache les voisins de chaque cellule. Une implémentation * doit étendre chaque nœud et ajouter ses voisins à l'ensemble ouvert pour la recherche. Si ce voisin est calculé à chaque fois plutôt que mis en cache, cela pourrait ralentir considérablement la recherche. Et si vous ne l'avez pas déjà fait, utilisez une file d'attente prioritaire pour A *.

user55564
la source
1

Si votre carte est statique, vous pouvez simplement avoir chaque section distincte avec son propre code et vérifiez-le d'abord avant d'exécuter A *. Cela peut être fait lors de la création de la carte ou même codé dans la carte.

Les tuiles infranchissables devraient avoir un drapeau et lorsque vous passez à une tuile comme celle-ci, vous pouvez choisir de ne pas exécuter A * ou de choisir une tuile à côté qui est accessible.

Si vous avez des cartes dynamiques qui changent fréquemment, vous n'avez pas de chance. Vous devez interrompre votre décision de faire votre algorithme avant la fin ou faire des contrôles sur les sections fermées fréquemment.

Madmenyo
la source
C'est exactement ce que je proposais avec un identifiant de zone dans ma réponse.
Steven
Vous pouvez également réduire la quantité de CPU / temps utilisé si votre carte est dynamique, mais ne change pas souvent. C'est-à-dire que vous pouvez recalculer les ID de zone chaque fois qu'une porte verrouillée est déverrouillée ou verrouillée. Comme cela se produit généralement en réponse aux actions d'un joueur, vous devez au moins exclure les zones verrouillées d'un donjon.
uliwitness
1

Comment puis-je faire en sorte que A * conclue plus rapidement qu'un nœud est infranchissable?

Profilez votre Node.IsPassable() fonction, déterminez les parties les plus lentes, accélérez-les.

Lorsque vous décidez si un nœud est passable, placez les situations les plus probables en haut, de sorte que la plupart du temps, la fonction revient immédiatement sans prendre la peine de vérifier les possibilités les plus obscures.

Mais c'est pour accélérer la vérification d'un seul nœud. Vous pouvez profiler pour voir combien de temps est passé à interroger les nœuds, mais il semble que votre problème soit que trop de nœuds soient vérifiés.

lorsque je clique sur une tuile infranchissable, l'algorithme parcourt apparemment toute la carte pour trouver un itinéraire vers la tuile infranchissable

Si la tuile de destination elle-même est infranchissable, l'algorithme ne devrait vérifier aucune tuile du tout. Avant même de commencer à rechercher le chemin, il doit interroger la vignette de destination pour vérifier si c'est possible, et sinon, retourner un résultat sans chemin.

Si vous voulez dire que la destination elle-même est praticable, mais qu'elle est entourée de tuiles infranchissables, de sorte qu'il n'y a pas de chemin, alors il est normal que A * vérifie la carte entière. Sinon, comment pourrait-il savoir qu'il n'y a pas de chemin?

Si c'est le cas, vous pouvez l'accélérer en effectuant une recherche bidirectionnelle - de cette façon, la recherche à partir de la destination peut rapidement trouver qu'il n'y a pas de chemin et arrêter la recherche. Voir cet exemple , entourez la destination de murs et comparez la direction bidirectionnelle à la direction unique.

Superbest
la source
0

Faites la recherche de chemin à l'envers.

Si seule votre carte n'a pas de grandes zones continues de tuiles inaccessibles, cela fonctionnera. Plutôt que de rechercher l'intégralité de la carte accessible, la recherche de chemin cherchera uniquement la zone fermée inaccessible.

aaaaaaaaaaaa
la source
C'est encore plus lent si les tuiles inaccessibles sont plus nombreuses que les tuiles accessibles
Mooing Duck
1
@MooingDuck Les tuiles connectées inaccessibles que vous voulez dire. Il s'agit d'une solution qui fonctionne avec à peu près n'importe quelle conception de carte saine, et elle est très facile à mettre en œuvre. Je ne vais rien suggérer de plus sophistiqué sans une meilleure connaissance du problème exact, comme la façon dont l'implémentation A * peut être si lente que la visite de toutes les tuiles est en fait un problème.
aaaaaaaaaaaa
0

Si les zones auxquelles le joueur est connecté (pas de téléportation, etc.) et les zones inaccessibles ne sont généralement pas très bien connectées, vous pouvez simplement faire l'A * à partir du nœud que vous souhaitez atteindre. De cette façon, vous pouvez toujours trouver un itinéraire possible vers la destination et A * cessera de rechercher rapidement les zones inaccessibles.

ent
la source
Le point devait être plus rapide que le A * normal.
Heckel
0

lorsque je clique sur une tuile infranchissable , l'algorithme parcourt apparemment toute la carte pour trouver un itinéraire vers la tuile infranchissable - même si je suis à côté d'elle.

D'autres réponses sont excellentes, mais je dois souligner l'évidence - vous ne devriez pas du tout exécuter la recherche de chemin vers une tuile infranchissable.

Cela devrait être une sortie anticipée de l'algo:

if not IsPassable(A) or not IsPasable(B) then
    return('NoWayExists');
Kromster dit de soutenir Monica
la source
0

Pour vérifier la distance la plus longue dans un graphique entre deux nœuds:

(en supposant que tous les bords ont le même poids)

  1. Exécutez BFS à partir de n'importe quel sommet v .
  2. Utilisez les résultats pour sélectionner un sommet le plus éloigné v, nous l'appelleronsd .
  3. Exécutez BFS à partir de u .
  4. Trouvez le sommet le plus éloigné u, nous l'appelleronsw .
  5. La distance entre uet west la plus longue distance dans le graphique.

Preuve:

                D1                            D2
(v)---------------------------r_1-----------------------------(u)
                               |
                            R  | (note it might be that r1=r2)
                D3             |              D4
(x)---------------------------r_2-----------------------------(y)
  • Disons la distance entre yetx est plus grande!
  • Ensuite, selon cela D2 + R < D3
  • ensuite D2 < R + D3
  • Alors la distance entre vet xest supérieure à celle de vetu ?
  • Ensuite, un'aurait pas été choisi dans la première phase.

Crédit au prof. Shlomi Rubinstein

Si vous utilisez des arêtes pondérées, vous pouvez accomplir la même chose en temps polynomial en exécutant Dijkstra au lieu de BFS pour trouver le sommet le plus éloigné.

Veuillez noter que je suppose que c'est un graphique connecté. Je suppose également que ce n'est pas dirigé.


Un * n'est pas vraiment utile pour un simple jeu basé sur des tuiles 2d car si je comprends bien, en supposant que les créatures se déplacent dans 4 directions, BFS obtiendra les mêmes résultats. Même si les créatures peuvent se déplacer dans 8 directions, le BFS paresseux qui préfère les nœuds plus proches de la cible obtiendra toujours les mêmes résultats. A * est une modification Dijkstra qui est beaucoup plus coûteuse en calcul que l'utilisation de BFS.

BFS = O (| V |) soi-disant O (| V | + | E |) mais pas vraiment dans le cas d'une carte descendante. A * = O (| V | log | V |)

Si nous avons une carte avec seulement 32 x 32 tuiles, BFS coûtera au plus 1024 et un vrai A * pourrait vous coûter 10000. Il s'agit de la différence entre 0,5 seconde et 5 secondes, peut-être plus si vous tenez compte du cache. Assurez-vous donc que votre A * se comporte comme un BFS paresseux qui préfère les tuiles les plus proches de la cible souhaitée.

Un * est utile pour les cartes de navigation où le coût des bords est important dans le processus de prise de décision. Dans un simple jeu basé sur des tuiles aériennes, le coût des bords n'est probablement pas une considération importante. Si c'est le cas, (les différentes tuiles coûtent différemment), vous pouvez exécuter une version modifiée de BFS qui reporte et pénalise les chemins qui traversent les tuiles qui ralentissent le personnage.

Donc oui, BFS> A * dans de nombreux cas en ce qui concerne les tuiles.

Wolfwawn
la source
Je ne suis pas sûr de comprendre cette partie "Si nous avons une carte avec seulement 32 x 32 tuiles, BFS coûtera au plus 1024 et un vrai A * pourrait vous coûter 10 000" Pouvez-vous expliquer comment êtes-vous arrivé au 10k numéro s'il vous plait?
Kromster dit soutenir Monica le
Qu'entendez-vous exactement par «BFS paresseux qui préfère les nœuds plus proches de la cible»? Voulez-vous dire Dijkstra, BFS ordinaire, ou un avec une heuristique (eh bien vous avez recréé A * ici, ou comment sélectionnez-vous le prochain meilleur nœud dans un ensemble ouvert)? Cela log|V|dans la complexité de A * vient vraiment du maintien de cet ensemble ouvert, ou de la taille de la frange, et pour les cartes de grille, il est extrêmement petit - à propos de log (sqrt (| V |)) en utilisant votre notation. Le journal | V | n'apparaît que dans les graphiques hyper-connectés. Il s'agit d'un exemple où l'application naïve de la pire des situations donne une conclusion incorrecte.
congusbongus
@congusbongus C'est exactement ce que je veux dire. N'utilisez pas une implémentation vanille de A *
wolfdawn
@KromStern En supposant que vous utilisez l'implémentation vanille de A * pour un jeu basé sur des tuiles, vous obtenez V * logV complexité, V étant le nombre de tuiles, pour une grille de 32 par 32 c'est 1024. logV, étant bien approximativement le nombre de bits nécessaire pour représenter 1024 qui est 10. Donc vous finissez par courir plus longtemps inutilement. Bien sûr, si vous spécialisez l'implémentation pour profiter du fait que vous exécutez sur une grille de tuiles, vous surmontez cette limitation qui est exactement ce à quoi je faisais référence
wolfdawn