Évacuation d'une salle

19 mai 2015 à 13:30:51

Bonjour,

J'essaye de programmer, dans le cadre d'un projet en informatique, une fonction qui va donner le temps d'évacuation d'une salle remplie de personnes et d'obstacles (comme des tables par exemple) en nombre d'itérations. Elle prend en arguments un tableau (composé de 0 (les vides), de 1 (les personnes) et de 2 (les obstacles)) modélisant la salle et la position (iporte,jporte) de la porte. Pour chaque 1 je calcule la distance à la porte des 4 cases l'entourant grâce à la formule : distance = sqrt((i-iporte)²+(j-jporte)²). La case vide de distance minimale reçoit un 3 (pour que le 1 ne soit pas déplacé plusieurs fois en une boucle) et l'ancienne un 0. Une boucle rechange ensuite tous les 3 en 1. Si la case contient un obstacle (2) ou est vide (0), elle n'est pas modifiée. A chaque entrée de boucle en remet à 0 la porte. Lorsque la somme des cases du tableau est égale à la somme des obstacles (il n'y a plus aucun 1) la fonction s'arrête et renvoie le nombre d'itérations nécessaires à l'évacuation de la salle. J'ai essayé de coder cette fonction en Python mais elle ne s'arrête pas et je ne vois pas où est le problème. Voilà le code de la fonction, est-ce que vous pourriez m'aider à voir ce qui ne vas pas ? Merci d'avance !

import numpy as np
import numpy.random as rd

def evacuation (M,iporte,jporte):
    Temps_evacuation=0
    (L,l)=np.shape(M)
    nombre_obstacles=0
    for i in range (L):
        for j in range (l):
            if M[i,j]==2:
                nombre_obstacles+=1
    while np.sum(M)>2*nombre_obstacles:
        print M        
        Temps_evacuation+=1
        M[iporte,jporte]=0 #On remet la porte à 0
        for i in range (L):
            for j in range (l):
                if M[i,j]==1:
                    distance=np.ones(4)*1000 #On génère un vecteur rempli d'un grand nombre pour que le nombre reste grand si on ne peut pas calculer la distance
                    if i>=0 and i+1<=L and j>=0 and j+1<=l:
                        if i>0 and M[i-1,j]==0:
                            distance[0]=np.sqrt((i-1-iporte)**2+(j-jporte)**2) #case du haut
                        if i<L-1 and M[i+1,j]==0:
                            distance[1]=np.sqrt((i+1-iporte)**2+(j-jporte)**2) #case du bas
                        if j>0 and M[i,j-1]==0:
                            distance[2]=np.sqrt((i-iporte)**2+(j-1-jporte)**2) # case de gauche
                        if j<l-1 and M[i,j+1]==0:
                            distance[3]=np.sqrt((i-iporte)**2+(j+1-jporte)**2) # case de droite
                            distancemin = min (distance)
                            indice_case_valeur_min=[]
                            for k in range (4): #On cherche l'indice associé à la valeur minimale
                                if distance[k]==distancemin:
                                    indice_case_valeur_min.append(k)
                            if len (indice_case_valeur_min)==2: #Si deux distances sont les mêmes on tire au hasard
                                indice=rd.randint (0,2)
                                if indice==0:
                                    indice_case_valeur_min=indice_case_valeur_min[0]
                                if indice==1:
                                    indice_case_valeur_min=indice_case_valeur_min[1]
                            else :
                                indice_case_valeur_min=indice_case_valeur_min[0]
                            if indice_case_valeur_min==0 and i>0 and M[i-1,j]!=2:
                                M[i-1,j]=3 
                                M[i,j]=0
                            if indice_case_valeur_min==1 and i<L-1 and M[i+1,j]!=2:
                                M[i+1,j]=3
                                M[i,j]=0
                            if indice_case_valeur_min==2 and j>0 and M[i,j-1]!=2:
                                M[i,j-1]=3
                                M[i,j]=0
                            if indice_case_valeur_min==3 and j<l-1 and M[i,j+1]!=2:
                                M[i,j+1]=3
                                M[i,j]=0
                        if M[i,j]==2: #Les 2 sont inchangés
                            M[i,j]=2
                        if M[i,j]==0: #Les 0 sont inchangés
                            M[i,j]=0
        for i in range (L): #On rechange les 3 en 1
            for j in range (l):
                if M[i,j]==3:
                    M[i,j]=1
    return Temps_evacuation

Dan737

19 mai 2015 à 14:00:06

Pourrais-tu ré-expliquer en français ton algorithme? Voici les passages qui me sont incompréhensibles.

Pour chaque 1 je calcule la distance à la porte des 4 cases l'entourant

La distance à la porte ? Aux portes ? Quelles sont ces cases l'entourant?

La case vide de distance minimale reçoit un 3

La case vide la plus proche de quoi? De la personne? De la porte?

et l'ancienne un 0

L'ancienne de quoi??? Je m'arrête là, car c'est imbuvable.

Dès que t'as remis de l'ordre dans cette explication, j'y jetterai un oeil.

Python FAQ FR - Pygame tutoriel en vidéo - Gerer les collisions avec Pygame - Programmation avec Tkinter

AntonAnton2

19 mai 2015 à 17:07:46

Pour une case du tableau contenant un 1, on regarde la case à sa gauche, celle à sa droite, celle d'en-dessous et celle d'au-dessus et pour chacune de ces 4 cases on calcule la distance de la case à la seule porte, qui est la case située à la ligne iporte et à la colonne jporte du tableau.

Pour chaque personne (pour chaque 1), on a donc les distances par rapport à la sortie des 4 cases définies précédemment l'entourant. Parmi ces 4 cases, on déplace la personne dans la case vide ayant la distance minimale par rapport à la sortie. (La personne devient un 3 provisoirement pour qu'elle ne soit pas à nouveau déplacée dans cette boucle).

Pour chaque 1 du tableau, l'ancienne case désigne celle qui contenait le 1 au début de la boucle (donc une personne) et qui se vide (devient un vide représenté par un 0) lorsqu'elle se déplace, sauf dans le cas où les 4 cases l'entourant sont occupées (alors la personne ne peut pas se déplacer car il ne peut pas y avoir plusieurs personnes sur une case).

La remise à 0 de la porte à chaque itération correspond à l'évacuation de la personne s'y trouvant.

La fonction s'arrête lorsque la somme des éléments tu tableau devient égale à la somme des obstacles qui sont représentés par des 2 (c'est-à-dire lorsque le tableau ne contiendra plus que des 0 et des 2, donc toutes les personnes (1) seront parties).

Merci d'avance !

-
Edité par AntonAnton2 19 mai 2015 à 17:10:23

Dan737

19 mai 2015 à 18:44:12

Si tu me permets, je pense que tu t'y prends mal. En gros, tu as un tableau qui représente des personnes, des objets qu'on ne peut traverser et une case destination. Tu veux savoir pour chaque personne quel est le chemin le plus court pour atteindre la sortie. Parmi toutes ces personnes, tu veux connaitre le plus long chemin, c'est à dire quelle est la personne qui, bien que prenant le chemin le plus court vers la sortie, doit parcourir le plus long chemin. Tu comptes un poids de 1 pour avancer d'une case, et tu ne peux pas avancer en diagonal.

Pour tout ce qui est chemin le plus court, le boulot est déjà fait pour toi. scipy.sparse.csgraph. Je te conseille de lire cette page attentivement.

Une fois que c'est fait, tu comprendras qu'il te suffit de te créer ta matrice qui contient les infos sur quel case est connectée à quelle case. Disons que ton tableau de départ a une taille de 5 colonnes sur 4 lignes. Il y a 20 cases. Donc tu vas faire une matrice de 20 sur 20 (400 cases!) qui contiendras l'information de quel case est connectée à quelle case. Comment?

L'idée est que tu as numéroté tes cases de 0 à 19. Autrement dit, pour une case située aux indices [i, j], le numéro de la case sera j * NBRE_COL + i. Dans notre cas, une case à [2, 3] (attention on commence toujours avec des indices à 0!) aura comme numéro de case 17. En effet c'est l'élément sur la 4ème ligne (indice 3) donc la dernière ligne, et la 3ème colonne (indice 2). Il ne reste que 2 cases à droite et on est au bout (case indice 19).

Maintenant qu'on a compris comment repérer une case grâce à son numéro, dans ce grand tableau de 20 lignes sur 20 colonnes, chaque intersection représente le coût qu'il faut payer pour aller d'une case à l'autre. Le coût sera de 1 pour des cases adjacentes libres, et de 0 sinon (car on ne peut pas y aller). En reprenant notre exemple de tableau de 5 colonnes et 4 lignes, on peut aller de la case 0 vers la case 1 et 5 (en bas et à droite). Donc dans notre matrice (qu'on va appeler dist_matrix), on aura dist_matrix[0, 1] = 1 et dist_matrix[0, 5] = 1. On fera de même pour le chemin inverse: dist_matrix[1, 0] = 1 et dist_matrix[5, 0] = 1.

Une fois que tu as créé cette énorme matrice, tu peux la réduire car elle contient pleins de zéros. Ta matrice de base peut être créée avec dist_matrix = scipy.sparse.lil_matrix((NBRE_LIGNE * NBRE_COL, NBRE_LIGNE * NBRE_COL)). Et après l'avoir rempli, tu fais dist_matrix = dist_matrix.tocsc(). Et te voilà avec un truc moins gros.

Bon on a notre matrice, mais t'as toujours pas ta solution. Alors il suffit d'appeler dist = dijkstra(dist_mat, indices=(iporte, jporte)) et tu obtiens une liste qui contient 20 éléments (dans le cas de notre tableau de 20 cases. Cette liste donne à chaque indice le coût pour se déplacer depuis la porte vers la case dont le numéro est l'indice. C'est pas très clair!!! Le premier élément (indice 0) contiendra peut-être un 5. Ca veut dire qu'il faut parcourir 5 cases pour aller de la case numéro 0 à la porte de sortie. Le deuxième élément de la liste (indice 1) contiendra un autre chiffre donnant la distance la plus courte pour aller de la case numéro 1 à la sortie. Etc... Toi tu ne veux que regarder les cases qui contenait une personne. Disons qu'il y avait 3 personnes sur les cases 3, 8 et 15. Tu regardes max(dist[3], dist[8], dist[15]) pour savoir quelle personne a eu le chemin le plus long. Et donc tu as ton temps d'évacuation.

-
Edité par Dan737 19 mai 2015 à 18:49:55

Python FAQ FR - Pygame tutoriel en vidéo - Gerer les collisions avec Pygame - Programmation avec Tkinter

fauquette

19 mai 2015 à 21:21:24

Une autre méthode serrait de créer une matrice de la même taille que son plateau et d'indiquer dans chaque case la distance du chemain maximale. Ca se fait tres bien récursivement (ou en gérant une pile si la matrice est trop grande)

AntonAnton2

20 mai 2015 à 22:00:45

Merci pour vos réponses, je vais regarder ça