+- 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 - niahoo - 26-09-2010
(26-09-2010, 09:02 AM)php_addict a écrit :(26-09-2010, 12:54 AM)niahoo a écrit : J'avais fait une implémentation de A* en php qui me calculait les routes entre les systèmes solaires (autofix), et le temps d'exécution n'a jamais atteint la minute !
quelle taille ton graphe?
voir ici : http://evemap.battleclinic.com/evemap.jnlp (c'est un applet java)
RE: calcul itinéraire comme Age of Empire et autres - Dexyne - 26-09-2010
C'est sympa le truc en Java.
C'est mieux ou plus simple de faire les "petits" calculs via php et faire les plus gros vers un programme en java, c/c++, etc. ou de tout faire en php / Java, C/C++ par exemple ?
RE: calcul itinéraire comme Age of Empire et autres - niahoo - 26-09-2010
ben si tu es motivé pour implémenter ton algorythme de recherche en C++ ce sera toujours plus rapide (à l'exécution, pas au dev :p)
mais perso, les A* que j'avais fait en PHP ça allait très vite, surtout quand les données sont stockées dans MySQL.
RE: calcul itinéraire comme Age of Empire et autres - Sephi-Chan - 26-09-2010
De toute façon, si tu détaches le processus, tu n'es pas à quelques secondes près.
Sephi-Chan
RE: calcul itinéraire comme Age of Empire et autres - Dexyne - 26-09-2010
Je me doute bien mais le calcul en lui même ne sera-t-il pas plus rapide si ils deviennent gros ?
Après c'est l'envoi des données donc c'est rapide normalement (mis dans une variable et récupérer en php après et ça devrait être bon).
RE: calcul itinéraire comme Age of Empire et autres - niahoo - 26-09-2010
J'avais appris avec cette page, qui dit (presque) tout (les bases quoi). Tu peux télécharger le programme du mec qui va te montrer comment cela fonctionne, visuellement.
RE: calcul itinéraire comme Age of Empire et autres - dryzd - 27-09-2010
Dexyne : "C'est mieux ou plus simple de faire les "petits" calculs via php et faire les plus gros vers un programme en java, c/c++, etc. ou de tout faire en php / Java, C/C++ par exemple ? "
=> Si je comprends bien, l'idéal c'est d'avoir une appli en C++ qui calcul le chemin et renvoie une variable à PHP. Sinon le faire côté client en javascript avec vérification du chemin avant validation. Et au pire, en PHP côté serveur. C'est bien ça ?
niahoo : "mais perso, les A* que j'avais fait en PHP ça allait très vite, surtout quand les données sont stockées dans MySQL. "
=> Tu peux nous en dire un peu plus ? Est-ce que ton script serait partagable sur le forum ? On pourrait le regarder et eventuellement certains membres l'optimiser ?
Sephi-Chan : "De toute façon, si tu détaches le processus, tu n'es pas à quelques secondes près."
=> c'est ce qu'on disait. C'est qu'on ne ferait pas du temps réel mais avec un temps de calcul à faire patienter l'utilisateur. C'est ça ? Avec du C++ on pourrait faire du temps réel ?
niahoo : "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. "
=> Si on sort du processus, est-ce nécessaire de le faire en javascript ?
niahoo : Merci pour le lien !
Est-ce la méthode A* ou Dijkstra qui est la plus performante ? Il me semble comprendre que ce serait Dijkstra. C'est ça ?
Merci à tous pour votre participation !
Dryzd
RE: calcul itinéraire comme Age of Empire et autres - niahoo - 27-09-2010
L'algo que j'avais fait je l'ai jetté, parce que la carte d'eve online est un graphe plutot complexe et en 3 dimensions, ce qui fait qu'A* n'était absolument pas optmisé et ne trouvait pas les chemins les plus courts. (parce que dans eve, les corrdonnées des systèmes ne signifient rien, seules les liaisons entre chaque point comptent, d'où la meilleure efficacité de dijkstra sur un graphe.
SI j'ai bien compris, tu comptes faire des cases, sur un territoire en 2D, là A* sera nettement meilleur.
Je pense que c'est nécéssaire de le faire en javascript parce que l'utilisateur dispose généralement d'une bécane qui fera ça sans problème, et enverra le chemin trouvé à ton serveur qui le validera. (il regardera juste si le chemin proposé existe seulement). Ton serveur, même avec un CGI en C++ risque de ramer un peu s'il trouve les chemins de tous les utilisateurs. Si la carte est stockée en BD, ça fait quand même pas mal de requêtes la résolution d'un seul algo. (3 requetes pour un chemin de 3 cases en ligne droite.. – y a moyen d'optimiser)
De toutes façons, tu veux que l'utilisateur clique et que son perso parte, pas qu'il attende après un appel ajax, donc javascript va de toute façon calculer le chemin. Autant pas s'emmerder à le faire 2 fois.
Et si tu veux vraiment le faire sur le serveur alors les processus, comme on l'a proposé, mais sur du mutu, oublies, avec PHP, oublies.
RE: calcul itinéraire comme Age of Empire et autres - dryzd - 27-09-2010
Oula, je ne tiens pas à le faire absolument côté serveur
Merci pour le conseil A* !
Je cherche simplement a le faire correctement.
Y'a un truc que je ne comprends pas bien. Si tu le fait côté client, pour que js trouve le chemin, il va faire des allers-retours avec la base de donnée. En quoi celà est plus rapide qu'en php ?
Concernant les processus, je ne sais pas ce que c'est. Qqn pourrait me dire, en deux mots, en quoi ca consiste ?
RE: calcul itinéraire comme Age of Empire et autres - niahoo - 27-09-2010
ah non, il faudrait trouver un moyen de donner à javascript les données de la carte en bloc.