vendredi 15 juin 2018

Maze by recursive division not working - C

I'm having some trouble with my recursive division generated maze. I know there's something wrong about the recursion, but I just can't find a way to solve it.

I also know the code is really big and not optimized at all, but I'm working better on this issue later.

The red maze is what I'm generating and the purple one is what I'm trying to do:

Result

Goal

What should I be doing to correct that?

Tnks.

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

#define MAX 41
#define FUNDO 0
#define PAREDE 1
#define SAIDA 2
#define SOLUCAO 3

int num_aleat(int min, int max)
{
    return rand()%(max-min+1)+min;
}


void paredes(int m[][MAX], int FINAL_i, int FINAL_j, int INICIO_i, int INICIO_j)
{
    int i=0, j=0;
    for(i=0; i<MAX; i++)
    {
        if (i!=FINAL_i && i!=INICIO_i)
            m[i][j]=PAREDE;
    }
    i=0;
    for(j=0; j<MAX; j++)
    {
        if (j!=INICIO_j)
            m[i][j]=PAREDE;
        else
            m[i][j]=SAIDA;
    }
    j=0;
    for(i=0; i<MAX; i++)
    {
        if (j!=FINAL_j && j!=INICIO_j)
            m[i][j+MAX-1]=PAREDE;
    }
    i=0;
    for(j=0; j<MAX; j++)
    {
        if (j!=FINAL_j)
            m[i+MAX-1][j]=PAREDE;
        else
            m[i+MAX-1][j]=SAIDA;
    }
    j=0;
}


void pardede_gener(int m[][MAX], int min, int max, int x, int dir)
{
    int i=0, passagem=0;
    switch (dir)
    {
        case 1:
            passagem=num_aleat(min, max);
            printf("\nc\n");
            for(i=min; i<=max; i++)
            {
                if(i!=passagem)
                    m[i][x]=PAREDE;
                printf("\nd_%i_%i\n", i, x);
            }
            return;  
            break;
        case 2:
            passagem=num_aleat(min, max);
            for(i=min; i<=max; i++)
            {
                if(i!=passagem)
                    m[x][i]=PAREDE;
            }
            return;
            break;
    }
    return;
}

void div(int m[][MAX], int i, int j, int max_i, int max_j, int dir)
{
    int parede_i=MAX, parede_j=MAX, flag=0;
    if(dir==1)
    {
        while(1)
        {
            parede_j=num_aleat(j, max_j);
            if (parede_j%2==0 && m[i+1][parede_j]==FUNDO && m[i+1][parede_j-1]!=PAREDE && m[i+1][parede_j+1]!=PAREDE || m[i+2][parede_j]!=PAREDE)
                break;
            else
                break;
        }
        if(m[i+1][parede_j]!=PAREDE && m[i+1][parede_j-1]!=PAREDE && m[i+1][parede_j+1]!=PAREDE)
        { 
            pardede_gener(m, i+1, max_i-1, parede_j, dir);
            dir=2;
            div(m, i, j, max_i, parede_j, dir);
            div(m, i, parede_j, max_i, max_j, dir);
        }
        else
            return;
    }
    else if(dir==2)
    {
        while(1)
        {
            parede_i=num_aleat(j, max_j);
            if (parede_i%2==0 && m[parede_i][j+1]==FUNDO && m[parede_i-1][j+1]!=PAREDE && m[parede_i+1][j+1]!=PAREDE || m[parede_i][j+2]==PAREDE)
                break;
            else
                break;
        }
        if(m[parede_i][j+1]!=PAREDE && m[parede_i-1][j+1]!=PAREDE && m[parede_i+1][j+1]!=PAREDE)
        {
            pardede_gener(m, j, max_j-1, parede_i-1, dir);
            dir=1;
            div(m, i, j, parede_i, max_j, dir);
            div(m, parede_i, j, max_i, max_j, dir);
        }
        else
            return;
    }
}


bool resolve(int *m, int i, int j, int fi, int fj)
{
    *(m + i*MAX + j)=SOLUCAO;
    if(i==fi-1 && j==fj)
        return true;
    if (i+1<MAX && *(m + (i+1)*MAX + j)==FUNDO)
    {
        if(resolve(m, i+1, j, fi, fj))
            return true;
    }
    if (i-1>=0 && *(m + (i-1)*MAX + j)==FUNDO)
    {
        if(resolve(m, i-1, j, fi, fj))
            return true;
    }
    if (j+1<MAX && *(m + i*MAX + (j+1))==FUNDO)
    {
        if(resolve(m, i, j+1, fi, fj))
            return true;
    }
    if (j-1>=0 && *(m + i*MAX + (j-1))==FUNDO)
    {
        if(resolve(m, i, j-1, fi, fj))
            return true;
    }
    *(m + i*MAX + j)=FUNDO;
   return false;
}


int main()
{
    int lab[MAX][MAX];
    int FINAL_i=0, FINAL_j=0, INICIO_i=0, INICIO_j=0, i=0, j=0;
    srand(time(NULL));
    FINAL_i=MAX-1;
    while (INICIO_j%2==0 || FINAL_j%2==0)
    {
        INICIO_j=rand()%(MAX-2)+1;
        FINAL_j=rand()%(MAX-2)+1;
    }
    zero(lab);
    paredes(lab, FINAL_i, FINAL_j, INICIO_i, INICIO_j);
    div(lab, 0, 0, MAX-1, MAX-1, 1);
//  resolve(*lab, 1, INICIO_j, FINAL_i, FINAL_j);
    return 0;
}




Aucun commentaire:

Enregistrer un commentaire