S'enregistrer | Rechercher | FAQ | Liste des Membres | Groupes d'utilisateurs | Connexion

  Nom d'utilisateur:    Mot de passe:       

  

Poster un nouveau sujet   Répondre au sujet Page 1 sur 1
Voir le sujet précédent :: Voir le sujet suivant  
Auteur Message
MessagePosté le: Dim Déc 09, 2007 3:23 pm    Sujet du message: programme en C Répondre en citant

CaMp3uR
Projets


 
Inscrit le: 24 Oct 2007
Messages: 104



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 =) Razz
"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 :
Citation:


#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;
}


Dernière édition par CaMp3uR le Mer Déc 12, 2007 1:55 pm; édité 2 fois
Voir le profil de l'utilisateur Envoyer un message privés
MessagePosté le: Mer Déc 12, 2007 1:54 pm    Sujet du message: Répondre en citant

CaMp3uR
Projets


 
Inscrit le: 24 Oct 2007
Messages: 104



Personne n'a d'idée? Smile
Voir le profil de l'utilisateur Envoyer un message privés
MessagePosté le: Mer Déc 12, 2007 2:02 pm    Sujet du message: Répondre en citant

Korigan
Site Admin


 
Inscrit le: 29 Mai 2007
Messages: 1781



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?
Voir le profil de l'utilisateur Envoyer un message privés Envoyer un e-mail
MessagePosté le: Mer Déc 12, 2007 5:26 pm    Sujet du message: Répondre en citant

CaMp3uR
Projets


 
Inscrit le: 24 Oct 2007
Messages: 104



Mon cousin à un projet à durer limiter, donc oui. Je vais me renseigner sur les dates à tenir =) Merci encore pour ton aide.
Voir le profil de l'utilisateur Envoyer un message privés
MessagePosté le: Mer Déc 12, 2007 10:52 pm    Sujet du message: Répondre en citant

Korigan
Site Admin


 
Inscrit le: 29 Mai 2007
Messages: 1781



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 Smile
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? Smile
Voir le profil de l'utilisateur Envoyer un message privés Envoyer un e-mail
MessagePosté le: Jeu Déc 13, 2007 8:52 pm    Sujet du message: Répondre en citant

CaMp3uR
Projets


 
Inscrit le: 24 Oct 2007
Messages: 104



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.
Voir le profil de l'utilisateur Envoyer un message privés
MessagePosté le: Jeu Déc 13, 2007 10:18 pm    Sujet du message: Répondre en citant

Korigan
Site Admin


 
Inscrit le: 29 Mai 2007
Messages: 1781



Je pensais fortement à cette solution aussi.
C'etait mal boutiqué! Rolling Eyes
Oui je suis interessé par la nouvelle version.
Et si tu veux l'équivalent en java je dois avoir ça quelquepart Smile
Voir le profil de l'utilisateur Envoyer un message privés Envoyer un e-mail
MessagePosté le: Mer Déc 19, 2007 4:22 pm    Sujet du message: Répondre en citant

CaMp3uR
Projets


 
Inscrit le: 24 Oct 2007
Messages: 104



Voilà le code source qui marche nickel Korigan :p

Citation:

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;
}

Voir le profil de l'utilisateur Envoyer un message privés
MessagePosté le: Mer Déc 19, 2007 7:35 pm    Sujet du message: Répondre en citant

Korigan
Site Admin


 
Inscrit le: 29 Mai 2007
Messages: 1781



Merci Cool
Je vais tester ça Smile
Voir le profil de l'utilisateur Envoyer un message privés Envoyer un e-mail
MessagePosté le: Ven Oct 17, 2008 9:02 pm    Sujet du message: xhunter Répondre en citant

xhunter
Projets


 
Inscrit le: 28 Déc 2007
Messages: 44



Salut,
Il y a une faute au debut du code
Code:
    
uais#include <stdio.h>

Ce code est vraiment difficile, j'ai rien compris , pourrais tu ajouter plus de commentaire ?
Merci.

++xhunter
Voir le profil de l'utilisateur Envoyer un message privés Envoyer un e-mail MSN Messenger
MessagePosté le: Ven Juil 10, 2009 1:37 am    Sujet du message: Re: xhunter Répondre en citant

LECHIENKITU
Projets


 
Inscrit le: 01 Avr 2009
Messages: 177



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

[EDIT by Sliim] : UP inutile, merci de regarder la date avant de poster un message n'apportant rien au sujet !!
Voir le profil de l'utilisateur Envoyer un message privés
MessagePosté le: Ven Juil 10, 2009 8:53 am    Sujet du message: Répondre en citant

Sliim
Site Admin


 
Inscrit le: 16 Mai 2008
Messages: 1177



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

++
Sliim
Voir le profil de l'utilisateur Envoyer un message privés Visiter le site web de l'utilisateur Messagerie Instantan√©e
MessagePosté le: Ven Juil 10, 2009 9:54 am    Sujet du message: Répondre en citant

LECHIENKITU
Projets


 
Inscrit le: 01 Avr 2009
Messages: 177



d'accord escusez moi pour ces fautes Sad ca ne se reproduira plus Wink
Voir le profil de l'utilisateur Envoyer un message privés
Poster un nouveau sujet   Répondre au sujet Page 1 sur 1

  


 
Sauter vers:  
Vous ne pouvez pas poster de nouveaux sujets dans ce forum
Vous ne pouvez pas répondre aux sujets dans ce forum
Vous ne pouvez pas éditer vos messages dans ce forum
Vous ne pouvez pas supprimer vos messages dans ce forum
Vous ne pouvez pas voter dans les sondages de ce forum



122962 Attacks blocked