+- JeuWeb - Crée ton jeu par navigateur (https://jeuweb.org)
+-- Forum : Discussions, Aide, Ressources... (https://jeuweb.org/forumdisplay.php?fid=38)
+--- Forum : Programmation, infrastructure (https://jeuweb.org/forumdisplay.php?fid=51)
+--- Sujet : calcul itinéraire comme Age of Empire et autres (/showthread.php?tid=2122)
RE: calcul itinéraire comme Age of Empire et autres - dryzd - 30-09-2010
niahoo et php_addict, j'entend bien ce que vous exprimez et j'en tiens compte.
J'ai cru comprendre que pour EVE, A* n'était pas adapté aussi parce que c'était en 3D.
Je voudrai juste présenter mon idée pour voir si elle tiens la route. Si je suis vraiment à côté de la plaque, j'abandonne le PHP et je me pencherai sur du C++ (si je trouve qqn pour le faire car je ne connais pas ce langage
)CARTE
_ | A | B | C | D | E |
1 |....|....|...|....|.X.|
2 |....|....|...|....|....|
3 |....|....|...|....|....|
4 |....|....|...|....|....|
5 |.X.|....|...|....|....|
La carte fait un million, mais les trajets seront plus courts (on limite à 20 cases par exemple par étape et je le joueur n'a pas exploré toute la carte).
Dans ce cas, le joueur veut aller de A5 à E1.
On ne chargerait pas toute la carte, mais uniquement la portion qui nous intéresse, soit dans ce cas 25 cases
Disons que des obstacles risquent de le faire déborder de la carte, on va prendre de la marge autour en ajoutant des lignes et des colonnes autour de cette trajectoire idéale. Disons qu'on arrive à 100 cases.
Le calcul ne porte donc pas sur un million de cellules mais sur 100. non ?
Avec ça, il me semble, qu'on devrait arriver à calculer le trajet pour 90% des cas.
Pour les cas les plus tordus, l'utilisateur fera des étapes plus courtes pour contourner "a la main" les obstacles.
Vous voyez ce que je veux dire ?
C'est délirant ?
RE: calcul itinéraire comme Age of Empire et autres - niahoo - 30-09-2010
non le problème de eve c'est que le déplacement entre les systèmes solaires n'est pas continu, il se fait via des stargates, des points de téléportation, alors que A* se base sur la distance réelle entre les points.
Pour la 3D, je pense que A* est tout à fait adaptable mais il existe peut-être mieux.
pour ton exemple, il n'y a aucun problème et PHP te fera ça en une milliseconde mais ça implique des points que nous avons déjà évoqué:
- comme on ne calcule pas le trajet global, il faut s'attendre à tomber dans un cul de sac et avoir fait 80% du trajet pour rien. (Ce qui est tout à fait honnête puisque on ne connaît pas la carte à l'avance.)
- dans ce cas, il faut permettre au joueur de ne pas retomber dans un cul de sac une fois le chemin connu, et donc l'algorithme, quel qu'il soit devra prendre ça en compte OU BIEN prévoir des waypoints, sinon ça va être lourd pour le joueur. à moins que les déplacement soient suffisamment lents pour piloter à la main.
RE: calcul itinéraire comme Age of Empire et autres - php_addict - 30-09-2010
ah ba effectivement si tu lances ton a* sur une 100aine de cases seulement, aucun soucis en php...
et le script que tu as trouvé te dira meme si il n'y a pas de chemin possible...
par contre je ne connais pas ton jeu mais lancer un recherche de chemin le plus court sur une si petite portion de carte, je ne vois pas bien l'intérêt...il doit y en avoir un en fonction de ton jeu...
je voyais ton problème beaucoup plus volumineux
RE: calcul itinéraire comme Age of Empire et autres - dryzd - 30-09-2010
Nickel
Je précise : on ne peut envoyer des unités que sur des cellules déjà "vues". Une cellule est "vue" quand elle rentre dans le camp de vision d'une unité (variable selon les unités). Donc le joueur sait toujours où il va.
Exemple de déplacement d'unité sur vers territoire inconnu :
1- La cavalerie a une porté de vue de 3 cases. Elle voit donc toujours trois cases autour d'elle.
PORTEE VUE AVANT LES TROIS DEPLACEMENTS
_ | A | B | C | D | E |
1 |....|....|...|....|.X.|
2 |.V.|....|...|....|....|
3 |.V.|.V.|...|....|....|
4 |.V.|.V.|.V|....|....|
5 |.X.|.V.|.V|.V.|....|
2- Le joueur fait avancer son unité de trois cases (maximum dû à sa portée de vue)
3- A chaque déplacement on actualise la liste des cases "vues". De cette manière, lorsqu'il se reconnecte quelques temps après, il voie à nouveau trois cases devant lui et peut relancer un nouveau déplacement (il peut revenir quand son déplacement est terminé ou avant, peu importe).
PORTEE VUE APRES LES TROIS DEPLACEMENTS
_ | A | B | C | D | E |
1 |.V.|.V.|.V|....|.X.|
2 |.V.|.V.|.V|.V.|....|
3 |.V.|.X.|.V|.V.|.V.|
4 |.V.|.V.|.V|.V.|....|
5 |.V.|.V.|.V|.V.|....|
J'imaginai des déplacements lents justement. En moyenne, ca pourrait prendre prendre 20 minutes par cases.
Alors ça a l'air de tenir debout cette histoire ?
RE: calcul itinéraire comme Age of Empire et autres - php_addict - 30-09-2010
tes cases vues ou pas vues ca va etre chaud ca par contre...
dans l'algo astar tu peut definir des murs (cases interdites)
par contre le soucis, c'est que tu veut faire une recherche de chemin le plus court d'un point a a un point b alors que tu ne vois pas le point b...
ce n'est donc pas une recherche de chemin le + court...car tu ne peut pas le determiner car ton point d'arrivée peut etre une case interdites (un mur, un obstacle...)
fais des recherche sur le net et tiens nous au courant, mais je ne suis pas certain que tu veuille utiliser le bon algorythme...
RE: calcul itinéraire comme Age of Empire et autres - dryzd - 30-09-2010
Je me suis mal exprimé alors.
J'ai oublié de préciser qu'il y a les cases vues (à porté de vue de l'unité) et les cases visitées.
Pour être plus précis, la carte serait comme ça :
V: à portée de vue
0 : déjà visitée par le passé, la cellule est connue.
... : la case est noire (jamais vue et pas à portée de vue
_ | A | B | C | D | E |
1 |....|.0.|.0|.0.|.X.|
2 |.V.|.0.|.0|.0.|.0.|
3 |.V.|.V.|.0|.0.|.0.|
4 |.V.|.V.|.V|.0.|.0.|
5 |.X.|.V.|.V|.V.|....|
On ne peux pas choisir comme destination une case noir. C'est forcément une case vue ou visitée. On vois (ou on a vu) toujours le point B.
Dans l'algo, les murs seraient les obstacles naturel, artificiels et les cases noires.
Est-ce ue c'est plus clair ?
Je suis désolé mais résumer un projet en quelques lignes c'est pas simple
--------------
Là où ca risque d'être plus compliqué, c'est que je pensais cacher les bâtiments et unités ennemies des cellules qui ne sont pas à portée de vue (0) dans notre exemple (on voit le terrain mais pas ce qu'il y a dessus).
Entre temps, le joueur adverse peut avoir construit des murs ou positionné des unités.
Dans ce cas, oui, on va arriver dans une impasse. L'unité et l'algo s'arrêteront au mouvement juste avant l'obstacle (le chemin le plus long obtenu même si on n'arrive pas à destination).
Le joueur ne le saura pas mais il découvrira son unité arrêtée face à une troupe ennemi ou à une construction. C'est plus réaliste comme ça
Vous en pensez quoi ?
RE: calcul itinéraire comme Age of Empire et autres - niahoo - 30-09-2010
tu peux tout à fait calculer le chamin le plus court vers une destination inconnue en te basant uniquement sur les coordonnées.
mais tu devrait surtout commencer à faire des tests ! :p
RE: calcul itinéraire comme Age of Empire et autres - dryzd - 30-09-2010
oui
Je crois que j'ai assez d'infos pour faire des tests.
Merci à vous tous !!!!
RE: calcul itinéraire comme Age of Empire et autres - Ter Rowan - 30-09-2010
j'ai du mal à comprendre l'intéret gameplay d'avoir le a* (ou n'importe quel calcul d'optimisation) si on est dans une logique ou une unité se déplace de si peu de cases à la fois :
on est dans un wargame si j'ai bien compris
je connais et me souviens (via la machine) des cases où je suis déjà allé et des cases à une distance de n (n petit genre 3) cases de là où je suis
je vois certaines unités (peut être toute, peu importe) sur les cases à une distance de n (la même que juste au dessus) cases de là où je suis
==> je ne vois pas (encore heureux) si des unités sont présentes sur des cases que je connais (d'avant) hors de mon champ de vision
quel est mon intérêt en tant que joueur de ne pas déplacer moi même mes unités cases par cases ?
en déplaçant case par case, je pourrais arrêter un déplacement qui m'amènerai à portée d'une unité ennemie (mais hors de vue de ma position d'origine)
en déplaçant en aveugle (donc avec le a * ou autre), je risquerai de tomber dans un traquenard (bien involontaire d'ailleurs dans beaucoup de cas, les autres joueurs ayant le même problème)
(à noter je pense que tes idées concernant les murs et unités adverses sont plus que nécessaires, je les prend donc comme hypothèse, le contraire rendrait le jeu.... sans intérêt)
Tout ça pour dire que le A* peut servir dans des jeux, mais vérifiez bien l'intérêt qu'il apporte aux joueurs
RE: calcul itinéraire comme Age of Empire et autres - Chandler - 30-09-2010
Déplacer des unités case par case ça signifie revenir toutes les 20 minutes pour le faire. Perso ça me gaverais ce genre de choses.