Map Hexagonale, Exemple de code pour un plateau hexa

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://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.

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?
@+

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

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

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/map-hexa.zip - 7Ko).

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 ^^

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.

Voilà c'est re-uploadé.

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?

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.

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 :map

Après, avec GD :mapGD

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

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 ?

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...

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

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 :/

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 mon message 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.

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 version de travail (0.3) 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.

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 ?

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. Quelques infos ici.

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.

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.

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

[URL=http://naholyr.free.fr/map-hexa]

Cette adresse me met un access forbidden. Pourtant, cela avait l'air intéressant.

Archeboc

Free a supprimé mon compte sans préavis, je ne sais même pas à qui m'adresser...

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

Si si les sources je les ai, il faut juste que je les remette quelque part