stevy Temat założony przez niniejszego użytkownika |
Wyszukiwanie drogi na mapie 2D » 2014-04-12 20:36:44 Witam, chciałbym Was prosić o pomoc w odnalezieniu, lub poradach w napisaniu kodu na inteligentnego przeciwnika w okienku;) mówiąc inteligentnego mam na myśli twór potrafiący omijać przeszkody, podczas szukania najkrótszej drogi do celu. Jakieś pomysły? Od razu mówię, że szukałem, żeby nie było burzy.
|
|
colorgreen19 |
» 2014-04-12 20:39:03 powiedz najpierw w jakiej grze. 3d, 2d od gory, czy 2d od boku(zwykla platformowka) ? co innego jest w 3d gdzie musisz omijac obiekty, co innego w 2d gdzie mozesz wykorzystawac np. mape kafelkowa (jesli chodzi o samo szukanie drogi) |
|
stevy Temat założony przez niniejszego użytkownika |
» 2014-04-12 20:43:46 Chodzi o 2d od góry. Podkreślam jednak że nie chcę kodu, ale wskazówki konieczne do napisania go. |
|
f651144 |
» 2014-04-12 21:44:06 Jeżeli to takie 2d z kafelkami (coś jak szachownica), to jet to proste szukanie drogi w grafie. |
|
stevy Temat założony przez niniejszego użytkownika |
» 2014-04-12 22:14:20 mógłbyś bardziej rozwinąć swoją myśl? |
|
ison |
» 2014-04-12 22:24:25 |
|
stevy Temat założony przez niniejszego użytkownika |
» 2014-04-13 00:21:49 dzięki wielkie, będę miał nad czym siedzieć |
|
stevy Temat założony przez niniejszego użytkownika |
» 2014-06-15 16:06:20 Pomyślałem, że wyślę kod jeśli ktoś jeszcze będzie go potrzebować. edit: nie ma to co prawda znaczenia, ale zamieniłem jakoś wszystkie 0 na "puste" więc proszę nie chejtować #include<stdio.h>
#include<stdlib.h>
#include<time.h>
#include<Windows.h>
#include<conio.h>
#define rozmy 20
#define rozmx 60
enum POLA { puste, sciana, gracz, wyjscie };
struct POZYCJE {
int wspx;
int wspy;
};
int gra[ rozmy ][ rozmx ];
int mysl[ rozmy ][ rozmx ];
int bylem[ rozmy ][ rozmx ];
POZYCJE pion;
POZYCJE cel;
bool koniec_szukania;
bool wygrana;
int ilosc_ruchow;
static HANDLE uch = GetStdHandle( STD_OUTPUT_HANDLE );
void wypelnienie( void );
void rysowanie( void );
bool myslenie( int x, int y );
void ruch( void );
int naj_wart( int x, int y );
bool droga( void );
void koloruj_obszar_zasiegu_mysli( void );
int main()
{
COORD pos;
SMALL_RECT rozmiar_konsoli = { 0, 0, 70, 26 };
COORD rozmiar_bufora;
rozmiar_bufora.X = 71;
rozmiar_bufora.Y = 27;
SetConsoleWindowInfo( uch, TRUE, & rozmiar_konsoli );
SetConsoleScreenBufferSize( uch, rozmiar_bufora );
bool do_wyjscia = false;
int i, j;
int pozX, pozY;
bool czy_droga_istnieje;
srand( time( NULL ) );
for(;; ) {
wypelnienie();
rysowanie();
pozX = pion.wspx;
pozY = pion.wspy;
czy_droga_istnieje = myslenie( pozX, pozY );
pos.X = 0;
pos.Y = 0;
SetConsoleCursorPosition( uch, pos );
for( i = puste; i < rozmy; i++ )
for( j = puste; j < rozmx; j++ )
if( bylem[ i ][ j ] > 0 && gra[ i ][ j ] == puste ) {
pos.X = j;
pos.Y = i;
SetConsoleCursorPosition( uch, pos );
printf( "*" ); }
if( czy_droga_istnieje == true )
for(;; )
{
ruch();
if( wygrana == true )
break;
}
else {
koloruj_obszar_zasiegu_mysli();
pos.Y = rozmy;
pos.X = 0;
SetConsoleCursorPosition( uch, pos );
printf( "droga nie istnieje..." );
_getch(); }
}
return 0;
}
void wypelnienie()
{
int i, j, ilosc_przeszkod = puste, X, Y;
wygrana = false;
ilosc_ruchow = 0;
for( i = puste; i < rozmy; i++ )
for( j = puste; j < rozmx; j++ ) {
gra[ i ][ j ] = puste;
mysl[ i ][ j ] = puste;
bylem[ i ][ j ] = puste; }
for( i = puste; i < rozmy; i++ )
for( j = puste; j < rozmx; j++ )
if( i == puste || j == puste || j == rozmx - 1 || i == rozmy - 1 ) {
gra[ i ][ j ] = sciana;
mysl[ i ][ j ] =- 1; }
while( ilosc_przeszkod < rozmy * rozmx / 4 ) {
X = 1 + rand() %( rozmx - 2 );
Y = 1 + rand() %( rozmy - 2 );
if( gra[ Y ][ X ] == puste ) {
gra[ Y ][ X ] = sciana;
mysl[ Y ][ X ] =- 1;
ilosc_przeszkod++; }
}
pion.wspx = 1 + rand() %( rozmx - 2 );
pion.wspy = 1 + rand() %( rozmy - 2 );
gra[ pion.wspy ][ pion.wspx ] = gracz;
for(;; ) {
cel.wspx = 1 + rand() %( rozmx - 2 );
cel.wspy = 1 + rand() %( rozmy - 2 );
if( cel.wspx != pion.wspx && cel.wspy != pion.wspy ) {
gra[ cel.wspy ][ cel.wspx ] = wyjscie;
break; }
}
mysl[ cel.wspy ][ cel.wspx ] =( rozmx - 1 ) *( rozmy - 1 );
mysl[ pion.wspy ][ pion.wspx ] =-( rozmx - 1 ) *( rozmy - 1 ) / 10;
}
void rysowanie()
{
COORD pos;
pos.X = 0;
pos.Y = 0;
SetConsoleCursorPosition( uch, pos );
int i, j;
for( i = puste; i < rozmy; i++ )
for( j = puste; j < rozmx; j++ ) {
if( gra[ i ][ j ] == puste )
printf( " " );
if( gra[ i ][ j ] == sciana )
printf( "%c", 176 );
if( gra[ i ][ j ] == gracz )
printf( "%c", 4 );
if( gra[ i ][ j ] == wyjscie )
printf( "%c", 219 );
if( j + 1 == rozmx )
printf( "\n" );
}
printf( "RUCHY: %d \n", ilosc_ruchow );
printf( "*-oznaczona jest optymalna droga, znaleziona przez program. Jesli nie\n" );
printf( "bedzie drogi, program zatrzyma sie i pokaze kolorami, ze droga\n" );
printf( "nie istnieje (czerwony-pola w zasiegu ruchu pionka, niebieski-poza\n" );
printf( "zasiegiem). Nastepnie program czeka na klikniecie klawisza. Jezeli \n" );
printf( "znajdzie droge, to sam ja przejdzie idac trasa zgodna z gwiazdkami." );
}
bool myslenie( int x, int y )
{
int i, j, k = 0;
int sX, sY;
bool czy_droga_istnieje;
if( gra[ y - 1 ][ x ] == puste )
mysl[ y - 1 ][ x ] = 1;
if( gra[ y + 1 ][ x ] == puste )
mysl[ y + 1 ][ x ] = 1;
if( gra[ y ][ x - 1 ] == puste )
mysl[ y ][ x - 1 ] = 1;
if( gra[ y ][ x + 1 ] == puste )
mysl[ y ][ x + 1 ] = 1;
for( k = 0; k <( rozmx - 1 ) *( rozmy - 1 ) / 4; k++ )
{
for( i = 1; i < rozmy - 1; i++ ) {
for( j = 1; j < rozmx - 1; j++ )
{
if( mysl[ i ][ j ] == puste )
{
sX = j;
sY = i;
mysl[ i ][ j ] = naj_wart( sX, sY );
}
if( koniec_szukania == true )
break;
}
if( koniec_szukania == true )
break;
}
if( koniec_szukania == true )
break;
}
czy_droga_istnieje = droga();
if( czy_droga_istnieje == true )
return true;
else
return false;
}
int naj_wart( int x, int y )
{
int i, j;
int najmniejsza = 0;
if( mysl[ y ][ x - 1 ] > 0 && mysl[ y ][ x - 1 ] <( rozmx - 1 ) *( rozmy - 1 ) / 2 ) {
najmniejsza = mysl[ y ][ x - 1 ];
if( mysl[ y ][ x + 1 ] < najmniejsza && mysl[ y ][ x + 1 ] > 0 )
najmniejsza = mysl[ y ][ x + 1 ];
if( mysl[ y - 1 ][ x ] < najmniejsza && mysl[ y - 1 ][ x ] > 0 )
najmniejsza = mysl[ y - 1 ][ x ];
if( mysl[ y + 1 ][ x ] < najmniejsza && mysl[ y + 1 ][ x ] > 0 )
najmniejsza = mysl[ y + 1 ][ x ];
}
else if( mysl[ y ][ x + 1 ] > 0 && mysl[ y ][ x + 1 ] <( rozmx - 1 ) *( rozmy - 1 ) / 2 ) {
najmniejsza = mysl[ y ][ x + 1 ];
if( mysl[ y ][ x - 1 ] < najmniejsza && mysl[ y ][ x - 1 ] > 0 )
najmniejsza = mysl[ y ][ x - 1 ];
if( mysl[ y - 1 ][ x ] < najmniejsza && mysl[ y - 1 ][ x ] > 0 )
najmniejsza = mysl[ y - 1 ][ x ];
if( mysl[ y + 1 ][ x ] < najmniejsza && mysl[ y + 1 ][ x ] > 0 )
najmniejsza = mysl[ y + 1 ][ x ];
}
else if( mysl[ y - 1 ][ x ] > 0 && mysl[ y - 1 ][ x ] <( rozmx - 1 ) *( rozmy - 1 ) / 2 ) {
najmniejsza = mysl[ y - 1 ][ x ];
if( mysl[ y ][ x - 1 ] < najmniejsza && mysl[ y ][ x - 1 ] > 0 )
najmniejsza = mysl[ y ][ x - 1 ];
if( mysl[ y ][ x + 1 ] < najmniejsza && mysl[ y ][ x + 1 ] > 0 )
najmniejsza = mysl[ y ][ x + 1 ];
if( mysl[ y + 1 ][ x ] < najmniejsza && mysl[ y + 1 ][ x ] > 0 )
najmniejsza = mysl[ y + 1 ][ x ];
}
else if( mysl[ y + 1 ][ x ] > 0 && mysl[ y + 1 ][ x ] <( rozmx - 1 ) *( rozmy - 1 ) / 2 ) {
najmniejsza = mysl[ y + 1 ][ x ];
if( mysl[ y ][ x - 1 ] < najmniejsza && mysl[ y ][ x - 1 ] > 0 )
najmniejsza = mysl[ y ][ x - 1 ];
if( mysl[ y ][ x + 1 ] < najmniejsza && mysl[ y ][ x + 1 ] > 0 )
najmniejsza = mysl[ y ][ x + 1 ];
if( mysl[ y - 1 ][ x ] < najmniejsza && mysl[ y - 1 ][ x ] > 0 )
najmniejsza = mysl[ y - 1 ][ x ];
}
if(( y == cel.wspy - 1 && x == cel.wspx && mysl[ y ][ x ] != 0 ) ||( y == cel.wspy + 1 && x == cel.wspx && mysl[ y ][ x ] != 0 ) ||
( y == cel.wspy && x == cel.wspx - 1 && mysl[ y ][ x ] != 0 ) ||( y == cel.wspy && x == cel.wspx + 1 && mysl[ y ][ x ] != 0 ) )
koniec_szukania = true;
if( najmniejsza > 0 )
return najmniejsza + 1;
else
return 0;
}
bool droga()
{
int i, j, k = 0;
int x = cel.wspx;
int y = cel.wspy;
int X = x, Y = y;
int najmniejsza = 0;
bylem[ y ][ x ] =( rozmx - 1 ) *( rozmy - 1 );
while( k <( rozmx - 1 ) *( rozmx - 1 ) / 5 )
{
k++;
if( mysl[ y - 1 ][ x ] > 0 && bylem[ y - 1 ][ x ] == 0 ) {
najmniejsza = mysl[ y - 1 ][ x ];
X = x;
Y = y;
Y = y - 1;
if( mysl[ y ][ x - 1 ] <=( najmniejsza - 1 ) && mysl[ y ][ x - 1 ] > 0 && bylem[ y ][ x - 1 ] == 0 ) {
najmniejsza = mysl[ y ][ x - 1 ];
X = x;
Y = y;
X = x - 1; }
if( mysl[ y ][ x + 1 ] <=( najmniejsza - 1 ) && mysl[ y ][ x + 1 ] > 0 && bylem[ y ][ x + 1 ] == 0 ) {
najmniejsza = mysl[ y ][ x + 1 ];
X = x;
Y = y;
X = x + 1; }
if( mysl[ y + 1 ][ x ] <=( najmniejsza - 1 ) && mysl[ y + 1 ][ x ] > 0 && bylem[ y + 1 ][ x ] == 0 ) {
najmniejsza = mysl[ y + 1 ][ x ];
Y = y;
X = x;
Y = y + 1; }
x = X;
y = Y;
bylem[ y ][ x ] = najmniejsza;
}
else if( mysl[ y + 1 ][ x ] > 0 && bylem[ y + 1 ][ x ] == 0 ) {
najmniejsza = mysl[ y + 1 ][ x ];
X = x;
Y = y;
Y = y + 1;
if( mysl[ y ][ x - 1 ] <=( najmniejsza - 1 ) && mysl[ y ][ x - 1 ] > 0 && bylem[ y ][ x - 1 ] == 0 ) {
najmniejsza = mysl[ y ][ x - 1 ];
X = x;
Y = y;
X = x - 1; }
if( mysl[ y ][ x + 1 ] <=( najmniejsza - 1 ) && mysl[ y ][ x + 1 ] > 0 && bylem[ y ][ x + 1 ] == 0 ) {
najmniejsza = mysl[ y ][ x + 1 ];
Y = y;
X = x;
X = x + 1; }
if( mysl[ y - 1 ][ x ] <=( najmniejsza - 1 ) && mysl[ y - 1 ][ x ] > 0 && bylem[ y - 1 ][ x ] == 0 ) {
najmniejsza = mysl[ y - 1 ][ x ];
Y = y;
X = x;
Y = y - 1; }
x = X;
y = Y;
bylem[ y ][ x ] = najmniejsza;
}
else if( mysl[ y ][ x + 1 ] > 0 && bylem[ y ][ x + 1 ] == 0 ) {
najmniejsza = mysl[ y ][ x + 1 ];
X = x;
Y = y;
X = x + 1;
if( mysl[ y ][ x - 1 ] <=( najmniejsza - 1 ) && mysl[ y ][ x - 1 ] > 0 && bylem[ y ][ x - 1 ] == 0 ) {
najmniejsza = mysl[ y ][ x - 1 ];
X = x;
Y = y;
X = x - 1; }
if( mysl[ y - 1 ][ x ] <=( najmniejsza - 1 ) && mysl[ y - 1 ][ x ] > 0 && bylem[ y - 1 ][ x ] == 0 ) {
najmniejsza = mysl[ y - 1 ][ x ];
Y = y;
X = x;
Y = y - 1; }
if( mysl[ y + 1 ][ x ] <=( najmniejsza - 1 ) && mysl[ y + 1 ][ x ] > 0 && bylem[ y + 1 ][ x ] == 0 ) {
najmniejsza = mysl[ y + 1 ][ x ];
Y = y;
X = x;
Y = y + 1; }
x = X;
y = Y;
bylem[ y ][ x ] = najmniejsza;
}
else if( mysl[ y ][ x - 1 ] > 0 && bylem[ y ][ x - 1 ] == 0 ) {
najmniejsza = mysl[ y ][ x - 1 ];
X = x;
Y = y;
X = x - 1;
if( mysl[ y ][ x + 1 ] <=( najmniejsza - 1 ) && mysl[ y ][ x + 1 ] > 0 && bylem[ y ][ x + 1 ] == 0 ) {
najmniejsza = mysl[ y ][ x + 1 ];
X = x;
Y = y;
X = x + 1; }
if( mysl[ y - 1 ][ x ] <=( najmniejsza - 1 ) && mysl[ y - 1 ][ x ] > 0 && bylem[ y - 1 ][ x ] == 0 ) {
najmniejsza = mysl[ y - 1 ][ x ];
Y = y;
X = x;
Y = y - 1; }
if( mysl[ y + 1 ][ x ] <=( najmniejsza - 1 ) && mysl[ y + 1 ][ x ] > 0 && bylem[ y + 1 ][ x ] == 0 ) {
najmniejsza = mysl[ y + 1 ][ x ];
Y = y;
X = x;
Y = y - 1; }
x = X;
y = Y;
bylem[ y ][ x ] = najmniejsza;
}
else
return false;
if( najmniejsza == 1 )
break;
}
if( najmniejsza == 1 )
return true;
else
return false;
}
void ruch()
{
COORD pos;
if( gra[ cel.wspy ][ cel.wspx ] == gracz )
wygrana = true;
if( bylem[ pion.wspy ][ pion.wspx + 1 ] > bylem[ pion.wspy ][ pion.wspx ] )
{
pos.X = pion.wspx;
pos.Y = pion.wspy;
SetConsoleCursorPosition( uch, pos );
printf( " " );
gra[ pion.wspy ][ pion.wspx ] = puste;
pion.wspx++;
gra[ pion.wspy ][ pion.wspx ] = gracz;
pos.X = pion.wspx;
pos.Y = pion.wspy;
SetConsoleCursorPosition( uch, pos );
printf( "%c", 4 );
ilosc_ruchow++;
}
else if( bylem[ pion.wspy ][ pion.wspx - 1 ] > bylem[ pion.wspy ][ pion.wspx ] )
{
pos.X = pion.wspx;
pos.Y = pion.wspy;
SetConsoleCursorPosition( uch, pos );
printf( " " );
gra[ pion.wspy ][ pion.wspx ] = puste;
pion.wspx--;
gra[ pion.wspy ][ pion.wspx ] = gracz;
pos.X = pion.wspx;
pos.Y = pion.wspy;
SetConsoleCursorPosition( uch, pos );
printf( "%c", 4 );
ilosc_ruchow++;
}
else if( bylem[ pion.wspy - 1 ][ pion.wspx ] > bylem[ pion.wspy ][ pion.wspx ] )
{
pos.X = pion.wspx;
pos.Y = pion.wspy;
SetConsoleCursorPosition( uch, pos );
printf( " " );
gra[ pion.wspy ][ pion.wspx ] = puste;
pion.wspy--;
gra[ pion.wspy ][ pion.wspx ] = gracz;
pos.X = pion.wspx;
pos.Y = pion.wspy;
SetConsoleCursorPosition( uch, pos );
printf( "%c", 4 );
ilosc_ruchow++;
}
else if( bylem[ pion.wspy + 1 ][ pion.wspx ] > bylem[ pion.wspy ][ pion.wspx ] )
{
pos.X = pion.wspx;
pos.Y = pion.wspy;
SetConsoleCursorPosition( uch, pos );
printf( " " );
gra[ pion.wspy ][ pion.wspx ] = puste;
pion.wspy++;
gra[ pion.wspy ][ pion.wspx ] = gracz;
pos.X = pion.wspx;
pos.Y = pion.wspy;
SetConsoleCursorPosition( uch, pos );
printf( "%c", 4 );
ilosc_ruchow++;
}
Sleep( 50 );
pos.Y = rozmy;
pos.X = 0;
SetConsoleCursorPosition( uch, pos );
printf( "RUCHY: %d", ilosc_ruchow );
}
void koloruj_obszar_zasiegu_mysli()
{
COORD pos;
int i, j;
for( i = 1; i < rozmy - 1; i++ )
for( j = 1; j < rozmx - 1; j++ ) {
if( gra[ i ][ j ] == wyjscie ) {
pos.X = j;
pos.Y = i;
SetConsoleCursorPosition( uch, pos );
SetConsoleTextAttribute( uch, BACKGROUND_BLUE | FOREGROUND_RED | FOREGROUND_GREEN | FOREGROUND_BLUE );
printf( "%c", 219 ); }
else if( mysl[ i ][ j ] == 0 ) {
pos.X = j;
pos.Y = i;
SetConsoleCursorPosition( uch, pos );
SetConsoleTextAttribute( uch, BACKGROUND_BLUE );
printf( " " ); }
else if( mysl[ i ][ j ] > 0 ) {
pos.X = j;
pos.Y = i;
SetConsoleCursorPosition( uch, pos );
SetConsoleTextAttribute( uch, BACKGROUND_RED );
printf( " " ); }
else if( gra[ i ][ j ] == gracz ) {
pos.X = j;
pos.Y = i;
SetConsoleCursorPosition( uch, pos );
SetConsoleTextAttribute( uch, BACKGROUND_RED | FOREGROUND_RED | FOREGROUND_GREEN | FOREGROUND_BLUE );
printf( "%c", 4 ); }
}
SetConsoleTextAttribute( uch, FOREGROUND_RED | FOREGROUND_GREEN | FOREGROUND_BLUE );
}
|
|
| « 1 » 2 |