+- 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 : Astar sur une map de 600x600 ? (/showthread.php?tid=4426)
Pages :
1
2
RE: Astar sur une map de 600x600 ? - php_addict - 28-10-2009
merci pour toutes vos réponses et d'avoir pris le temps d'y repondre
il faut que je revois entierement la conception de ma (grosse) map ;-)
bonne journée
RE: Astar sur une map de 600x600 ? - barst - 28-10-2009
Autre suggestion :
1) Calcule le trajet du point A au point B en ligne droite
2) Pour chaque case du parcours, vérifie si elle est "traversable", Si c'est le cas passe au point suivant du parcours.
3) si la case n'est pas "traversable" alors
3-1)Stocke dans X le dernier point "traversable"
3-2) continue ton parcours pour rechercher le prochain point "traversable" que tu stockeras dans Y
3-3) Applique l'algo A* entre X et Y, ce qui te fera contourner l'obstable non "traversable"
3-4) incorpore ce sous-parcours dans le parcours global entre les pionts X et Y
Du coup, ça te donne un chemin toujours en ligne droite, sauf qu'il contournera les obstacles.
Cet algo n'est pas optimal car il contourne littéralement l'obstacle pour retrouver l'ancien parcours.... mais pour les portions sans obstacle il devient optimal.
RE: Astar sur une map de 600x600 ? - Sephi-Chan - 28-10-2009
(28-10-2009, 01:13 PM)webmasterdemonsite a écrit : donc Le Astar en terme de ressource serveur (apache et php) c'est inconcevable? beaucoup trop gourmand? (je parle pour un dédié forcément...) ???
A* est un algorithme de plus court chemin assez économique (plus que l'algorithme de Djikstra, par exemple) mais pas toujours optimal (dans des cas de chemins complexes). Je pense donc que c'est un bon choix dans ton cas.
Après, dans le cas d'un serveur dédié, tu peux tout à fait imaginer implémenter l'algorithme en C et faire en sorte que ton application appel cet algorithme. Tu peux même précalculer des itinéraires types et les stocker. Mais pour ce genre de chose, ça dépend de tes besoins (dans un premier temps, tu n'auras pas besoin des performances de C) : on ne peut pas dire à ta place s'il y aura des chemins types…
Sephi-Chan
RE: Astar sur une map de 600x600 ? - php_addict - 28-10-2009
salut
(28-10-2009, 06:00 PM)Sephi-Chan a écrit : Après, dans le cas d'un serveur dédié, tu peux tout à fait imaginer implémenter l'algorithme en C et faire en sorte que ton application appel cet algorithme. Tu peux même précalculer des itinéraires types et les stocker.
pas évident à mettre en place mais pourquoi pas...merci
(28-10-2009, 06:00 PM)Sephi-Chan a écrit : Mais pour ce genre de chose, ça dépend de tes besoins (dans un premier temps, tu n'auras pas besoin des performances de C) : on ne peut pas dire à ta place s'il y aura des chemins types…
je crois que je vais etre obligé vu la taille de ma map de faire des cases genre "auberges de jeunesse"
bonne fin d'apres midi.
RE: Astar sur une map de 600x600 ? - php_addict - 31-10-2009
bonjour
tout d'abord, merci à tous
bilan des courses: faire un algo astar sur une map 600x600 en php est une Aberration...le php n'est pas fait pour ca...
je vais donc me pencher sur le probleme du C++, mais faut que j'apprenne depuis le debut, et je me permet quelques petites questions:
- j'ai essayé binaryPHP pour convertir du php objet en c++ mais sans résultat...connaitriez vous un moyen de traduire du php en c++ automatiquement (on a le droit de rêver ;-) )
- connaitriez vous un example simple d'algo A* en c++ (pas ceux qui ouvre un fenetre windows avec de jolis dessins de parcours, mais un truc simple, genre en mode console...)
si je parviens un jour a faire dialoguer mon site php et mon algo A* en c++, croyez vous que cela soit une bonne solution pour une map de 600x600 (360.000 cases) ?
encore merci
(PS: notez que mon pseudo viens de changer, il ne change pas la mise en page du forum...je me demande pourquoi ce forum n'est pas du phpBB qui offre de meilleur fonctionnalités...)
RE: Astar sur une map de 600x600 ? - Sephi-Chan - 31-10-2009
(31-10-2009, 12:08 PM)php_addict a écrit : bonjour
tout d'abord, merci à tous
bilan des courses: faire un algo astar sur une map 600x600 en php est une Aberration...le php n'est pas fait pour ca...
je vais donc me pencher sur le probleme du C++, mais faut que j'apprenne depuis le debut, et je me permet quelques petites questions:
- j'ai essayé binaryPHP pour convertir du php objet en c++ mais sans résultat...connaitriez vous un moyen de traduire du php en c++ automatiquement (on a le droit de rêver ;-) )
- connaitriez vous un example simple d'algo A* en c++ (pas ceux qui ouvre un fenetre windows avec de jolis dessins de parcours, mais un truc simple, genre en mode console...)
si je parviens un jour a faire dialoguer mon site php et mon algo A* en c++, croyez vous que cela soit une bonne solution pour une map de 600x600 (360.000 cases) ?
encore merci
(PS: notez que mon pseudo viens de changer, il ne change pas la mise en page du forum...je me demande pourquoi ce forum n'est pas du phpBB qui offre de meilleur fonctionnalités...)
L'algorithme A* reste le même. C'est juste le langage dans lequel tu l'implémentes qui change. Si tu l'as écrit en PHP, tu devrais pouvoir le réécrire en C++ assez facilement.
Cependant, je ne pense pas que ce soit la meilleure solution. Tu as un problème de conception : ce que tu cherches à faire n'est probablement pas adapté à un webgame. Je t'invite donc à plutôt réfléchir dans ce sens là et éviter de lancer un algorithme sur un graphe si important.
Si tu veux vraiment le faire en C++ et que tu es sur un serveur dédié, tu peux tout à fait effectuer un appel système depuis PHP. Tu crées alors une commande en C++ qui effectue les requêtes nécessaires (MySQL propose des API pour C++, je suppose que d'autres SGBDR en proposent aussi) et renvoie le résultat (en sortant du JSON par la sortie standard, par exemple, JSON qui est facilement converti par PHP en un tableau).
Ps : Concernant le forum, ce choix a été fait il y a 4 ans pour je ne sais quelles raisons. Changer maintenant serait très chiant et pas forcément utile (à moins qu'avoir un pseudo insécable de 19 caractères soit une fonctionnalité phare…
iffle: ). D'autant que ça fait environ un an que je n'ai pas développé en PHP…Sephi-Chan