Discussion :

[wiwaxia]

... Le but premier c'est de faire en sorte que les persos se rangent les uns à côté des autres en arrivant au fur et à mesure...
Un peu comme dans une salle de concert par exemple, ou une manifestation où les gens vont se mettre devant la barrière petit à petit en respectant la place de chacun ...

Cela suggère des coordonnées entières ... les personnages se déplacent-ils dans des cases, sur une grille ?

Peut-on envisager une part d'aléatoire dans leur mouvement ?

PS: Je viens de lire ta réponse, à la question dont j'ai repris la formulation.
Avec des coordonnées réelles, le problème de l'évitement est plus difficile; la solution s'apparente à ce que j'ai déjà indiqué (#14): il faudra pour (N) points calculer à chaque pas (N - 1) distances.

[Flodelarab]

Ok. Compris.



En fait, étant donné une distance d, il te faut trouver le locus de tous les points étant à une distance d de tous les autres objets.
Puis tu détermines le point avec une ordonnée minimale.
C'est ça ?

Sauf que là, la vitesse est considérée infinie.
Avec une vitesse finie, c'est plus dure.
Tu dis vouloir te passer de la physique, mais le mouvement est intrinsèquement de la physique.
Si un petit personnage a la possibilité de se trouver un passage dans un empilement d'obstacles, tu vas bien rigoler à déterminer le passage dans les couloirs en arcs de cercles.

Comment gères-tu le cas du personnage qui ne va pas au bout dans le temps imparti ?

[wiwaxia]

On peut, pour chaque boule prise au hasard, envisager un déplacement aléatoire l'amenant en moyenne un peu plus à droite par un double tirage, par exemple:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
a:= Random; b:= random; 
r:= Dm * a;
t:= (2*Pi)*b;
Dx:= r*(0.5 + Cos(t));
Dy:= r*Sin(t);

Les valeurs moyennes des déplacements vaudront: Dxmoy = (Dm/2)*0.5 = Dm/4 ; Dymoy = 0 .

On pourra envisager jusqu'à 10 tirages par exemple, pour obtenir des distances aux (N - 1) autres points supérieures aux minimums requis; en cas d'échec, on renonce au déplacement et passe à une autre boule, toujours tirée au hasard.

Tu ne vas peut-être pas aimer beaucoup l'aspect mathématique , mais il faudra bien en venir là - quelle que soit le type de solution retenue pour ton problème.

[mazertys17]

Peut-on envisager une part d'aléatoire dans leur mouvement ?

à priori il n'y a pas de problème...mais je ne vois pas en quoi cela est nécessaire ?
Dans le cas où un personnage est bloqué par un autre, il va là où l'angle est le plus petit par exemple (soit en haut soit en bas).

il faudra pour (N) points calculer à chaque pas (N - 1) distances.

Heu oui effectivement...maintenant je crois que c'est pas grave si chaque perso va calculer son déplacement en fonction de la position des autres objets qui changera au fur et à mesure...en somme premier arrivé premier servi (si j'ai bien compris ce à quoi tu fais allusion).

Flodelarab oui ton schéma c'est à peu près ça.
Bon maintenant tous les persos vont avoir le même "cercle", mais c'est pas obligé.


Mais la vitesse je vois pas trop ce que vous voulez dire ?

En fait chaque perso va se déplacer en fonction de sa propre vitesse ce qui fait qu'à chaque boucle de calcul il aura une distance différente à parcourir, ce en fonction de sa "vitesse" (ou devrais-je dire unité de distance) et le temps écoulé d'où :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
 
        x += speed*Surface.elapsedTime ;//Surface étant le thread qui donne un temps écoulé entre les frames et speed étant en fait l'unité de distance, pour au final obtenir la vitesse qui elle est ajoutée à la position

Pour essayer d'être le plus clair possible voilà un petit shémat :


Chaque rond plein représente un personnage et le pointillé et la fleche sa destination quand il bouge.
S'il n'y a aucun obstacle alors il avance tout droit jusqu'à la ligne rouge.
Si en revanche il y a un autre personnage sur son chemin alors, comme sur celui d'en haut de ce shemat, il doit recalculer sa position pour passer à côté en le frolant, pour finalement se positionner au bout à côté s'il peut.
Sinon, il s'arrête et point barre.

J'espère que c'est compréhensible !

[Flodelarab]

Hmmm. Tes personnages pratiquent exclusivement la ligne droite pendant un tour ?

ici, tu montres un cas sans embouteillages. Ma question était le contraire. Comment gérer s'il y a beaucoup d'embouteillage ?



Par où passe la boule rouge ?

Si tu ne vas qu'en ligne droite, le problème devient : "Dans le demi-cercle acceptable, quel est l'angle qui permet d'avancer le plus loin ?"
"Acceptable" veut dire "vers l'avant", "vers la ligne".

[mazertys17]

Flodelarab Bah a la limite le meilleur trajet sera determiné en fonction de l'éloignement par rapport au but :
Plus la nouvelle position sera proche de la ligne plus ce sera celle qui sera choisie.

ici, tu montres un cas sans embouteillages. Ma question était le contraire. Comment gérer s'il y a beaucoup d'embouteillage ?

Tout va dépendre de l'ordre des personnages dans le tableau :

Ex 1 :



Ou :



Dans un cas ou dans l'autre il y en aura toujours un qui l'aura dans le baba et qui sera obligé de ne pas bouger.

Maintenant cela risque de poser effectivement un petit problème de cohérence puisque j'utilise un petit algo qui trie tous ces personnages en fonction d'un Zorder (position Y puisque c de la 2D) pour bien les dessiner.

Donc ce sera systématiquement celui qui est au dessus qui sera calculer d'abord.
Mais bon dans l'absolut je peux me débrouiller pour calculer de façon aléatoire c pas un gros pb.

[wiwaxia]

à priori il n'y a pas de problème...mais je ne vois pas en quoi cela est nécessaire ? ...

Cela permet d'éviter le maintien prolongé d'un blocage, par le déplacement aléatoire de toutes les boules.

... Dans le cas où un personnage est bloqué par un autre, il va là où l'angle est le plus petit par exemple (soit en haut soit en bas) ...

Il faut justement que des déplacements d'orientations différentes soient possibles, pour que les obstacles soient contournables ...

Mais il va de soi que les plus probables sont parallèles à (x'x), et de même sens ... et tu les retrouveras toutes sagement rangées contre le mur de droite.

... Mais la vitesse je vois pas trop ce que vous voulez dire ?

Elle est liée à la vitesse d'exécution du calcul, et à la valeur du déplacement moyen (Dmoy) programmé. On devra prendre pour celui-ci une valeur d'autant plus élevée que le nombre total (N) de boules est plus grand.

[mazertys17]

wiwaxia wow...j'en demande pas tant !

Cela permet d'éviter le maintien prolongé d'un blocage, par le déplacement aléatoire de toutes les boules.

Oui effectivement, c'est une bonne idée!
Mais c'est du bonus, du plus...dans mon cas je ne suis même pas sur que ce soit fondamentalement nécessaire...si quelques persos restent bloqués c'est pas un problème.
D'autre part le but est d'avoir des objets stables qui ne bougent pas dans tous les sens...une fois qu'ils sont au plu près de la ligne, ils y restent normalement.

Il faut justement que des déplacements d'orientations différentes soient possibles, pour que les obstacles soient contournables ...

Ok on peut faire ça en fonction de la ligne d'arrivée exemple entre 2 possibilités, celle qui sera le plus proche de la ligne sera choisie.
Et encore on peut aussi ajouter de l'aléatoire pour diversifier si on a envie.

Ex ici : on compare d1 et d2 et on prend le plus petit (ici d2).






D'ailleurs en pensant à ce shémat peut être que ça peut apporter une solution vu qu'on a un angle droit...
Mais ça biaise un peu la problématique...a moins que ce soit l'élément fondamentalement manquant pour élucider correctement la chose ?

Elle est liée à la vitesse d'exécution du calcul, et à la valeur du déplacement moyen (Dmoy) programmé. On devra prendre pour celui-ci une valeur d'autant plus élevée que le nombre total (N) de boules est plus grand.

Là encore je ne vois pas.
En fait, dans mon cas, je calcule a chaque début de boucle depuis le thread d'affichage, une durée écoulée.
Cette durée écoulée sera utilisée pour tous les éléments du jeu.

Code Java :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
    @Override
    public void onDrawFrame(GL10 gl10) {
        elapsedTime = (time()-time)/1000000000f ;//time() équivaut à System.nanosecond() c'est juste une fonction utilisée pour le cas où le joueur fait pause.
        time = java.lang.System.nanoTime() ;

Donc s'il y a beaucoup de choses a calculer et le tout avec une machine peu performante, le temps écoulé sera plus grand donc chaque distance parcourue de tous les objets va s'adapter et être plus grande ce qui fait que le résultat sera saccadé, certes, mais stable et la distance parcourue sera la même avec un téléphone pourri par exemple qu'avec un super smartphone de la naza...
Enfin en théorie...en tout cas c'est le but recherché.

Donc chaque objet se déplace dans le même révérenciel de temps.

[Flodelarab]

Ok, c'est en ligne droite.

Conclusion : à chaque tour, les coordonnées du centre sont celles du point d'intersection du locus, dont je parlais précédemment, et le cercle, de rayon "avance", et de centre, le centre du personnage. ("avance" = distance dont avance le personnage)
S'il n'y a pas d'intersection, on fonce droit vers la ligne.
S'il y a plusieurs intersections, on choisit la plus proche de la ligne.

Il faudrait même avoir le demi-cercle complet devant le personnage principal et le faire grignoter par les autres personnages.
Obtenant une liste d'arcs de cercles, on déterminerait le point le plus proche de la ligne.

C'est la solution idéale mais le code n'est pas écrit.

Allez, un petit schéma vaut mieux qu'un long discours.
(je n'ai mis que les centres)

[wiwaxia]

Cela permet d'éviter le maintien prolongé d'un blocage, par le déplacement aléatoire de toutes les boules.
Oui effectivement, c'est une bonne idée!
Mais c'est du bonus, du plus...dans mon cas je ne suis même pas sur que ce soit fondamentalement nécessaire...si quelques persos restent bloqués c'est pas un problème.
D'autre part le but est d'avoir des objets stables qui ne bougent pas dans tous les sens...une fois qu'ils sont au plu près de la ligne, ils y restent normalement.

Il ne s'agit pas d'une fioriture, mais du seul moyen pour mener toutes les particules à la position limite disponible la plus à droite, sans recherche compliquée de position.
Le mouvement d'ensemble obtenu est très fluide, et l'on peut très bien faire en sorte que les déplacements deviennent très faibles à l'extrême-droite.
D'ailleurs l'algorithme proposé laisse les particules immobiles lorsqu'elles sont totalement emprisonnées par leurs voisines ou la paroi.

... Ok on peut faire ça en fonction de la ligne d'arrivée exemple entre 2 possibilités, celle qui sera le plus proche de la ligne sera choisie.
Et encore on peut aussi ajouter de l'aléatoire pour diversifier si on a envie.

Ex ici : on compare d1 et d2 et on prend le plus petit (ici d2).



D'ailleurs en pensant à ce schéma peut être que ça peut apporter une solution vu qu'on a un angle droit...
Mais ça biaise un peu la problématique...a moins que ce soit l'élément fondamentalement manquant pour élucider correctement la chose ?

L'angle observé n'est pas droit, et c'est un cas particulier qui n'apporte rien. Cela suppose en plus le calcul de deux positions, ce qui n'a rien de simple ... Et comment procéderas-tu dans le cas de 5 ou 6 voisins peu éloignés ?

Elle est liée à la vitesse d'exécution du calcul, et à la valeur du déplacement moyen (Dmoy) programmé. On devra prendre pour celui-ci une valeur d'autant plus élevée que le nombre total (N) de boules est plus grand.

Là encore je ne vois pas.
En fait, dans mon cas, je calcule a chaque début de boucle depuis le thread d'affichage, une durée écoulée.
Cette durée écoulée sera utilisée pour tous les éléments du jeu ...

Le calcul des distances séparant chacune des (N) particules de leurs (N-1) voisines exige un temps proportionnel au produit N*(N-1):

T₁ = T₀*N*(N-1) .

(D_m) représentant le déplacement horizontal moyen de chaque particule et (L) le déplacement total, la durée de migration du nuage de points aura pour expression approchée:

T = T₁*L/D_m = T₀*N*(N-1)*L/D_m .

La durée d'exécution sera donc approximativement proportionnelle à N² .
Il se peut qu'un logiciel très rapide (T₀ quasi-nul) te laisse toute latitude pour imposer d'autres délais.

[mazertys17]

C'est la solution idéale mais le code n'est pas écrit.

Oui en effet j'avoue que c'est un peu pour ça que je suis là !

Car j'ai un peu du mal a finaliser ce code...

Il ne s'agit pas d'une fioriture, mais du seul moyen pour mener toutes les particules à la position limite disponible la plus à droite, sans recherche compliquée de position.

Hum...ok.
Et concrètement ça donnerait quoi en terme de code ?

[wiwaxia]

Quand je vous disais que les points viennent se ranger sagement à droite, sans qu'on ait à s'ennuyer avec de bêtes problèmes de géométrie ...
Ici N_Point = 1000 , Rmax = 0.01 , Dmin2 = 0.0002 .
On procède à un tirage pseudo-aléatoire:
a) du rang du point concerné: k = 1 + Rand(N_Point) ,
b) de la longueur du déplacement: r = Rmax*Rand ,
c) de l'angle définissant son orientation: t = (2*Pi)*Rand ,
et les coordonnées du déplacement envisagé admettent pour expression:
Dx = r*(0.9 + Cos(t)) , Dy = r*Sin(t) .
On procède jusqu'à 30 tirs d'essai avant de renoncer à trouver une nouvelle position compatible avec les distances.

__

__

__

__

Deux images successives sont séparées par une séquence de 30000 déplacements (réalisés ou non); au delà, l'évolution est beaucoup plus lente.
Les valeurs de la plus petite abscisse (Xmin) sont les suivantes:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
 1   0.000
 2   0.003
 3   0.027
 4   0.063
 5   0.070
 6   0.183
 7   0.292
 8   0.437
09   0.688
10   0.757
11   0.768
12   0.770
13   0.777

[wiwaxia]

... Et concrètement ça donnerait quoi en terme de code ?

Le cœur du programme, c'est ça, et ce n'est pas compliqué :

Code Pascal :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
 CONST NmaxP = 10000;
 
 TYPE Ve2D    = RECORD  x, y: Reel  END;
      LstVe2D = ARRAY[1..NmaxP] OF Ve2D;
 
 VAR N_Point: Word;
     Nuage: LstVe2D;
 
(*HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH
 
 P2 / Migration du nuage
 
HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH*)
 
 PROCEDURE Aff2b(Nd: Word; Xm: Reel);
   CONST C2 = 30; L1 = 20;
   BEGIN
     E(0010); We(C2, L1 - 1, Nd, 9);
     Wr(C2, L1 + 1, Xm, 2118)
   END;
 
 PROCEDURE Aff2a;
   CONST C1 = 2; L1 = 20;
   BEGIN
     E(0015); Wt(C1, L1 - 1, 'Nombre de d‚placements: Nd = ');
     Wt(C1, L1 + 1, 'Abcisse minimale:       Xm = ')
   END;
 
 PROCEDURE CalcXmin(Np: Word; VAR Xm: Reel; VAR Nu_: LstVe2D);
   VAR k: Word; Min, u: Reel;
   BEGIN
     Min:= 1;
     FOR k:= 1 TO Np DO BEGIN
                          u:= Nu_[k].x; IF (Min>u) THEN Min:= u
                        END;
     Xm:= Min
   END;
 
 FUNCTION Dist2(W1, W2: Ve2D): Reel;
   VAR X2, Y2: Reel;
   BEGIN
     X2:= Sqr(W1.x - W2.x); Y2:= Sqr(W1.y - W2.y); Dist2:= X2 + Y2
   END;
 
 FUNCTION TestXY(K1, Np: Word; W1: Ve2D; VAR Nu_: LstVe2D): Bool;
   CONST D2min = 0.0002;
   VAR k: Word; D2: Reel; Test, TestX, TestY: Bool;
   BEGIN
     Test:= True;
     FOR k:= 1 TO Np DO
       IF (k<>K1) THEN BEGIN
                         D2:= Dist2(W1, Nuage[k]);
                         IF (D2<D2min) THEN Test:= False
                       END;
     TestX:= ((0<W1.x) AND (W1.x<1));
     TestY:= ((0<W1.y) AND (W1.y<1));
     TestXY:= Test AND (TestX AND TestY)
   END;
 
 PROCEDURE Migration(VAR Nu_: LstVe2D);
   CONST Rmax = 0.01; D_Pi = 2 * Pi;
   VAR k, Ntir: Word; Ndep: Z_32; Ct, Dx, Dy, r, St, t, u, Xmin: Reel;
       W: Ve2D; Test: Bool;
   BEGIN
     Ndep:= 0;
     REPEAT
       Inc(Ndep); Ntir:= 0;
       REPEAT
         Inc(Ntir);           k:= Random(N_Point); Inc(k);
         u:= Random;          r:= Rmax * u;
         u:= Random;          t:= D_Pi * u;
         St:= Sin(t);         Ct:= Cos(t);         u:= Ct + 0.9;
         Dx:= r * u;          Dy:= r * St;
         W.x:= Nu_[k].x + Dx; W.y:= Nu_[k].y + Dy;
         Test:= TestXY(k, N_Point, W, Nuage)
       UNTIL ((Ntir=20) OR Test);
       We(20, 25, Ntir, 6);          // Instruction de contrôle, à supprimer
       IF Test THEN Nu_[k]:= W;
       CalcXmin(N_Point, Xmin, Nuage);
       Aff2b(Ndep, Xmin)
     UNTIL ((Ndep=30000) OR KeyPressed)
   END;
 
(*HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH
 
 P0 / Initialisation du nuage de points
 
HHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHHH*)
 
 PROCEDURE Init_N(Np, Germe: Z_32; VAR Nu: LstVe2D);
   CONST Pzero: Ve2D = (x:0; y:0);
   VAR k: Word; u, v: Reel;
   BEGIN
     RandSeed:= Germe;
     FOR k:= 1 TO NmaxP DO
       IF (k>Np) THEN Nu[k]:= Pzero
                 ELSE BEGIN
                        u:= Random; Nu[k].x:= 0.3 * u;
                        Nu[k].y:= Random
                      END
   END;
 
 PROCEDURE SaisieNp(VAR Np: Word);
   CONST C1 = 2; C2 = C1 + 35; L1 = 2; o = 6;
   VAR n: Word;
   BEGIN
     E(1015); Wt(C1, L1, 'Nombre de points (<=');
     E(0012); Write(NmaxP:o); E(0015); Write(' ): Np = '); E(0007);
     REPEAT
       Rn2(C2, L1, n); We(C2, L1, n, o)
     UNTIL ((0<n) AND (n<=NmaxP));
     Np:= n;  E(0010); We(C2, L1, N_Point, o)
   END;;

Dans l'état initial le nuage de points, confiné à gauche du domaine, n'occupe que 30 % de la surface totale.

PS: J'ai repris la fin du code source (initialisation), version incomplètement corrigée d'un autre texte plus ancien.

[Flodelarab]

Bravo Wiwaxia.

[mazertys17]

Le coeur du programme, c'est ça, et ce n'est pas compliqué :

Ca dépend pour qui

En fait, déjà je ne connais pas ce code à moins que ce soit du pseudo code ?
Mais bon même en lisant j'ai du mal a comprendre ce qui se passe.

Je vais quand même essayer de déchiffrer tout ça et de comprendre donc merci .

Maintenant si tu pouvais me traduire ça en Java ce serait super.

Si j'ai bien compris le principe :


Quand un objet avance et qu'il tombe sur un autre objet, alors il va calculer sur un demi cercle qui va vers la droite, aléatoirement jusqu'à 30 positions différentes et dès qu'il y en a une valide alors il y va tout simplement ?
Hum...pourquoi pas (si j'ai bien compris).

Est ce que c'est pas faire beaucoup de calculs inutiles ?

[Flodelarab]

C'est faire des calculs utiles qui prend trop de temps.

En tirant 30 fois au hasard, tu obtiens des résultats suffisamment bons pour que payer plus de temps pour faire les vrais calculs soit trop cher.

Tu parles d'un demi-cercle, mais dans son code, tu noteras qu'il couvre [0;2π]. Donc tout le cercle.
Donc tu peux changer de cible sans réécrire ton code.

[wiwaxia]

... En fait, déjà je ne connais pas ce code à moins que ce soit du pseudo code ?
Mais bon même en lisant j'ai du mal a comprendre ce qui se passe.

Je vais quand même essayer de déchiffrer tout ça et de comprendre ...

C'est du Pascal, et ça se lit pratiquement comme du pseudo-code.

... Quand un objet avance et qu'il tombe sur un autre objet, alors il va calculer sur un demi cercle qui va vers la droite, aléatoirement jusqu'à 30 positions différentes et dès qu'il y en a une valide alors il y va tout simplement ?
Hum...pourquoi pas (si j'ai bien compris).

Est ce que c'est pas faire beaucoup de calculs inutiles ?

La boucle interne

Code Pascal :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
       REPEAT
 ... / ... 
       UNTIL ((Ntir=20) OR Test);

effectue jusqu'à 20⁽¹⁾ tentatives de trouver une position convenable
# située dans le domaine (((0<W1.x) AND (W1.x<1)) et ((0<W1.y) AND (W1.y<1)) ,
# suffisamment éloignée des autres points (Test devient faux dès qu'on trouve D2<D2min .
La répétition maximale des tirages (et éventuellement leur échec) n'intervient que dans les zones denses, où les points sont très rapprochés; le nombre maximal (qui peut paraître élevé) permet de trouver et de combler les derniers espaces encore disponibles.
L'évolution est alors lente, mais conduit à une accumulation compacte des points à droite, en fin d'évolution.
Dans le cas des états intermédiaires, pour lesquels les points sont plus espacés, l'évolution est beaucoup plus rapide, parce que deux ou trois essais suffisent pour trouver le bon déplacement: limiter le nombre à 20 ou 50 ne change alors pas le rythme de la progression.

Je ne sais pas si tu as bien compris le tirage: la nouvelle position (M) se trouve à l'intérieur d'un cercle de rayon (Rmax), sur un autre cercle plus petit de rayon (r) et de centre (C) décalé par rapport à l'ancienne position:
M_kC = 0.9*r (voir la ligne 72); l'augmentation moyenne de (x), de l'ordre de 0.9*Rmax/2 se traduit par un mouvement d'ensemble vers la droite.

(1) J'ai indiqué 30 par erreur, mais on peut très bien prendre une autre valeur ... les paramètres dépendent du nombre de points mobiles, ainsi que des dimensions du domaine.