La semaine dernière, nous avons parlé dans notre blog de changements qui permettront aux ennemis (mordeurs) de ne pas se croiser, mais ce n'était pas la seule mise à jour liée aux mordeurs. Par coïncidence, les mises à jour de cette semaine comprenaient ce sur quoi nous avons travaillé au cours des dernières semaines - la mise à jour du système de recherche d'ennemis.
Rechercher un moyen
Lorsqu'une unité veut se déplacer quelque part, elle doit d'abord comprendre comment s'y rendre. Dans le cas le plus simple, vous pouvez vous rendre directement au but, mais parfois des obstacles surgissent sur le chemin - rochers, arbres, nids ennemis (reproducteurs), unités de joueurs. Afin d'ouvrir la voie, nous devons indiquer à la fonction Pathfinder la position actuelle et finale, et Pathfinder nous renverra (peut-être après de nombreuses mesures) un
chemin qui est simplement un ensemble de points de cheminement que l'unité doit se déplacer pour se rendre. destination
Pour accomplir son travail, pathfinder utilise un algorithme appelé A * (prononcé "A star"). Un exemple simple de trouver un chemin en utilisant A * est montré dans la vidéo: mordeur veut trouver un chemin autour des rochers. La fonction de recherche de chemin commence à explorer la carte autour du mordeur (l'étude est indiquée par des points blancs). Au début, elle essaie d'aller directement au but, mais dès qu'elle atteint les falaises, elle «se renverse» dans les deux sens, essayant de trouver une position à partir de laquelle il sera possible de se déplacer vers le but.
L'algorithme de cette vidéo est ralenti afin que vous puissiez mieux voir comment il fonctionne.Chaque point de l'animation représente un
nœud . Chaque nœud se souvient de la distance entre le début de la recherche et une estimation de la distance de ce nœud à la cible (cette estimation est calculée par la
fonction heuristique ). C'est grâce à la fonction heuristique que A * fonctionne - il oriente l'algorithme dans la bonne direction.
Dans le cas le plus simple, cette fonction calcule simplement la distance en ligne droite du nœud à la position cible - c'est l'approche que nous avons utilisée dans Factorio depuis le tout début du développement, et grâce à elle, l'algorithme se déplace initialement en ligne droite. Cependant, ce n'est pas la seule option - si la fonction heuristique connaissait certains des obstacles, elle pourrait diriger l'algorithme autour d'elle, ce qui accélérerait la recherche, car elle n'aurait pas à examiner les nœuds supplémentaires. De toute évidence, plus l'heuristique est intelligente, plus elle est difficile à mettre en œuvre.
Une simple fonction heuristique d'estimation de distance en ligne droite est utile pour trouver des chemins sur des distances relativement courtes. Cela nous convenait dans les versions précédentes de Factorio - presque toujours les mordeurs se déplaçaient sur de longues distances uniquement parce qu'ils étaient en colère par la pollution, et cela ne se produisait pas très souvent. Cependant, nous avons maintenant de l'artillerie. L'artillerie peut facilement tirer sur un grand nombre de mordeurs de l'autre côté d'un grand lac (et les «agrifier»), après quoi ils essaient d'ouvrir la voie autour du lac. La vidéo ci-dessous montre comment le simple algorithme A * que nous avons utilisé précédemment tente de contourner le lac.
Cette vidéo montre la vitesse de l'algorithme en réalité; il n'est pas ralenti.Réduction de bloc
Trouver un chemin est une tâche longue et il existe de nombreuses techniques pour l'améliorer. Certaines de ces techniques appartiennent à la catégorie de la
recherche de chemin hiérarchique : dans ce cas, la carte est d'abord simplifiée, le chemin se trouve sur cette carte simplifiée, qui est ensuite utilisée pour trouver le vrai chemin. Je le répète, il existe plusieurs implémentations spécifiques d'une telle technique, mais toutes nécessitent une simplification de l'espace de recherche.
Comment pouvez-vous simplifier le monde de Factorio? Nos cartes sont générées de manière aléatoire et changent constamment: placer et supprimer des entités (par exemple, des collectionneurs, des murs ou des tourelles) - c'est probablement la mécanique la plus élémentaire de tout le jeu. Nous ne voulons pas recompter l'intégralité de la carte simplifiée chaque fois que nous ajoutons ou supprimons une entité. Dans le même temps, si nous simplifions à nouveau la carte chaque fois que nous avons besoin de trouver un moyen, nous pouvons facilement perdre tout le gain de performances.
L'une des personnes ayant accès au code source du jeu (Allaizn) a eu une idée. que j'ai mis en œuvre en conséquence. Maintenant, cette idée semble évidente.
Le jeu est basé sur des blocs de tuiles 32x32. Le processus de simplification remplace chaque bloc par un ou plusieurs
nœuds abstraits . Puisque notre objectif est d'améliorer la recherche d'un chemin autour des lacs, nous pouvons ignorer toutes les entités et ne considérer que les tuiles: vous ne pouvez pas vous déplacer sur l'eau, sur la terre, vous le pouvez. Nous séparons chaque bloc en
composants séparés. Un composant est une zone de tuile dans laquelle une unité peut passer d'une tuile à l'intérieur d'un composant à n'importe quelle autre tuile du même composant. Dans l'image ci-dessous, le bloc est divisé en deux composants distincts, rouge et vert. Chacun de ces composants deviendra un nœud abstrait - en fait, le bloc entier est réduit à deux «points».
La pensée la plus importante d'Allaizn était que nous n'avons pas besoin de stocker un composant pour chaque tuile de carte - rappelez-vous simplement les composants de tuile le long du périmètre de chaque bloc, car nous ne sommes intéressés que par quels autres composants sont connectés (dans les blocs voisins) de chaque composant, et cela dépend uniquement des tuiles qui sont à la frontière même du bloc.
Recherche de chemin hiérarchique
Nous avons donc compris comment simplifier la carte, mais comment l'utiliser pour trouver des chemins? Comme je l'ai dit, il existe de nombreuses techniques de recherche de chemin hiérarchique. L'idée la plus simple est de trouver le chemin à l'aide de nœuds abstraits du début à l'objectif, c'est-à-dire que le chemin sera une liste des composants des blocs que vous devez visiter. Ensuite, nous utilisons la série de bonnes vieilles recherches A * pour comprendre spécifiquement comment passer d'un composant du bloc à un autre.
Le problème ici est que nous avons trop simplifié la carte: que se passe-t-il s'il est impossible de passer d'un bloc à un autre, car certaines entités (par exemple, les roches) bloquent le chemin? Lors de la réduction des blocs, nous ignorons toutes les entités, donc nous savons seulement que les carreaux entre les blocs sont en quelque sorte connectés, mais nous ne savons absolument pas s'il est possible de passer de l'un à l'autre.
La solution est d'utiliser la simplification simplement comme une «recommandation» pour une vraie recherche. En particulier, nous l'utiliserons pour créer une version intelligente de la fonction de recherche heuristique.
En conséquence, nous avons obtenu le schéma suivant: nous avons deux pathfinder: le
pathfinder de base , qui trouve le path réel, et le
pathfinder abstrait , qui fournit la fonction heuristique au pathfinder de base. Chaque fois que le pathfinder de base crée un nouveau nœud de base, il appelle un pathfinder abstrait pour obtenir une estimation de la distance jusqu'à la cible. Le pathfinder abstrait agit dans l'ordre opposé - il commence par la cible de recherche et ouvre la voie au début, passant d'un composant du bloc à un autre. Lorsqu'une recherche abstraite trouve le bloc et le composant dans lesquels un nouveau nœud de base est créé, elle utilise la distance depuis le début de la recherche abstraite (qui, comme je l'ai dit, est la position cible de toute la recherche) pour calculer une estimation de la distance entre le nouveau nœud de base et la cible générale.
Cependant, l'exécution de l'ensemble du pathfinder pour chaque nœud individuel sera loin d'être rapide, même si le pathfinder abstrait se déplace d'un bloc à l'autre. Par conséquent, à la place, nous utilisons un schéma appelé «Reverse Resumable A *». «Inverse» signifie que, comme je l'ai dit ci-dessus, est effectué du but au début. «Renouvelable» signifie qu'après avoir trouvé un bloc intéressant pour le pathfinder de base, nous sauvegardons tous ses nœuds en mémoire. La prochaine fois que le pathfinder de base crée un nouveau nœud et a besoin d'une estimation de distance, nous regardons simplement les nœuds abstraits enregistrés à partir de la recherche précédente. Dans le même temps, il existe une forte probabilité que le nœud abstrait requis soit toujours en mémoire (au final, un nœud abstrait couvre la majeure partie du bloc, et souvent le bloc entier).
Même si le pathfinder de base crée un nœud situé dans un bloc qui n'est couvert par aucun des nœuds abstraits, nous n'avons pas besoin d'effectuer à nouveau l'intégralité de la recherche abstraite. Une caractéristique pratique de l'algorithme A * est que même après avoir «fini de travailler» et trouvé un chemin, il continue son exécution, explorant les nœuds autour des nœuds déjà étudiés. Et c'est exactement ce que nous faisons si nous avons besoin d'une estimation de distance pour un nœud de base situé dans un bloc non encore couvert par la recherche abstraite: nous reprenons la recherche abstraite à partir des nœuds stockés en mémoire jusqu'à ce qu'elle se développe jusqu'au nœud dont nous avons besoin.
La vidéo ci-dessous montre un nouveau système d'orientation en action. Les cercles bleus sont des nœuds abstraits; points blancs - recherche de base. Le pathfinder dans la vidéo est beaucoup plus lent que le jeu pour montrer comment cela fonctionne. À vitesse normale, la recherche entière ne prend que quelques ticks. Notez que la recherche de base, qui utilise toujours l'ancien algorithme que nous avons toujours utilisé, «sait» tout simplement magiquement comment se déplacer autour du lac.
Puisque le pathfinder abstrait est utilisé uniquement pour obtenir une estimation heuristique de la distance, la recherche de base peut assez facilement s'écarter du chemin proposé par la recherche abstraite. Cela signifie que même si le schéma de réduction de bloc ignore toutes les entités, le pathfinder de base peut les contourner presque sans problème. En raison de l'ignorance des entités dans le processus de simplification de la carte, nous n'avons pas besoin de la répéter à chaque fois qu'une entité est ajoutée ou supprimée, il suffit de couvrir uniquement les tuiles qui ont été modifiées (par exemple, comme dans le cas d'une décharge d'ordures), ce qui se produit beaucoup moins souvent que de placer des entités.
De plus, cela signifie que nous utilisons essentiellement le même pathfinder que nous utilisons depuis des années, seule la fonction heuristique a été mise à jour. Autrement dit, ce changement n'affectera pas de nombreux autres systèmes et n'affectera que la vitesse de recherche.