Algorithme de combat

On a affecté cette tâche à Quentin, mais pour implémenter une solution, il faut quand même l'avoir trouvée. Il faudrait donc qu'on réfléchisse à ce que doit faire l'algorithme, et surtout pour quelles raisons, pour éviter d'avoir des stratégies gagnantes. Mais histoire de changer un peu des habitudes - et surtout parce que j'ai flemme - je ne vais pas faire de pavé de suite

edit 20h37 : en fait Quentin, je vais peut-être te piquer le job. Parce que si on se base sur le gros pavé que je suis en train d'écrire plus bas, tu vas t'emmerder pour pas grand chose, vu que le plus gros du boulot sera de t'adapter à ce dont je parle, ce qui n'est jamais très marrant...
Mais bien sûr, si tu tiens vraiment à le faire te peux hein :p

algoCombat()
{
nbMort = rand(1000);
}

voila

Hem, no comment :p
Bon, cette fois-ci je vais vraiment partir sur un gros pavé donc je vais poster en plusieurs fois mon idée :


Je vais prendre dans mes exemples deux types d'unités :
- des fantassins légers (hp = 40; atq = 20; def = 5)
- des cavaliers lourds (hp = 80; atq = 30; def = 12)

Cas de base : combat entre deux armées identiques

1) 100 fantassins contre 100 fantassins :

100 fantassins = 4000 hp
100 fantassins = 2000 pts d'attaque
100 fantassins = 500 pts de défense
Donc le pourcentage de morts de part et d'autre sera égal à :

Code:

constanteMultiplicative * (2000 - 500) / 4000 = constanteMultiplicative * 37,5%

2) 100 cavaliers lourds contre 100 cavaliers lourds :

100 cavaliers lourds = 8000 hp
100 cavaliers lourds = 3000 pts d'attaque
100 cavaliers lourds = 1200 pts de défense
Donc le pourcentage de morts de part et d'autre sera égal à :

Code:

constanteMultiplicative * (3000 - 1200) / 8000 = constanteMultiplicative * 22,5%

Quand les forces en présence varient (dans le cadre de 1 vs 1)

Par rapport au cas de base, on peut supposer que si un groupe A est en position de force face à un groupe D, il le sera encore plus après un affrontement.

En utilisant la formule du cas de base, on prend cela en compte. Cependant, on oublie un facteur essentiel. Admettons que 1000 soldats en attaquent 100. Bien sûr, ils écraseront les 100. MAIS :
- les 100 soldats sont submergés par les ennemis, donc ils passent leur temps à se battre, et donc leurs capacités sont utilisées au maximum.
- tant que les 100 soldats restent groupés, ils ne peuvent pas être attaqués à 10 contre un. Les soldats de la grosse armée seront obligés de venir au combat petit à petit. En fait, le combat ressemble finalement beaucoup à ce qu'il aurait été si la grosse armée était composée de 200 soldats au lieu de 1000. La seule vraie différence est que dans la grande armée, les soldats morts au front peuvent du coup sans problème être remplacés.

Compte tenu de tout cela, on pourrait avoir :

1) Groupe A : 150 fantassins contre Groupe D : 100 fantassins :

Somme des statistiques, telles qu'elle a été faite dans le cas de base :
- Groupe A : 6000 hp; 3000 pts d'attaque; 750 pts de défense
- Groupe D : 4000 hp; 2000 pts d'attaque; 500 pts de défense

La différence par rapport au cas de base est que l'on va modifier les points d'attaque et de défense du groupe le plus puissant, avant de commencer le combat. Deux facteurs sont pris en compte :
- Le fait que pour chaque groupe, il y a une limite théorique au nombre de soldats pouvant se trouver en face. A cette limite là, on considère que le champ de bataille est noir (ou rouge ) de monde. Quand elle est dépassée, les soldats supplémentaires doivent donc attendre qu'il y ait des morts sur le front pour prendre leur place.
- Le fait qu'être plus nombreux que son adversaire est un handicap sur le plan organisationnel.

Dans l'exemple donné plus haut, le groupe D est moins nombreux que le groupe A, donc il n'a pas de malus. Pour le groupe A, on va chercher à calculer le nombre d'unités qui pourront prendre part activement au front. On détermine cela de la manière suivante :
- on calcule le max d'unités pouvant faire face à B simultanément : 100 * constante = par exemple 100 * 2 = 200 unités.
- Le groupe A est capable d'envoyer 150 unités au front, mais étant plus nombreux que son adversaire, il a un handicap. Il arrive en pratique à mobiliser :
(nbUnitesGroupeA + nbUnitesGroupeD) / 2 = (100 + 150) / 2 = 125 (passage à revoir sûrement, c'est un choix un peu trop fait au pif pour être équilibré)
- on retient la plus petite des deux valeurs : 125. C'est le nombre d'hommes qui se battront contre les 100 adversaires à ce moment.
- on calcule les points d'attaque qu'ont 125 des unités du groupe A : 125 * 20 = 2500 pts
- on calcule les points de défense qu'on 125 unités du groupe D : 125 * 5 = 625 pts

Les stats prises en compte pour le combat seront donc :
- Groupe A : 6000 hp; 2500 pts d'attaque; 625 pts de défense
- Groupe D : 4000 hp; 2000 pts d'attaque; 500 pts de défense

On calcule alors le résultat du combat de la même manière que pour le cas de base :

Code:


- Groupe A : pourcentageMorts = constanteMultiplicative * (2000 - 625) / 6000 = constanteMultiplicative * 22,92% (34,4 morts)
- Groupe B : pourcentageMorts = constanteMultiplicative * (2500 - 500) / 4000 = constanteMultiplicative * 50 % (50 morts)


2 groupes contre 1 : cas simple (groupes de même taille)

Un exemple simple :
- Groupe A1 : 100 fantassins légers
- Groupe A2 : 100 fantassins légers
- Groupe D : 200 fantassins légers

L'idée de base, c'est de considérer qu'il est toujours plus rentable d'attaquer sur deux fronts avec 2*100 unités, que de les grouper. Le danger est qu'il y ait une stratégie imparable toute conne (sauf si l'adversaire fait pareil bien sûr) : diviser plusieurs fois chacun de ses groupes, et systématiquement attaquer de tous les côtés. Mais en fait, je pense que non. Dans le cas présent, A1 et A2 ont un avantage sur D lorsqu'ils l'attaquent. Par contre, lorsque D ripostera, il aura forcément à faire à un groupe plus faible que lui, et donc il aura l'avantage, ce qui équilibre les choses. Il faudra vérifier que ça le fasse vraiment ceci-dit.

Autre chose : difficile de vraiment déterminer quel est l'avantage d'une prise en sandwich dans une bataille à grande échelle, vu que ça dépend de 3 tonnes de choses... Pour simplifier, on peut dire là que ça donne un bonus en attaque et défense aux attaquants, et un malus en attaque et défense aux défenseurs.

Total des stats :
- Groupe A1 : 4000 hp; 2000 points d'attaque; 500 points de défense.
- Groupe A2 : idem
- Groupe D : 8000 hp; 4000 points d'attaque; 1000 points de défense.

Bonus/malus à appliquer :
2 vs 1 => atq +7% aux attaquants, def +7% aux attaquants, atq -7% aux défenseurs, def -7% aux défenseurs (ça le fait pas trop mal je trouve, même s'il reste à tester bien ^^)

Stats incluant les bonus et malus :
- Groupe A (comprend A1 et A2) : 8000 hp; 4280 points d'attaque; 1070 points de défense.
- Groupe D : 8000 hp; 3720 points d'attaque; 930 points de défense.

Calcul de l'issue du combat :
- On détermine le nombre de morts qu'il y aura dans le groupe A et dans le groupe D, de la même manière qu'au point précédent. Les deux groupes ayant exactement le même nombre d'unités, il n'a a aucun malus de ce côté là.

Code:

pourcentageMortsGroupeA = constanteMultiplicative * (3720 - 1070) / 8000 = constanteMultiplicative * 33,125% (66,25 morts)
pourcentageMortsGroupeD = constanteMultiplicative * (4280 - 930) / 8000 = constanteMultiplicative * 41,875% (83,75 morts)


- Il reste à répartir les morts entre A1 et A2.

Code:

mortsGroupeA1 = 3/4 * mortsGroupeA // Parce que le groupe D a choisi d'attaquer A1
mortsGroupeA2 = 1/4 * mortsGroupeA // le groupe D n'a pas choisi d'attaquer ce groupe, mais il faut bien que ses soldats se défendent, donc y'a quelques morts


Survivants dans chaque groupe :
Groupe A1 : 50,3125
Groupe A2 : 83,4375
Groupe D : 116,25
(rapport de force : 1,15 contre 1 en faveur de A)

n groupes contre 1 : cas simple (groupes de même taille)

Même principe que pour des 2 vs 1, à quelques détails près :

Bonus/Malus à appliquer :
2 vs 1 => atq +7% aux attaquants, def +7% aux attaquants, atq -7% aux défenseurs, def -7% aux défenseurs.
3 vs 1 => atq +9% aux attaquants, def +9% aux attaquants, atq -9% aux défenseurs, def -9% aux défenseurs.
>3 vs 1 => pas mieux

Répartition des morts dans le groupe A à réarranger un peu peut-être. Mais la flemme de réfléchir à ça.

n groupes contre 1 : généralisation pour des groupes de même type

Là, on est dans des cas comme, par exemple :
Groupe A1 : 5 fantassins
Groupe A2 : 20 fantassins
Groupe A3 : 200 fantassins
Groupe D : 300 fantassins

La différence avec les cas précédents se trouve dans le choix du bonus à donner au supergroupe "A", et par conséquent du malus à donner au groupe D. Dans un cas où seul l'un des n groupes a une taille significative, on peut considérer que le fait de prendre en sandwich l'adversaire ne sert à rien. Le bonus doit donc être quasi-nul. Au contraire, le bonus doit être maximal lorsque les Ai sont parfaitement équilibrés entre eux (c'était le cas au point précédent). Il faut donc déjà une formule qui puisse nous dire par exemple que A1+A2+A3, c'est comme si on avait une attaque faite par 1,1*A3.
Un algo pour ça :

Code:


max = "puissance" du plus gros Ai
nbRetenuPourBonus = 0;
pour chaque Ai
  nbRetenuPourBonus += puissance(Ai) / max


Calcul de "puissance" :

Code:


Pouet = attaque(Ai) - defense(D) // une indication des dégâts que fait Ai au groupe D
Gneuh = attaque(D) - defense(Ai) // valeur proportionnelle au temps que peut survivre D face à A.
puissance = Pouet * Gneuh // => indication à peu près valable de la force du groupe Ai face à D.


Ça nous donne donc une valeur très proche de 1 si seul un des groupes a une taille conséquente (puisque seul ce gros groupe est à prendre en compte), et qui peut être égale au nombre de Ai s'ils sont tous de taille identique. On peut donc se baser dessus pour calculer le bonus à appliquer. Il doit s'agir d'une fonction continue sur [1;6] ayant pour valeurs :

1 => aucun bonus ni malus
2 => atq +7% aux attaquants, def +7% aux attaquants, atq -7% aux défenseurs, def -7% aux défenseurs.
3 ou plus => atq +9% aux attaquants, def +9% aux attaquants, atq -9% aux défenseurs, def -9% aux défenseurs.

Mais j'ai la flemme d'en chercher une bien pour l'instant

En tous cas, une fois qu'on connaît le bonus/malus à appliquer, on peut gérer la bataille de la même manière que vu précédemment.

Moi je dit le miens est plus rapide à coder

Sinon ouai, pourquoi pas. constante multiplicative c'est quoi ? la ou on va mettre de l'aléatoire ?

Bah c'est pas grand chose à coder en fait, même si je blablate beaucoup ^^

La constante, c'est pas pour l'aléatoire, c'est juste pour paramétrer le truc, vu qu'il faut que les combats ne soient ni trop courts, ni trop longs (100% de pertes en un tour, c'est trop. 0.000034%, c'est pas assez ). Il faudra mieux séparer l'aléatoire de ça pour rendre les choses plus compréhensibles ^^

(dans le cas où tu ne l'auras pas vu, j'ai ajouté la seconde partie au premier post)

troisième partie du pavé ajoutée (ça commence à être long ).
Et c'est pas fini :p

le seul truc c'est que ça va être galère à équilibrer ^^

C'est clair... Mais si on simplifie trop, certes on équilibrera plus vite, mais il restera de grosses failles au bout du compte ^^

constanteMultiplicative * (2000 - 500) / 4000 = constanteMultiplicative * 37,5%

c'est pas HP = ATQ - DEF ??????

C'est exactement ce que j'ai écrit en fait. Je voulais juste mettre en évidence le pourcentage de morts plus que le nombre, d'où la division par le nombre total d'hp.

Cédric a écrit:C'est exactement ce que j'ai écrit en fait. Je voulais juste mettre en évidence le pourcentage de morts plus que le nombre, d'où la division par le nombre total d'hp.

ah oué exacte, j'ai rien dit :p
J'viens de faire le calcule. En même temps a 3h du mat, j'avais plus trop mes esprits :p
Autant pour moi

"au temps pour moi" on dit

bref, esque l'on fait que le bonus d'encerclement marche moins bien en foret ? ou que l'on puisse moins avoir de gars sur la même unité en face ?

non je pense pas, on leur donne le bonus malus de foret. c'est tout non ?

Et pis je dit Autant pour moi, au temps que je veux

Je suis avant tout d'avis d'essayer de valider des règles de base avant de chercher à perfectionner, sinon on ne va pas s'en sortir :p

Sinon, même si "au temps pour moi" est l'expression recommandée par l'académie française, "autant pour moi" n'est pas une faute pour autant. "esque" par contre...

et "ta gueule" c'est recommandé par l'académie française ? De toute façon je suis Dieu alors forcément j'ai raison

J'avais oublié de continuer
Bon bah, j'ai mis deux autres parties du coup ^^

Il ne reste plus qu'à voir ce qu'il faut changer pour faire une généralisation à tout type d'unité (parce qu'un jeu avec seulement des fantassins, c'est bien lourd quand même )

La constante dans tout ça c'est que tu fais toujours aussi peur

Et comme ça ?
http://sonsetcouleurs.net/resources/Casimir+gloubiboulga-+480x359_03.jpg

Bon, j'avoue, c'est pas moi

Donc, pour ce qui est du codage du truc... (Séb, toujours chaud ?)

Pour le prototype de la méthode, il faudrait un truc du genre :
std::map<Coordonnees*,float> attaque(const std::vector<Coordonnees>& attaquants, const Coordonnees& defenseur);

Because :
- il faut pouvoir stocker les dégâts subis par chaque groupe, vu qu'il faut que l'interface les affiche par la suite => map
- on a besoin de connaître la distance entre les groupes (un fantassin ne peut pas riposter contre un archer s'il n'est pas au corps à corps par ex), donc passer les coordonnées au lieu des groupes est quand même plus pratique.



A part ça, j'avais un peu cherché à voir comment on pouvait connaître précisément la distance entre deux cases, vu que le fait d'avoir des faux hexagones bordélifie un peu le truc. En prenant comme point d'origine une case située sur une colonne impaire, donc décalée vers le haut, ça donne ça :

Cases situées à une distance de 1 autour de + :
ooo
o+o
xox

légende : + est la case d'origine, o les points situés à une distance <= 1, et x les points plus éloignés

Distance de 2 :
xooox
ooooo
oo+oo
ooooo
xxoxx

Distance de 3 :
xxoooxx
ooooooo
ooooooo
ooo+ooo
ooooooo
xooooox
xxxoxxx

Distance de 4 :
xxxoooxxx
xooooooox
ooooooooo
ooooooooo
oooo+oooo
ooooooooo
ooooooooo
xxoooooxx
xxxxoxxxx

Distance de 5 :
xxxxoooxxxx
xxoooooooxx
ooooooooooo
ooooooooooo
ooooooooooo
ooooo+ooooo
ooooooooooo
ooooooooooo
xooooooooox
xxxoooooxxx
xxxxxoxxxxx

Et si la case de base est sur une colonne paire, il suffit d'inverser le haut et le bas dans mes trucs tout moches.

On peut donc voir les points situés à une distance donnée comme étant situés sur un losange raboté, ou alors dans un carré privé des angles... Ça se gère, mais en fait, tu gagnerais peut-être du temps à patcher ton A*, même si c'est pas super joli

Bouboup ?

bouboup toi même

Ohhhhh !!! Ça fait plaisir de voir des gens cultivés !

on le met où le code de l'algo de combat ?

std::map<Groupe*,float> calculerAttaque(const std::vector<Groupe*>& attaquants, const Groupe& def);

Par contre je ne sais pas si t'as suivi, mais c'est Séb qui le fait, vu qu'il a perdu son boulot sur le min-max ^^
C'est pas comme si t'étais totalement au chômage technique ceci-dit : il faut réfléchir à l'IA aussi.

ok

Euh en fait, on parlait de laisser ça à Sébastien pour combler son avidité de travail, mais avec les merdouilles qu'on a à faire pour l'IHM, elle s'est vite évaporée, et l'algo n'est toujours pas commencé. Du coup je re-retourne ma veste : Quentin, ça te dit de le faire ?

Il y a quelques trucs à savoir pour implémenter ça, mais j'y reviendrai une fois que j'aurais posté la dernière version du schmilblick.