Discussion :

[Twice22]

Bonjour à tous ! J'ai un projet à faire et j'aimerais réaliser un programme qui simule le mouvement d'une foule de personne dans une pièce. J'espère que la longueur de mon poste ne rebutera pas les potentiels personnes aptes à m'aider. Pour réduire la complexité de l'exercice, au début j'aimerais programmer un mouvement de foule dans une pièce rectangulaire (avec une sortie) et sans obstacle (à part les murs de la pièce). J'ai donc commencé la programmation (je suis pas très doué), j'ai quelques idées mais je bloque sur pas mal de choses aussi, je viens donc ici en espérant avoir des réponses à mes questions.

Voici les premiers codes effectués :

Code :

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

1
2
3
#open "graphics";;
#open "random";;
(* initialise les librairies *)

(dans la suite l'entier n correspond aux nombres de personnes)

On crée un point (cercle de rayon 5) au hasard dans l'espace (on fixe l = largeur = 800 pixels et h la hauteur = 600 pixels )

Code :

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

1
2
let create_point h l =
	fill_circle ((random__int l)+6) ((random__int h)+6) 5;; (*on ajoute 6 pour éviter que le point touche bordure inférieure car 5 = rayon du point *)

Puis on pose la fonction qui créée une foule de n personne dans l'espace 600 800 :

Code :

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

1
2
3
4
5
6
7
let create_foule n =
	if n=0 then failwith "pas de foule"
	else begin
		for i = 0 to (n-1) do
		create_point 588 788; (*poser create_point 588 788 car random__int l peut prendre valeur de 0 à l exclu. Puis on rajoute 6 à ce point d'après algo précédent et encore 5 -> 599 799 ce qui est bon*)
		done;
		end;;

Enfin, on créé le cadre avec l'ouverture et la foule :

Code :

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

1
2
3
4
5
6
7
let cadre = open_graph " ";
	moveto 0 0; lineto 800 0; lineto 800 280; moveto 800 320;
	lineto 800 600; lineto 0 600; lineto 0 0; moveto 0 0;
	set_color red;
	create_foule 200;
	read_key();
	close_graph();;

Bien sûr il y a un soucis dans ma création de foules : deux personnes peuvent
se superposer, je pense voir comment il faudrait faire pour éviter cela mais,
pour l'instant ce n'est pas la priorité.

Ce que je cherche à faire mais dont j'ai pas franchement d'idées, c'est faire
en sorte que les points se déplace dans l'écran graphique vers la sortie et ceux sans se rentrer dedans.

Je défini donc le type personne comme suit :

Code :

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

1
2
3
4
type personne = {mutable pos : int*int;  
			   mutable vit : float;
			   mutable dir : int*int;
			   mutable dist : float};;

j'initialise mon tableau contenant les infos des 200 personnes (position, vitesse, direction et distance de la sortie)

Code :

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

let tp = make_vect n {pos = (0,0); vit = 0.; dir =(0,0); dd = 0.};; (*remplacer n par 200*)

l'idée serait de mettre à jour les informations du tableau tp à chaque tour et
de "rafraichir" l'affichage graphique avec ces nouvelles informations.

Il y a donc plusieurs points sur lesquels j'aurais besoin de votre aide :
Seulement, je n'arrive pas à concevoir comment l'affichage graphique peut changer puisque caml light exécute qu'une seule fois le programme... ? Je ne vois pas non plus comment faire en sorte que les points représentants les personnes ne se traversent pas entre eux et ne traverse pas les murs (mon idée serait d'évaluer à chaque tour et pour chaque point si il existent des voisins dans un rayon de 15 pixels et d'agir en conséquence, en prenant en compte qu'à chaque tour on considère dans un premier temps que le point se déplace de 5 pixels. On peut créer une fonction auxiliaire qui calculerait la distance entre deux points).

Je vous remercie d'avance pour vos explications et vos idées.
Bonne journée
Twice22.

[Cacophrene]

Bonsoir,

La façon dont tu as présenté ton projet, en commençant par la partie graphique, révèle à mon sens le principal problème qui te rend la tâche si difficile : l'affichage est la dernière chose à faire ! Tu devrais commencer par te soucier de la représentation d'une pièce avec caml light, des personnages de la foule et de leurs interactions. Quelques idées pour y parvenir :

• Comment représenter une pièce de L lignes et C colonnes ?
• Comment représenter un personnage ?
• Comment savoir si un personnage occupe une case donnée ?

Est-ce qu'on a besoin de stocker une information de position dans une valeur de type personnage ? Prends une feuille de papier et un crayon, dessine une petite pièce et essaie de voir ce qui est important pour le type personnage et les fonctions associées.

Dès que tu as un premier code pour tout ça, on en rediscute et ensuite on verra l'affichage graphique.

Cordialement,
Cacophrène

[Twice22]

merci de votre réponse. Je vais y réfléchir, j'espère pouvoir donner un début de réponse ce week-end, étant donné que je n'ai accès à l'ordinateur que le week-end.
Edit : Je pense bien sûr qu'il faut modéliser la pièce par une matrice "trinaire" 800 par 600 dans mon cas. où les 0 représenterait des zones vides, les 1 des zones où il y a des personnes, et les 2 les obstacles (pour l'instant il n'y que les murs de la pièce). Par contre étant donné que mes personnes sont des sphères de rayon 5, si on ne change pas la taille de la matrice, cela voudrait dire que j'aurais une disposition de 1 en forme de cercle dans ma matrice. Il faudrait alors peut-être distinguer le centre de la personne du contour en donnant un autre nombre au contour de la personne (3 par exemple).
Pour ce qui est de la collision etc... j'essayerais de donner une réponse assez précise ce week-end. Mais j'arrive toujours par à concevoir comment faire évoluer le programme dans caml-light... car généralement, on tape du code, on exécute et ensuite on utilise notre fonction créé et caml nous renvoie un résultat, alors que là, il faudrait qu'en l'exécutant une fois, caml nous donne "les détails" de l'opération.

Merci à vous. Bonne soirée

[Twice22]

Bonjour !
Je suis désolé de n'avoir pas répondu plus tôt, mais j'ai pas mal de boulot. Je vais tenter de répondre aux mieux aux questions que vous m'avez posé.
Sachant que j'ai testé plusieurs voies. Mai c'est très loin d'être fini.

• Comment représenter une pièce de L lignes et C colonnes ?
• Comment représenter un personnage ?
• Comment savoir si un personnage occupe une case donnée ?

Est-ce qu'on a besoin de stocker une information de position dans une valeur de type personnage ?

• Je représente donc sous forme de matrice ma pièce de largueur 800 pixels et de hauteur 600 pixels remplie de 0 :
  
  

  Code :

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

  let M = make_matrix 800 600 0;;

• L'idée retenue pour présenter un personnage, sachant qu'il fait 5 pixels de rayon a été de voir graphiquement comment était représenté un rond de rayon 5 pixels sur l'ordinateur et de créer une fonction appelée create_point_M qui associe au point x et y (coordonnée dans la matrice : x allant de 5 à 795, y de 5 à 595) un cercle de rayon 5 remplit de 1 centré au point de coordonnées (x,y) dans la matrice. Voici la fonction :
  
  

  Code :

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

  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  let create_point_M x y =
  	M.(x).(y-5) <- 1; M.(x+1).(y-5) <- 1; M.(x-1).(y-4) <- 1; M.(x).(y-4) <- 1; M.(x+1).(y-4) <- 1;
  	M.(x+2).(y-4) <- 1; M.(x-4).(y) <- 1; M.(x-4).(y-1) <- 1; M.(x+5).(y-1) <- 1; M.(x+5).(y) <- 1;
  	M.(x-1).(y+3) <- 1; M.(x).(y+3) <- 1; M.(x+1).(y+3) <- 1; M.(x+2).(y+3) <- 1; M.(x).(y+4) <- 1; 
  	M.(x+1).(y+4) <- 1; 
  		for i = (-3) to 4 do
  		    for j = (-3) to 2 do
  			M.(i+x).(j+y) <- 1
  		    done;
  		done;
  	M;;

  Pour la tester sous CAML, on peut créer une matrice M suivante :
  
  

  Code :

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

  let M = make_matrix 12 12 0;;

  et exécuter le code (par exemple) :
  

  Code :

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

  create_point_M 6 5;;

• Ainsi, la fonction précédente me place un "cercle" remplit de 1 centré au point de coord (x,y) dans la matrice. Pour créer une population de 200 personnes au sein de la matrice, il faut que ces cercles remplit de 1 ne se touchent pas dans la matrice, l'idée pour éviter de remplir des cases de la matrices déjà changée en 1 a été de créer une fonction appelée placement_vide qui prend x, y les coordonnées dans la matrice où on souhaite placer le prochain "cercle de 1" représentant la personne et évalue si le contour du cercle que l'on souhaiterait créer ne touche pas un autre cercle. En CAML, cela donne :
  
  

  Code :

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

  1
  2
  3
  4
  5
  6
  7
  let placement_valide x y M =  
  if (M.(x).(y-5) = 1 )|| (M.(x+1).(y-5) = 1 )||(M.(x+2).(y-4) = 1 )||(M.(x+3).(y-3) = 1 )||(M.(x+4).(y-3) = 1 )
  ||(M.(x+4).(y-2) = 1 )||(M.(x+5).(y-1) = 1 )||(M.(x+5).(y) = 1 )||(M.(x+4).(y+1) = 1 )||(M.(x+4).(y+2) = 1 )
  ||(M.(x+3).(y+2) = 1 )||(M.(x+2).(y+3) = 1 )||(M.(x+1).(y+4) = 1 )||(M.(x).(y+4) = 1 )||(M.(x-1).(y+3) = 1 )
  ||(M.(x-2).(y+2) = 1 )||(M.(x-3).(y+2) = 1 )||(M.(x-3).(y+1) = 1 )||(M.(x-4).(y) = 1 )||(M.(x-4).(y-1) = 1 )
  ||(M.(x-3).(y-2) = 1 )||(M.(x-3).(y-3) = 1 )||(M.(x-2).(y-3) = 1 )||(M.(x-1).(y-4) = 1 ) then false
  else true;;

  Ainsi pour placer une foule aléatoire de n personnes au début, on pourrait utiliser la fonction

  Code :

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

  create_foule

  qui prend en paramètre l (=largueur de la matrice), h (=hauteur de la matrice) et n le nombre de personnes que l'on souhaite créer. En CAML :
  
  

  Code :

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

  1
  2
  3
  4
  5
  6
  7
  8
  9
  let rec create_foule n l h = match n with 
  	|1 -> create_point_M (random__int (l-10))+5  (random__int (h-10)+5;  
  	|n -> let p1 = (random__int (l-10))+5 in
  		  let p2 = (random__int h-10)+5 in 
  		  if (placement_valide p1 p2 M)=true  then begin 
  							create_point_M p1 p2
  							create_foule (n-1) l h
  							end
  		  else create_foule n l h;;

  qui ne marche pas, (apparemment on ne peut pas faire de let k = random qqch ?), de plus la complexité de create_foule est aléatoire ce qui n'est pas super ! cette fonction peut ne jamais se terminer, si à partir d'un certain moment à chaque passage placement_valide = false... Comment peut-on améliorer cela, vous auriez une idée ?.
  
  Pour éviter que deux personnes ne se touche lors de l’exécution du programme on réutilisera la fonction placement_vide. Cela dit , même si il faut s'intéresser à la partie graphique à la fin, je me demande comment faire en sorte que le programme s'exécute en temps réel devant nos yeux et que l'on voit les points se mouvoir devant nos yeux ?

Voilà pour l'instant. On peut facilement créer des figures géométriques au sein
de la matrice et des contour qui constituerons le décor (on remplira la matrice de 2 pour ces formes géométriques).

Une dernière question : le déplacement des personnages. Comment faire en sorte qu'ils aillent tous sans se rentrer dedans vers la sortie et qu'ils évitent les obstacles. On a deux trois idées là-dessus (pas encore de programme) avec mon pote mais j'aimerais bien si possible avoir l'avis d'une personne éclairée.

Merci à vous ! J'espère avoir de vos réponses.
Et désolé pour le retard.
Bonne journée.

[Cacophrene]

Bonjour,

L'idée retenue pour présenter un personnage, sachant qu'il fait 5 pixels de rayon a été de voir graphiquement comment était représenté un rond de rayon 5 pixels sur l'ordinateur et de créer une fonction appelée create_point_M qui associe au point x et y (coordonnée dans la matrice : x allant de 5 à 795, y de 5 à 595) un cercle de rayon 5 remplit de 1 centré au point de coordonnées (x,y) dans la matrice.

Votre fonction create_point_M est confuse et ne devrait pas être écrite de cette façon. À la première lecture on est surpris par la présence des boucles imbriquées et des multiples éditions manuelles du tableau. Essayez de vous inspirer de quelque chose comme ceci qui ne fait pas exactement la même chose que vous :

Code :

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

1
2
3
4
5
6
7
8
let add_guy room x y =
  for i = -4 to 4 do
    let k = [|0; 2; 3; 3; 4|].(4 - abs i) in
    for j = -k to k do
      room.(x + i).(y + j) <- 1
    done
  done

Voici la représentation de ce que cette fonction permet d'obtenir (X désigne le point central du personnage) :

Code :

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
 
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . 1 . . . . . . .
. . . . . . 1 1 1 1 1 . . . . .
. . . . . 1 1 1 1 1 1 1 . . . .
. . . . . 1 1 1 1 1 1 1 . . . .
. . . . 1 1 1 1 X 1 1 1 1 . . .
. . . . . 1 1 1 1 1 1 1 . . . .
. . . . . 1 1 1 1 1 1 1 . . . .
. . . . . . 1 1 1 1 1 . . . . .
. . . . . . . . 1 . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . .

Au passage, notez que l'utilisation des majuscules dans les noms de variables n'est pas une bonne pratique. C'est autorisé par Caml-light mais interdit en OCaml. Comme nous sommes à peu près tous des utilisateurs d'OCaml sur ce forum (Caml-light n'existe pour ainsi dire plus hors du monde de l'enseignement), nous risquons d'avoir des soucis de partage du code. Bon, là en l'occurrence c'est un détail.

Ainsi, la fonction précédente me place un "cercle" remplit de 1 centré au point de coord (x,y) dans la matrice. Pour créer une population de 200 personnes au sein de la matrice, il faut que ces cercles remplit de 1 ne se touchent pas dans la matrice, l'idée pour éviter de remplir des cases de la matrices déjà changée en 1 a été de créer une fonction appelée placement_vide qui prend x, y les coordonnées dans la matrice où on souhaite placer le prochain "cercle de 1" représentant la personne et évalue si le contour du cercle que l'on souhaiterait créer ne touche pas un autre cercle. En CAML, cela donne :

Même chose ici que tout à l'heure : votre fonction est confuse, vous n'avez pas besoin d'écrire manuellement le test à effectuer. Reportez-vous à la fonction add_guy et essayez de la modifier pour qu'elle renvoie un booléen. Autre remarque : quand vous écrivez if foo then false else true, considérez plutôt not foo qui veut dire la même chose.

Concernant la fonction create_foule (autre considération annexe : create_crowd ou creer_foule), vous avez plusieurs choses bien distinctes à faire :

• Choisir un emplacement valide. Comment feriez-vous pour vous assurer que les fonctions de type random vont vous donner une valeur qui est nécessairement valide ?
• Placer les personnages. Vous pouvez simplifier votre fonction : parenthèses et filtrage inutiles qui nuisent à la compréhension, etc. Utilisez des noms parlants pour vos variables et suivez la règle "une tâche par fonction".

Pour éviter que deux personnes ne se touche lors de l’exécution du programme on réutilisera la fonction placement_vide. Cela dit , même si il faut s'intéresser à la partie graphique à la fin, je me demande comment faire en sorte que le programme s'exécute en temps réel devant nos yeux et que l'on voit les points se mouvoir devant nos yeux ?

Avec une simple boucle ! Je vous donnerai en temps voulu un exemple en OCaml que vous facilement adapter à Caml-light.

Une dernière question : le déplacement des personnages. Comment faire en sorte qu'ils aillent tous sans se rentrer dedans vers la sortie et qu'ils évitent les obstacles. On a deux trois idées là-dessus (pas encore de programme) avec mon pote mais j'aimerais bien si possible avoir l'avis d'une personne éclairée.

Pour aller vers la sortie, il faut savoir quelle direction choisir. Pour éviter les collisions, il faut trouver un moyen efficace de repérer les contours des obstacles... est-ce bien différent des contours des personnages ?

Cordialement,
Cacophrène

[Twice22]

Bonjour ! Merci d'avoir répondu aussi vite, malheureusement je ne peux répondre de suite étant donné la masse de travail (surtout que je suis disponible que les week-end). Par ailleurs j'ai pas énormément avancé sur les TIPE étant donné que ces 2 dernières semaines on a été mon pote et moi de passage en ADS (prépa oblige). Je vous présente quand même ce qu'on a fait.

-> On a donc enlevé le M majuscule, repris votre nom de fonction qui été pas mal. Puis on a donc recodé sur votre idée la fonction qui a la base se nommée create_point_M. Cependant, les placements des "1" au sein de la matrice n'étant pas symétriques on a eu quelques petits soucis. Par ailleurs on a eu un problème de dépassement de tableau (vect_item...). Cela a été résolu, voici la fonction :

création d'une petite pièce pour voir dans caml si la fonction marche comme prévu :

Code :

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

let room = make_matrix 20 20 0;;

Code :

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

1
2
3
4
5
6
7
8
9
10
let add_guy room x y =
 let p = ref 0 in 
 for i = -5 to 4 do 
    if i>=0 then p:=1 else p:=0;
    let k = [|1; 2; 4; 4; 5|].(5 - (abs (i) + !p ) ) in
    for j = (1-k) to k do
      room.(x + 1 + i).(y + j) <- 1
    done
  done;
room;;

On peut tester la fonction avec par exemple :

Code :

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

add_guy room 10 10;;

-> Pendant mon ADS mon pote a refait par la suite la fonction qui à l'origine s'appelait placement_vide suivant le modèle que vous nous avez indiqué. Je dois dire que j'ai pas eu le temps de voir si elle fonctionnait bien sur un exemple mais j'ai corrigé les dernières fautes, ce qui fait qu'elle s’exécute quand même. La voici :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
let can_i_go_there x y = 
let you_can =  ref true in  
let p = ref 0 in
let i = ref(-5) in 
 while ( !you_can ) && (!i<5) do 
    if !i>=0 then p:=1 else p:=0;
    let k = [|1; 2; 4; 4; 5|].(5 - (abs (!i) + !p )) in
    for j = (1-k) to k do
      if room.(x + 1 + !i).(y + j) = 1 then
      you_can := false;
     done;
i := !i+1; 
done;
!you_can;;

Comment feriez-vous pour vous assurer que les fonctions de type random vont vous donner une valeur qui est nécessairement valide ?

On a pas pu y réfléchir plus que cela, mais du coup l'idée (juste une idée) serait de ne pas analyser si le nième couple d'entiers tirés au hasard convient. Il faudrait que ce nième couple conviennent forcément sans analyse. L'idée serait de scinder le terrain en sous terrains (par exemple 60 sous terrains).
A la 1ère passe on effectuerait un tirage aléatoire sur le première sous terrain, a la seconde passe un tirage aléatoire sur le second sous terrain...

Ainsi, si on délimite bien les "sous terrains" il n'y aura pas de débordement d'un cercle sur l'autre. Bien évidemment le quadrillage des sous terrains dépend de la variable n (= nombre de personnes à introduire dans la pièce) de telle sorte qu'on ne se retrouve pas avec un terrain remplit aléatoirement sur toute une partie et pas du tout remplie sur une autre partie.


déplacement des personnages

Même si on a quelques idées, on réfléchit encore pour que cela soit réaliste.

Si la salle ne contient aucun obstacles autres qu'humains alors on peut considérer que la direction choisie est celle en ligne droite depuis le point vers la sortie.

Si en revanche il y a des obstacles (élémentaires : triangle, cercle, carré...) alors il serait bête de choisir comme meilleure direction à la base celle en ligne droite du point à la sortie étant donné qu'il peut être confronté sur son passage à l'obstacle en question et qu'il faudrait alors le contourner (donc ce n'est pas le chemin le plus rapide). Faudrait-il réaliser une fonction "plus_court_chemin" qui sont assez dures je pense à réaliser... ?

Merci à vous.
Bonne Journée.

[Twice22]

Re Bonjour à tous.
Alors voilà je reviens après avoir essayé d'avancer...

Donc à l'heure d'aujourd'hui nous avons choisi de représenter la salle par une matrice (de taille 600*800)
- Les personnes par des cercles (rouges dans cette matrice) : pour cela on a fait une fonction qui remplissait une zone à peu près circulaire de la matrice de 1 et on a créer une fonction qui a chaque "1" lu attribué un pixel rouge dans la partie graphique".
- On a créé une fonction permettant de générer et de placer aléatoirement une population de personne dans la matrice : pour cela on a créé une fonction permettant d'analyser si oui ou non on peut mettre une personnage à cet endroit (ie d'analyser si la place qu'on souhaite occuper ne l'est pas déjà pas un obstacle ou un personnage)
-On a créé une fonction qui répertorie les sorties de la salle dans une liste (elle renvoie les coordonnées extrémales des sorties moins 5 pixels de chaque coté histoire de prendre en compte l'épaisseur du point). (Cette fonction bug un peu)
-Enfin on a créer une fonction qui donne la plus proche sortie pour un point donné. Celle-ci prend en compte la distance du point à la sortie, le nombre de personnes déjà devant cette sortie, la taille de la sortie, (il faudrait à l'avenir qu'elle prenne aussi en considération la présence ou non d'obstacles autres qu'humains devant la trajectoire théorique empruntée)
Voici un schéma simplifié du résultat pour l'instant :

Les points roses sont les personnage, le carré en pointillé orange la zone devant la sortie qui permet de pondéré la plus proche sortie, le point bleu, le personnage auquel on s’intéresse à un moment du programme.

Le problème en fait c'est comment programmer une fonction qui détecte les obstacles avant de les heurter. Je mets une image simplifié du problème :

Au lieu de se frotter à l'obstacle et d'être obligé de faire le tour, il faudrait que le point détecte l'obstacle et qu'il se déplace de manière à le contourner directement... Peut-on pour cela réutiliser la fonction qui analyse si on peut placer un individu à un endroit de la matrice ? J'ai pas vraiment d'idée étant donné qu'il peut aussi y a avoir des individus sur le trajet de l'individu...

J'espère que vous pourriez m'aider dans la résolution de mon problème.
Merci à vous par avance,
Bonne journée.

[learne]

il s'agit en faite d'un problème de path-finding (classique dans le domaine du jeu vidéo), sa se résout avec des algorithme qui parcours des graphes représentant l'ensemble des directions possible,
dans le cas d'obstacle immobile, A* (ou A star) est a la fois relativement simple et efficace(dans la partie AI du forum tu devrais trouver davantage d'information, sinon le web regorge de documentation plus ou moin complète), si tu maitrise les graphes, c'est une solution

(en bref, tu parcours l'ensemble des directions possible en explorant d’abord celles qui te rapproche de ton objectif, si une direction t'amène a l'objectif alors tu as ton chemin)