Optimisation d'un code...

... de génération de mines pour un démineur ^^

19 avril 2006 à 19:12:19

(Désolé.. j'ai galéré pour trouver un titre, et je reconnais qu'il veut pas dire grand chose

)

Bonsoir

En fait voilà... Pour appliquer un peu les cours, je me suis lancé dans l'élaboration d'un démineur.
J'ai réussit à faire un code qui marche, en me focalisant dans un premier temps sur la génération des mines.

En gros, voilà la structure que j'emplois :

Des sprites de 15 x 15 px pour les cases
Le tout dans un écran de 15 sprites par 15
10 mines réparties dans l'écran

Je créé un tableau de 15 x 15 donc, qui représente l'écran en terme de variable.
Pour chaque case (dans un premier temps), je mets juste les valeurs 0 si case vide, ou 10 si case minée.

Désolé pour cette longue introduction, mais au moins avec un coup d'oeil vous pourrez de suite comprendre mon code (même si il est tellement chargé en commentaires qu'il est je pense facilement compréhensible

//Je vais générer la répartition des mines avec une boucle
for(k = 0 ; k < NOMBRE_MINES ; k++) //je liste les mines
{
//Pour chacune d'elle je détermine 2 nb aléatoires entre 0 et (NB_BLOCS_LARGEUR - 1)
srand(time(NULL));
alea1 = (rand() % (NB_BLOCS_LARGEUR + 1));
alea2 = (rand() % (NB_BLOCS_HAUTEUR + 1));
//Je regarde si il n'y a pas déjà une mine à cet endroit
if(tableau[alea1][alea2]==10)
k--; //Si jamais il y a déjà une mine, je ne fais rien, mais je recule mon k d'un cran pour en placer une ailleurs
else
tableau[alea1][alea2]=10; //Si pas encore de mine, j'en place une
}

That's la portion de mon code chargée de générer la carte.
Il fonctionne. Mais il est horriblement lent (5-6 secondes de chargement pour une carte de 15 x 15.. j'ose pas imaginer un 40 x 40.

Le hic c'est que je ne vois pas ce que je peux optimiser. la boucle "for" est censée être parcourue 10 fois.

Si quelqu'un pouvait m'expliquer pourquoi ca rame tant, je lui en serait reconnaissant...

Merci d'avoir lu jusqu'au bout

Arkhiall

19 avril 2006 à 19:21:53

Ja sais pas si c'est ca, mais on n'appelle srand qu'une seule fois, donc avant le for!

Kayl

19 avril 2006 à 19:25:20

Contradiction :
//Pour chacune d'elle je détermine 2 nb aléatoires entre 0 et (NB_BLOCS_LARGEUR - 1)

avec

alea1 = (rand() % (NB_BLOCS_LARGEUR + 1));

%k renvoit de 0 à k-1 déjà...

Ensuite plutot que de feinte avec ton k-- je te conseille un
do
{
choisir 2 nombres au pifs
} while(la case en quesdtion est une mine};

mettre une mine

-ed-

19 avril 2006 à 19:32:41

Citation : Matheus07

srand(time(NULL));
alea1 = (rand() % (NB_BLOCS_LARGEUR + 1));
alea2 = (rand() % (NB_BLOCS_HAUTEUR + 1));

J'ai l'impression que dans le cours de M@teo, il y a un message qui a du mal à passer, c'est que srand() ne doit être appellé qu'une fois au début du programme. Sinon, tu retires la même séquence pendant une seconde, alors normal que ça mettre un temps fou, il faut attendre la seconde suivante pour avoir un nouveau tirage !

Pour une jeu carré :

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

enum
{
N = 10
};

static void clear(int tab[][N], size_t n)
{
size_t i;
for (i = 0; i < n; i++)
{
size_t j;
for (j = 0; j < n; j++)
{
tab[i][j] = 0;
}
}
}

static void place(int tab[][N], size_t n, size_t n_mines)
{
size_t i;
for (i = 0; i < n_mines; i++)
{
size_t x;
size_t y;
do
{
x = rand() % n;
y = rand() % n;
}
while (tab[x][y] != 0);
tab[x][y] = 1;
}
}

static void print(int const tab[][N], size_t n)
{
size_t i;
for (i = 0; i < n; i++)
{
size_t j;
for (j = 0; j < n; j++)
{
putchar (tab[i][j] ? '*' : '_');
}
putchar ('\n');
}
putchar ('\n');
}

int main(int argc, char *argv[])
{
int tab[N][N];
srand((unsigned)time(NULL));
clear(tab, N);
place(tab, N, (N * N) / 5);
print(tab, N);
}

Essai 50x50 :

__*__*_________*______________*____*___*_______*__
_____________________**__**______*_*________**_*__
__*____*_____*_*________*________________*___*_*__
**______*__**___*______*__*__*_______*___*___*____
__****____*________*__*______*_________*__________
_______*__*__**___________*_____*__________*____*_
____*_*_*______*__*______________________*___*____
______*__*________*_____*_______*_*______________*
**_*_*____*__*__**___**_**___*__*____*______*____*
______*____**___________*_____*_______*___________
_____*_*____*__*____________*______*_*_**_______*_
*________*_*______*__*___*_*_*_______*____***_*___
___*_*_____*_____________**____________*______*___
*_*___*________*_______*______________*___*____*__
__*__*____________**_**____________*___*________*_
*_*__*__________*_________________*___*_*_*_*_____
_______________**________*_______________**____*__
____*_________*___*___*____***_*________*_*_*_____
__*______*___***_____*_*___*____*__**_*______*__*_
_*_______*_*__*__*___________*_______*_____*_____*
____*_____*_*_____*___*___________________**______
______*_____*_____*__*_____*___*_*_*__*____*____*_
______*_*__*_*___*_*_______*______________*__*___*
_____*___________*___**____*_*__________**___*____
_____**____*___*_**___*_________*__****_*____*____
___*___________*_______**__*_**____*_*_______*____
________**_**_*_______*_______________*_________*_
**___**__*_______****_*___*____*_*____*____*______
**________*___**____________*_______*____*__*_____
_*______*______*_*_______*_____****__*__*_________
__*____*___*_________**___**___________*______*_**
**_______________*___**_______*_*_______*_*___*___
____*_**______*____*______*__________*__*_*___**__
__*_________*_*__*___________*__________*_________
________*_____**__*_*___*_______**_*_________*____
__***____*____*___________**_*_______**___*____*__
**__*___*________*_*_____****_____*_____****_*____
___*___*___****_______*___*___*____*_*___***______
_______**_____*_*________*___**__*_*_____*________
____*____*________***___***________*__________*___
_____*_______*__*______*_________*___*__*_**______
*_*____*__________**_**__*___*___________________*
*______*__**___*___*__*_______________*________*_*
_________________*___*____*___*_*_*_____*__*___*__
__**________________*_*_____*_____*_*__*___*_*__*_
___*_____*_____*__*_**_______________*____*_______
_****__*____________*_*_______**__________________
*___*____*_*_***__*__________*______*_*__*_______*
_*____*_*_____________*______*______**__*________*
*__*_*_*_*__**________**_______*________*____*____

Music only !

bluestorm

19 avril 2006 à 19:35:39

Ce qui prend du temps, c'est tout d'abord le srand() inutile, mais surtout le fait qu'il est possible que tu doives rééssayer indéfiniment si tu tombes à chaque fois sur une case déja occupée.

Il te faudrait un moyen d'être sur de jamais tomber sur une case occupée quand tu tires une position au hasard.

Ce que tu pourrais faire, c'est un tableau de NB_BLOCS_LARGEUR cases, qui contient le nombre de cases libres dans chaque colonne de ton démineur :
tu commences par tirer la colonne de la mine suivante au hasard. Ensuite, tu vas voir dans ce tableau le nombre de cases libres dans cette colonne, et tu tires un nombre au hasard qui soit inférieur strictement à ce nombre. Si par exemple tu tires 3, tu vas poser une mine dans la troisième case libre de cette colonne.

En associant ça à une variable qui stocke le nombre de colonnes qui ne sont pas totalement occupées par les mines, tu peux être sûr de ne jamais tirer plusieurs fois la même case, et donc de réduire beaucoup le temps du choix au hasard si tu as beaucoup de mines sur peu de cases.

Matheus07

19 avril 2006 à 19:46:40

En effet, je n'avais pas bien saisi le fonctionnement de srand().
Ca améliore déjà pas mal la rapidité du code.

Je vais tester le tableau de NB_BLOCS_LARGEUR, j'imagine que pour un rapport d'une mine pour 22,5 cases comme c'est le cas dans mon exemple, le temps d'exécution ne changera pas tellement, mais je vois bien le truc arriver si ma proportion de mine augmente.

Merci à tous les quatre =)

bluestorm

19 avril 2006 à 19:54:58

Attention : si tu as peu de mines sur ton tableau, mon truc fera même augmenter le temps d'execution, vu que tu es obligé de faire des parcours du tableau en plus.

Ce que je ferais à ta place, c'est utiliser ta technique tout en notant les résultats dans le tableau (décrémentant le nombre de cases vides dans la colonne qui est sortie à chaque fois que le tirage marche), et passer à ma méthode une fois seulement que la proportion de cases vides restantes est faible (je pense que 3/4 est une bonne valeur par défaut).

Matheus07

19 avril 2006 à 20:13:40

En fait, j'ai fait un test avec ma méthode pour 225 mines sur 225 cases.. du 100% quoi, et le temps d'exécution est quasi instantané. :euh:

Donc je ne pense même pas qu'il soit nécessaire de rajouter un tableau et grossir le code.
Tant que personne s'amuse à tenter des parties de démineur à 1 000 000 de mines sur 1 000 001 cases

EDIT pour -ed- : Je ne l'ai pas précisé, mais je le réalise grâce à la librairie SDL, pas en console (ce qui ne change en rien le script de génération de mines, soit).