Explorer des algorithmes de recherche de chemin bien connus avec la bibliothèque graphique SFML | de Anton Yarkov | août 2023

Il y a quelques années, Yandex a organisé un concours appelé Coursiers de robots avec un prix alléchant : un billet pour un conférence fermée sur la conduite autonome pour les professionnels. Le concours ressemblait à un jeu. Les participants ont été chargés de trouver les itinéraires optimaux sur une carte et d’optimiser la livraison à l’aide de coursiers robotisés.

En approfondissant le sujet, j’ai découvert que même si la recherche d’itinéraire était un problème résolu, elle continuait d’intéresser la communauté professionnelle du développement de jeux. Entre 2010 et 2020, les ingénieurs apporté des optimisations significatives à l’algorithme A*, particulièrement bénéfique pour les jeux AAA avec des cartes massives. En lisant articles et documents de recherche sur ces optimisations a été une expérience passionnante.

De plus, les exigences du concours ont été conçues pour permettre une évaluation facile des résultats du programme par le système de test du concours. En conséquence, l’accent a été peu mis sur la visualisation.

J’ai trouvé fascinant d’explorer ce domaine et de développer une petite application qui utilise des algorithmes graphiques bien connus pour trouver des itinéraires sur une carte quadrillée. Pour visualiser mes découvertes, j’ai utilisé la bibliothèque graphique SFML.

Ce projet s’appuie sur l’un de mes efforts précédents, dans lequel j’ai démontré que quatre algorithmes de recherche de chemin bien connus (BFS, DFS, Dijkstra et A*) ne sont pas fondamentalement différents et peuvent être implémentés universellement. Cependant, mettre en évidence des différences de performances significatives entre ces algorithmes dans ce projet était un défi.

Mon objectif est d’utiliser des données de test améliorées dans cet article et de concevoir quelque chose de visuellement excitant. Bien que la tâche du concours Yandex mentionnée précédemment corresponde bien à mes objectifs, je ne résoudrai pas leur problème spécifique ici car elle repose fortement sur leur système de test, qui est actuellement indisponible.

Au lieu de cela, j’extraireai des idées générales sur les paramètres d’entrée de ce concours et créerai mon implémentation.

Imaginez une ville techniquement avancée et innovante où l’avenir est arrivé depuis longtemps. Dans cette ville, les robots coursiers livrent la plupart des commandes, et il est devenu rare que quelqu’un livre une commande dans un café. Dans cette tâche, nous vous invitons à participer à la recherche des itinéraires optimaux pour livrer les commandes efficacement.

Imaginons la ville comme une carte N × N. Pour simplifier, nous supposons que chaque robot occupe précisément une cellule, et que chaque cellule peut être praticable ou non pour les robots. En une seule étape, un robot peut se déplacer dans l’une des quatre directions cardinales (haut, bas, gauche ou droite) si la cellule cible est libre.

Et j’ignore le reste de la tâche d’origine :

Au début du test, vous devez indiquer le nombre de robots que vous souhaitez utiliser pour livrer les commandes et leurs coordonnées initiales. La construction de chaque robot coûtera Costc roubles.

Suivant, T des itérations de la simulation seront effectuées. Une itération représente une minute virtuelle et comprend 60 secondes. À chaque itération, votre programme recevra le nombre de nouvelles commandes et, en réponse, le programme devra vous indiquer les actions effectuées par chaque robot (60 actions par robot).

Pour chaque commande livrée avec succès, vous recevrez max(0, MaxTips — DeliveryTime) dollars en pourboires, où MaxTips est le nombre maximum de pourboires pour une commande, et DeliveryTime est le temps écoulé entre l’apparition de la commande et sa livraison, en secondes.

Le nombre total de points que vous gagnez dans un test est calculé par la formule TotalTips — R × Costcoù TotalTips est le nombre total de pourboires gagnés, R est le nombre de robots utilisés, et Costc est le coût de construction d’un robot. Le Costc et MaxTips les valeurs sont définies dans chaque test. Si vous avez gagné moins de pourboires que vous n’en avez dépensé pour fabriquer des robots, votre total de points sera de 0. Vous recevrez également 0 point pour le test si vous effectuez des actions incorrectes.

Saisir

Le programme utilise une entrée standard pour lire les paramètres. Cette approche nous permet de spécifier des données de test de diverses complexités à l’aide de fichiers d’entrée.

La première ligne de saisie contient trois nombres naturels : N (la taille du plan de la ville), MaxTips (le nombre maximum de pourboires par commande), et Costc (le coût de construction d’un robot). J’ignore MaxTips et Costc paramètres pour ma première implémentation et je pourrai peut-être l’envisager à l’avenir.

Ensuite, chacune des N lignes suivantes contient N caractères représentant le plan de la ville. Chaque chaîne peut être composée de deux types de caractères :

• # — indique une cellule occupée par un obstacle
• . — indique un espace libre

Ensuite, vous recevrez deux nombres naturels : T et D (T ≤ 100,000, D ≤ 10,000,000). T représente le nombre d’itérations d’interaction et D représente le nombre total de commandes.

Sortir

Votre tâche consiste à visualiser la carte et les itinéraires optimaux à l’aide de la bibliothèque graphique SFML.

J’aime les cartes représentées sous forme de grille de cellules. Ainsi, je préfère restituer tous les résultats et les cartographier sous forme de grille, cellule par cellule.

Il existe également une option pour exécuter une recherche de chemin directement sur la grille sans utiliser de structure de données supplémentaire (je l’ai implémenté à des fins d’apprentissage. Vous pouvez voir les résultats dans le code).

Cependant, grâce à une grille, il est facile de représenter une carte sous forme de graphique d’une manière ou d’une autre. Je préfère utiliser une liste de cellules adjacentes pour la plupart des algorithmes comme BFS, Dijkstra et A-Star. Pour des algorithmes comme Bellman-Ford, l’utilisation d’une liste de bords au lieu d’une liste de contiguïté peut avoir du sens. C’est pourquoi si vous explorez la base de code, vous trouverez tout cela, et ce sont tous des exemples fonctionnels.

Pour diviser la logique et la responsabilité, j’ai un Navigator entité responsable de l’exécution de la recherche de chemin conformément à la configuration des commandes et des tâches spécifiées via AppConfig fichier et les fichiers de cartes associés.

App Config ressemble à ça:

{
"font": "../../data/arial.ttf",
"map": "../../data/maps/test_29_yandex_weighten_real_map",
"shadow": false,
"map_": "../../data/maps/test_08_low_res_simple_map",
"map__": "../../data/maps/test_10",
"map___": "../../data/maps/test_07_partially_blocked_map",
...

Noter que “map_», «map__», etc., ne sont pas des propriétés de configuration. Ils sont ignorés lors de l’exécution de l’application. Puisqu’il n’y a aucun moyen de commenter une partie du fichier JSON, j’utilise le soulignement dans le nom de la propriété afin qu’il puisse rester dans le fichier de configuration mais ne pas être utilisé.

Le fichier de carte ressemble à ça:

25 50 150
#########################
#########################
#########################
###.......#####.......###
###.......#####.......###
###.......#####.......###
###...................###
###.......#####.......###
###.......#####.......###
###...................###
######.###########.######
######.###########.######
######.###########.######
###.......#####.......###
###.......#####.......###
###.......#####.......###
###.......#####.......###
###.......#####.......###
###.......#####.......###
###.......#####.......###
######.###########.######
#########################
#########################
#########################
#########################
2 4
2
6 6 4 20

Il s’agit de l’un des exemples les plus simples contenant des cellules bloquées ou non. J’ai préparé de nombreux exemples de paramètres d’entrée et de données de test. En commençant par de très petites parties qui vous permettent de déboguer et d’apprendre le code, pour finir par un énorme morceau de carte (de la vraie ville existante) qui nous permet de mesurer les performances d’un algorithme Graph.

Lorsqu’une carte contient uniquement des cellules avec un état binaire (bloqué ou non bloqué), n’importe quelle arête d’un graphique existe.

Pour trouver un chemin dans le graphique, nous devons le représenter efficacement. Comme dans mon article précédent, j’ai utilisé un liste de contiguïté avec la relation comme Vector(NodeId)->points to->Vector(Neighbour Nodes):

typedef std::vector<std::vector<std::shared_ptr<Cell>>> Graph;

Il est intéressant de noter que lors de l’exploration de grilles, il n’est pas du tout nécessaire d’utiliser des graphiques. Nous sommes capables de parcourir des grilles en utilisant les algorithmes BFS/DFS cellule par cellule sans penser aux arêtes. Voir la méthode _GetPathByBFSOnGrid.

Tout d’abord, le code d’initialisation lit le fichier et le convertit en la grille ligne par ligne et colonne par colonne. Voici à quoi cela ressemble :

bool RectangularMap::LoadMap(const std::string& filepath, bool shadow)
{
...
// Fill the grid.
_verticesNumber = 0;
for (int row = 0; row < _height; row++)
{
...
for (int col = 0; col < _width; col++)
{
int x = col;
int y = row;
if (line(col) == BLOCK_CELL)
{
// Create a shared pointer to safely pass pointers between the classes.
_grid(row)(col) = std::make_shared<Cell>(x, y, line(col), 
blockColor, shadow, _scaleFactor);
}
else
{
...
}
}
}
// Make a graph
InitialiseGraph();
...
}

Ensuite, il crée un véritable graphique comme une liste de contiguïté:

void RectangularMap::InitialiseGraph()
{
MapBase::InitialiseGraph();
...
unordered_set<int> visited;
for (int rr = 0; rr < _grid.size(); rr++)
{
for (int cc = 0; cc < _grid(rr).size(); cc++)
{
if (_grid(rr)(cc)->GetId() > -1)
{
for (int i = 0; i < 4; i++)
{
int r = rr + dr(i);
int c = cc + dc(i);
if (r >= 0 && c >= 0 && r < _width && c < _height &&
_grid(r)(c)->GetId() > -1)
{
if (_isNegativeWeighten)
{
...
}
else
{
_adjacencyList(_grid(rr)(cc)->GetId()).push_back(_grid(r)(c));
}
}
}
}
}
}
}

La représentation en grille est utile pour dessiner sur l’écran à l’aide de la bibliothèque SFML. Nous pouvons le dessiner en créant des objets géométriques (c’est précisément ce que je fais pour les petites cartes) :

...
for (int j = _visibleTopLeftY; j < _visibleBottomRightY; j++)
{
for (int i = _visibleTopLeftX; i < _visibleBottomRightX; i++)
{
_grid(j)(i)->Draw(_window, _scaleFactor);
}
}
...
sf::RectangleShape tile;
tile.setSize(sf::Vector2f(_cellSize - 5, _cellSize - 5));
tile.setPosition(sf::Vector2f(_x * _cellSize, _y * _cellSize));
tile.setFillColor(_color);
window.draw(tile);

Ou, pour des cartes plus grandes, nous pouvons le faire pixel par pixel, ce qui est plus efficace. Voici à quoi cela ressemble :

sf::Uint8* pixels = new sf::Uint8(_width * _height * 4);
for (int j = _visibleTopLeftY; j < _visibleBottomRightY; j++)
{
for (int i = _visibleTopLeftX; i < _visibleBottomRightX; i++)
{
int index = (_grid(j)(i)->GetY() * _width + _grid(j)(i)->GetX());
sf::Color color = _grid(j)(i)->GetColor();
pixels(index * 4) = color.r;
pixels(index * 4 + 1) = color.g;
pixels(index * 4 + 2) = color.b;
pixels(index * 4 + 3) = color.a;
}
}
sf::Texture texture;
texture.create(_width, _height);
texture.update(pixels);
sf::Sprite sprite;
sprite.setTexture(texture);
sprite.setScale(cellSize, cellSize);
_window.draw(sprite);

Enfin, voyons ce qu’est une carte définie par le fichier test_25_xmax ressemblerait.

Initialement, les définitions du fichier ressemblent à ceci :

..............C.................
..............#.................
.............###................
............#####...............
...........#######..............
..........##1###2##.............
.........###########............
........##3######4###...........
.......###############..........
......#################.........
.....###################........
....#####################.......
.............###................
.............###................
.............###................

Et une carte rendue avec SFML ressemble à ceci :

Parce que je voulais que tout cela soit contrôlé par l’utilisateur avec le clavier, j’ai laissé toute la logique de comportement de l’utilisateur dans le main.cpp. J’aime l’appeler Controller logique.

La bibliothèque SFML facilite la gestion des événements clavier :

while (window.isOpen())
{
Event event;
while (window.pollEvent(event))
{
if (event.type == Event::Closed)
window.close();
if (event.type == Event::KeyPressed && event.key.code == Keyboard::Space)
{
... Do what you need here
}
}
}

L’idée principale est qu’appuyer sur le bouton espace déclenchera la lecture et le rendu du fichier carte par le programme. Ensuite, vous pouvez charger des tâches de routage et calculer le chemin le plus court entre deux points sur une carte en créant un deuxième déclencheur (appuyez à nouveau sur le bouton espace). Voici comment procéder :

...
if (navigator->IsReady())
{
navigator->Navigate(); // Finding route between two points
}
else
{
if (map->IsReady()) // Second SPACE press runs the routing
{
skipReRendering = true;
if (navigator->LoadTasks(filepath))
{
navigator->SetMap(map);
}
}
else // Load and draw map
{
drawLoading(window, font);
if (!map->LoadMap(filepath, shadowed))
{
return 0;
}
drawProcessing(window, font);
}
}
...

Je voulais jouer avec davantage d’algorithmes Graph, qui ont tous leurs limites, j’ai donc également implémenté des cartes multicolores que des graphiques multipondérés peuvent représenter.

Chaque cellule est colorée, ce qui signifie que le bord existe non seulement mais qu’il applique également un certain poids (ou des frais, ou une amende, comme vous l’appelez). Ainsi, le bord peut être bloqué, à moitié bloqué, non bloqué, etc. Vous avez compris l’idée.

Alors maintenant, j’ai implémenté des cartes multicolores qui ont l’air joyeuses, comme un jeu prêt à jouer (exemple du fichier test_31_multi_weight_graph_map) :

Certains fichiers de configuration contiennent des cartes plus complexes de villes réellement existantes, comme test_29_yandex_weighten_real_map:

En guise de défi, nous devrions désormais gérer des cartes avec des configurations très flexibles. RectangularMap.cpp contient beaucoup de logique à l’intérieur, y compris tous les algorithmes graphiques et même plus que nécessaire (car j’aime jouer avec les choses, même si ce n’est pas particulièrement utile pour l’instant).

j’ai implémenté BFS#Ligne 598, Dijkstra#Ligne 299, A-Star#Ligne 356, Bellman-Ford#Ligne 428 algorithmes, et un certain nombre d’algorithmes « utilitaires » supplémentaires comme le tri topologique, le chemin source unique, qui ne sont pas utiles pour l’état actuel de l’application (car ils fonctionnent sur des graphiques directement acycliques, qui ne sont pas le type de graphiques que j’utilise actuellement), mais J’ai quelques idées pour l’utiliser dans de futures améliorations.

Je n’ai pas peaufiné tout le code, mais cela me permet (et, je l’espère, vous permettra) de jouer avec le code et de comparer les mesures de performances.

Désolé pour quelques lignes commentées ici et là, peut-être du code sale… c’est toute une façon d’apprendre :). Pour avoir une idée de ce qu’il y a à l’intérieur, je vous recommande de consulter le RectangularMap.h.

Il existe également des fonctionnalités amusantes, comme une fonctionnalité Focus permettant de restituer uniquement une partie particulière de la carte. Il change le focus en restituant la partie nécessaire à l’aide du Observer modèle lorsque l’utilisateur appuie sur les boutons PgDown ou PgUp. Améliorer cette fonctionnalité et implémenter la fonctionnalité « Zoom » est assez simple. Utilisez-le comme devoir si vous l’aimez.

Fonction de focus avec un fichier de carte fonctionnel, test_29_yandex_weighten_real_map:

Le diagramme des classes ressemble à ceci :

La partie la plus amusante est d’exécuter cette petite application et de jouer avec les variations de sa configuration et de ses algorithmes. Vous pouvez faire de nombreuses expériences en utilisant divers fichiers de carte comme paramètres d’entrée avec différentes données de test et en modifiant la logique du code.

Après avoir démarré, vous devez appuyer sur ESPACE. Une application restituera une carte en fonction du fichier de configuration, et il est tout à fait logique de commencer à explorer à partir des cas de test les plus simples, puis de passer aux plus complexes.

Appuyer à nouveau sur ESPACE exécute les algorithmes de routage et trouve le chemin entre le début et l’ordre le plus proche. Soit dit en passant, ce n’est pas encore fait, mais il est facile d’implémenter des moyens de lire tous les autres ordres disponibles dans les fichiers de configuration de carte et d’exécuter une recherche de chemin pour chacun d’entre eux.

Voici l’itinéraire trouvé sur la carte définie par fichier test_18_yandex_super_high_res:

Il est également capable de trouver des itinéraires sur les cartes qui simulent des villes existantes, comme test_29_yandex_weighten_real_map:

Trouver des chemins efficaces entre deux coordonnées devient un défi pour des algorithmes comme BFS, mais peut être facilement réalisé par A-star.

Sur la base des cellules trouvées dans les fichiers de configuration de la carte, l’application traitera la carte comme un graphique pondéré ou non pondéré et sélectionnera le bon algorithme (et vous pourrez également le modifier facilement). Il est facile de voir la différence entre les performances BFS et A-Star :

Sur ce, je veux vous laisser tranquille et vous laisser jouer avec ces exemples de code. J’espère que vous le trouverez fascinant et que vous en apprendrez beaucoup.

Restez à l’écoute!

1. Implémentation universelle des algorithmes BFS, DFS, Dijkstra et A-Star
2. JPS+ : plus de 100 fois plus rapide que A* par Steve Rabin
3. A* Optimisations et améliorations par Lucho Suaya