+- 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 : du récursif et des arbres... (/showthread.php?tid=3762)
du récursif et des arbres... - maniaco_jazz - 04-03-2009
Bonsoir,
Alors voilà mon problème :
J'ai un système de carte à case, avec mes unités dessus, jusque là pas de problème.
Lorsque je clique sur une unité, je voudrais que mon système me renvoie toutes les cases où mon unité peut avancer suivant un nombre de point de mouvement (PM).
Chaque case à un coût.
Mon idée de base est de me calculer tous les chemins le plus court possibles.
Pour cela, je dois me faire un arbre...
J'ai fait mon arbre, pas de soucis, mais j'ai un grave problème de performance.
Ayant un système "classique" (pas hexagonale... encore heureux...), j'ai donc 8 coordonnées pour chaque branche... Et comme vous le savez avec les arbres, plus on monte dans les niveaux, plus il y a de feuilles... (récursif powaa
). Du coup, arrivé au niveau 6 (potentiellement 6 cases tout autour de mon départ), ça met déjà 9 secondes (299593 coordonnées...).Le soucis, c'est que je compte aller plus loin tout de même à chaque fois (genre 10 voir 20 cases à la ronde) ; j'ai essayé 10 niveaux... ça tourne depuis 5 minutes... ^^).
Je me demandais donc s'il y avait d'autres moyens pour faire ce genre de chose mis à part du récursif et système d'arbre.
PS : j'ai utilisé des arrays avec des array_push, je n'ai pas testé avec d'autre type de variable ; ça joue peut-être.
C'est le seul point bloquant dans mon projet... et une fois résolu, ça sera tout bonheur, pas cool donc :pleure2:
Merci par avance de votre aide, j'espère avoir été clair dans mon explication
RE: du récursif et des arbres... - Sulfuin - 04-03-2009
Question voir si j'ai bien compris. Si une unité à 3PM par exemple, elle peut se déplacer sur les case à une distance de 3 c'est bien ça?
Donc si ton unité es en 0,0 elle pourra se déplacer sur les case contenu dans le carré (-3,-3)(-3,3)(3,3)(3,-3)? c'est bien ça?
Sulfuin
RE: du récursif et des arbres... - keke - 05-03-2009
(petite parenthèse à 23h00 ... en hexagonale, tu aurais moins de choix à faire ^^. y'a que 6 cases autour de toi, au lieu de 8 dans ton exemple)
Pour raccourcir ton algo. Si tu peux te déplacer en Diagonal ... tu peux estimer que ton joueur n'ira jamais à plus de 20 cases de ton points X. Cela fait donc (20 + 1 + 20 ) * (20 + 1 + 20 ) = 1681 cases à tester au maximum !
Ensuite, dans la manière que tu indiques, il faut que tu te dises qu'une case déjà testé, c'est une information importante.
Dans ton cas, recherche toutes les cases adjacentes à ta position initiale et associe leur la valeur 1. puis toutes les cases encore adjacente n'ayant encore pas de valeur et associe la valeur 2, ainsi de suite ...
Si y'a un mur, indique une valeur limite (exemple 10 000)
Tu dois pouvoir trouver un système plus rapide ^^
Kéké
RE: du récursif et des arbres... - maniaco_jazz - 05-03-2009
:mauvais: Boulet que je suis... Autant pour moi pour l'hexagonal...
sulfuin : Oui, c'est ça, le carré de centre mon point de départ avec comme côté (niveau * 2 + 1).
keke : merci pour la réponse.
Je crois avoir saisie la méthode (mais je vais réfléchir à ça à tête reposée demain) ; je vais tester ça.
Les cases n'ont pas forcément le même coût car des terrains différents.
Donc certaines coordonnées dans mon carré de recherche ne seront pas forcément accessible.
Si j'ai bien compris dans ta méthode, tu élimines les cases déjà testées, c'est bien ça ?
Aurais-tu un exemple ?
Je dois bien passer par un arbre ?
Que de questions :heuuu:
RE: du récursif et des arbres... - keke - 05-03-2009
Ben j'ai pas trop de mérite. J'ai fais un bomber-man Like, dans lequel les IA allaient se réfugier quand on plaçait des bombes ... je devais calculer rapidement des chemins (de l'ordre du dixième de secondes). L'a bien fallu que j'optimise ^^.
Dans ton cas, à chaque case testé, tu indique toujours 1, mais tu associe la valeur de ralentissement.
Première itération :
1 case à tester : Je la note 1 (signifiant que j'aurais que 1 déplacement à faire) et j'associe la valeur 5 car il s'agit de sable et que ça ralenti.
2eme itération :
2 case à tester : Je les note 3 (signifiant que j'aurais que 2 déplacement à faire pour m'y rendre)
pour la première case j'associe 6 (5+1) car il s'agit d'une route avec un facteur de déplacement optimal !
Pour la deuxième case j'associe 8 (5+3) car il s'agit d'une prairie avec de l'herbe haute
Si ton personnage ne peut pas se déplacer à plus de 20 points d'action, dès que ton algo associe une valeur supérieur à 20, tu indique qu'il s'agit d'une case inaccessible.
Ainsi, tu obtiens rapidement un arbre de coordonnée avec les points nécessaires pour y acceder.
Kéké
RE: du récursif et des arbres... - maniaco_jazz - 05-03-2009
Merci beaucoup !
La nuit porte conseil et après avoir relu et réfléchi au sujet, je pense avoir bien saisie la méthode.
Je n'y aurai pas pensé à vrai dire, bien joué ! :respect:
Je vais de ce pas tester ça !
:good: