MountyHall - La Terre des Trõlls

	Ze T-Shirt
MountyHall

Référencé sur

Nous sommes le 2° jour du Gnu du 24° cycle après Ragnarok

Bienvenue Invité

Tous les Forums

Avis et Idées : Modifications

Modérateurs de ce forum : Aghabeu, Dabihul, Grankausto, Loinvu, Madère, Mamoune, Modérateur 6, Modérateur1, Modérateur2, Modérateur3, Modérateur4, Modérateur5, Mr x, Rouletabille, Schtroumpf, TilK, VYS, Xaruth

Si vous avez une idée, n'hésitez pas à en faire part à la communauté. Donnez également votre avis sur les 'features' du jeu.', 'Toutes les suggestions de Modification d'un élément existant seront discutées ici. Soyez objectif, respectez les avis des autres participants et donnez un maximum d'explications de votre choix ou de votre suggestion.

Votre idée doit servir à améliorer le gameplay du jeu et pas à satisfaire un intéret personnel.

Ce Forum sera modéré avec rigueur et aucun débordement ne sera toléré.

Trajectoire de charge et pièges (Résumé)
Pages : [1], 2, 3

#. Message de Indigos Jaunes le 02-11-2006 à 00:15 [Ami de MountyHall]	48766 - ( )
Pays: France Inscrit le : 25-10-2004 Messages: 259 (Golem Costaud)	Citer

Vue la discussion sur ce thème démarrée en 2003 (!) et dont on trouve un résumé validé par le DM ici,

et vues les toutes récentes discussions sur le sujet (avec la participation de Toeaaah et g012 entre autres

) ,

je propose un résumé, aussi objectif qu'il m'est possible

, sur les dernies échanges concernant la détermination de la trajectoire de la charge, qui permettrait de déclencher les pièges se trouvant le long de celle-ci.

Pour commencer, à peu près tout le monde est d'accord sur le fait que cette trajectoire devrait être aussi "droite" que possible. Mais il semble que le calcul efficace de cette trajectoire ait posé des difficultés techniques (si les difficultés techniques dont on a parlé à plusieurs reprises ne sont pas celles-là, dites-moi! )

La bonne nouvelle (d'accord, ce n'est peut-être pas une remarque très objective

) c'est qu'il existe un algorithme très efficace pour calculer justement cette trajectoire, qui porte le nom de son inventeur, Bresenham. Cet algorithme ne travaille qu'avec des entiers, et il est utilisé pour tracer des segments sur des images.

Le pseudo-code est disponible sur Wikipedia (page en Anglais, page en Français, avec une version que je trouve longue du pseudo-code )

Si cette piste est considérée intéressante, il restera à modifier légèrement l'algorithme pour qu'il ne "trace" pas la case de départ...

#. Message de Toeaaah le 02-11-2006 à 08:02	8866 - Toeaaah (Tomawak 44) - Vachement Troll -
Pays: France Inscrit le : 13-06-2003 Messages: 1427 (Trõll de Compèt')	Citer

Je tiens à préciser qu'en résumé, avant optimisation du code, le principe est de considérer les cases comme des points et la trajectoire de la charge comme une droite entre deux de ces points. Ensuite, pour une charge à une distance d, il a d-1 cases à tester pour voir si elles contiennent des pièges. Ces d-1 cases correspondent aux d-1 points équidistants entre eux placés sur la droite (après arrondis des valeurs non-entière).

Ce calcul est déjà simple (les coordonnées du ième point sont simplement : i) = round( x1 + i*(x2-x1)/d ) et y(i) = round( y1 + i*(y2-y1)/d ) ), et l'algorithme accélère encore le calcul si j'ai bien compris en se débarrassant du problème des 1/2 entiers si j'ai bien compris ce qui a été dis dans l'autre sujet.

Toeaaah

#. Message de dekar le 02-11-2006 à 11:34	13124 - ( )
Pays: France Inscrit le : 20-06-2003 Messages: 1101 (Trõll de Compèt')	Citer

L'algo est pas si compliqué, moi je l'avais programmé pour un problème similaire que j'avais eu en Java. Le seul réel problème étant en diagonale pure. Puisque la 'droite' de charge passe pile entre toutes les cases, est ce qu'on considère qu'aucun piège est déclenché, ou alors on considère toutes les cases comme explosables (parce que dans ce cas là, bonjours les degats, pour une charge à une case de distance en diagonale, on peut déclencher 2 pieges d'un coup...

#. Message de Toeaaah le 02-11-2006 à 12:03	8866 - Toeaaah (Tomawak 44) - Vachement Troll -
Pays: France Inscrit le : 13-06-2003 Messages: 1427 (Trõll de Compèt')	Citer

Quote: Originally posted by dekar on 2006-11-02 11:34:56
L'algo est pas si compliqué, moi je l'avais programmé pour un problème similaire que j'avais eu en Java. Le seul réel problème étant en diagonale pure. Puisque la 'droite' de charge passe pile entre toutes les cases, est ce qu'on considère qu'aucun piège est déclenché, ou alors on considère toutes les cases comme explosables (parce que dans ce cas là, bonjours les degats, pour une charge à une case de distance en diagonale, on peut déclencher 2 pieges d'un coup...

Il n'y a aucun problème pour la diagonale pure: la trajectoire passe pile au milieu des cases !
Par exemple, pour charger de 0,0 en 3,3 y'a une distance de 3, donc deux cases à traverser, et ce sont tout simplement les cases 1,1 et 2,2.

Ou alors j'ai pas compris ce que tu voulais dire ?

Toeaaah

#. Message de dekar le 02-11-2006 à 12:09	13124 - ( )
Pays: France Inscrit le : 20-06-2003 Messages: 1101 (Trõll de Compèt')	Citer

Non je me suis mal exprimé en fait.
C'était pour savoir quelles cases seraient considérées lors d'une diagonale pure, parce que bon pour peu qu'on dévie un peu de la diagonale, le nombre de cases traversées par la droite imaginaire peut sacrément augmenter.

Genre sur cette image:

Ils grisent pas vraiment toutes les cases réellement traversées par la droite. Donc dans le cadre d'une diagonale pure je me demandais si seules étaient considérées les cases de la diagonale ou aussi celle se touchant sur la droite de charge...

#. Message de Indigos Jaunes le 02-11-2006 à 13:58 [Ami de MountyHall]	48766 - ( )
Pays: France Inscrit le : 25-10-2004 Messages: 259 (Golem Costaud)	Citer

Dans tous les cas, la trajectoire entre deux cases (x0, y0) et (x1, y1) comportera un nombre de cases égal à la distance entre les deux cases moins un (si on ne compte pas la case de départ ni celle d'arrivée).

Donc toutes les cases traversées ne sont pas forcément choisies. Dans ton exemple, dekar, le segment tracé par l'algorithme de Bresenham est bien celui qui est grisé.

#. Message de dekar le 02-11-2006 à 14:01	13124 - ( )
Pays: France Inscrit le : 20-06-2003 Messages: 1101 (Trõll de Compèt')	Citer

Il y a donc une part d'aléatoire dans les cases choisies?

#. Message de Indigos Jaunes le 02-11-2006 à 14:40 [Ami de MountyHall]	48766 - ( )
Pays: France Inscrit le : 25-10-2004 Messages: 259 (Golem Costaud)	Citer

Non, il n'y a pas d'aléatoire. L'algorithme est complètement déterministe.

L'idée est la suivante : pour faire la boucle, on choisit l'axe qui correspond à la pente la plus faible. Dans ton exemple, c'est l'axe horizontal (par convention, disons l'axe des x). Ensuite, pour chaque colonne, l'algo revient à prendre la case la plus "entamée" par le segment. Sauf qu'il n'est pas du tout question de calcul d'aires, ou de fractions. Tout est fait très efficacement avec des entiers.

En cas d'égalité entre deux cases (par exemple, le segment entre (0, 0) et (2,1) : faut-il prendre (1,0) ou (1,1) ? ) le choix est indirectement fait par l'inégalité, stricte ou pas.

#. Message de JoeyStarr le 02-11-2006 à 14:47 [Ami de MountyHall]	18138 - ( )
Pays: France Inscrit le : 12-01-2004 Messages: 388 (Golem Costaud)	Citer

Je prends le truc en passant, et je vois que y'en a ici qui font des merveilles !

En fin de compte, c'est ni plus ni moins une droite tirée entre 2 points sur un tableau Excel, et on prend une case par une case celle où y'a le plus de droite... oui, je suis pas clair, mais j'ai du mal à expliquer aussi bien que vous aut'

mais le dessin de dekar montre l'exemple.
Ce que je veux dire, c'est que sans avoir une représentation visuelle de la trajectoire, j'ai du mal. Bah avec cette formule, y suffit d'avoir un tableur quelconque et on trouve la solution sans calcul compliqué machin tout ça.

Bref, carrément pour

Joey, après les BMM ? AIEUH !

#. Message de Toeaaah le 02-11-2006 à 16:14	8866 - Toeaaah (Tomawak 44) - Vachement Troll -
Pays: France Inscrit le : 13-06-2003 Messages: 1427 (Trõll de Compèt')	Citer

Ah ben non ! avant, c'est quand même plus facile

! (enfin je pense...)

Toeaaah

#. Message de dekar le 02-11-2006 à 16:22	13124 - ( )
Pays: France Inscrit le : 20-06-2003 Messages: 1101 (Trõll de Compèt')	Citer

Oui c'était certes plus facile.
Moins fun pour les trolls piégeurs par contre...

#. Message de Toeaaah le 05-11-2006 à 22:21	8866 - Toeaaah (Tomawak 44) - Vachement Troll -
Pays: France Inscrit le : 13-06-2003 Messages: 1427 (Trõll de Compèt')	Citer

Heu... on pourrait savoir si on est dans le vrai ou pas ?

Toeaaah, uppeur

#. Message de Shaksgärt le 05-11-2006 à 22:39 [MH Team] [Ami de MountyHall]	110844 - Pesch (Skrim 49)
Pays: France (68 - Haut-Rhin) Inscrit le : 03-11-2004 Messages: 2294 (Djinn Tonique)	Citer

J'comprends rien

shaks, ignare

#. Message de madtotoro le 05-11-2006 à 22:45	40620 - MadTotoro (Tomawak 60) - MadFamily -
Pays: France Inscrit le : 19-09-2004 Messages: 1143 (Trõll de Compèt')	Citer

Quote: Originally posted by Indigos Jaunes on 2006-11-02 00:15:28
Pour commencer, à peu près tout le monde est d'accord sur le fait que cette trajectoire devrait être aussi "droite" que possible. Mais il semble que le calcul efficace de cette trajectoire ait posé des difficultés techniques (si les difficultés techniques dont on a parlé à plusieurs reprises ne sont pas celles-là, dites-moi! )

Non, non, non monsieur.
Moi je pense que cette trajectoire doit etre la plus courte et la plus aleatoire possible.
Ainsi les difficultés techniques liées au calcul de la trajectoire disparaissent.
Et le piegeur peut se proteger assez facilement sur une courte trajectoire mais difficilement sur une longue et le hasard reste relativement important car rien n'est absolu dans le hall...

MadTotoro, piegeur

#. Message de Toeaaah le 06-11-2006 à 00:51	8866 - Toeaaah (Tomawak 44) - Vachement Troll -
Pays: France Inscrit le : 13-06-2003 Messages: 1427 (Trõll de Compèt')	Citer

Qu'entends-tu par une trajectoire "courte et aléatoire qui réduit les difficultés techniques ?"

Et puis Indigos Jaunes souhaite, je cite "une trajectoire devrait être aussi "droite" que possible" et toi, je cite, "la trajectoire doit etre la plus courte". Or, la trajectoire la plus courte entre deux points... c'est aussi la plus droite !!

Et notre technique de calcul est droite et courte, et y'a même de l'aléatoire sur les 1/2 entiers !

Toeaaah

#. Message de Troll de Dame le 06-11-2006 à 01:22	54570 - Tony Truand (Tomawak 60) - Cons Trolls Alt Sup -
Pays: France Inscrit le : 23-09-2005 Messages: 3563 (Djinn Tonique)	Citer

Quote: Originally posted by Toeaaah on 2006-11-06 00:51:10
Or, la trajectoire la plus courte entre deux points... c'est aussi la plus droite !!

C'est aussi ce que j'aurais dit à priori, mais bon, les lois du Hall semblent impénétrables...

#. Message de Agulla le 06-11-2006 à 06:33	77514 - Agulla (Tomawak 43) - Atra Caterva -
Pays: France (47 - Lot-et-Garonne) Inscrit le : 27-04-2006 Messages: 2369 (Djinn Tonique)	Citer

Quote: Originally posted by Toeaaah on 2006-11-06 00:51:10
Or, la trajectoire la plus courte entre deux points... c'est aussi la plus droite !!

Mouais mais mathématiquement ça dépend dans quel type d'espace tu réside. En Euclidien aucun soucis, le plus droit c'est la ligne, en Rieman ou Lobatchewski là par contre il existe une quasi infinité de trajectoire à temps ou longueur minimale (le OU n'est pas un hasard) qui sont bien loin de la ligne droite (courbes circulaires ou courbes hyperboliques suivant les cas).

Pour le détail, ce type d'espace non euclidien est utilisé pour les loies d'impact des atomes (type cyclotron) ou pour les trajets spatiaux (notamment on a jamais utilisé de ligne droite pour aller de la terre à la lune)

Dans le hall, vu que l'espace est constitué d'entiers, il est improbable (à qques exceptions près) de réaliser une ligne droite entre 2 coordonnées, la "ligne" la plus courte sera toujours une succession de segments suivants l'axe X ou Y puis l'axe XY (ou XnY). Tout ceci encore bien loin d'une ligne droite.

Ex pour aller de 0-0 en 7-3, il existes de nombreux chemins, tous "courts":
qqus uns:
0-0 1-1 2-2 3-3 4-3 5-3 6-3 7-3
0-0 1-0 2-0 3-0 4-1 5-2 6-3 7-3
0-0 1-0 2-1 3-1 4-1 5-2 6-2 7-3

Le problème est de trouver un algorithme simple pour "choisir" quel trajet utiliser, d'ou celui de la pente minimale que je trouve à mon sens le plus "simple" car pour deux positions distincte c'est un des algorithmes qui donne toujours le même résultat.

A mon sens il ne devrait pas y avoir d'aléatoire dans le calcul de cettetrajectoire de charge. Autant le chargeur sait exactement ou il arrive, autant le piègeur doit avoir la possibilité de prévoir une trajectoire pour se défendre.

#. Message de madtotoro le 06-11-2006 à 10:23	40620 - MadTotoro (Tomawak 60) - MadFamily -
Pays: France Inscrit le : 19-09-2004 Messages: 1143 (Trõll de Compèt')	Citer

Je veux dire par courte que si on charge une cible a 3 cases, le deplacement pendant la charge ne doit etre que de 3 cases.

Je veux dire par aleatoire, que la prochaine case sur laquelle le chargeur va poser le pied doit etre tiré au sort parmis les cases qui le rapproche de sa cible.

La plus droite est la plus courte mais ce n'est pas obligatoirement la seule !!!

Prenons l'exemple de 2 trolls séparés par 1 case:
A est en x=0 y=0
B est en x=0 y=2

A peut charger B en passant par x=0 y=1 ou x=1 y=1

Le nombre de case parcouru est le meme (et la distance aussi) et le choix entre ces 2 parcours doit se faire de maniere aleatoire.
Ainsi le piegeur doit poser 2 pieges pour etre sur d'abimer le chargeur.

Le cas particulier etant la diagonale ou le parcours du chargeur est unique pour pouvoir se rapprocher de la cible a chaque deplacement.

C'est ce que j'avais ecrit plus simplement ici

Du coup, c'est l'inverse de ce que dit Agulla. Le piegeur doit pouvoir se defendre mais il doit aussi, si possible, pouvoir laisser une chance au chargeur de passer entre les mailles du filets (sauf si le piegeur a truffé la zone et que les mailles du filet sont trop fines.

MadTotoro

#. Message de Agulla le 06-11-2006 à 10:59	77514 - Agulla (Tomawak 43) - Atra Caterva -
Pays: France (47 - Lot-et-Garonne) Inscrit le : 27-04-2006 Messages: 2369 (Djinn Tonique)	Citer

Quote: Originally posted by madtotoro on 2006-11-06 10:23:47
A peut charger B en passant par x=0 y=1 ou x=1 y=0

Tu as du vouloir dire en passant par x=0 y=1 ou x=1 y=1 mais j'ai compris

A mon avis il ne faut pas cette part d'aleatoire, d'abord parce que une charge c'est pas fin :p et surtout car pour des trajet simple comme dans ton exemple de charge à 2 cases il y a deja 3 chemins possibles à calculer, imagine pour des charges à 4 5 voire 6 cases la masse de calculs que cela peut donner et le nombre de possibilités à etudier.

pour une trajectoire ''simple'' suivant uniquement les X ou les Y c'est la ou il y a le plus de possibilités qui se montent deja à 17 possibilites (sauf erreur) pour une charge à 4 cases.

#. Message de Le amp le 06-11-2006 à 11:06	63422 - amp (Durakuir 54) - La Fine Equipe -
Pays: France Inscrit le : 17-07-2005 Messages: 333 (Golem Costaud)	Citer

Je suis pour une trajectoire déterministe : une charge, ce n'est pas du slalom !
Le chargeur fonds sur sa cible et s'il y a des pièges sur son chemin il les décléenche, point barre.
Après, qu'on choisisse l'algorithme de Bresenham ou un autre, peu importe même si je préfère (car plus simple même si le trajet aller et le trajet retour entre 2 cases ne se fait pas par le même chemin, et aussi parce que c'est celui des gowaps) celui présenté par Gorakiki ici qui consiste à commencer par des déplacements en diagonale jusqu'à égaler l'une des coordonnées puis un déplacement en ligne droite en ne modifiant plus que la dernière coordonnée.

Amp

#. Message de Agulla le 06-11-2006 à 11:42	77514 - Agulla (Tomawak 43) - Atra Caterva -
Pays: France (47 - Lot-et-Garonne) Inscrit le : 27-04-2006 Messages: 2369 (Djinn Tonique)	Citer

Une solution.... (parmis tant d'autres)

Pages : [1], 2, 3

Pour poster une réponse sur ce Forum, vous devez d'abord vous connecter

Si vous n'êtes pas encore enregistré, vous devez d'abord vous inscrire.

[ Contact : ] - [ Heure Serveur : 09:25:40 le 04/05/2026 ] - [ Page générée en 0.005 sec. ]