calcul itinéraire comme Age of Empire et autres

[niahoo]

si tu veux simuler une ligne de vision, tu limite le déplacement à 20 cases. là le pathfinding est très simple, il suffit d'avancer de 20 cases dans la direction du point d'arrivée, quitte à se manger un cul de sac 100 cases plus loin. du coup, l'algorithme s'arrête à une certaine distance.
mais pour rendre ça réaliste, il faut aussi que l'algo redémarre quand le perso voit arriver l'obstacle (côté client c'est cool) et, quand à l'Est ça passe pas, quand on arrive à un deuxième cul de sac au nord, l'algo se relance, il risque de retenter par l'Est. Il va donc falloir mémoriser tous les chemins tentés, et encore une fois, côté serveur ça fait vite lourd.

j'ajouterais qu'au bout de 3 allers retours, le perso le connaît le bon chemin, donc soit il faut implémenter un systeme de waypoints, soit en revenir à l'A* sur tout le chemin.

[gameprog2]

Le mieux c'est donc que le perso (pour faire réaliste), se déplace que de case en case comme ça plus de waypoints à placer, plus de Astart etc...

[dryzd]

Merci pour tous ces échanges !!!

L'idée que j'en avais, c'est que le perso ne connait pas tout le territoire. Il doit l'explorer. Une unité a un champ de vision, trois cases par exemple. Au bout d'un certain temps, le territoire du joueur va s'agrandir.
Tout ce qui n'est pas exploré est noir. On ne peut pas envoyer de troupes sur une case noire.
Est-ce que ca limite les recherche de A* ? Autrement dit, est-ce qu'on peut donner un périmètre de recherche ?

Pour le tronconage, concrètement, le joueur clique sur son unité puis "déplacer". Il selectionne alors la case de destination de sa première étape (dans un périmètre de 20 cases par exemple, et sur une case non noire). Il valide ensuite cette première étape. Si c'est suffisant, on arrête là. Sinon il peut cliquer sur "ajouter une étape" et il reselectionne une unité dans un périmètre donné et sur une case déjà explorée. On recaclul alors le trajet uniquement sur cette deuxième étape.

Les temps de trajets entre les cases étant assez long (plusieurs minutes voir dizaines de minutes), l'exploration se fera progressivement. L'objectif n'est pas d'explorer toute la carte dans la soirée.

Est-ce que vous voyez mieux ce que je veux dire ?

[atra27]

Ben tu fait pas d'endroit ou l'on peut pas passer!

J'assume dans l'exemple que ton monde se situe sur une planète similaire a la terre.

Au vu de ton pb, perso je me dirai que:
Une armée peut très bien passer l'importe ou!
On peut très bien faire traverser des montagnes a une division d'hommes, mais cela prend du temps et fatigue (donc malus combat)

De la même façon un cours d'eau n'est jamais infranchissable! avec du temps, des brassards (lol) les hommes traverserons.

Donc, tu as ton point de départ, le joueur donne son point d'arrivée, et sa trace une ligne droite entre les deux!
Tu calcule le temps ainsi que le cout (par ex, si tu as des chars, construire un pont de fortune coute des pierres/metal ainsi que 1h d'arret!)
Et hop aux chiottes le pathfinding!
Rajoute juste la possibilité au joueur de programmer des waypoints (va la, puis ici et enfin la) et le tour est réglé.

Enfin niveau technique, tu stocke en bdd:
-coord de départ
-coord d'arrivée
-Heure départ
-Heure arrivée
Donc quand le joueur charge une page ou tu dois afficher ou ses armées se trouvent (carte)
Tu calcule a partir de l'heure actuelle la position de son armée (sur la ligne entre arrivée et départ)
Update départ et coord avec celles calculées comme etant position actuelle (éviter de recalculer? Dépend des cas, *facultatif*)
Si time()>Heure arrivée alors tu place l'armée direct a sa destination...

Tu comprend ma vision?

[dryzd]

Je comprends tout à fait et c'est très interessant.

Mais je vois deux choses :
- il y a des obstacles (même si on considère qu'une rivière n'en est pas un) :
---- naturel : lac, mer ... => on pourrait les virrer de la carte mais c'est peut-être moins sympa.
---- artificiels : cité fortifiée, unité d'armée existant déjà sur une case ....
- comment tu gères un déplacement de 3 degrès nord, par exemple ? Tu fais une fonction qui calcul l'angle et donc la diagonale à prendre (dix cases vers le nord, une vers l'est, dix vers le nord, une vers l'est ...) ?

[gameprog2]

le joueur clique sur son unité puis "déplacer". Il selectionne alors la case de destination de sa première étape

Juste un conseil de joueur : ça fait lourd comme systeme, de sélectionner l'unité puis de cliquer sur "déplacer" puis de sélectionner la case où l'on veut le déplacement.

Pourquoi ne fais-tu pas le truc classique : Sélection de l'unité puis click sur la case où l'on veut le déplacement.

Sinon pour les obstacles, je ne suis pas d'accord avec le fait de dire qu'il suffit de tracer une ligne droite, car déjà il y a des obstacles que l'on ne peut traverser, et puis ça enlève le truc de gérer les contournement d'ennemi etc...

[atra27]

limite tu implémente aussi le déplacement en diagonale...

naturel : lac, mer: ben non tu les vire pas... mais tu met un quadrillage distinct qui indique que seuls les unités navales peuvent y aller.
Pour les unités terrestres, ben tu est obligé de lire toutes les cases... DONC si une case est de type mer, soit abort la sélection, soit la ligne s'arrête a la case précédentes!

artificiels : cité fortifiée, unité d'armée: Dépend de ton jeu mais j'imagine que plusieurs divisions peuvent se cotoyer IRL...

Sinon ben pareil, tu peut tester si la case est prise comme tu teste pour la mer...

Mais je trouve sa dommage vu que sa retirer un intérêt stratégique:
Exemple: char lance flamme vs infanterie AC distantes de plusieurs cases -> infanterie gagne (RPG de loin sa marche bien)
char lance flamme vs infanterie AC sur la même case -> char gagne (Lance flamme de prés...)

char vs infanterie AC distantes de plusieurs cases -> char gagne (Canon de 125mm de loin...)
char vs infanterie AC sur la même case -> infanterie gagne (Soldat intouchable tant qu'en dessous de la ligne de tir... et puis de prés les soldats balancent une grenade a l'intérieur et c'est réglé!)

Bref Voila!

---

Sinon pour les obstacles, je ne suis pas d'accord avec le fait de dire qu'il suffit de tracer une ligne droite, car déjà il y a des obstacles que l'on ne peut traverser, et puis ça enlève le truc de gérer les contournement d'ennemi etc...

Qu'est ce qui empêche un joueur de placer un waypoint a droite de l'ennemi pour lui revenir sur sa gauche?

Et qu'est ce qui empêche a un joueur de traverser une montagne pour prendre une région par le coté le moins défendu?

Tu sais.. la guerre... y a pas de règles... Si y faut absolument passer... ben sa passera!

[gameprog2]

Tu sais.. la guerre... y a pas de règles... Si y faut absolument passer... ben sa passera!
Je ne crois pas qu'une armée peut passer n'importe quel obstacle naturel déjà.
Elle est obligée de contourner une chaine escarpée de montagnes s'il est impossible de les escalader.
Les avions c'est normal que ça passe mais pas l'infanterie et les chars.

Tu sais.. la guerre... y a pas de règles...

Si, il y en a

[dryzd]

Gameprog2 : Juste un conseil de joueur : ça fait lourd comme systeme, de sélectionner l'unité puis de cliquer sur "déplacer" puis de sélectionner la case où l'on veut le déplacement.
==> Oui, tu as raison, c'est une meilleure idée !

atra27 : Dépend de ton jeu mais j'imagine que plusieurs divisions peuvent se cotoyer IRL...
==> je partai plutôt du principe qu'il y avait une unité par case. Ca me semblait plus lisible sur la carte (sauf pour les unités aérienne qui peuvent survoler toutes les cases). Par contre, on pourrait avoir une unité+un bâtiment sur la même case (unité défend le bâtiment).

Concernant le débat obstacle/pas obstacle, est-ce qu'on pourrait se rencentrer sur notre ami A* ?

atra27, je garde ton idée en mémoire car elle pourrait être une alternative interessante, mais j'aimerai bien explorer la faisabilité d'un algo de contournement

Je repost le message où on s'était arrêté sur A* :

"L'idée que j'en avais, c'est que le perso ne connait pas tout le territoire. Il doit l'explorer. Une unité a un champ de vision, trois cases par exemple. Au bout d'un certain temps, le territoire du joueur va s'agrandir.
Tout ce qui n'est pas exploré est noir. On ne peut pas envoyer de troupes sur une case noire.
Est-ce que ca limite les recherche de A* ? Autrement dit, est-ce qu'on peut donner un périmètre de recherche ?

Pour le tronconage, concrètement, le joueur clique sur son unité puis "déplacer". Il selectionne alors la case de destination de sa première étape (dans un périmètre de 20 cases par exemple, et sur une case non noire). Il valide ensuite cette première étape. Si c'est suffisant, on arrête là. Sinon il peut cliquer sur "ajouter une étape" et il reselectionne une unité dans un périmètre donné et sur une case déjà explorée. On recaclul alors le trajet uniquement sur cette deuxième étape.

Les temps de trajets entre les cases étant assez long (plusieurs minutes voir dizaines de minutes), l'exploration se fera progressivement. L'objectif n'est pas d'explorer toute la carte dans la soirée.

Est-ce que vous voyez mieux ce que je veux dire ? "

Merci de continuer à m'aider sur ce chemin escarpé

[gameprog2]

A mon avis si tu utilise la couche noire, tu n'a pas besoin d'un long chemin pour le Astart, le calcul se limitera aux cases visibles du champ de vision.