Discussion :

[ToTo13]

Postez dans cette discussion toute vos bibliothèques.

[ToTo13]

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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 :

Sélectionner tout - Visualiser dans une fenêtre à part

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

[FlashLogic]

Bonjour.

Je développe un projet nommé Daedalus Lib. Cette librairie permet de modéliser des environnements 2D sur une base de triangulation contrainte de Delaunay et de faire du pathfinding dessus.

La suite est ici:

Présentation de Daedalus Lib dans la rubrique projets