[Algorithme] Trouver tous les couples de coordonées entier d'une droite

[Sephi-Chan]

On ne peut pas forcément trier soi-même.

[niahoo]

Mouais, si tu récup les données sous forme de liste je vois pas pourquoi tu ne saurais les trier.

[Argorate]

En fait, je n'ai pas envie de m'amuser a comprendre l'algo, du coup je ne sais absolument pas dans quel ordre il fait les choses, la seul chose que je sais c'est que j'ai pas forcement les couples dans l'ordre, alors oui je peux faire un array_flip() (ou un truc comme ça) pour avoir le sens inverse, mais dans ce cas ma question est: es-ce suffisant? et dans quel cas dois-je le faire?

[niahoo]

Je comprends pas, tu t'en fous de l'algo, c'est une boîte noîre. tu prends le résultat, et tu le tries, simplement. Et oui ça doit être suffisant.

---

il te faudra par exemple trier sur les X sauf si les cases sont toutes de la m^me colonne.

[php_addict]

bah oui tu te prends la tête pour rien...tu sort tes couples de ton algo et tu n'as plus qu'à trier...soit pragmatique, ca te prend 2 lignes de php au lieu d'y passer plusieurs heures à trouver une autre solution...on s'en fout si l'algo sort les résultats triés, ce qui est important c'est que ca marche, point barre...

sauf si tu as des milliers de données cette optimisation pourrait se comprendre mais bon...

[niahoo]

Si il a des miliers de données c'est le calcul des cases qui va être lent de toute façon.

[sclabet]

salut,

déjà cet algorithme est fait pour tracer des traits "esthétiques", il ne regarde pas si la droite passe ou non par la case, il teste simplement l'ordonnée (ou l'abscisse, ça dépend des cas) correspondant aux valeurs entières(plus 1/2) sur la droite et regarde si c'est plus proche du centre de la case de la gauche ou de droite (du haut ou du bas dans l'autre cas)

l'algo te renvoie un ordre qui peut être soit le bon, soit complètement l'inverse (si c'est le cas tu n'as qu'a retourner ta liste...

mais toi tu t'en fout... si ce qui t'intéresse c'est plus de savoir si ta droite rentre suffisamment dans ta case (genre pour toucher ou non ton personnage qui s'y trouve) ( exemple : dans le cercle qui part du centre de ta case et qui touche les bords de ta case) et surtout tu n'as pas beaucoup de test à faire (juste pour quelques personnages en fait)

exemple de test : (je pars d'un repère où les coordonnées des points qui se situent au centre de chaque case, ajouter des demis au besoin à toutes les coordonnées de tes cases)
position du joueur : (X1;Y1)
position de la case visée par le joueur (X2;Y2)
position du MOB : (Xi;Yi)

pour chaque mob il faut faire le test : ( je te passes les détails mathématiques...)
((Y2-Y1)Xi + (X1-X2)Yi + Y1X2-Y2X1)² < 1/4 * ((X1-X2)² + (Y2-Y1)²)
si c'est vrai ton mob est touché (visible^^) sinon ça passe pas suffisamment dans la case pour le voir...
remarque : avec ça tu peux introduire une notion de grosseur de ton mob, pour un mob dont la grosseur (rayon de ton cercle, notée r) varie de 1 à 10 (1 étant le mob filiforme et 10 étant le fat mob qui touche les bords de ta case)
la formule deviens :
((Y2-Y1)Xi + (X1-X2)Yi + Y1X2-Y2X1)² < r²/400 ((X1-X2)² + (Y2-Y1)²)

voilà, j'espère que ça t'aide

ps : modif d'oubli d'une parenthèse...

[Argorate]

Ce n'est pas pour la visé mais pour savoir le chemin le plus droit vers une cible.
Si c'est sur qu'il n'y a que le cas où la liste est strictement inversé c'est facile du coup.

Sinon le fait de trier c'est bien mais je trouve ça dommage de perdre du temps en augmentant la complexité de l'algorithme de base en les triant en plus...

je vais tester le coup de l'inversion

[niahoo]

Attends, tu savais que le seul cas où la liste n'est pas triée c'est quand elle est triée à l'envers, mais il a quand même fallu que tu demandes notre avis pour penser à l'inverser ??

[sclabet]

ce n'est pas une perte de temps en fait...

il y a un régionnement du plan en fonction de la direction que prend ta droite... (le concept de gauche droite n'a pas de sens pour une droite verticale par exemple )

mais je suis d'accord avec toi, dans le deuxième algo, il aurai pu exclure ces cas et faire des symétries...