Szukanie drogi w labiryncie - algorytm
Ostatnio zmodyfikowano 2017-01-15 00:04
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: #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; }
|
|
michal11 |
» 2017-01-07 08:38:13 Algorytm A* |
|
mokrowski |
» 2017-01-07 09:21:37 |
|
Saran |
» 2017-01-15 00:04:25 Tak właściwie to concurrent dijkstra jest lepszy: https://www.youtube.com/watch?v=cSxnOm5aceA |
|
« 1 » |