calcul itinéraire comme Age of Empire et autres

[dryzd]

Bonsoir,

J'aimerai proposer au joueurs un calcul des trajets au plus court entre deux cases éloignées. En sachant qu'il peut y avoir des obstacles (rivières, bâtiments) et que les trajets ne sont pas forcément en ligne droite.

Une case =un temps de trajet (variable si forêt, route ...)

Vous soyez les jeux type Ageo of Empire ou Settlers dans leurs anciennes
versions ?

En CSS/PHP

Est-ce que vous auriez une idée de comment s'y prendre ?

Merci à vous tous

[Sephi-Chan]

Il faut modéliser ta carte par un graphe et utiliser des algorithme de recherche de plus court chemin comme A* ou Dijkstra.


Sephi-Chan

[dryzd]

Alors pour les algos, je vais voir ça avec un copain car là, à froid, c tendu

Merci pour ces deux liens et je reviens :p

au fait, tu as déjà fait ? En php, c'est faisable ?

[Scrat]

Oui en php tu peux faire ça (pour calculer l'itinéraire le plus rapide, ou le moins couteux en point par exemple).

Et en effet, à froid c'est tendu, mais faut passer par là

[php_addict]

au fait, tu as déjà fait ? En php, c'est faisable ?

oui bien sur...c'est un language de programation

mais en fait tu vas avoir un très gros problème: surcharge de ta mémoire et lenteur d'exécution de ton script

j'avais tenté l'expérience avec l'algorithme a star j'ai du abandonné; j'arrivais à des temps d'execution de plusieures minutes

il y a un topic sur ce forum dont je suis l'instigateur, cherche le.

ta carte est de quelle dimension ? combien de cases entourent une seule et même case ?

[niahoo]

J'avais fait une implémentation de A* en php qui me calculait les routes entre les planètes, et le temps d'exécution n'a jamais atteint la minute !

(Bon, ensuite je me suis rendu compte qu'il fallait utiliser Dijkstra pour eve, et c'est de l'ordre de la seconde).

Je te propose plutot de le faire en javascript que côté serveur, tu n'a plus qu'a envoyer le path au serveur pour vérification, et tu peux déjà déplacer le perso en javascript avant d'avoir la validation.

[php_addict]

J'avais fait une implémentation de A* en php qui me calculait les routes entre les planètes, et le temps d'exécution n'a jamais atteint la minute !

quelle taille ton graphe?

[dryzd]

Merci pour vos réponses

La carte fait 1 000*1 000 cases.
C'est sur la base d'un tableau.
Les cases sont carrées et seuls les déplacements horizontaux et verticaux sont autorisés. Donc 4 possibilités par cases, soit trois si on déduit la case d'origine.
On pourrait limiter le nombre de cases du trajet pour modérer les temps de calculs ?

Il n'y a pas besoin de déplacer le personnage en temps réel. L'idéal serait de pouvoir cliquer sur une unité, puis "déplacer" et cliquer sur sa case de destination. L'appli calculerai alors le trajet au plus court.

C'est délirant comme demande ?

[Sephi-Chan]

À toi de voir comment tu modélises ton graphe, et si tu peux ou non travailler avec des sous-graphes (à moins que le mec ne puisse cliquer à l'autre bout du monde, je ne connais pas tes besoins).

Tu dis que tu n'as pas besoin de temps réel, mais une solution comme la suivante serait-elle envisageable :

1. Je choisis mon unité et sa destination ;
   
2. Je reçois un message genre "Déplacement en cours…" sans vraiment de détail (je n'ai même pas l'heure d'arrivée puisque le calcul n'est pas encore effectué), on a une petite requête Ajax (n'allons pas compliquer ça avec du push tout de suite) exécutée toutes les 10 secondes (c'est arbitraire) capable de déterminer si le calcul d'itinéraire est terminé pour afficher plus de détail (la durée du trajet, notamment) ;
   
3. Côté serveur, l'application génère un processus dans laquelle la résolution du chemin est effectuée (on a vu que c'est une tâche longue, donc l'inclure dans le processus de génération de la page de réponse n'est pas envisageable si l'on travaille sérieusement), avec un passage de flag à true pour que notre requête Ajax suscitée sache que le calcul est terminé ;
   

Bien sûr, ça implique d'avoir un serveur sur lequel tu as le droit de créer des processus, je ne sais pas si on peut sur du mutualisé.
De plus, tout ceci ne te sers qu'à déterminer le chemin, après, il faut gérer un déplacement, deux cas de figure :

1. Le déplacement doit être granulaire dans l'espace et le temps : c'est le cas si l'on veut un système où passer dans certains endroit peut provoquer des événements (exemple, si je passe par une route dans la forêt, je peux me faire attaquer par des bandits). La gestion dans le temps est d'autant plus capitale si tu veux permettre aux joueurs d'assurer le rôle des bandits (avec un message sur leur panneau de jeu du genre "un convoi arrive près de vous") ;
   
2. Le calcul servait juste à déterminer le temps de trajet et tu considères que le déplacement sera terminé (et l'unité passera directement du point de départ au point d'arrivée à l'heure prévue).
   

Dans le premier cas, tu vas vraiment en chier, dans le second c'est très simple.


Sephi-Chan

[dryzd]

À toi de voir comment tu modélises ton graphe, et si tu peux ou non travailler avec des sous-graphes (à moins que le mec ne puisse cliquer à l'autre bout du monde, je ne connais pas tes besoins).

Il y aura des régions (une carte par région) mais je voudrai avoir le jeu le plus à plat possible. Il existe déjà une offre plétorique de jeu basé sur le même modèle (travian, heros might and magic ...) où tu as une carte et après tout le monde a la même sous carte.

Tu dis que tu n'as pas besoin de temps réel, mais une solution comme la suivante serait-elle envisageable :

1. Je choisis mon unité et sa destination ;
   
2. Je reçois un message genre "Déplacement en cours…" sans vraiment de détail (je n'ai même pas l'heure d'arrivée puisque le calcul n'est pas encore effectué), on a une petite requête Ajax (n'allons pas compliquer ça avec du push tout de suite) exécutée toutes les 10 secondes (c'est arbitraire) capable de déterminer si le calcul d'itinéraire est terminé pour afficher plus de détail (la durée du trajet, notamment) ;
   
3. Côté serveur, l'application génère un processus dans laquelle la résolution du chemin est effectuée (on a vu que c'est une tâche longue, donc l'inclure dans le processus de génération de la page de réponse n'est pas envisageable si l'on travaille sérieusement), avec un passage de flag à true pour que notre requête Ajax suscitée sache que le calcul est terminé ;
   

Oui, ça me semble très bien comme idée. Avec une fréquence peut-être variable en fonction de la longueur estimée du trajet. Pour faire un déplacement de trois cases, c'est dommage d'avoir à attendre 15 secondes. Non ?

Bien sûr, ça implique d'avoir un serveur sur lequel tu as le droit de créer des processus, je ne sais pas si on peut sur du mutualisé.

Je suis sur du semi-dédié. Est-ce qu'une tâche cron pourrait faire l'affaire ?

De plus, tout ceci ne te sers qu'à déterminer le chemin, après, il faut gérer un déplacement, deux cas de figure :

1. Le déplacement doit être granulaire dans l'espace et le temps : c'est le cas si l'on veut un système où passer dans certains endroit peut provoquer des événements (exemple, si je passe par une route dans la forêt, je peux me faire attaquer par des bandits). La gestion dans le temps est d'autant plus capitale si tu veux permettre aux joueurs d'assurer le rôle des bandits (avec un message sur leur panneau de jeu du genre "un convoi arrive près de vous") ;
   
2. Le calcul servait juste à déterminer le temps de trajet et tu considères que le déplacement sera terminé (et l'unité passera directement du point de départ au point d'arrivée à l'heure prévue).
   

Dans le premier cas, tu vas vraiment en chier, dans le second c'est très simple.

Disons que j'ai vraiment envie d'en chier
Je pensais faire un système où la minute serait l'unité de mesure pour calculer les déplacements (pas la seconde) ceci afin de faire une pseudo économie de ressources sans être dans le tour par tour. Ce serait du "temps réel" sans être à la seconde.
En plus, avec un système granulaire, il peut se passer des éléments venant interompre le déplacement (construction d'un mur, destruction d'un pont ...).
Comme je voyais les choses, on avait une table des déplacements avec une heure/minute du prochaine mouvement. A chaque minute, on déplace toutes les troupes et on regarde ce qui se passe. Est-ce une bonne faaçon de voir les choses ?

Merci pour tous ces échanges !!!