c++ - 3d labyrint - Udvikleren.dk - Programmering, webdesign og grafik

Tags: c++

<< < 1 2 3 4 5 > >>

Bruger #4414 @ 03.02.06 16:14

Her er et lille stykke kode jeg har skrevet, det er naturligvis lang fra færdigt, men jeg har et par spørgsmål til hvordan det kan gøres, har nogle problemer der mangler løsninger osv.

Kode

#include <iostream>
#include <vector>

const int SIZE = 256;

struct cell { 
        bool xy: 1;
        bool xz: 1;
        bool yz: 1;
        bool ac: 1;
};
std::vector<std::vector<std::vector<cell> > >GRID(SIZE,
std::vector<std::vector<cell> >(SIZE,
std::vector<cell>(SIZE)));
bool rand_bit() {
    return rand() > (RAND_MAX / 2);
}
void new_grid() {
    int x;
    int y;
    int z;
    for (z = 0; z < SIZE; z++) {
        for (y = 0; y < SIZE; y++) {
            for (x = 0; x < SIZE; x++) {
                GRID[x][y][z].xy = rand_bit();
                GRID[x][y][z].xz = rand_bit();
                GRID[x][y][z].xz = rand_bit();
            }
        }
    }
}

int main() {
    new_grid();
    std::cout << "done!";
    std::cin.get();
}

1)
Jeg har lavet en struct 'cell' med 4 boole variabler der hver fylder én bit, altså 4 bit total pr celle, nu forholder det sig sådan at selvom jeg reelt kun har brug for en halv byte pr celle, bruger den 1 byte. Om den bruger 8 eller 16 MB for en sådan 256^3 struktur, gør ikke den helt store forskel, men jeg kunne godt tænkte mig at få løst problemet alligevel hvis det kan lade sig gøre.

2)
I 'new_grid()' tildeler den værdier (0 eller 1) til til alle xy/xz/yz variablerne i cellerne. disse xy/xz/yz skal forstås som vægge i en 3d_labyrint; hvis værdien er 0 er der ingen væg og er den 1 er der en væg.
Det første problem er naturligvis at jeg har brug for en 'ikke pseudo' rand_bit(), men der er et lille problem, her på test stadiet fungerer denne fint nok.
Nu kommr den lumske del
Hver celle har 6 vægge. 3 af disse vægge er defineret i cellen, og de resterende vægge er defineret af de omkring liggende celler.
dvs.
celle xyz har væggene:
GRID[x][y][z].xy
GRID[x][y][z].xz
GRID[x][y][z].yz
GRID[x][y][z-1].xy
GRID[x][y-1][z].xz
GRID[x-1][y][z].yz

strukturen er uendelig/endelig hvilket vil sige hvis man skulle være så uheldig at befinde sig i 257,257,257, befinder man sig i hvirkeligheden i 1,1,1.
det er lidt kringle, men det virker.

Problemet består i at disse celler skal opfylde nogle krav:
De må ikke være lukkede, dvs. der skal være mindst én manglende væg pr celle.
Det skal være muligt at bevæge sig fra en given celle til en anden, uanset placering.

Dette er noget jeg grubler over.

3)
Jeg ønsker at høre en masse gpde idéer til forbedringer o.lign.
Jeg ønsker at høre om fejl og mangler.
Jeg ønsker en interessant diskution om hvorledes man kan/bør løse dette problem, det stykke kode jeg har postet er kun et oplæg, det kan meget vel gøres smartere.

4)
Jeg kan forestille mig at der måske er nogle der grubler over hvad meningen med galskaben er og det er jo naturligvis meningen at der skal skrives et grafisk interface med tiden og derefter kan jeg se adskillige muligheder for hvad det kan bruges til.

5)
I skal vide at jeg er nubegynder og faktisk ikke har været i gang i meget over en uge, jeg har dog lavet en del php scripts osv. men altså stadig en c++ n00b ;-)
Jeg er klar over at meget af dette ville tage sig rigtig godt ud i classes, men jeg har aldrig brug dem før og selv om jeg er igang med at læse på sagen, bliver jeg blot mere og mere forviret...

[Redigeret d. 08/02-06 17:12:02 af Felix Nielsen]

41 svar postet i denne tråd vises herunder
1 indlæg har modtaget i alt 4 karma

Sorter efter stemmer Sorter efter dato

Bruger #4414 @ 05.02.06 22:33

113

Jeg er lidt på den her.
Efter at have indkoorporeret det nye system, virker den del af funktionen der skal sørge for at der ikke er nogen lukkede rum, ikke mere.
Jeg har prøvet forskellige ting for at finde fejlen, men det her går over min forstand.

Denne del virker:

Kode

void new_grid() {
    srand(time(0));
    int x;
    int y;
    int z;
    int x_cache;
    int y_cache;
    int z_cache;
    bool loop;
    for (z = 0; z < size; z++) {
        for (y = 0; y < size; y++) {
            for (x = 0; x < size; x++) {
                write(x,y,z,yz,rand_int(2));
                write(x,y,z,xz,rand_int(2));
                write(x,y,z,xy,rand_int(2));
            }
        }
    }

Denne del virker ikke:

Kode

    for (z = 0; z < size; z++) {
        for (y = 0; y < size; y++) {
            for (x = 0; x < size; x++) {
                if (read(x,y,z,yz)+read(x,y,z,xz)+read(x,y,z,xy) == 3) {
                    x_cache = x;
                    y_cache = y;
                    z_cache = z;
                    if (x == 0) {x_cache = size-1;}
                    else {x_cache = x;}
                    if (y == 0) {y_cache = size-1;}
                    else {y_cache = y;}
                    if (z == 0) {z_cache = size-1;}
                    else {z_cache = z;}
                    if (read(x,y,z,yz)+read(x,y,z,xz)+read(x,y,z,xy) == 3) {
                        x = x_cache;
                        y = y_cache;
                        z = z_cache;
                        write(x,y,z,yz,rand_int(2));
                        write(x,y,z,xz,rand_int(2));
                        write(x,y,z,xy,rand_int(2));
                        x--;
                    }
                }
            }
        }
    }

Denne del virker måske/måske ikke, men den stopper ihvertfald ikke programmet:

Kode

    for (x = 0; x < size; x++) {
        for (y = 0; y < size; y++) {
            for (z = 0; z < size && read(x,y,z,yz) == 1; z++) {
                if (z == size - 1) {
                    write(x,y,rand_int(size),yz,0);
                }
            }
        }
        for (z = 0; z < size; z++) {
            for (y = 0; y < size && read(x,y,z,yz) == 1; y++) {
                if (y == size - 1) {
                    write(x,rand_int(size),z,yz,0);
                }
            }
        }
    }
    for (y = 0; y < size; y++) {
        for (x = 0; x < size; x++) {
            for (z = 0; z < size && read(x,y,z,xz) == 1; z++) {
                if (z == size - 1) {
                    write(x,y,rand_int(size),xz,0);
                }
            }
        }
        for (z = 0; z < size; z++) {
            for (x = 0; x < size && read(x,y,z,xz) == 1; x++) {
                if (x == size - 1) {
                    write(rand_int(size),y,z,xz,0);
                }
            }
        }
    }
    for (z = 0; z < size; z++) {
        for (y = 0; y < size; y++) {
            for (x = 0; x < size && read(x,y,z,xy) == 1; x++) {
                if (x == size - 1) {
                    write(rand_int(size),y,z,xy,0);
                }
            }
        }
        for (x = 0; x < size; x++) {
            for (y = 0; y < size && read(x,y,z,xy) == 1; y++) {
                if (y == size - 1) {
                    write(x,rand_int(size),z,xy,0);
                }
            }
        }
    }
}

Jeg håber virkelig at der er en der kan hjælpe...

Bruger #4996 @ 05.02.06 23:33

196

Jeg har ikke kikket hele koden igennem, men et par kommentarer.

write funktionen kan så vidt jeg kan se kun sætte bits ikke resette, er det med vilje?
I stedet for at bruge pow var det nok mere optimalt at bruge <<

read funktionen kan returnere 8 eller 128, det er måske ikke nogen god idé, da den står til at returnere en bool?

Bruger #4414 @ 06.02.06 14:02

113

Jeg har ikke kikket hele koden igennem, men et par kommentarer.

write funktionen kan så vidt jeg kan se kun sætte bits ikke resette, er det med vilje?
I stedet for at bruge pow var det nok mere optimalt at bruge <<

read funktionen kan returnere 8 eller 128, det er måske ikke nogen god idé, da den står til at returnere en bool?

Write() burde fungerer efter hensigten. Kan ikke lige huske hvordan det fungerer med b?mask:0, men har fungeret før.

Boolen i read er lavet helt efter hensigten da den returnerer 0 hvis der ingen værdi er og ellers 1, jeg skal jo bare vide om bit'en er aktiv eller ej.

Bruger #2695 @ 06.02.06 15:33

1.963

1: Det er ikke muligt.

Well...og så igen.
Lav et langt char array og fortolk det som et array af 4 bit størrelser:

Kode

char data[5];//Indeholder 10 4-bit størrelser

struct Cell {
    bool xy;
    bool xz;
    bool yz;
    bool ac;
};

void getCell(struct Cell * cell, int num) {
    int value = data[idx / 2];
    if (value % 2 == 0) {
        value >>= 4;
    }
    cell->xy = ((value & 1) != 0);
    cell->xz = ((value & 2) != 0);
    cell->yz = ((value & 4) != 0);
    cell->ac = ((value & 8) != 0);
}

Bruger #2695 @ 06.02.06 15:38

1.963

Mht. generering af labyrinten så har jeg lavet labyrinter i 1000000 x 1000000 celle størrelsen med minimum spanning tree algoritmer.
Start med et grid hvor alle celler har alle vægge og start i en tilfældig celle. Hvis der er en ubesøgt nabo (celle med alle vægge intakte) så bryd væggen ned mellem den nuværende celle og naboen. Læg derefter den nuværende celle på stakken og flyt til naboen.
Hvis den nuværende celle ikke har ubesøgte naboer så gå tilbage til forrige celle (pop fra stakken).
Sådan fortsættes til alle celler har været besøgt.

Bruger #4414 @ 06.02.06 16:40

113

Mht. generering af labyrinten så har jeg lavet labyrinter i 1000000 x 1000000 celle størrelsen med minimum spanning tree algoritmer.
Start med et grid hvor alle celler har alle vægge og start i en tilfældig celle. Hvis der er en ubesøgt nabo (celle med alle vægge intakte) så bryd væggen ned mellem den nuværende celle og naboen. Læg derefter den nuværende celle på stakken og flyt til naboen.
Hvis den nuværende celle ikke har ubesøgte naboer så gå tilbage til forrige celle (pop fra stakken).
Sådan fortsættes til alle celler har været besøgt.

Det lyder slet ikke som nogen dum idé og hvis oven i købet randomizer rækkefølgen hvori man ønsker at undersøge de omkringliggende celler, kan man også undgå at der bliver et fast system i gridet.

Du taler om "stakken" jeg kan sagtens finde på en måde hvorpå tingende vil fungere, men jeg kunne godt tænke mig at vide om du mener noget bestemt med udtrykket?

Bruger #4414 @ 06.02.06 18:53

113

Så har jeg løst problemet med write funktionen, men jeg mener stadig at det kan gøres nemmere.

Kode

void write(int x, int y, int z, int m, bool b) {
    if (z % 2 == 0) {
        if ((GRID[x][y][z/2] >> m) % 2 == 0 && b == 1) {
            GRID[x][y][z/2] += 1 << m;
        }
        else if ((GRID[x][y][z/2] >> m) % 2 != 0 && b == 0) {
            GRID[x][y][z/2] -= 1 << m;
        }
    }
    else {
        if ((GRID[x][y][((z+1)/2)-1] >> (m+4)) % 2 == 0 && b == 1) {
            GRID[x][y][((z+1)/2)-1] += 1 << (m+4);
        }
        else if ((GRID[x][y][((z+1)/2)-1] >> (m+4)) % 2 != 0 && b == 0) {
            GRID[x][y][((z+1)/2)-1] -= 1 << (m+4);
        }
    }
}

Bruger #4996 @ 06.02.06 19:55

196

Dette bør virke:

Kode

void Write(int x, int y, int z, int m, bool b)
{
   if(z & 1)
      m += 4;
   if(b)
      Grid[x][y][z/2] |= 1 << m;
   else
      Grid[x][y][z/2] &= ~(1 << m);
}

Bruger #4414 @ 06.02.06 21:23

113

Dette bør virke:

Kode

void Write(int x, int y, int z, int m, bool b)
{
   if(z & 1)
      m += 4;
   if(b)
      Grid[x][y][z/2] |= 1 << m;
   else
      Grid[x][y][z/2] &= ~(1 << m);
}

Ja det er da noget mere simpelt, vil straks prøve om det virker... takker.

Bruger #4414 @ 06.02.06 22:49

113

Dette bør virke:

Ja det er da noget mere simpelt, vil straks prøve om det virker... takker.

Jo tak, det virker fint ;-)
således ser read og write ud nu:
write():

Kode

void write(short x,short y,short z,short m,bool b) {
    if (z & 1) m += 4;
    if (b) GRID[x][y][z/2] |= 1 << m;
    else GRID[x][y][z/2] &= ~(1 << m);
}

read():

Kode

bool read(short x,short y,short z,short m) {
    if (z & 1) m += 4;
    return GRID[x][y][z/2] >> m & 1;
}

Det er noget kortere og simplere. ;-)

Tilbage er nu at lave en funktion der bruger Robert Larsens idé til at klargøre Gridet.
Lave en funktion der undervejs kan ændre på tilfældige celler uden at det ødelægger strukturen.
Lave en pathfinder til at teste om det virker efter hensigten.
putte det hele i classes, headers og alt det jeg ikke har forstand på.
lave et grafisk interface.
Få en eller flere virtuelle laboratorie mus til at rende rundt i labyrinten.
Kunstig inteligens O_o
Multiplayer spil ala pacman ;-)
Jeg har mange idéer ;-)

Nuvel, tak for alt hjælpen.
Jeg vil naturligvis forsætte med at følge denne tråd, men jeg tror at jeg har styr på det værste nu. Der dukker jo nok flere ting op undervejs, så jeg vender jo nok tilbage med flere spørgsmål, det er dog ikke usandsynligt at jeg opretter en ny.

Jeg vil som sagt fortsat følge denne tråd, så hvis der er nogen der har idéer, gode råd, spørgsmål eller bare vil have en sluder for en slader skal de være velkomne. ;-)

Der er o også lige 100 point der skal deles ud, noget siger mig at der ikke er så meget rift om dem, men hvis nogen skulle være intereseret går pointene nu til bedste idé/forslag/kode bidrag (fx. pathfinder el.lign)

Tak for idag.

<< < 1 2 3 4 5 > >>

3d labyrint

Karma barometer (30 dage)

Modtaget

Givet

Favorit hos
Forum tråde
Artikler