µLua DS - Forum officiel | Official forum Index du Forum

µLua DS - Forum officiel | Official forum
Le bon endroit pour en savoir plus sur MicroLua et pour parler de vos projets ! | The right place to learn more about MicroLua and talk about your projects !

 FAQFAQ   RechercherRechercher   MembresMembres   GroupesGroupes   S’enregistrerS’enregistrer   ProfilProfil   Se connecter pour vérifier ses messages privésSe connecter pour vérifier ses messages privés   ConnexionConnexion 

[Lua/Lib] Jumper, Pathfinder 2D (extrêmement) rapide!

 
Poster un nouveau sujet   Répondre au sujet    µLua DS - Forum officiel | Official forum Index du Forum -> Section française -> Coin du dév' -> Librairies
Sujet précédent :: Sujet suivant  
Auteur Message
Roland_Yonaba


Hors ligne

Inscrit le: 02 Sep 2011
Messages: 22

MessagePosté le: Lun 28 Mai 2012 - 15:15    Sujet du message: [Lua/Lib] Jumper, Pathfinder 2D (extrêmement) rapide! Répondre en citant

Salut,




En prélude à un mon projet personnel de RTS (Age of Nations) sur lequel je prévois de retravailler bientôt, j'ai développé une librairie de pathfinding.





Le pathfinding ou "Recherche de chemin" est un algorithme essentiel à tout jeu de simulation de stratégie en temps réel. C'est l'algorithme sur lequel les différentes entités définies dans le jeu se baseront pour trouver le chemin à suivre sur une carte en évitant de manière intelligente les obstacles.


Le problème du "pathfinding" fait appel aux algorithmes d'intelligence articielle. A l'heure actuelle, il existe plusieurs types d'algorithmes basés sur les graphes : Dijkstra, Bellman-Ford, DFS, BFS, ... sans compter les variantes... 
Mais de façon communément admise, l'algorithme le plus utilisé, sous diverses formes est le pathfinding A* (prononcer "A-star"). En effet, il est généralement préféré car il permet de trouver un chemin rapidement -s'il en existe au moins un - sans pour autant que cela soit forcément le meilleur chemin.


Jumper est une libre implémentation de l'algorithme A-star que vous pourrez utiliser sur une carte 2D. C'est une librairie extrêmement rapide, car son implémentation se base deux concepts qui se révèlent très efficaces: l'emploi de tas binaires (qui permettent d’accélérer les opérations de recherche lorsque l'algorithme tourne) et l'utilisation de l'algorithme Jump Point Search développé par Danier Harabor et Alban Grastien qui permet d'accélérer le pathfinding.


Les résultats sont tout simplement bluffants. Les benchmarks que j'ai effectué sur des cartes très larges provenant de Dragon Age : Origins (voir movingAI Labs) permettent de résoudre le problème de pathfinding dans des délais de l'ordre des millisecondes.


Intégrer Jumper dans vos propres projets est très simple. Voici le code minimal :


Citation:
-- Appeler la librarie
local Jumper = require('Lib')


--Créer sa carte 2D, ici une carte 3x3
-- 0 représente une cellule 'traversable'
-- Les autres valeurs représentent des obstacles


local map = {
      {3,0,0},
      {0,2,0},
      {0,1,1},
      }


local walkable = 0  -- walkable désignera alors les valeurs traversables sur la carte 2D
local allowDiagonal = true -- Les mouvements en diagonales sont autorisés


-- On initialise le pathfinder
local pather = Jumper(map,walkable,allowDiagonal) 


-- On cherche le chemin de (1,3) à (3,1)
local path, length = pather:searchPath(1,3,3,1)



Le chemin ainsi que sa longueur sont retournés dans les variables path et length. A vous de jouer! 


Pour plus de détails, consulter le Readme.


Jumper est toujours en cours d'évolution, car certaines fonctionnalités restent à implémenter. Mais la version disponible (v0.2) est parfaitement fonctionnelle et déjà utilisable.


En plus de la librairie, vous trouverez également deux fichiers complémentaires avec l'extension *.love.
- Jumper_(Demo).love est une démo pour PC (Windows, Mac, Linux) qui vous permet de tester l'effectivité de la librairie.
- Jumper_(Tests).love est une application PC, plus orientée développeur, qui effectue des benchmarks sur des cartes de Dragon Age. Fonctionnelle sur Windows, Linux. Les utilisateurs de Mac rencontreront un bug avec, à fixer plus tard.


Notez bien: Pour utiliser l'une ou l'autre de ces deux démos, vous devrez vous procurer les binaires du framework Löve, en version 0.8.0. Ils sont disponibles pour toutes architectures ici.


Téléchargement : Package complet : Jumper
Page: Jumper


Revenir en haut
Publicité






MessagePosté le: Lun 28 Mai 2012 - 15:15    Sujet du message: Publicité

PublicitéSupprimer les publicités ?
Revenir en haut
Fantasix
Modérateur

Hors ligne

Inscrit le: 26 Avr 2010
Messages: 1 317
Localisation: SCREEN_UP, en -1, -1

MessagePosté le: Lun 28 Mai 2012 - 16:20    Sujet du message: [Lua/Lib] Jumper, Pathfinder 2D (extrêmement) rapide! Répondre en citant

Ah, ça c'est intéressant !

Moi qui utilise l'A-Star depuis le début, j'vais peut-être tester celui-ci Smile

Merci,

Fanta'
_________________


BMA News :

Création du Homebrew Storage en cours ...


Revenir en haut
Visiter le site web du posteur
Roland_Yonaba


Hors ligne

Inscrit le: 02 Sep 2011
Messages: 22

MessagePosté le: Lun 28 Mai 2012 - 17:22    Sujet du message: [Lua/Lib] Jumper, Pathfinder 2D (extrêmement) rapide! Répondre en citant

Mais je t'en prie! 
Very Happy


Revenir en haut
thermo_nono
Modérateur

Hors ligne

Inscrit le: 31 Déc 2008
Messages: 2 415
Localisation: La Géhenne

MessagePosté le: Lun 28 Mai 2012 - 19:21    Sujet du message: [Lua/Lib] Jumper, Pathfinder 2D (extrêmement) rapide! Répondre en citant

Génial !  Okay  
ça c'est un truc que je n'ai pas réussi à faire (avec mon jeu de tanks).. il faudra que je le refasse avec cette lib.. 
merci
_________________
“Qui reçoit une idée de moi reçoit de la connaissance sans diminuer la mienne, comme celui qui allume sa chandelle à la mienne reçoit la lumière sans me plonger dans l’obscurité.” - Thomas Jefferson


Revenir en haut
Visiter le site web du posteur MSN
Xaychru04


Hors ligne

Inscrit le: 04 Mar 2011
Messages: 42
Localisation: Error: Localisation was not declared in this scope.

MessagePosté le: Mar 29 Mai 2012 - 19:30    Sujet du message: [Lua/Lib] Jumper, Pathfinder 2D (extrêmement) rapide! Répondre en citant

Ah ouais, ça peut être vraiment utile !

*Pense à un tower defense en uLua ^^*

Je testerai dès que j'aurai le temps...
_________________
http://xaychru04.tumblr.com/


Revenir en haut
Skype
Roland_Yonaba


Hors ligne

Inscrit le: 02 Sep 2011
Messages: 22

MessagePosté le: Mar 29 Mai 2012 - 20:51    Sujet du message: [Lua/Lib] Jumper, Pathfinder 2D (extrêmement) rapide! Répondre en citant

Xaychru04 a écrit:
Ah ouais, ça peut être vraiment utile !

*Pense à un tower defense en uLua ^^*

Je testerai dès que j'aurai le temps...



Merci.
Dans l'éventualité où quelqu'un décelerait un bug, ou autre comportement anormal,
l'idéeal serait de poster une message sur la page du projet, dans la section réservée aux reports de bugs...
Ou sinon, ici.


Revenir en haut
Reylak
Administrateur

Hors ligne

Inscrit le: 24 Nov 2008
Messages: 2 838
Localisation: Toulouse

MessagePosté le: Mar 29 Mai 2012 - 21:51    Sujet du message: [Lua/Lib] Jumper, Pathfinder 2D (extrêmement) rapide! Répondre en citant

Pour le tower defense, même avec différentes maps, même avec des carrefours dans la map, je ne pense pas que le path finding soit utile puisque finalement, les trajets sont toujours les mêmes. ^^
_________________


Plein d'infos sur le SourceForge !


Revenir en haut
Visiter le site web du posteur MSN Skype
spectrenoir06


Hors ligne

Inscrit le: 13 Jan 2012
Messages: 184
Localisation: Paris

MessagePosté le: Mar 29 Mai 2012 - 22:17    Sujet du message: [Lua/Lib] Jumper, Pathfinder 2D (extrêmement) rapide! Répondre en citant

Super j'y connais rien en patchfinder et IA


*pense a pacman*


Revenir en haut
Visiter le site web du posteur
Xaychru04


Hors ligne

Inscrit le: 04 Mar 2011
Messages: 42
Localisation: Error: Localisation was not declared in this scope.

MessagePosté le: Mar 29 Mai 2012 - 22:19    Sujet du message: [Lua/Lib] Jumper, Pathfinder 2D (extrêmement) rapide! Répondre en citant

Hum, pour un TD ou le programmeur ne veut pas s'embéter, il ne gère pas les collisions tours/ennemis et oblige le joueur a mettre ses défenses dans des zones ou l'ennemi ne va pas. Mais imagine un TD un minimum réaliste, les ennemis arrivent de la gauche et vont vers le bord droit, et ils y vont directement. Imagine que le joueur place des tourelles au milieu, le pathfinding peut se révéler très utile pour recalculer le trajet qui passe a coté des tourelles Smile
_________________
http://xaychru04.tumblr.com/


Revenir en haut
Skype
Reylak
Administrateur

Hors ligne

Inscrit le: 24 Nov 2008
Messages: 2 838
Localisation: Toulouse

MessagePosté le: Mer 30 Mai 2012 - 16:53    Sujet du message: [Lua/Lib] Jumper, Pathfinder 2D (extrêmement) rapide! Répondre en citant

Ah ouais pardon, j'avais oublié ces TD libres où tu mets tes tours où tu veux ^^'
Du coup oui, ça sert Smile
_________________


Plein d'infos sur le SourceForge !


Revenir en haut
Visiter le site web du posteur MSN Skype
Xaychru04


Hors ligne

Inscrit le: 04 Mar 2011
Messages: 42
Localisation: Error: Localisation was not declared in this scope.

MessagePosté le: Mer 30 Mai 2012 - 19:46    Sujet du message: [Lua/Lib] Jumper, Pathfinder 2D (extrêmement) rapide! Répondre en citant

En tout cas bravo,

Je l'ai testé et ça fonctionne parfaitement, pour le moment en tout cas puisque j'ai juste recopié le code d'exemple Smile
Je vais faire quelques tests (Avec une plus grande map) et si c'est fonctionnel, et il n'y a pas de raisons que ça ne le soit pas, quelqu'un d'autre et moi allons créer un homebrew avec...

Encore merci pour cette lib Wink


Edit:

J'ai un problème avec la librairie: j'ai rajouté un petite boucle à la fin du programme d'exemple, et quand je lance le programme, ça revient tout de suite au shell...
Ensuite, quand je relance le programme, cette fois, il me sort plein d'erreurs du style "loop or previous error loading module "libs" "...
J'ai testé avec un émulateur (DeSmuMe) et ça me fait exactement pareil.

J'espère que je n'ai pas fait de fausse manip, voici mon dossier au cas ou: ça
_________________
http://xaychru04.tumblr.com/


Revenir en haut
Skype
Roland_Yonaba


Hors ligne

Inscrit le: 02 Sep 2011
Messages: 22

MessagePosté le: Sam 1 Sep 2012 - 13:23    Sujet du message: [Lua/Lib] Jumper, Pathfinder 2D (extrêmement) rapide! Répondre en citant

Salut.
Je ressors ce topic des décombres...


Xaychru04 a écrit:


J'ai un problème avec la librairie: j'ai rajouté un petite boucle à la fin du programme d'exemple, et quand je lance le programme, ça revient tout de suite au shell...
Ensuite, quand je relance le programme, cette fois, il me sort plein d'erreurs du style "loop or previous error loading module "libs" "...
J'ai testé avec un émulateur (DeSmuMe) et ça me fait exactement pareil.

J'espère que je n'ai pas fait de fausse manip, voici mon dossier au cas ou: ça
Ce projet n'est probablement plus d'actualité, vu le temps que j'ai mis avant de repasser par ici. Mais je récupère néanmoins tes sources, et j'y jette un coup d'oeil au plus vite.

Revenir en haut
Contenu Sponsorisé






MessagePosté le: Aujourd’hui à 03:46    Sujet du message: [Lua/Lib] Jumper, Pathfinder 2D (extrêmement) rapide!

Revenir en haut
Montrer les messages depuis:   
Poster un nouveau sujet   Répondre au sujet    µLua DS - Forum officiel | Official forum Index du Forum -> Section française -> Coin du dév' -> Librairies Toutes les heures sont au format GMT + 1 Heure
Page 1 sur 1

 
Sauter vers:  

Index | Creer un forum | Forum gratuit d’entraide | Annuaire des forums gratuits | Signaler une violation | Conditions générales d'utilisation
Powered by phpBB © 2001, 2005 phpBB Group
Traduction par : phpBB-fr.com