Le probleme est le suivant :
J'ai un monde spherique represente par un tableau.
Dans ce monde, se trouvent deux joueurs (A et B) ayant donc chacun leurs coordonnees.
Je cherche depuis plusieurs heures un algo simple me permettant de trouver les coordonnees de la case franchie par le chemin le plus court entre A et B avant d'arriver au joueur B, afin qu'il puisse savoir dans quelle direction se trouve le joueur A.
 
Si vous avez des idees, je suis preneur.
 
Merci d'avance

Un monde sphérique avec un tableau ?

Disons que quand un des joueurs depasse la hauteur ou la largeur du tableau, il repasse de l'autre cote.

A donc c'est plus un tore qu'une sphère.
 
Dans ce cas il faut reproduire ton tableau par translation et tu compares les chemins possibles.

J'ai dejà fais l'algo qui decide si le chemin est "direct" ou "indirect" mais je n'arrive pas à trouver l'algo pour déterminer la dernière case du chemin rectiligne.
 
PS: j'ai l'impression que je suis pas très clair alors demain je fais un scan avec un exemple.

Suit les indications de Verdoux :
T es sur un tors donc il y a 9 chemins pour aller de A vers B
trajet direct, trajet vers B par la frontiere du haut, celle de droite, celle du bas, et, celle de gauche. Puis il a les combines haut-gauche, haut-droite, etc.
 Moi je decouperais mon tableaux en 9 sous zones  
123
456
789
 
pour analyser si les points sont dans la meme sous-zone, le chemin le + cours est forcement dans cette sous-zone inutile de chercher ailleurs
Si ils ne sont pas dans la meme sous-zone ils sont forcement dans des sous-zonnes adjacentes par exemple si A est dans la zone 1 et que B n'est pas dans 1...
B peut etre dans 2,4,ou 5 et il faut utiliser le chemin direct
si B est dans 3 ou 6 il faut aller vers la gauche, si B est dans 7, 8, ou 9 il faut aller vers le haut...
voir le tableau sous la forme
978
312
645
 
Une autre facon de faire est d'utiliser des modulos pour acceder a ton tableau (ce qui reproduit l'effet torique)
puis faire un changement de coordonnes pour que A se trouve au milieux du tableau, le chemin lke plus cours vers B est alors le chemin direct

j'aimerais bien t'aider aussi mais ce n'est pas tres clair, alors donne un peu plus de precisions ou un beau dessin je crois que c'est le mieux.

Voici le sujet et l'exemple :
 

 

J'avais fait cela il y a longtemps (une sombre histoire de réseaux de Transputers), et la solution de Verdoux est juste.
Le plus simple est que tu réduises le problème à sa solution à 1 dimension, et ensuite tu généralises à n dimensions en appliquant ta solution pour chaque dimension de ton (hyper-)espace.
 
Ici on est en 2 dimensions. Donc, si DIM(1) et DIM(2) sont les dimensions de ton tableau à 2 dimensions, tes points A et B ayant pour coordonnées (x1A, x2A)  et (x1B, x2B).
 
Pour chaque dimension ß (ici, ß=1 puis 2), en supposant que xßB > xßA, il te faut comparer les distances xßB - xßA et xßB - (xßA + DIM(ß)). Tu prends la plus petite distance des 2, et tu sauras pour cette dimension-là si tu dois passer par la "frontière" ou pas.
 
Si pour l'une des dimensions ß, tu as xßB <= xßA, il faut alors que tu compares xßA - xßB et xßA - (xßB + DIM(ß)) au lieu des 2 distances que j'ai écrites plus haut.

[edit]--Message édité par BifaceMcLeOD--[/edit]

en fait, j'ai déjà fait l'algo qui me permet de trouver le chemin le plus court :
 
si xa > xb
  direct_path_x = xa - xb
sinon
  direct_path_x = xb - xa
 
si ya > yb
  direct_path_y = ya - yb
sinon
  direct_path_y = yb - ya
 
indirect_path_x = world_width - direct_path_x
 
indirect_path_y = world_height - direct_path_y
 
Il me suffit ensuite de comparer les valeurs obtenues pour savoir quel chemin je doit prendre.
 
Je pensais me ramener à un chemin direct dans tous les cas, en passant un des deux point en coordonnees negatives, mais ca ne me trouve pas la derniere case par laquelle le son passe.

Bon bah tu y es...  

Je sais quel est le chemin le plus court mais je ne sais pas l'utiliser pour trouver la fameuse case

Tu dois pouvoir t'en sortir en t'inspirant de l'algo de Bresenham pour le tracé des lignes.

Oups ! J'avais pas compris.
Encore exact Verdoux.

En fait c'est pas sûr. Déjà si on regarde ton dessin, dans le cas du haut il faut considérer que le signal arrive de la case 4 ou de la case 3 ?

case 3
 
j'ai une technique qui fonctionne mais qui est très porc : je définit des "plages de cases sources possibles" pour chaque case proche du la cible (j'ai donc 8 zones définies).

 
c'est koi cet algo et où je peux le trouver

Ca veut dire que c'est seulement quand les 2 objets seront sur une diagonale que les cases 2,4,6 et 8 seront utilisées ?
Auquel cas, c'est pas trop dur, il suffit de regarder la pente du rayon entre les 2 objets.

La formule du coéficient directeur c'est bien : (x2 -x1)/(y2 - y1)?

Ben Bresenham, c'est ce qu'il y a de plus efficace, mais si tu veux faire simple et que tu peux te permettre quelques divisions, le calcul de la pente, c'est ce qu'il y a de plus facile à programmer.
 
Verdoux>   Ben non, la diagonale est utilisée plus souvent que cela. S'il doit aller de (0, 0) à (x=3, y=2), il va passer par (1, 1), (2, 1) puis (3, 2). Donc il aura bien utilisé la diagonale à partir de (0, 0).
 
titoine> Tu ne peux pas arriver par la case 3 dans l'exemple que tu as donné. Car dans ce cas, le chemin utilisé n'est pas le plus court.

[edit]--Message édité par BifaceMcLeOD--[/edit]

Non, son inverse :  (y2 - y1) / (x2 - x1)

ça fait longtemps que j'ai pas fait de maths

D'après ce que j'ai compris pour aller de (0,0) à (3,2) dans sa logique, le chemin sera:
(0,0) - (1,0) - (1,1) - (2,1) - (2,2) - (3,2)
C'est pour ça que Bresenham n'est sans doute pas adapté.

Oui et non.
Soit il a un réseau où chaque case est connectée à 4 cases voisines -- dans ce cas, pas de diagonale et tu as raison -- soit chaque case a huit cases voisines et là, comme je le disais plus haut, le chemin que tu donnes n'est pas minimal : il te faut passer par 6 cases alors que le chemin que je donne ne passe que par 4 cases (cases de départ et d'arrivée incluses, évidemment) !

C'est pour ça que j'avais posé la question sur les cases 3 et 4.
 
Dans son dessin, si on dit que le rayon passe par la case 3 pour l'objet du haut (et de même par la case 5 pour l'objet du bas), le chemin ne sera pas minimal dans ton sens.
 
Le chemin semble dans son cas défini par l'ensemble des cases traversées par le rayon.

les joueurs ne se déplacent que dans les quatre directions cardinales mais le sont n'est pas dépendant des cases, il fait le chemin le plus court

OK, dans ce cas, on considère que son réseau est carré... (au passage, ta question était effectivement très judicieuse, puisque l'énoncé est flou de ce point de vue    ).
 
Mais c'est tout le problème de passer d'un système continu à un système discret. Il faut que titoine décide ce qu'il choisit, i.e si chaque case de son réseau a 4 ou 8 voisines. Mais s'il choisit la solution 4 voisines, il ne peut plus y avoir de chemin diagonal : le chemin (1,1) vers (3,3) doit forcément passer par (1,2) ou (2,1), puis par (3,2) ou (3,2). Sinon, il y a incohérence.

titoine> Ce n'est pas une bonne façon de raisonner à mon avis. Imagine que tes cases soient en fait des pièces carrées dans un bâtiment. Les cloisons entre les pièces sont telles qu'elles isolent totalement les pièces les unes par rapport aux autres du point de vue sonore. Dans chaque pièce, sur chacun des 4 murs, tu as un haut-parleur et un micro, qui font ce qu'est en train de faire ton algorithme, pour transmettre des sons d'une pièce à un autre. Si tu te mets au centre d'une des pièces et que tu écoutes, tu n'entendras jamais un son venant d'un coin de la pièce. Seulement d'un des 4 murs. Même si en fait le son était diagonal.
 
Bref, c'est une contrainte du réseau carré.

[edit]--Message édité par BifaceMcLeOD--[/edit]

dans le cas présent, j'ai pas trop le choix car c'est le sujet du projet qui l'impose :
 - les joueurs se deplacent de case en case en fonction de leur direction (NORD, EST, SUD et OUEST)
 - le son lui ne suis pas les cases ete va directement du joueur A au joueur B

La question est donc : est-ce que tu dois décrire le chemin le plus court qu'un joueur devrait parcourir pour rejoindre la source du son qu'il a entendu ? Ou, en supposant que le son est strictement directionnel (ce que je trouve déjà aberrant comme hypothèse   ), l'ensemble des cases depuis lesquelles on peut entendre le son émis par A (en supposant aussi que le son s'arrête net en B) ?
 
Heu... en fait, ça doit être la même chose, mais bon...  
 
Ce que je veux dire, c'est qu'il y a une incohérence dans ce que tu dis : dès lors qu'on raisonne de manière discrète (sous forme de cases), le son ne peut pas "ne pas suivre les cases". Il passe par une case ou il n'y passe pas, point. Mais tu ne peux pas faire correspondre un monde discret et un monde continu. Il te faut décider (si l'énoncé ne le fait pas) un critère (forcément un peu arbitraire, donc) pour mapper le monde continu sur ton monde discret.

[edit]--Message édité par BifaceMcLeOD--[/edit]

Je veux juste avoir la provenance du son pour B, ainsi, à chaque tour, A appelera B, et B avancera d'une case en fonction de la provenance du son.
Je me sert du chemin le plus court à parcourir par A ou B afin de déterminer la direction approximative du chemin parcouru par le son.
Quoi?! Je suis pas clair!  

Ben il me semble que si : ton réseau est bel et bien carré. Donc pas de chemin diagonal possible.

Je suis trop une buse : je faisait mes petits test et je me rends compte que mon calcul de coeficient directeur me sort des valeurs bizarres... au bout de quelques minutes, je me dis: "bizarre, j'ai que des valeures entieres"... une seconde plus tard ca t'apprendra a travailler avec des int tete de bite
 
PS: oui je sais, je parle tout seul et en plus je m'insulte et alors !!!!????

euhhhhhhhhhhhhhhhhh, j ai du me planté de Forum là!!!!!  
Je vais retourné sur celui de LoftSTORY  
C est chaud l algo!

C'EST PAS FINI!
 
J'ai maintenant les coordonnees du point d'arrive du son
mais je vois pas trop comment je vais faire pour retrouver
l'indice de la case en fonction de l'orientation.
 
Un petit peu d'aide ne serait pas de refus.

[edit]--Message édité par titoine42--[/edit]

Encore ?!
 
Sors la tête de l'écran, prends du papier et un crayon, vas dans un parc, loin d'un PC, et fais des dessins pour illustrer ton pb, une solution devrait apparaître.

en fait, c'est ce que je fais mais la solution que j'ai trouvee
est simple mais ca passe par une rotation de matrice a 2 dimensions
et je ne sais pas le faire.

tu dois faire :
  1. une rotation à l'aide de matrices 2d,
  2. faire tourner une matrice 2D.
 
?

Les matrices de rotation compatibles avec un réseau carré, y en a pas des masses (4 exactement en comptant la matrice identité).

normalment c'est  
 
rotation de 0° :
[ 1  0]
[ 0  1]
 
rotation de 90° :
[ 0  1]
[ 1  0]
 
rotation de 180° :
[-1  0]
[ 0 -1]
 
rotation de 270° (-90°) :
[ 0 -1]
[ 1  0]
 
j'espere ne pas avoir fait d'erreurs