Pathfinding Cooperatif

[Fig]

J'ai enfin terminé mon pathfinding coopératif pour mon (futur arf) RTS... Bien sûr programmé avec PB !
J'ai aussi fini la partie HPA*.
Le pathfinding coopératif permet aux unités de se mettre d'accord et d'éviter les situations de blocage.
Il n'est pas nécessaire de relancer le pathfinding A* puisqu'il s'agit en fait d'un A* en 3 dimension: X,Y et Temps. (Bien sûr A* est implémenté avec un tas et la map une hashtable "x/y/t".)

Ca donne une impression d'intelligence aux agents.

Ajouter/Effacer un obstacles [clic Gauche]
Sélectionner une unité [clic Gauche]
Pathfind de l'unité vers un but [clic droit]
Ajouter une unité [Espace]
Supprimer l'unité sélectionnée [Suppr]

Voici le lien pour télécharger le listing test.
http://wordoxhelper.free.fr/Projet%20pathfinding.zip
Le fichier à compiler est Main.

Problèmes connus de ce test.
1- Deadlock possible si on joue dans un couloir de 1 case de large (les unités se repoussent à droite, puis à gauche sans arrêt)
2- Ne pas ajouter d'unité sur le chemin et pendant le déplacement d'une unité; à moins de relancer son pathfinding par clic droit.
3- Ne pas envoyer d'unité dans un espace inaccessible.[résolu]
4- agent devient passant dans certaines configurations à partir de 11...
5- FPS bas à revoir[résolu]
Merci de reporter tout autre bug.

MAJ 25/03/14: selection multiple et HPA à un niveau intégré.
MAJ 28/03/14: Code revu, plus de plantage, pathfind vers le point le plus proche si but inaccessible.

Voici le lien en anglais de l'article qui m'a inspiré: http://www0.cs.ucl.ac.uk/staff/D.Silver ... Wisdom.pdf
Voici le lien en anglais de l'article qui m'a inspiré pour le HPA*: http://webdocs.cs.ualberta.ca/~jonathan ... s/jogd.pdf

[falsam]

Il y a aussi un bug dans le download

[Fig]

A peine posté, tu cliques !
Ca y est, ça doit être bon...

[falsam]

Yeah c'est bon et je teste ça tout de suite

[falsam]

A peine télécharger et je rale !!

Code : Tout sélectionner

XIncludeFile "C:\Users\François\Desktop\Projet pathfinding\Heap Final.pb"
XIncludeFile "C:\Users\François\Desktop\Projet pathfinding\path Astar.pb"
XIncludeFile "C:\Users\François\Desktop\Projet pathfinding\Hpa.pb"
XIncludeFile "C:\Users\François\Desktop\Projet pathfinding\Agent.pb"
XIncludeFile "C:\Users\François\Desktop\Projet pathfinding\cooperative.pb"

Merci françois ! ha ha ha

[Fig]

Le fichier à compiler est Main.
Merci de modifier le chemin lignes 14, 21, 22, 23, 24, 25.

T'avais qu'a lire ce que j'ai posté au lieu de cliquer, cliquer...
Malheureusement on ne peut mettre de variables textes dans les Xinclude...

[falsam]

T'avais qu'a lire ce que j'ai posté au lieu de cliquer, cliquer...

J'étais trop presser de voir ce code. Joli travail en tout cas. Pas trop mal à la tête ? Merci pour ce partage Fig.

[Fig]

Ca va... j'ai codé ça en quelques jours (mais jours complets), mais il est vrai que j'ai fait de tests précédemment, notamment les différentes solutions concernant le A* (A* avec différents tris, ou fringe search par exemple), les différentes solutions d'abstraction pour réduire le graph (POV A*, HPA*, Quadtree, hybride...)
Je suis arrivé à la conclusion que la meilleur implémentation est bien le A* basé sur un Tas et le HPA* à un seul niveau hierarchique pour les grand cartes en ce qui concerne mon besoin.

[falsam]

... en ce qui concerne mon besoin.

Application qui va voir le jour ? un jeu ?

[Fig]

Un jeu façon Age of empire...

[graph100]

tu peux utiliser une constante, ou bien tout mettre en relatif !!!

Code : Tout sélectionner

XIncludeFile "Heap Final.pb"
XIncludeFile "Path Astar.pb"
XIncludeFile "Hpa.pb"
XIncludeFile "Agent.pb"
XIncludeFile "cooperative.pb"

ca marche très bien.
de même pour le chemin global.

Beau boulot ! C'est vraiment super comme logique

[Fig]

Merci pour le chemin relatif

J'ai modifié le programme pour qu'il soit plus "userfriendly" pour jouer avec.

[G-Rom]

La démo plante quand il n'y a pas de chemin possible.
Si tu programmes un rts, quand est il des unités ennemies ? vont elles coopératif avec le camp adverse ?

[Fig]

Il me reste beaucoup à faire encore, dans le désordre:

1- La coopération doit se faire entre agent d'une meme équipe, il faut que je rajoute une dimension à mes procédures pour les différentier.
2- Transformation de la procédure de tris par tas optimisé en asm. (déja très rapide mais peu mieux faire encore)
3- multithreading de cette recherche
4- résoudre le deadlock par la gestion des priorités entre agents
5- Mise en place d'un "langage" pour le dialogue avec l'Ia et l'interface utilisateur afin de permettre les scénarios (ii).
6- Améliorer l'affichage, intégrer mon moteur 2D iso déja fait. (zoom et animation du terrain- rivière/eau déja fonctionnel)
...
Xieme- graphismes.... je demanderai à une connaissance s'il veut s'associer quand tout sera fini, pour donner de l'unité esthétique à tout ça.


En cours:
1- Sélections multiples d'agent.
2- chemins inaboutis renvoyant le point le plus proche.

Fait:
Intégration d'une abstraction pour les grandes cartes. (HPA* à un niveau)

Je mettrais à jour l'archive pour test quand l'en cours sera fini.
J'apprécie qu'on souligne ce qui ne va pas ou reste encore à faire, ça montre de l’intérêt et ça me stimule ! Merci.

[Ar-S]

Fig, tu nous fais un Syndicate Like ? (ce serait top)