| Xapac | Дата: Воскресенье, 08.02.2009, 15:11 | Сообщение # 1 |
|
Башка вар
Группа: Администраторы
Сообщений: 168
Статус: Offline
| Волновой алгоритм поиска путей
описание алгоритма
нажать тут
Дано 2-ч мерный массив (карта) состоящая из чисел
Code int MAP[10][10]=
{
0,1,0,0,0,0,0,0,0,0,
0,1,0,0,0,0,0,0,0,0,
0,0,0,1,0,0,0,0,0,0,
1,1,0,1,0,0,0,0,0,0,
0,0,0,1,0,0,0,0,0,0,
0,0,0,1,0,0,0,0,0,0,
0, 0,0,1,1,1,1,1,0,0,
0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,
0,0,0,0,0,0,0,0,0,0,
};
где 1 - это непроходимое(стена, или еще какое-нибуть зелье) 0 - тропа путника
Code
int x_b=0;
int y_b=0;
начальные координаты (в которых находится испытуемый)
Code
int to_x_b=4;
int to_y_b=5;
конечная точка пути.
времменная карта, в которой будем рисовать весы путей
Code void CreateMap(void);
Code void FindPath(int x,int y,int to_x,int to_y,int upper);
передаваемые параметры x,y начало пути, to_x,to_y конец пути, upper глубина вхождения
далее получаем из временной карты путь с помощью
Code void GetPathList(int x,int y,int to_x,int to_y,int upper); пример программы
Code #include <stdio.h> #include <conio.h> #include <iostream> #include <math.h> #include "wintypes.h" using namespace std; #include <vector> int MAP[10][10]= { 0,1,0,0,0,0,0,0,0,0, 0,1,0,0,0,0,0,0,0,0, 0,0,0,1,0,0,0,0,0,0, 1,1,0,1,0,0,0,0,0,0, 0,0,0,1,0,0,0,0,0,0, 0,0,0,1,0,0,0,0,0,0, 0, 0,0,1,1,1,1,1,0,0, 0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0, 0,0,0,0,0,0,0,0,0,0, }; int x_b=0; int y_b=0; int to_x_b=4; int to_y_b=5; bool findings=false; struct my_point { int x; int y; }; vector<my_point> PathList; int tempMAP[10][10]; void CreateMap(void); void DrawMap(void); void ClearMap(void); void DrawMap_temp(void); void FindPath(int x,int y,int to_x,int to_y,int upper); void GetPathList(int x,int y,int to_x,int to_y,int upper); void main() { CreateMap(); MAP[to_x_b][to_y_b]=9; DrawMap(); FindPath(x_b,y_b,to_x_b,to_y_b,1); ClearMap(); DrawMap_temp(); findings=false; GetPathList(to_x_b,to_y_b,0,0,tempMAP[to_x_b][to_y_b]); // while(!PathList.empty()) { // point P=PathList.front(); // PathList.pop(); // cout<<P.x<<" : "<<P.y<<endl; } } void GetPathList(int x,int y,int to_x,int to_y,int upper) { if(tempMAP[x][y]!=upper)return; if(findings)return; my_point p; p.x=x; p.y=y; cout<<p.x<<" : "<<p.y<<endl; if(x==to_x&&y==to_y) {findings=true;return;} //PathList.push_back(p); cout<<p.x<<" : "<<p.y<<endl; if(x>0)GetPathList(x-1,y,to_x,to_y,upper-1); if(y>0)GetPathList(x,y-1,to_x,to_y,upper-1); if(x>0&&y>0)GetPathList(x-1,y-1,to_x,to_y,upper-1); if(x<10)GetPathList(x+1,y,to_x,to_y,upper-1); if(y<10)GetPathList(x,y+1,to_x,to_y,upper-1); if(x<10&y<10)GetPathList(x+1,y+1,to_x,to_y,upper-1); }; void FindPath(int x,int y,int to_x,int to_y,int upper) { if(upper>20)return; if(tempMAP[x][y]<=upper&&tempMAP[x][y]>0)return; if(x==to_x&&y==to_y){tempMAP[x][y]=upper;return;} if(MAP[x][y]>0)return; tempMAP[x][y]=upper; if(x>0)FindPath(x-1,y,to_x,to_y,upper+1); if(y>0)FindPath(x,y-1,to_x,to_y,upper+1); if(x>0&&y>0)FindPath(x-1,y-1,to_x,to_y,upper+1); if(y<10)FindPath(x,y+1,to_x,to_y,upper+1); if(x<10)FindPath(x+1,y,to_x,to_y,upper+1); if(y<10&&x<10)FindPath(x+1,y+1,to_x,to_y,upper+1); }; void CreateMap(void) { for(int i=0;i<10;i++) for(int l=0;l<10;l++) tempMAP[i][l]=0; }; void DrawMap(void) { for(int i=0;i<10;i++) { for(int l=0;l<10;l++) cout<<MAP[i][l]<<" "; cout<<endl; } }; void DrawMap_temp(void) { cout<<endl; for(int i=0;i<10;i++) { for(int l=0;l<10;l++) cout<<tempMAP[i][l]<<" "; cout<<endl; } }; void ClearMap(void) { for(int i=0;i<10;i++) { for(int l=0;l<10;l++) if(tempMAP[i][l]>tempMAP[to_x_b][to_y_b])tempMAP[i][l]=0; } }; |
| |
| |
помошь проекту
