programme en C

Moderator: Mod

programme en C

Postby CaMp3uR » Sun Dec 09, 2007 3:23 pm

Voilà, vu qu'il n'y a aucun forum pour la programation en C, je poste mon message ici, je previent que c'est pour les gens bien calés en fin je pense =)
En fait c'est un prog pour mon cousin qui séche un petit peu dessu =) :P
"Salut !



Je code un petit programme pour générer aléatoirement un labyrinthe.

Je procède en deux temps :

-> Je crée une matrice que je remplis avec des "0" (passages) et des "-1" (murs) aléatoirement.

-> Je "creuse" un passage aléatoire dans les murs, d'en haut à gauche à en bas à droite

pour ça, j'utilise une liste doublement chaînée qui contient :

-> le numéro de la case de mon passage creusé

-> les coordonnées de cette case dans la matrice

-> l'adresse mémoire de la précédente et de la suivante

-> le nombre de mouvements qui étaient autorisés à la création

je cherche un moyen d'insérer à la ligne 157 un bout de code qui fasse rebrousser chemin (à cause d'un cul de sac déjà détecté) jusqu'à une case où le nombre de mouvements possibles était d'au moins 2, et de forcer le chemin à ne pas repartir dans le même sens.

Merci d'avance!"

Voilà le code source :
[quote:ace8579b72]

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

#define N 15
#define P 45

/*strucure de liste doublement chaînée*/

struct LC
{
int x;
int y;
int num;
struct LC *next;
struct LC *prev;
int nbmvts;
};

typedef struct LC lc;

/*renvoie le nombre de mouvements qui peuvent être effectués depuis la case de coordonnées x, y*/

int nb_mvts(int grid[N][P], int x, int y, int dx[4], int dy[4])
{
int i, n;
n = 0;
for(i = 0 ; i < 4 ; i++)
{
if(x + 2 * dx[i] < P-1 && x + 2 * dx[i] > 0 && y + 2 * dy[i] < N-1 && y + 2 * dy[i] > 0)
if(grid[y + 2 * dy[i]][x + 2 * dx[i]] == 0)
n++;
}
printf("nb mvts (%d,%d) : %d\n",x, y, n-1);
return n;
}

/*affiche la grille*/

void disp(int grid[N][P])
{
int i, j;
printf("\n");
for(i = 0 ; i < N ; i++)
{
for(j = 0 ; j < P ; j++)
{
if(grid[i][j] == -1)
printf(".");
else
printf(" ");
}
printf("\n");
}
}

/*affiche la grille et le chemin creusé*/

void disp_p(int grid[N][P], lc *path, int mx[2], int my[2])
{
int i, j;
lc *cur;
j = 0;
for(cur = path ; cur->next == 0 ; cur = cur->next)
{
/*grid[cur->y][cur->x] = 1;*/
j++;
printf("mvt %d : (%d,%d) -> (%d,%d)\n", j, cur->x, cur->y, cur->next->x, cur->next->y);
}
printf("\n\t");
for(j = 0 ; j < P ; j++)
{
if(j < 10)
printf(" %d", j);
else
printf("%d", j);
}
printf("\n\n");
for(i = 0 ; i < N ; i++)
{
printf("%d\t", i);
for(j = 0 ; j < P ; j++)
{
if((i != my[0] || j != mx[0]) && (i != my[1] || j != my[1]))
{
if(grid[i][j] == -1)
printf("++");
if(grid[i][j] == 0)
printf(" ");
if(grid[i][j] > 0 && grid[i][j] < 10)
printf("0%d", grid[i][j]);
if(grid[i][j] > 9)
printf("%d", grid[i][j]);
}
else
printf("##");
}
printf("\n");
}
}

/*toutes les gestions de variables sont faites dans main*/

int main(int argc, char *argv[])
{
int grid[N][P], i, j, ch, dx[4] = {1,0,-1,0}, dy[4] = {0,-1,0,1}, poss[4]={1,1,1,1}, cpt, k, mx[2], my[2];
lc *path, *last, *el;
srand(time(0));
/*remplir la matrice de 0 (passages) et de -1 (murs)*/
for(i = 0 ; i < N ; i++)
for(j = 0 ; j < P ; j++)
grid[i][j] = (i==0 || j==0 || i==N-1 || j==P-1 || (i%2==0 && j%2==0)) ? -1 : 0;
for(i = 1 ; i < N-1 ; i++)
for(j = 1 ; j < P-1 ; j++)
if((i+j)%2 == 1 && rand()%2 == 0)
grid[i][j] = -1;
disp(grid);
/*initialisation du chemin creusé*/
path = (lc *) malloc(sizeof(lc));
path->num = 1;
path->nbmvts = 2;
path->x = 1;
path->y = 1;
grid[1][1] = 1;
path->next = 0;
last = path;
/*on boucle jusqu'à arriver en bas à droite (et on se débrouille pour y arriver)*/
while(last->x != P-2 || last->y != N-2)
{
el = (lc *) malloc(sizeof(lc));
last->next = el;
el->prev = last;
el->num = last->num + 1;
for(cpt = 0 ; cpt < 4 ; cpt++)
{
/*liste des mouvements possibles : a priori tous le sont*/
poss[cpt] = 1;
}
/*choix aleatoire d'un mouvement :

^
1
<2 0>
3
v
*/
ch = rand()%4;
/*conditions pour quel le mouvement choisi soit valide :
* ne pas sortir de la grille
* ne pas revenir vers le départ quand on est contre un mur (sinon on s'enferme)
* ne pas se croiser
* le nombre de mouvements possibles depuis la nouvelle case n'est pas égal à 0*/
while(last->x + 2 * dx[ch] < 1
||last->x + 2 * dx[ch] > P-2
||last->y + 2 * dy[ch] < 1
||last->y + 2 * dy[ch] > N-2
||( (last->x == 1 || last->x == P-2) && ch == 1)
||( (last->y == 1 || last->y == N-2) && ch == 2)
||grid[ last->y + 2 * dy[ch] ][ last->x + 2 * dx[ch] ] > 0
||nb_mvts(grid, last->x + 2 * dx[ch], last->y + 2 * dy[ch], dx, dy) <= 0)
{
/*ce mouvement n'est pas bon, on l'élimine*/
poss[ch] = 0;
printf("mouvement impossible : %d\n", ch);
/*Si tous les mouvements sont impossibles*/
if(poss[0] == 0 && poss[1] == 0 && poss[2] == 0 && poss[3] == 0)
/*mauvaise idée que j'avais eue avant :*/
/* {
printf("cul de sac : (%d, %d) -> (%d, %d)\n",last->x, last->y, last->prev->x, last->prev->y);
mx[0] = last->x;
my[0] = last->y;
mx[1] = last->prev->x;
my[1] = last->prev->y;
grid[last->y][last->x] = 0;
last = last->prev;
free(el);
el = (lc *) malloc(sizeof(lc));
last->next = el;
el->prev = last;
el->num = last->num + 1;
for(k = 0 ; k < 4 ; k++)
{
poss[k] = 1;
}
}*/
{
/*c'est là que j'ai besoin d'un gros coup de main =) */
}
srand(rand());
/*choisir un nouveau mouvement qui ne soit pas un déjà éliminé*/
while(poss[ch] == 0)
ch = rand()%4;
}
/*la nouvelle "dernière case" du chemin est "el".*/
el->x = last->x + 2 * dx[ch];
el->y = last->y + 2 * dy[ch];
el->nbmvts = nb_mvts(grid, el->x, el->y, dx, dy);
grid[last->y + dy[ch]][last->x + dx[ch]] = 0;
grid[el->y][el->x] = el->num;
last = el;
getchar();
disp_p(grid, path, mx, my);
}
return 0;
}
[/quote:ace8579b72]
Last edited by CaMp3uR on Wed Dec 12, 2007 1:55 pm, edited 2 times in total.
CaMp3uR
Projets
 
Posts: 104
Joined: Wed Oct 24, 2007 3:22 pm

Postby CaMp3uR » Wed Dec 12, 2007 1:54 pm

Personne n'a d'idée? :)
CaMp3uR
Projets
 
Posts: 104
Joined: Wed Oct 24, 2007 3:22 pm

Postby Korigan » Wed Dec 12, 2007 2:02 pm

Sisi,
Ton code m'intéresse mais je voudrais prendre le temps d'y réléchir un peu de façon à ne pas injecter une solution trop compliqué.
Tu as des délais à respecter?
User avatar
Korigan
Site Admin
 
Posts: 1781
Joined: Tue May 29, 2007 6:57 pm

Postby CaMp3uR » Wed Dec 12, 2007 5:26 pm

Mon cousin à un projet à durer limiter, donc oui. Je vais me renseigner sur les dates à tenir =) Merci encore pour ton aide.
CaMp3uR
Projets
 
Posts: 104
Joined: Wed Oct 24, 2007 3:22 pm

Postby Korigan » Wed Dec 12, 2007 10:52 pm

Tu devrais utiliser une matrice en plus. Ce serait une sorte de mémoire pour lui.
Tu l'initialise au fur et à mesure et quand tu detecte un cul de sac tu fais comme si c'etait un mur et contrairement a ton hypothese, tu fais demi-tour. Tu va faire un petit robot poseur de brique :)
Il finira tôt ou tar par trouver un chemin possible.

Ok ce n'est pas optimisé, mais de toute façon tu fais des déplacements aléatoire donc cela ne change pas grand chose. Ce n'est pas du temps perdu puisque tu saura que tel chemin n'est pas valide.

Là le programme tourne dans le vide quand il est bloqué. Si l'on suivait la logique un autre déplacement aléatoire ne serait-il pas plus facile à implémenter? :)
User avatar
Korigan
Site Admin
 
Posts: 1781
Joined: Tue May 29, 2007 6:57 pm

Postby CaMp3uR » Thu Dec 13, 2007 8:52 pm

Merci bien, mais en fait il a apparamment trouver une autre solution. Je lui ai donné un petit conseil : Control+A plus Del^^ et apparemmentt il a refait un code qui marche, donc si ca t'interresse, je peut toujours le mettre ici.
CaMp3uR
Projets
 
Posts: 104
Joined: Wed Oct 24, 2007 3:22 pm

Postby Korigan » Thu Dec 13, 2007 10:18 pm

Je pensais fortement à cette solution aussi.
C'etait mal boutiqué! :roll:
Oui je suis interessé par la nouvelle version.
Et si tu veux l'équivalent en java je dois avoir ça quelquepart :)
User avatar
Korigan
Site Admin
 
Posts: 1781
Joined: Tue May 29, 2007 6:57 pm

Postby CaMp3uR » Wed Dec 19, 2007 4:22 pm

Voilà le code source qui marche nickel Korigan :p

[quote:04d8647ce5]
uais#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define N 25
#define P 45

/*Structure de liste doublement chaînée, utilisée pour les cases successives du chemin creusé à travers le labyrinthe*/
struct LC
{
int x; /*abscisse de la case dans grid*/
int y; /*ordonnée de la case dans grid*/
int poss[4]; /*poss[i] = (mouvement i possible) ? 1 : 0;*/
int n; /*numéro de la case dans le chemin*/
int mc; /*mouvement effectué depuis la case*/
struct LC *next;
struct LC *prev;
};

typedef struct LC lc;

float rand_val()
{
float ran;
ran = (rand() % 100000000)/100000000.0;
return ran;
}

/*Nouvel élément*/
lc *new(lc *prev)
{
lc *el;
el = malloc(sizeof(lc));
el->prev = prev;
el->next = 0;
return el;
}

void disp2(int grid[N][P] , int x , int y)
{
int i,j;
printf("\n");
for(i = 0 ; i < N ; i++)
{
for(j = 0 ; j < P ; j++)
{
if(grid[i][j] == -1)
{
printf("++");
}
else
{
if(i == y && j == x)
printf(" X");
else
{
if(grid[i][j] == 0)
printf(" ");
if(grid[i][j] > 0 && grid[i][j] < 10)
printf(" %d", grid[i][j]);
if(grid[i][j] > 9)
printf("%d",grid[i][j]);
}
}
}
printf("\n");
}
printf("\n");
}

int ind_min(int L[4])
{
int i, a = 0, l[4], cpt = 0;
for(i = 1 ; i < 4 ; i++)
{
a = (L[i] < L[a]) ? i : a;
}
for(i = 0 ; i < 4 ; i++)
{
if(L[i] == L[a])
{
l[cpt] = i;
cpt++;
}
}
return l[rand() % cpt];
}

/*Choix du mouvement à effectuer (résolution)*/
int mvt(int grid[N][P] , int x , int y , int dx[] , int dy[])
{
int mp[4] , m , i , compt[4] , tot = 0, ran;
ran = rand() % 4;
for(i = ran ; i < 4 + ran ; i++)
{
mp[i % 4] = (grid[y + dy[i % 4]][x + dx[i % 4]] < 0) ? (0) : (1);
}
ran = rand() % 4;
for(i = ran ; i < 4 + ran ; i++)
{
if(mp[i % 4] == 1)
{
compt[i % 4] = grid[y + dy[i % 4]][x + dx[i % 4]];
tot += compt[i % 4];
}
}
ran = rand() % 4;
for(i = 0 ; i < 4 ; i++)
{
if(mp[i % 4] == 0)
{
compt[i % 4] = tot + 1;
}
}
m = ind_min(compt);
return m;
}

/*Affichage du labyrinthe et du chemin creusé dedans*/
void disp(int grid[N][P])
{
int i, j;
printf("\n\n");
for(i = 0 ; i < N ; i++)
{
for(j = 0 ; j < P ; j++)
{
if(grid[i][j] == 0)
printf(" "); /*2 espaces : couloir*/
if(grid[i][j] == -1)
printf("++"); /*++ : un mur*/
if(grid[i][j] > 0 && grid[i][j] < 10)
printf("0%d", grid[i][j]); /*chemin : numéro de la case*/
if(grid[i][j] > 9)
printf("%d", grid[i][j]); /*chemin : numéro de la case*/
}
printf("\n");
}
printf("\n");
}

int main(int argc, char *argv[])
{
int grid[N][P], i, j, dx[4] = {1, 0, -1, 0}, dy[4] = {0, -1, 0, 1}, ch, x = 1, y = 1, m;
lc *path, *last, *el;
srand(time(0));
/*On remplit tout le tour et une case sur 4 avec un mur [-1], le reste étant des couloirs [0]*/
for(i = 0 ; i < N ; i++)
for(j = 0 ; j < P ; j++)
grid[i][j] = (i == 0 || j == 0 || i == N - 1 || j == P - 1 || (i % 2 == 0 && j % 2 == 0)) ? -1 : 0;
/*On place des murs [-1] aléatoirement aux emplacement susceptibles*/
for(i = 1 ; i < N-1 ; i++)
for(j = 1 ; j < P-1 ; j++)
if((i+j)%2 == 1 && rand()%2 == 0)
grid[i][j] = -1;
disp(grid);
getchar();
path = malloc(sizeof(lc));
path->x = 1;
path->y = 1;
path->n = 1;
path->prev = 0;
path->next = 0;
last = path;
/*Boucle principale : ajout d'une case [el] dans le chemin à chaque itération*/
while(last->x != P - 2 || last->y != N - 2)
{
grid[last->y][last->x] = last->n;
el = new(last);
last->next = el;
/*On regarde le nombre de mouvements possibles depuis la case créée juste avant la boucle en cours [last]*/
for(i = 0 ; i < 4 ; i++)
{
last->poss[i] = (last->x + 2 * dx[i] < 1
|| last->x + 2 * dx[i] > P - 1
|| last->y + 2 * dy[i] < 1
|| last->y + 2 * dy[i] > N - 1
|| (i == 1 && (last->x == 1 || last->x == P - 2))
|| (i == 2 && (last->y == 1 || last->y == N - 2))
|| grid[last->y + 2 * dy[i]][last->x + 2 * dx[i]] >0
) ? 0 : 1;
}
/*Si on est dans un cul-de-sac, on rebrousse chemin, et on interdit un nouvel accès au cul-de-sac*/
while(last->poss[0] == 0 && last->poss[1] == 0 && last->poss[2] == 0 && last->poss[3] == 0)
{
grid[last->y][last->x] = 0;
last = last->prev;
last->poss[last->mc] = 0;
}
/*Choix du mouvement :
^
1
<2 0>
3
v */
ch = rand() % 4;
while(last->poss[ch] == 0)
{
ch = rand() % 4;
}
last->mc = ch;
el->n = 1 + last->n;
el->x = last->x + 2 * dx[ch];
el->y = last->y + 2 * dy[ch];
/*On remplace l'éventuel mur entre la dernière case [last] et celle créée dans cette boucle [el] par un couloir*/
grid[last->y + dy[ch]][last->x + dx[ch]] = 0;
grid[el->y][el->x] = el->n;
/*Le nouveau dernier élément [last] est celui créé dans cette boucle [el]*/
last = el;
/*disp(grid);*/
/*getchar();*/
}
disp(grid);
getchar();
/*On "nettoie" la grille*/
for(i = 0 ; i < N ; i++)
{
for(j = 0 ; j < P ; j++)
{
grid[i][j] = (grid[i][j] > 0) ? 0 : grid[i][j];
}
}
disp2(grid , x , y);
while(y != N - 2 || x != P - 2)
{
grid[y][x]++;
m = mvt(grid , x , y , dx , dy);
x += dx[m];
y += dy[m];
disp2(grid , x , y);
getchar();
}
printf("Fini !\n");
return 0;
}

[/quote:04d8647ce5]
CaMp3uR
Projets
 
Posts: 104
Joined: Wed Oct 24, 2007 3:22 pm

Postby Korigan » Wed Dec 19, 2007 7:35 pm

Merci 8)
Je vais tester ça :)
User avatar
Korigan
Site Admin
 
Posts: 1781
Joined: Tue May 29, 2007 6:57 pm

xhunter

Postby xhunter » Fri Oct 17, 2008 9:02 pm

Salut,
Il y a une faute au debut du code [code:1:c609c952ed]
uais#include <stdio.h> [/code:1:c609c952ed]
Ce code est vraiment difficile, j'ai rien compris , pourrais tu ajouter plus de commentaire ?
Merci.

++xhunter
User avatar
xhunter
Projets
 
Posts: 44
Joined: Fri Dec 28, 2007 9:25 pm

Re: xhunter

Postby LECHIENKITU » Fri Jul 10, 2009 1:37 am

juste en C LES COMMENTAIRES SUR UNE SEUL LIGNES COMMENCES PAS PAR // au lieu de/**/ comme l'a fait ton couzin :roll:
LeChienKiTu

[color=red:3355756016][b:3355756016][EDIT by Sliim][/b:3355756016] : UP inutile, merci de regarder la date avant de poster un message n'apportant rien au sujet !!
[/color:3355756016]
LECHIENKITU
Projets
 
Posts: 177
Joined: Wed Apr 01, 2009 4:12 am

Postby Sliim » Fri Jul 10, 2009 8:53 am

LECHIENKITU : Tu peux utiliser les deux pour une seule ligne.. rien ne dit que // est obligatoire quand c'est seulement sur une seule ligne..

[EDIT] : Evites ce genre de UP inutile, j'en ai compté 3 ou 4 ce matin où ce que tu disais ne servait à rien donc bon c'est pas très agréable..
De plus tu as google, la recherche se fait avant de poster ...

++
[u:2b6d8297b6]Sliim[/u:2b6d8297b6]
User avatar
Sliim
Site Admin
 
Posts: 1177
Joined: Fri May 16, 2008 12:53 pm

Postby LECHIENKITU » Fri Jul 10, 2009 9:54 am

d'accord escusez moi pour ces fautes :( ca ne se reproduira plus ;)
LECHIENKITU
Projets
 
Posts: 177
Joined: Wed Apr 01, 2009 4:12 am


Return to C/C++

Who is online

Users browsing this forum: No registered users and 1 guest

cron