Bibliothèques (non image, IA et math)

librarie proposée par Roland_Y.

Jumper est une librairie de pathfinding sur laquelle je travaille à mes temps libres. Elle est développée en language (de script) Lua, ce qui convient parfaitement pour être embarqué et interfacé avec des projets en Lua, C/C++, etc.

Cette librairie est conçue pour résoudre les problèmes de pathfinding sur un environnement 2D fait de tuiles. Il propose plusieurs algorithmes: Astar, Breadth first search, Dijkstra, Depth first search et le plus récent Jump Point Search.

Fonctionnalités:
Jumper vous offre la possibilité d'utiliser différents algorithmes de pathfinding, différentes heuristiques de pathfinding et même de définir vos propres heuristiques. Les chemins sont calculés en temps réel, et il reste possible, avec des modifications mineures de simuler le déplacement en troupe de plusieurs unités sur un environnement 2D.

La dynamicité de la (pseudo) classe Pathfinder permet de créer des instances de recherche modulables, capables de se déplacer sur un environnement à plusieurs types de tuiles. L'on peut ainsi aisément simuler une unité marchant uniquement sur un type de tuile 'sol', ou 'eau' uniquement, ou un véhicule amphibie se déplacant à la fois sur les tuiles 'sol' et 'eau'.

Jumper offre également des itérateurs de grille 2D ainsi que la possibilité de modifier l'environnement créé de manière simple à travers des classes/objets/méthodes explicites définies dans une API facile à utiliser. Vous retrouverez également des outils/méthodes permettant de filtrer/compresser les chemins retournés, d'effectuer un 'tunnelling' lors de la recherche de chemin, etc.

Example d'utilisation:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 -- Soit un environnement 2D représenté par une matrice 2D, 0 pour les -- zones traversables, 1 pour les obstacles local map = { {0,1,0,1,0}, {0,1,0,1,0}, {0,1,1,1,0}, {0,0,0,0,0}, } -- Variable désignant les cases traversables local walkable = 0 -- Créons des références vers des classes de la librairie local Grid = require ("jumper.grid") -- La classe Grid local Pathfinder = require ("jumper.pathfinder") -- La classe Pathfinder -- Créons une grille 2D à partir de notre matrice 2D local grid = Grid(map) -- Créons une instance "Pathfinder" utilisant l'algorithme Jump Point Search, -- en précisant quelles sont les cellules traversables. local myFinder = Pathfinder(grid, 'JPS', walkable) -- Définissons les coordonnées des points de dépar et d'arrivée local startx, starty = 1,1 local endx, endy = 5,1 -- Calculons le chemin local path = myFinder:getPath(startx, starty, endx, endy) -- Si le chemin a été trouvé if path then print(('Chemin trouvé! Longueur: %.2f'):format(path:getLength())) -- Itérons le long du chemin pour afficher les coordonées des noeuds for node, count in path:nodes() do print(('Step: %d - x: %d - y: %d'):format(count, node:getX(), node:getY())) end end
Code:

1 2 3 4 5 6 7 8 9 --> Output: --> Chemin trouvé! Longueur: 8.83 --> Step: 1 - x: 1 - y: 1 --> Step: 2 - x: 1 - y: 3 --> Step: 3 - x: 2 - y: 4 --> Step: 4 - x: 4 - y: 4 --> Step: 5 - x: 5 - y: 3 --> Step: 6 - x: 5 - y: 1
Benchmarking:
Il y a un dépôt dans lequel je maintiens un programme en ligne de commande qui permet de tester la performance de la librarie Jumper. Ce programme n'est pas à jour, car il teste la version 1.6.3 de la librairie, mais il donne néammoins une idée très précise de ses performances. Les cartes 2D sur lesquels les tests sont effectués proviennent de la compétition GPPC 2012.
Github :Jumper-Benchmark

Code source:
Le code source est disponible pour tous, open-source, sous license MIT. J'essaie, tout au long de ma progression dans le code, d'avoir un produit stable, simple à utiliser et une librarie rapide. L'API est documenté, avec des examples de code disponibles sur le dépôt Git.

Tests et spécifications:
J'utilise un framework de tests unitaires Telescope afin de verifier la stabilité de l'ensemble entre différents commits. Le tout est relié à une plate-forme d'intégration continue bien connue, Travis.

Page du projet: Jumper
Source (dernière release, stable) : 1.8.1
Autres releases, stables: Tags
Source (version development, instable) : Dépôt Github