Panel użytkownika
Nazwa użytkownika:
Hasło:
Nie masz jeszcze konta?

Szukanie drogi w labiryncie - algorytm

Ostatnio zmodyfikowano 2017-01-15 00:04
Autor Wiadomość
Przems
Temat założony przez niniejszego użytkownika
Szukanie drogi w labiryncie - algorytm
» 2017-01-07 00:24:18
Witam, dostałem projekt do zrobienia, polega on na tym że mapa jest wczytywania z pliku do tablicy dwuwymiarowej, i program musi znaleźć wyjście z labiryntu, znany jest start i stop. Napisałem już większość funkcji, nie wiem tylko jak się zabrać za napisanie algorytmu przeszukującego labirynt, coś tam próbowałem googlować, ale średnio mi to idzie. Dodam tylko że droga nie musi być optymalna, po prostu ma znaleźć wyjście z labiryntu i wypisać na koniec kierunki w jakich szedł po kolei. Np. DPLDPLLDDD (D-dol,P-prawo itp). Może ktoś poratować wskazówkami jak się za to zabrać? :) Wklejam jeszcze kod który do tej pory napisałem:


C/C++
#include <stdio.h>
#include <stdlib.h>
#define W 7
#define K 6
char plansza[ W ][ K ];

typedef struct {
    int i, j;
} wspol;
wspol start, end;

void szukam() {
    wspol * wsks = & start, * wske = & end;
    int i, j;
    for( i = 0; i < W; i++ ) {
        for( j = 0; j < K; j++ ) {
            if( plansza[ i ][ j ] == '$' ) {
                wsks->i = i;
                wsks->j = j;
            }
            if( plansza[ i ][ j ] == '@' ) {
                wske->i = i;
                wske->j = j;
            }
        }
    }
}


void droga() {
    wspol * wsks = & start, * wske = & end;
    int sw, sk, ew, ek;
    sw = wsks->i;
    sk = wsks->j;
    ew = wske->i;
    ek = wske->j;
    while( plansza[ sw ][ sk ] != plansza[ ew ][ ek ] ) {
        if( plansza[ sw ][ sk + 1 ] != '#' ) {
            ++sk;
            plansza[ sw ][ sk ] = 'X';
           
        }
        else if( plansza[ sw + 1 ][ sk ] != '#' ) {
            ++sw;
            plansza[ sw ][ sk ] = 'X';
        }
        else if( plansza[ sw ][ sk - 1 ] != '#' ) {
            --sk;
            plansza[ sw ][ sk ] = 'X';
        }
    }
}

void WczytajLab() {
    int i = 0, j = 0;
    char c;
    FILE * obraz;
    obraz = fopen( "obraz.txt", "r" );
    if( obraz ) {
        while( c != EOF ) {
            c = getc( obraz );
            if( c != '\n' ) {
                plansza[ i ][ j ] = c;
                j++;
            }
            else {
                i++;
                j = 0;
            }
        }
    }
    else {
        printf( "Blad otwarcia planszy" );
        return - 1;
    }
    fclose( obraz );
}

void PokazLab() {
    int i, j;
    for( i = 0; i < W; i++ ) {
        for( j = 0; j < K; j++ ) {
            printf( "%c ", plansza[ i ][ j ] );
        }
        printf( "\n" );
    }
}

int main()
{
    WczytajLab();
    PokazLab();
    szukam();
    droga();
    printf( "\n\n" );
    PokazLab();
    return 0;
}
P-156151
michal11
» 2017-01-07 08:38:13
Algorytm A*
P-156157
mokrowski
» 2017-01-07 09:21:37
P-156158
Saran
» 2017-01-15 00:04:25
Tak właściwie to concurrent dijkstra jest lepszy:
https://www.youtube.com/watch?v=cSxnOm5aceA
P-156450
« 1 »
  Strona 1 z 1