Version imprimable du sujet
Cliquez ici pour voir ce sujet dans son format original |
Forum TourDeJeu > Programmer > Map Hexagonale |
Ecrit par: naholyr Dimanche 28 Août 2005 à 21h05 |
Pour un projet perso j'ai une carte à base d'hexagones (type wargames), et je me suis un peu creusé pour trouver un moyen de le réaliser "simplement". J'ai vu la solution de zumba (DIV + Javascript), j'ai donc voulu tester une autre méthode : une image et une map. La démo et les sources sont ici : http://www.jeu-web.fr/map-hexa La démo fonctionne en 3 étapes : 1. Choix d'une map (taille aléatoire) 2. Choix du départ 3. Choix de l'arrivée, calcul de la distance Je n'ai pas encore implémenté le calcul de la visibilité (calcul de la liste des tiles compris sur une ligne de vue entre le tile A et le tile mais l'algo est relativement répandu je pense. Notez que je "refile" ça vite fait, je n'ai pas vraiment beaucoup commenté, et il vaut mieux avoir un minimum d'aisance avec la géometrie pour retrouver les formules si ça vous chante. Questions, conseils, critiques (constructives), sont les bienvenues. |
Ecrit par: khiguard Dimanche 28 Août 2005 à 22h56 |
Ben en fait c'est du GD ta map, non? (je vois le lien de l'image qui va sur map.php) Sinon c'est fluide, ca ne prend pas trop de place (23.30ko pour une bonne carte), le code est simple, rien a redire. Juste qu'il faut faire attention, ce n'est pas la carte vide qui risque de poser problème, c'est la carte complète. Voir comment elle sera utiliser et comment tu va la remplir (si tu utiliser des DIV avec beaucoup d'image, ca rame pas mal). Tu va distribuer tes sources en open source? c'est pour quel style de jeu? @+ |
Ecrit par: naholyr Lundi 29 Août 2005 à 00h15 | ||||||||
Oui oui bien sûr. J'ai utilisé path_info pour avoir un lien du genre map.php/arg1/timestamp.png : ça règle le problème des navigateurs qui gèrent le content-type par l'extension plutot que par l'entête http, et avec le timestamp dans l'url, ça règle le problème du cache du navigateur.
ça restera du GD, les cases seront remplies par des tiles hexagonales comme une map classique. A priori (je n'ai pas creusé la question plus avant) j'utiliserai des "fonds de case" avec des morceaux transparents, dans ce genre :
Sans aucun doute, ça aidera certainement à sécuriser le code, et ça me forcera à commenter un peu
Un wargame plutôt simpliste dans les règles, pas plus de détails pour l'instant plusieurs points ne sont pas encore fixés dans ces dites règles mais je tiens à essayer de réduire l'impact du hasard. Je développe lentement, car j'ai un boulot assez pesant et en fin de journée je n'ai jamais le courage d'allumer mon cerveau qui se retrouve bien usé... En gros je tourne à 3h/semaine de développement. Histoire de dire que bon, il faut pas attendre de résultat rapidement |
Ecrit par: naholyr Jeudi 01 Septembre 2005 à 23h08 |
Mise à jour. Très franchement je déconseille à ceux qui ne sont pas super à l'aise avec PHP d'aller voir le source pour l'instant, tellement c'est caca Je vais mettre ça sous la forme d'une classe, et nettoyer et optimiser les algos. Il y a tout ce dont on a besoin pour gérer une map : - Conversion des coordonnées - Affichage À partir de ça on a les fonctions : - Calcul de distance entre deux cases - Calcul de la ligne de vue (hexagones qui doivent être libres pour que A voit À ça je pense qu'il serait utile d'ajouter une fonction de calcul de la zone visible (hexagones situés à une distance de A inférieure à D), et éventuellement un path-finding (mais ça je m'en passerai vu que je n'en aurai pas besoin pour l'instant). Passée cette phase "technique" dont je préfère m'acquitter dès le début, promis je vous parle du jeu mais je me dis que ça mérite que j'y passe du temps, avoir une classe de gestion pour les maps hexagonales ne me parait pas inutile |
Ecrit par: naholyr Samedi 03 Septembre 2005 à 03h14 | ||
Mise à jour, on dispose maintenant d'une librairie sous forme de classe. Pour le moment c'est assez mal pensé dans le sens où l'objet HexPlateau travaille systématiquement avec une image chargée. Ce qui est un peu stupide quand on veut simplement faire des calculs sans affichage. Mais le code est d'ores et déjà plutôt utilisable. Edit Voici les fonctionnalités finales de la classe (pas bien méchante, elle fait 439 lignes pour tout ça) :
Maintenant on peut créer un objet HexPlateau, et le manipuler sans avoir à systématiquement générer une image en mémoire (elle n'est générée que si on le force en utilisant une méthode graphique). De plus elle permet de sauver/charger un objet directement (dans la démo on sauvegarde l'état du plateau pour les 2 prochaines étapes, pour les gros plateaux on sent une accélération de l'affichage). Les fonctionnalités de calcul (ligne de vue, distance, portée) suffisent pour gérer toute situation, d'autant plus qu'on peut définir les options que l'on souhaite sur chaque case (option 'occupee' par exemple). Je m'arrête personnellement là pour l'instant, je vais m'atteler à des parties un peu moins techniques, je complèterai si personne ne l'a fait d'ici là pour gérer l'affichage sur 3 niveaux (image de fond, image de "décor" - arbres, ville, etc -, image d'occupant - personnage, véhicule, etc -). C'est sous licence LGPL, et toujours dispo sur http://naholyr.free.fr/map-hexa (source téléchargeable sur http://naholyr.free.fr/map-hexa/img.zip) - 7Ko). |
Ecrit par: Damascus Dimanche 29 Avril 2007 à 22h37 |
Hum les liens sont morts, je ne sais pas si tu es encore présent sur le forum, mais j'aurais bien voulu voir les sources que tu proposes. Tu avais l'air d'avoir fait un gros boulot de pédagogie ^^ |
Ecrit par: naholyr Lundi 30 Avril 2007 à 10h11 |
En effet, je viens de voir ça, je ne sais pas quand j'ai effacé ça par mégarde :/ Je le renvoie dans la journée. |
Ecrit par: naholyr Lundi 30 Avril 2007 à 11h41 |
Voilà c'est re-uploadé. |
Ecrit par: Damascus Lundi 30 Avril 2007 à 19h40 |
Merci beaucoup, je vais étudier ça. Je suis sûr que ça me fera progresser pas mal sur mon propre projet (et sur PHP-GD de façon générale) Par contr eje vois que tu crées une map pour permettre de cliquer sur chaque hexa. Est ce que ça ne rend pas le fichier html trop lourd à la fin? Est ce qu'il y a une autre manière d'arriver au même résultat, même si moins optimisé? J'ai bien envie de faire un compedium des différentes façon de faire une map moi... Si tu avais supprimé à l'origine, c'est pas parce que ça te crée deux fichiers à chaque nouvelle map et qu'à force ça a pu faire exploser ton espace web? |
Ecrit par: naholyr Lundi 30 Avril 2007 à 23h08 |
Oui mais le index.php du site n'est pas exactement celui de l'archive, il supprime les archives de plus de 48h La taille du fichier HTML n'est pas vraiment un problème, si tu as une map de 100x100 évidemment que ça va commencer à faire beaucoup (à vue de nez dans les 700 Ko), mais pas non plus des Mo. Pour exemple sur la démo lorsque la map fait 21x21, la page pèse 29 Ko. Sans compression c'est acceptable, avec une compression Gzip c'est vraiment négligeable. |
Ecrit par: Damascus Mardi 01 Mai 2007 à 00h04 |
Première tentative d'adaptation de tes sources à ma propre sauce (assez insipide pour le moment, le 3 étoiles ce sera pour une autre fois). Avant, avec un tableau :http://ourobouros.free.fr/robot/map.php Après, avec GD :http://ourobouros.free.fr/robot/mapGD.php Pour la vitesse d'affichage, bof, mais pour la taille de fichier je passe de 5.08Ko à 2Kp. Plus de 60% de réduction, j'aime beaucoup. Merci à toi |
Ecrit par: Mindiell Mardi 01 Mai 2007 à 10h42 |
Damascus> Tes maps sont super lentes. C'est plutôt free, je pense. Pour le reste, je n'ose te mettre des photos d'écran tellement ta mise en page semble laisser à désirer. Je le fais quand même pour que tu puisses réparer tout ca. Dernière chose, c'était un emap hexa et toi tu utilises des carrés. C'est normal ? |
Ecrit par: Damascus Mardi 01 Mai 2007 à 10h54 |
Alors alors : Il s'agit évidemment d'une simple page de test, donc la mise en forme n'a pas vraiment d'importance, à mon sens. Même si de mon coté je n'ai aucun des problèmes graphiques que tu as screen. Plus d'infos sur le comment (version navigateur, résolution, connexion, etc etc) me serais tout de même utiles pour tenter de reproduire ça. J'ai quand même pu constater que ni l'une ni l'autre ne fonctionne correctement sous IE 7 : i prend le contenu des balises Button comme valeur au lieu de l'attribut value correspondant. Weird Oui il s'agit d'une carte à carrés, parce que ça correspond à mon projet, et aussi parce que c'est plus simple pour débuter (en tout cas pour moi). Une grosse partie du code de naholyr est destiné à l'aspect hexa, j'ai préféré commencer petit avant de me noyer. Au final on peut considérer mes liens comme "hors topic" vu que c'est pas de l'hexa, mais je les voyais plutot comme une forme de "merci, j'ai compris!" à naholyr. Enfin chacun sa façon de voir... |
Ecrit par: Mindiell Mercredi 02 Mai 2007 à 06h46 |
Ok, je pensais que tu t'étais trompé de lien Pour les erreurs de présentation, j'utilise Firefox 1.5, Win2000 et de l'ADSL. A mon avis ca tient de Firefox qui est bien strict |
Ecrit par: naholyr Mercredi 02 Mai 2007 à 12h11 |
Pour en revenir à ma map hexa je profite d'une semaine de vacances pour la reprendre intégralement, car en relisant le code j'ai eu du mal à comprendre comment ça marchait, donc : - commentaires (conformes phpdoc). - réécriture de certaines portions. - correction de bugs dans la fonction de conversion de coordonnées (en me basant sur l'article de gamedev, leur algo sera plus fiable que mon imbroglio). - ajout de fonctions pour le pathfinding. - et d'autres petites choses. Je ne me donne pas plus d'objectifs, car je sais pertinemment que je n'aurai pas le temps. Place aux jeunes, profitez des années lycée après c'est mort :/ |
Ecrit par: naholyr Mardi 08 Mai 2007 à 22h10 |
J'ai mis à jour la classe HexPlateau pour corriger les méthodes de conversions de coordonnées (en m'inspirant de l'algorithme donné sur GameDev), et ajouter une méthode chemin() qui calcule le plus court chemin (et son coût) entre deux cases. Il s'agit d'une implémentation de l'algorithme A*. Toujours au même endroit : http://naholyr.free.fr/map-hexa/ J'édite http://www.tourdejeu.net/forum/index.php?showtopic=1104&view=findpost&p=13185 pour y ajouter la fonction chemin(). Au niveau commentaire j'ai fait un gros effort au niveau du code (les algorithmes sont décrits le plus précisément que j'ai pu), mais les commentaires PHPDoc ne sont pas encore mis en place. |
Ecrit par: Haram turval Mercredi 09 Mai 2007 à 08h41 |
Tiens, ça fait longtemps que je ne suis pas passé sur le forum moi. J'aurai pu t'aider au niveau de cette histoire de map hexagonale. Voici une http://90plan.ovh.net/~furiesin/steel/map.php5 d'un truc tout en javascript (Firefox recommandé, IE a des soucis de cadrage et Opera supporte pas le XSL) Je me base sur un système à trois coordonnées pour identifier les hexagones. |
Ecrit par: naholyr Mercredi 09 Mai 2007 à 09h33 | ||
C'est très chouette, c'est l'inconvénient avec la méthode d'affichage GD : on peut difficilement faire le même genre d'interface très dynamique C'est intéressant comme travail je regarderai car si on peut lier les deux on peut faire une véritable librairie de gestion de map hexa client/serveur (avec ajax & cie). J'avais prévu de faire un portage en JS de ma librairie. Pour le pathfinding tu utilises quel algorithme ? Car j'avais peur que le A* soit trop gourmand pour le JS. Quant au XML/XSL, je trouve dommage de se limiter à ça un simple xhtml aurait permis d'être compatible avec tous les systèmes, franchement ça apporte quoi de si important pour faire de tels sacrifices de compatibilité ? En même temps c'est peut-être tout un débat :gla:
Pourquoi ça ? Tu gères l'altitude ? |
Ecrit par: Haram turval Mercredi 09 Mai 2007 à 10h30 |
Le XML/XSL est un choix technologique que j'ai fait au début du dev. L'intéret majeur est de laisser le client faire toute la mise en page en déchargeant par la même le serveur et la bande passante de manière non négligeable. Très bon support FF et IE. Seul Opera pêche encore un peu avec des bugs et des incompatibilités. Rien n'empêche cependant de générer la même chose via PHP en se passant du XML. Ma référence de travail de toute manière est un tableau JS. L'affichage est 100% JS ainsi que la détection de l'hexagone sous le curseur (au pixel près via quelques formules). Le système à trois coordonnées est plus pratique (à mon sens) pour tous les calculs de ligne de vue et la surcouche qu'il rajoute pour la notion de portée/zone d'effet est négligeable. http://sc.tri-bit.com/Hex_Grids Je n'ai pas de pathfinding à proprement parler (mais je peux m'y pencher), juste un algo A->B avec test des cases pour voir si la ligne de vision est bloquée ou pas. |
Ecrit par: naholyr Mercredi 09 Mai 2007 à 14h28 |
Ce serait certainement intéressant de voir le coût d'implémentation d'un même algo de pathfinding (le A* est le plus répandu) dans les différents systèmes de coordonnées sur map hexagonale (interlacing, staggered, trapezoidal, 3d...). Note : le A* selon son implémentation est plus ou moins précis. Dans mon cas je sais qu'il ne détecte pas toujours forcément le plus court chemin selon l'heuristique. Je suis en train d'ajuster pour trouver la bonne Exemple : edit: url expirée Il trouve le chemin le plus court en terme de compromis ( coût , nombre de cases ) mais pas le moins coûteux. Pour avoir le moins coûteux il faudrait une heuristique par défaut constante nulle. Tout ceci est à documenter précisément. |
Ecrit par: naholyr Mardi 15 Mai 2007 à 19h48 |
Je travaille maintenant sur une classe fille gérant les terrains et l'affichage qui va avec, avec gestion des “débordements”. Elle a pour but d'afficher des maps façon Wesnoth (wesnoth.org). C'est quasiment terminé après je jetterai un œil à l'isométrie pour les maps hexa, et on aura une belle librairie pour gérer les maps hexa avec GD (et pourquoi pas une sous-classe pour la version layers ?). Au passage pour l'algorithme A* je l'ai maintenant bien compris, et on peut expliquer les deux fonctions (cout et heuristique) de cette manière : - cout : le cout d'un déplacement représente la difficulté à l'effectuer, la fatigue qu'il va entraîner, etc... cela représente bien les «PM» tels qu'on les a en général dans les jeux. - heuristique : cette fonction au nom si vague a en fait pour rôle de pondérer le coût. si on prend une fonction d'heuristique à valeur constante seul le coût sera pris en compte. En général on va la faire dépendre (directement proportionnelle) de la distance à la case d'arrivée : dans ce cas elle représentera la tendance naturelle du personnage à se diriger directement vers sa destination. Par exemple si le point est à 2 cases en traversant une rivière (coût total : 15), mais à 10 cases en la contournant (coût total : 10) alors avec une heuristique égale à 1 fois la distance (totaux : 17 et 20), le personnage choisira de traverser la rivière car c'est le chemin le plus direct même s'il est plus coûteux en effort. Avec des heuristiques bizarroïdes (fonction du terrain selon les préférences du personnage par exemple) on peut avoir une IA de déplacement très sympa |
Ecrit par: archeboc Samedi 15 Septembre 2007 à 00h44 |
[URL=http://naholyr.free.fr/map-hexa] Cette adresse me met un access forbidden. Pourtant, cela avait l'air intéressant. Archeboc |
Ecrit par: naholyr Samedi 15 Septembre 2007 à 22h18 |
Free a supprimé mon compte sans préavis, je ne sais même pas à qui m'adresser... |
Ecrit par: archeboc Samedi 15 Septembre 2007 à 23h22 |
Tu n'as pas gardé les sources ? Et aucun lecteur du forum ne les a gardées ? Arg, c'est trop bête, dites moi que ce n'est pas vrai. Archeboc |
Ecrit par: naholyr Dimanche 16 Septembre 2007 à 20h30 |
Si si les sources je les ai, il faut juste que je les remette quelque part |
Ecrit par: blueace Mardi 02 Octobre 2007 à 23h31 |
Archeboc, vous ici ? Sinon j'ai des vraies questions. 1) Tu geres bien des plateaux de jeu hexagonaux ? Parceque l'exemple montre un plateau a case carrées non ? 2) Tu utilises quel systeme de coordonnées pour ta classe ? Perso j'ai un systeme basique 00 10 20 ...01 11 21 02 12 22 L'algo A* est il facilement adaptable à ce systeme de coordonnées ? |
Ecrit par: naholyr Dimanche 07 Octobre 2007 à 19h43 |
Lien en première page mise à jour, c'est encore un hébergement temporaire mais ça devrait durer un moment. |
Ecrit par: blueace Lundi 08 Octobre 2007 à 19h12 |
Merci. Au passage, 18 Meg, il y a pas moyen d'avoir une version un peu plus light ? |
Ecrit par: naholyr Mardi 09 Octobre 2007 à 10h18 |
Heu oui en effet j'ai pas fait gaffe mais c'est la version "Wesnoth" avec toutes les images du jeu qui fait que c'est extrèmement lourd. Surtout qu'a priori tu n'en as pas besoin |
Ecrit par: blueace Mardi 09 Octobre 2007 à 16h58 |
C'est ce que je pensais aussi... Sinon, pour que ton truc soit vraiment vraiment genial, il manque un truc indispensable (pas interessé que je suis moi tiens !). Prévoir le cas des maps avec les hexagones alignés en ligne et non pas en colonnes. Tu penses que tu pourrais le faire ? |
Ecrit par: Lord-Gargoyle Vendredi 28 Mars 2008 à 02h48 |
Hugh Naholyr, Super intéressant ton truc sur les hexagones, mais je regarde et je vois que tu affiches en vert les hexagones à une même distance D de l'origine en rouge. Moi ce qui m'aurait intéressé c'est d'avoir tous les hexagones que l'on peut atteindre en utilisant des chemins de cout inférieur ou égal au plus court chemin. Genre, j'ai un perso avec 10 PM, les plaines coutent 1PM, les montagnes 3 PM. Problème : Afficher tous les terrains qui sont accessibles par le perso. Ca c'est pas le même algo. Bon, je vais regarder dans Wesnoth si je trouve l'algo (jeu que j'ai découvert la semaine dernière ) qui est génial d'ailleurs... D'ailleurs personne n'a un guide pour mieux comprendre le code de Wesnoth, c'est pas évident de rentrer dans le code comme ça |
Ecrit par: Jim Mardi 29 Avril 2008 à 15h58 |
Ca touche la recherche opérationnelle comme algo, j'ai du voir ça à l'école. Faut construire un graph puis l'explorer en calculant le chemin le plus court. Essaye de regarder si tu trouves des exemples sous operational research en anglais. |
Ecrit par: Lord-Gargoyle Vendredi 02 Mai 2008 à 21h52 |
J'en ai trouvé plein des algos de plus court chemin, mais aucun bien implémenté. Mais c'est bon j'ai réussi à faire ce que je voulais |
Ecrit par: Jim Mardi 17 Juin 2008 à 17h38 |
C'est super, je viens de pouvoir télécharger le code map-hex, merci |