Plop | Domaine concerné: algorithmique
Logiciel utilisé: VX ace
Bonjour,
Je travaille sur une refonte du système de combat de RPG maker en combat tactique, en m'inspirant fortement de GTBS mais en retravaillant aussi la structure pour rendre le système plus modulable et y intégrer des scripts externes.
Je m'inspire notamment de systèmes de combat comme dofus, bg3 ou wildermyth où les entités :
-ont une position (qui n'est partagée par nulle autre entité)
-ont leur propre tour de jeu ou alors un tour partagé avec une ou plusieurs membres de leur équipe
-peuvent se déplacer avec un coût de déplacement dépendant du terrain et de l'unité
-ont des capacités qui coûtent des ressources mais qui peuvent se jouer dans n'importe quel ordre (ressource pouvant être point d'action, portée de déplacement etc.)
-ont des capacités qui ont une portée pouvant, selon la capacité, être obstruée par des obstacles ou être limitée géométriquement (par exemple une capacité pourrait ne pouvoir se lancer que sur l'axe horizontal ou vertical)
Je m'intéresse au calcul des portées, et plus précisément de son intégration au calcul des capacité des adversaires.
Et je cherche à déterminer la façon la plus efficace (au sens algorithmique) de les calculer afin d'éviter que les tours adverses soient trop longs.
Pour calculer la portée d'un sort, j'associe une stucture à chaque sort qui est :
[portée_min, portée_max, besoin_de_ligne_de_vue?, type_de_portée]
Avec portée_min et portée_max les distances permises pour lancer la capacité, besoin_de_ligne_de_vue? un booléen indiquant si la portée est obstruée par les obstacles et enfin type_de_portée qui indique si la portée se restreint à la distance, à un carrée, aux lignes verticales/horizontales ou encore aux lignes diagonales.
Quand je calcule la portée d'un sort, je prend une position source (src) et j'établie la liste des position cibles [tgt] en me basant sur une exploration depuis le point de départ et en limitant selon les paramètres portée_min, portée_max, type_de_portée.
Ce calcul a une complexité linéaire en nombre de cases générées, ce qui me semble satisfaisant.
En revanche, pour déterminer si une case tgt est visible depuis la source src, je dois faire un calcul qui dépend de sa distance avec la source : Je trace un trait entre src et tgt, et je déduis la liste de cases qui sont traversées par ce trait, enfin, pour chaque case (dans l'ordre), je regarde si la case est obstruante (vérification en temps constant) puis je passe à la case suivante jusqu'à tomber sur un obstacle qui fera terminer la recherche.
Le soucis, c'est que ce calcul (dont le nombre de case traversées dépend de la distance) doit être fait pour CHAQUE case de ma portée, je passe alors d'un résultat linéaire à quadratique. Je ne sais pas si je peux l'améliorer.
Enfin, chaque sort peut avoir une zone d'effet qui est similaire en permission à la structure de portée, la zone peut toucher des cibles sur une ligne droite, en croix, en cercle en carré etc.
J'en viens au calcul des ia (qui ne sont pas encore torp déterminées), je cherche à avoir une ia qui fonctionne à peu près comme l'ia native de RPG Maker : choisir une capacité parmi celle disponibles et jouable (au sens avoir assez de mana etc.) avec une probabilité définie par the maker, puis sélectionner une cible parmi les cibles valides avec une proba définie par la chance d'être ciblé (donc dépendant du projet).
Dans un tactical, c'est plus complexe, il faut prendre en compte d'autres paramètres et notamment la position où on est dans les conditions de lancement de capacité.
Je pense alors définir l'algorithme suivant pour le choix d'une ia basique (indépendamment de son équipe) :
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| Tant que je peux faire une action :
L = la liste d actions que je peux faire #(coût en ressources, cooldown etc.)
M = la liste des cases où je peux me rendre en me déplaçant
Ordonne L selon mes préférences d actions #(donc probabilité + éventuellement un état interne qui me ferait privilégier certaines actions par rapport aux autres)
Pour chaque capacité c de L (ordonnée) :
Je calcule la liste des cases que c peut toucher depuis ma position ou une position où je me serai déplacé #voir pb A
Si cette liste contient des cibles pertinentes :
Je prends la meilleure cible #(calcul propre à l ia, une meilleure cible dépendra du nombre de cibles, et d'à quel point ça avantage mon équipe, genre tuer les cibles, les affaiblir ou soigner mes alliés etc.)
Je regarde où je peux atteindre cette cible #voir pb B
Je me déplace vers la meilleure position qui peut atteindre ma cible #(calcul propre à l'ia, dépend de si elle veut se rapprocher ou s'éloigner, de ses déplacements restants etc.)
Je lance la capacité sur la cible
Je reviens au tant que
Sinon:
Je passe à la capacité suivante
Si aucune action ne peut être faite, je regarde la meilleure position où je peux aller, j'y vais et je termine mon tour
|
Donc voilà les soucis que j'ai :
- A : Le calcul de la liste des cases que je peux toucher est un calcul long, naïvement, pour chaque case de M, je calcule la portée de c (un ensemble de cases) puis je prend l'union de ces portées, c'est un calcul conséquent (il implique de faire |M|*quadratique) et d'autant plus si on le répète avec les capacités à parser, je me demande si on y gagnerait pas à calculer une portée maximale (prendre la portée la plus permissive de L qui vérifie les obstacles) sur toutes les cases de M. Ou alors changer l'ordre la logique, d'abord chercher les cibles puis les actions ?
- B : filtre entre M et la portée inversée depuis la cible, le calcul devrait ne pas être trop long j'espère, soit je fais la portée qui part de la cible et je garde toutes les cases qui sont dans M, soit directement, je regarde pour chaque case de M si cette case peut voir la cible. Ou enfin, je m'arrange pour que dans le calcul A, on sauvegarde pour chaque case de cette union, la liste des cases qui peuvent les voir dans M.
Voilà c'est très conséquent, j'ai pas non plus évoqué les situations où un ennemi pourrait se recharger en ressource puis re-agir, ou se rajouter des points de mouvements. Ne le fait que certaines cases où on marche dessus pourraient activer des pièges/capacités, je pense que ça se fera plus sur le calcul de l'attrait d'une case.
Si vous avez des suggestions de comment faire les calculs de portée ou des ias je suis preneur. Pour information tout ça a pour vocation d'être codée en ruby.
À bientôt
|
Chat
