Pathfinding

Voici la classe pathfinding et un main d'exemple d'utilisation.

ça m'a l'air de fonctionner mais il est 2h15 quand j'ai fait les tests alors ... heu ... retestez

Utilisation :
On créer un objet pathfinding (il va chercher tout seul la carte courante)

puis on appelle astar en lui donnant : une position de départ (Pathfinding::Coordonnees), un but(Pathfinding::Coordonnees), un type d'unité (TypeUnite*)
On peut appeler plusieurs astar d'affiler sans problème tant que c'est sur la même map. si on change de map on recréer l'objet
Par contre je n'ai pas gérer de faire tourner deux fois l'algo en même temps à partir du même objet (je sais même pas si on peut ?) donc attention au multithreading.


demain je ferais la fonction pour récupérer les cases accessible par les unités.

http://www.megaupload.com/fr/?d=7EDHPQW8


Edit : oui oublié de préciser, pour le moment il ne prend en compte que le terrain. J'attends de voir que ça fonctionne bien pour ajouter la présence de groupes ennemie.

J'étais en train de réfléchir pour prendre en compte les groupes ennemies mais je me demandais :

si une unité en "pos" veux aller sur la case "but" mais qui a un ennemie sur la case "en". si j'ai bien compris il peut aller sur toute les cases numérotés mais ce sera alors sa position final ? donc il peut pas aller derrière les cases 1 et 5 ?

Il est bloqué, et c'est ça qui est bon !
Au moins en faisant comme ça, il est possible d'établir des "fronts". Mais ton exemple est un peu extrême, vu qu'en général, il n'y a pas trop de raisons de faire des couloirs si étroits (si on prend des cartes à la Wesnoth en tous cas ^^).

Par contre, s'il va en 7, il peut se re-déplacer en 4, puis en 2, puis en 4, puis en 7...

Et donc il peut aller directement en 1 et 5 si il à envie ? ou il doit forcément s'arrêter en 3-6 ?

l'exemple c'était surtout parcque j'ai fait ça sur paint et que ça me casser les couilles mais on peut imaginer que c'est une bande de terre au milieu d'eau profonde ^^

Cédric a écrit:Par contre, s'il va en 7, il peut se re-déplacer en 4, puis en 2, puis en 4, puis en 7...

Oui mais aucune utilité. Il faut virer les cycles dans le pathfinding.

Je dis ça juste pour rigoler, j'ai pas vu si son algo le fait. Mais c'est clair que ça à vérifier quand même ^^

Bon sinon à première vue ça ressemble à du C++
Juste un truc : Les ifndef define endif, ça ne sert à rien pour les .cpp, vu qu'on ne les inclus jamais (ou alors c'est sacrément gore )

codeBlocks me les avais générer tout seul ^^

Par contre j'ai toujours pas ma réponse
est ce que les déplacements :
pos-7-3-1 et pos-7-6-5 sont autoriser ? ou est ce que l'on doit forcément s'arrêter à la première case adjacente à un ennemie que l'on rencontre ?

Aucun des deux, sinon la logique du truc deviendrait assez floue (des fois ça marche, des fois ça marche pas... Gneuh ? )

7-3-1 non
mais 7-4-2-1 oui
et donc 7-6-5 non mais juste 7-6

une unité ne peut pas traverser une case adjacente a une unité ennemi. C'est ce qu'on avais dit non ?

Wakata

Comme j'ai dis à cédric au tel : bug connu de mon algo : il triche un poil et ça le dérange pas particulièrement d'aller faire un tour par la bordure si il peut se déplacer plus vite ^^ Ce sera corriger au prochain commit ^^

wakatta, espèce de n00b !!!

Ta gueule

me souviens plus :
- on peut avoir deux groupes sur la même case ? je pense pas (niveau interface bof...)
- on peut "traverser" un de nos groupes pour s'arrêter plus loin ?

sebastien a écrit:me souviens plus :
- on peut avoir deux groupes sur la même case ? je pense pas (niveau interface bof...)
- on peut "traverser" un de nos groupes pour s'arrêter plus loin ?

On ne peut pas avoir plusieurs groupes sur la même case, sauf s'ils fusionne.

Et pour "traverser" je pense pas non plus. Mais faudrait être d'accord la dessus.

Pour traverser perso je vote non car ça m'arrange pour le code (je peut traiter tous les groupes de la même façon ^^)

Pareil, ça serait un bordel monstreux :p

Et puis bon, il est plutôt logique qu'un mauvais déploiement des troupes soit gênant pour les tours suivants ^^

Voici la version qui prend en compte les unités ennemis. je commence à bosser sur les cases accessibles à une unités.

http://www.megaupload.com/fr/?d=GWOF9FV9

Edit : voici les test que j'ai effectué :

en partant de cette map :
http://xerius.nuxit.net/glouglou/carte.pdf

position initiale (1,3)
destination (5,3)

1/ sans unités ennemies sur la carte :
chemin : (1,3) -> (2,2) -> (3,2) -> (4,2) -> (5,3)

2/ avec une unité ennemie en (3,2) :
chemin : (1,3) -> (2,3) -> (3,4) -> (4,3) -> (5,3)

3/ avec une unité ennemie en (3,2) et une autre en (3,3) :
chemin : (1,3) -> (1,4) -> (2,4) -> (3,5) -> (4,4) -> (5,4) -> (5,3)

4/ avec une unité ennemie en (3,2) et une autre en (3,4) :
Aucun chemin possible

5/ avec une unité ennemie en (3,2) et une autre en (5,2) :
chemin : (1,3) -> (2,3) -> (3,4) -> (4,3) -> (5,3)

6/ avec une unité ennemie en (3,2) et une unité allié en (5,3) :
aucun chemins possible

7/ avec une unité ennemie en (1,2) :
aucun chemins possible



Je pense avoir vue toutes les situations possibles mais dites moi si j'en ai oublié ^^

Bon bah, j'avais bien fait de ne pas tout lire tout à l'heure

j'ai édité mon dernier post pour mettre les quelques tests que j'ai effectué.

7/ avec une unité ennemie en (1,2) :
aucun chemins possible

Ce cas précis pose problème : deux groupes collés seraient forcés de le rester tant que l'un d'entre eux n'est pas mort.

Sinon, vu que tu as l'air d'être en mode berserk sur le boulot, et que tu n'auras bientôt plus rien à te mettre sous la dent, il y a un truc que tu pourrais essayer d'améliorer : faire en sorte que les groupes se déplacent le plus possible en ligne droite. Autrement dit, que pour l'exemple 1/ tu ais plutôt un chemin du genre (1,3),(2,3),(3,3),(4,3),(5,3).

edit: quoi que... Même si c'est un peu plus intuitif, je ne suis pas sûr que ça rende super bien à l'écran...

Cédric a écrit:

7/ avec une unité ennemie en (1,2) :
aucun chemins possible

Ce cas précis pose problème : deux groupes collés seraient forcés de le rester tant que l'un d'entre eux n'est pas mort.

ah, bah il suffit d'enlever une correction alors ...

Cédric a écrit:Sinon, vu que tu as l'air d'être en mode berserk sur le boulot, et que tu n'auras bientôt plus rien à te mettre sous la dent, il y a un truc que tu pourrais essayer d'améliorer : faire en sorte que les groupes se déplacent le plus possible en ligne droite. Autrement dit, que pour l'exemple 1/ tu ais plutôt un chemin du genre (1,3),(2,3),(3,3),(4,3),(5,3).

edit: quoi que... Même si c'est un peu plus intuitif, je ne suis pas sûr que ça rende super bien à l'écran...

non non ^^ (3,3) = montagne = poids de 1.5 alors que (3,2) = foret = poids de 1.25
et puis ça fait chier de forcer l'algo à se déplacer en ligne droite pour pas grand chose.

Sur le lien que t'as mis, il n'y a pas de montagne :p

Ouai mais t'aurais du le deviner !

Et voici la version qui contient la méthode possibilitesDeplacements(Coordonnees position, TypeUnite typeUnite, ptsDeplacementRestant) qui retourne un vecteur contenant toutes les cases disponibles pour l'unité de type typeUnite, à partir de la case position et avec les points de déplacements ptsDeplacementRestant (si ce dernier champ n'est pas renseigner le programme prendra en compte les points de déplacements initiaux de l'unité).
par contre j'ai eu la flemme de trier le vecteur retourné alors c'est un poil le bronx, mais vu que l'ordre importe peut on sen fou ^^

bref, je ne vois pas quoi d'autre ajouter à cette classe ci...

Ah et précision : pour n'importe quelle méthode de pathfinding (astar ou possibilitesDeplacements) on peut l'appeler à partir d'une case qui ne contient pas réellement d'unité si on à besoin d'une simulation (on peut appeler astar( (1,3),(3,3),archer) même si il n'y à pas d'archer en (1,3) ) mais par contre, il demande a la partie le numéro de joueur courant pour savoir les groupe "ennemies".
donc a priori on ne peut pas (dans l'ia) simuler un pathfinding pour une unité adverse (vu que quand l'ia joue le numero de joueur courant dans la partie est le sien). je ne sais pas si c'est un problème ou non. Si on veux avoir la possibilité de simuler un déplacement pour une unité adverse je peut toujours rajouter numJoueur dans l'appelle de astar.

Bref voici les sources :

http://www.megaupload.com/fr/?d=SXJQ4YHW


je désactive le mode berserk ou y a encore du boulot ?

Mais arrête de bosser !!!