C ++中的简单探路者
Simple Pathfinder in c++
我正在开发一个简单的探路者。我有一个基于网格的小地图。
“1”是一层
“0”是一堵墙
'G'是目标之一
特点:
- 没有对角线移动
- 路径成本总是等于 1
- 可以有很多目标
我的完整代码:
#include <vector>
#include <iostream>
#include <map>
#include <algorithm>
using namespace std;
const int MapWidth = 10, MapHeight = 10;
// Y pos X pos
char Map[MapHeight][MapWidth] = {
{ '1', '1', 'G', '1', '1', '1', '1', '1', '1', '1' },
{ '1', '1', '1', '1', '1', '1', '1', '1', '1', '1' },
{ '1', '1', '0', '1', '1', '1', '1', '1', '0', 'G' },
{ '1', '1', '0', '0', '1', '1', '1', '1', '0', '1' },
{ '1', '1', '1', '1', '1', '1', '1', '1', '1', '1' },
{ '1', '1', '1', '1', '1', '1', '1', '0', '0', '1' },
{ '1', '1', '1', '1', '1', '1', '1', '0', '1', '1' },
{ '1', '1', '1', '0', '0', '1', '1', '0', '1', '1' },
{ '1', '1', '0', '0', '0', '1', '1', '0', '0', '0' },
{ '1', '1', '1', 'G', '0', '1', '1', '1', '1', '1' }
};
struct Pos
{
int X;
int Y;
};
bool PosIsUsed(vector <Pos> Position, int Y, int X)
{
for (vector <Pos>::iterator it = Position.begin(); it != Position.end(); ++it)
{
if (it->X == X && it->Y == Y)
{
return true;
}
}
return false;
}
void SearchNext(int Y, int X, vector <Pos> Position)
{
Pos NewStep = { X, Y };
Position.push_back(NewStep);
//North
if (Y >= 1 && !PosIsUsed(Position, Y - 1, X))
{
vector <Pos> NewPosition = Position;
switch (Map[Y - 1][X])
{
case '1':
SearchNext(Y - 1, X, NewPosition);
break;
case 'G':
printf("Found!\n");
break;
}
}
//East
if (X + 1 < MapWidth && !PosIsUsed(Position, Y, X + 1))
{
vector <Pos> NewPosition = Position;
switch (Map[Y][X + 1])
{
case '1':
SearchNext(Y, X + 1, NewPosition);
break;
case 'G':
printf("Found!\n");
break;
}
}
//Soth
if (Y + 1 < MapHeight && !PosIsUsed(Position, Y + 1, X))
{
vector <Pos> NewPosition = Position;
switch (Map[Y + 1][X])
{
case '1':
SearchNext(Y + 1, X, NewPosition);
break;
case 'G':
printf("Found!\n");
break;
}
}
//West
if (X >= 1 && !PosIsUsed(Position, Y, X - 1))
{
vector <Pos> NewPosition = Position;
switch (Map[Y][X - 1])
{
case '1':
SearchNext(Y, X - 1, NewPosition);
break;
case 'G':
printf("Found!\n");
break;
}
}
}
int main()
{
vector <Pos> Pos;
SearchNext(9, 9, Pos); //We start here (Pos [9][9])
printf("End\n");
system("PAUSE");
return 0;
}
有问题。它永远不会结束。你能告诉我,我做错了什么吗?
编辑:
我在 SearchNext 函数中切换了 X 和 Y 参数的顺序。此更改后,程序显示无穷大 "Found!".
工作代码(不是我的):
#include <vector>
#include <iostream>
#include <map>
#include <algorithm>
#include <string>
using namespace std;
const char FLOOR = '1' ;
const char WALL = '0' ;
const char GOAL = 'G' ;
const int MapWidth = 10, MapHeight = 10;
// Y pos X pos
char Map[MapHeight][MapWidth] = {
{ '1', '1', 'G', '1', '1', '1', '1', '1', '1', '1' },
{ '1', '1', '1', '1', '1', '1', '1', '1', '1', '1' },
{ '1', '1', '0', '1', '1', '1', '1', '1', '0', 'G' },
{ '1', '1', '0', '0', '1', '1', '1', '1', '0', '1' },
{ '1', '1', '1', '1', '1', '1', '1', '1', '1', '1' },
{ '1', '1', '1', '1', '1', '1', '1', '0', '0', '1' },
{ '1', '1', '1', '1', '1', '1', '1', '0', '1', '1' },
{ '1', '1', '1', '0', '0', '1', '1', '0', '1', '1' },
{ '1', '1', '0', '0', '0', '1', '1', '0', '0', '0' },
{ '1', '1', '1', 'G', '0', '1', '1', '1', '1', '1' }
};
struct Pos
{
short x,y;
Pos operator + ( Pos p ) const { return Pos(x+p.x,y+p.y); }
bool operator < ( Pos p ) const { return ( y==p.y ) ? (x<p.x) : (y<p.y) ; }
bool operator != ( Pos p ) const { return ( y!=p.y ) || (x!=p.x) ; }
Pos(short x=0,short y=0) : x(x), y(y) {}
};
bool valid(Pos p) { return p.x>=0 && p.x<MapWidth && p.y>=0 && p.y<MapHeight; }
enum Dir { d_beg, d_up=d_beg, d_rg, d_dn, d_lf, d_end };
Pos deltas[d_end] = { {0,-1}, {+1,0}, {0,+1}, {-1,0} };
Dir& operator ++ ( Dir& d ) { d = (Dir) ( 1+(int)d ) ; return d; }
Dir other(Dir d)
{
switch(d)
{
case d_up: return d_dn;
case d_rg: return d_lf;
case d_dn: return d_up;
case d_lf: return d_rg;
default: return d_end;
}
}
struct SearchMapItem
{
bool traversble;
bool goal;
bool visited;
int cost_here;
Dir came_from;
bool paths[d_end];
};
map<Pos,SearchMapItem> search_map;
typedef map<Pos,SearchMapItem>::iterator SMII;
void MakeMap()
{
search_map.clear();
Pos p;
for(p.y=0;p.y<MapHeight;++p.y) for(p.x=0;p.x<MapWidth;++p.x)
{
SearchMapItem smi;
smi.visited = false;
smi.cost_here = -1;
smi.came_from = d_end;
if( Map[p.y][p.x] == WALL )
{
smi.traversble = false;
}
else if( Map[p.y][p.x] == GOAL )
{
smi.traversble = true;
smi.goal = true;
}
else if( Map[p.y][p.x] == FLOOR )
{
smi.traversble = true;
smi.goal = false;
for( Dir d = d_beg; d != d_end; ++d )
{
Pos p2 = p + deltas[d];
smi.paths[d] = valid(p2) && (Map[p2.y][p2.x] != WALL) ;
}
}
search_map[p] = smi;
}
}
void FindGoalFrom( Pos start )
{
vector<SMII> found;
{
SMII smii = search_map.find(start);
if(smii==search_map.end()) { cout << "starting outside map\n"; return; }
if(smii->second.goal) { cout << "already at target\n"; return; }
if(!smii->second.traversble) { cout << "starting in a wall\n"; return; }
smii->second.visited = true;
smii->second.cost_here = 0;
found.push_back(smii);
}
int cost_so_far = 0;
bool did_find = false;
while(!did_find)
{
vector<SMII> candidates;
for( SMII smii : found )
{
for( Dir d = d_beg; d != d_end; ++d )
{
if( ! smii->second.paths[d] ) continue;
Pos p = smii->first + deltas[d];
if(!valid(p)) continue;
SMII cand = search_map.find(p);
if(cand==search_map.end()) continue;
if(cand->second.visited) continue;
cand->second.came_from=d;
candidates.push_back(cand);
}
}
++cost_so_far;
if( candidates.empty() ) break;
for( SMII smii : candidates )
{
smii->second.visited = true;
smii->second.cost_here = cost_so_far;
found.push_back(smii);
if( smii->second.goal ) { did_find = true; break; }
}
}
if( ! did_find ) { cout << "no goal reachable\n"; return; }
SMII pos = found.back();
vector<Dir> path;
while( pos->first != start )
{
Dir d = pos->second.came_from;
path.push_back(d);
Pos p = pos->first + deltas[ other(d) ];
pos = search_map.find(p);
}
for( auto itr = path.rbegin(); itr != path.rend(); ++itr )
{
const char* dir_names[] = { "Up", "Right", "Down", "Left" } ;
cout << "Walk " << dir_names[*itr] << endl;
}
cout << "Then you are at goal in total " << to_string(cost_so_far) << " steps" << endl;
}
int main()
{
MakeMap();
FindGoalFrom( Pos(5,9) );
cout << "\ndone\n";
}
您正在对 SearchNext 的递归调用中切换 X 和 Y 的顺序。
一般来说,您可以在调试器中或通过添加跟踪输出来分析这些类型的问题。您会在第二次调用 SearchNext 时发现问题:"huh, why is X equal to 8 while I subtracting 1 from Y?".
假设平均有 2.5 个方向可供选择,那么
您的算法将需要 2.5n 个步骤才能完成,其中 n 是
正方形的数量。那将是一个令人难以置信的大数字,甚至
对于相当小的 n。您需要查看 Djikstra's algorithm
假设您最终想找到到
的最便宜路线
一个目标,而不仅仅是任何路线。
或者写二维地图,标明可以割草的地方,用直线作为方向,然后根据方向隐藏离那条直线较远的地方。这样你就可以有地方去。
我正在开发一个简单的探路者。我有一个基于网格的小地图。
“1”是一层
“0”是一堵墙
'G'是目标之一
特点:
- 没有对角线移动
- 路径成本总是等于 1
- 可以有很多目标
我的完整代码:
#include <vector>
#include <iostream>
#include <map>
#include <algorithm>
using namespace std;
const int MapWidth = 10, MapHeight = 10;
// Y pos X pos
char Map[MapHeight][MapWidth] = {
{ '1', '1', 'G', '1', '1', '1', '1', '1', '1', '1' },
{ '1', '1', '1', '1', '1', '1', '1', '1', '1', '1' },
{ '1', '1', '0', '1', '1', '1', '1', '1', '0', 'G' },
{ '1', '1', '0', '0', '1', '1', '1', '1', '0', '1' },
{ '1', '1', '1', '1', '1', '1', '1', '1', '1', '1' },
{ '1', '1', '1', '1', '1', '1', '1', '0', '0', '1' },
{ '1', '1', '1', '1', '1', '1', '1', '0', '1', '1' },
{ '1', '1', '1', '0', '0', '1', '1', '0', '1', '1' },
{ '1', '1', '0', '0', '0', '1', '1', '0', '0', '0' },
{ '1', '1', '1', 'G', '0', '1', '1', '1', '1', '1' }
};
struct Pos
{
int X;
int Y;
};
bool PosIsUsed(vector <Pos> Position, int Y, int X)
{
for (vector <Pos>::iterator it = Position.begin(); it != Position.end(); ++it)
{
if (it->X == X && it->Y == Y)
{
return true;
}
}
return false;
}
void SearchNext(int Y, int X, vector <Pos> Position)
{
Pos NewStep = { X, Y };
Position.push_back(NewStep);
//North
if (Y >= 1 && !PosIsUsed(Position, Y - 1, X))
{
vector <Pos> NewPosition = Position;
switch (Map[Y - 1][X])
{
case '1':
SearchNext(Y - 1, X, NewPosition);
break;
case 'G':
printf("Found!\n");
break;
}
}
//East
if (X + 1 < MapWidth && !PosIsUsed(Position, Y, X + 1))
{
vector <Pos> NewPosition = Position;
switch (Map[Y][X + 1])
{
case '1':
SearchNext(Y, X + 1, NewPosition);
break;
case 'G':
printf("Found!\n");
break;
}
}
//Soth
if (Y + 1 < MapHeight && !PosIsUsed(Position, Y + 1, X))
{
vector <Pos> NewPosition = Position;
switch (Map[Y + 1][X])
{
case '1':
SearchNext(Y + 1, X, NewPosition);
break;
case 'G':
printf("Found!\n");
break;
}
}
//West
if (X >= 1 && !PosIsUsed(Position, Y, X - 1))
{
vector <Pos> NewPosition = Position;
switch (Map[Y][X - 1])
{
case '1':
SearchNext(Y, X - 1, NewPosition);
break;
case 'G':
printf("Found!\n");
break;
}
}
}
int main()
{
vector <Pos> Pos;
SearchNext(9, 9, Pos); //We start here (Pos [9][9])
printf("End\n");
system("PAUSE");
return 0;
}
有问题。它永远不会结束。你能告诉我,我做错了什么吗?
编辑:
我在 SearchNext 函数中切换了 X 和 Y 参数的顺序。此更改后,程序显示无穷大 "Found!".
工作代码(不是我的):
#include <vector>
#include <iostream>
#include <map>
#include <algorithm>
#include <string>
using namespace std;
const char FLOOR = '1' ;
const char WALL = '0' ;
const char GOAL = 'G' ;
const int MapWidth = 10, MapHeight = 10;
// Y pos X pos
char Map[MapHeight][MapWidth] = {
{ '1', '1', 'G', '1', '1', '1', '1', '1', '1', '1' },
{ '1', '1', '1', '1', '1', '1', '1', '1', '1', '1' },
{ '1', '1', '0', '1', '1', '1', '1', '1', '0', 'G' },
{ '1', '1', '0', '0', '1', '1', '1', '1', '0', '1' },
{ '1', '1', '1', '1', '1', '1', '1', '1', '1', '1' },
{ '1', '1', '1', '1', '1', '1', '1', '0', '0', '1' },
{ '1', '1', '1', '1', '1', '1', '1', '0', '1', '1' },
{ '1', '1', '1', '0', '0', '1', '1', '0', '1', '1' },
{ '1', '1', '0', '0', '0', '1', '1', '0', '0', '0' },
{ '1', '1', '1', 'G', '0', '1', '1', '1', '1', '1' }
};
struct Pos
{
short x,y;
Pos operator + ( Pos p ) const { return Pos(x+p.x,y+p.y); }
bool operator < ( Pos p ) const { return ( y==p.y ) ? (x<p.x) : (y<p.y) ; }
bool operator != ( Pos p ) const { return ( y!=p.y ) || (x!=p.x) ; }
Pos(short x=0,short y=0) : x(x), y(y) {}
};
bool valid(Pos p) { return p.x>=0 && p.x<MapWidth && p.y>=0 && p.y<MapHeight; }
enum Dir { d_beg, d_up=d_beg, d_rg, d_dn, d_lf, d_end };
Pos deltas[d_end] = { {0,-1}, {+1,0}, {0,+1}, {-1,0} };
Dir& operator ++ ( Dir& d ) { d = (Dir) ( 1+(int)d ) ; return d; }
Dir other(Dir d)
{
switch(d)
{
case d_up: return d_dn;
case d_rg: return d_lf;
case d_dn: return d_up;
case d_lf: return d_rg;
default: return d_end;
}
}
struct SearchMapItem
{
bool traversble;
bool goal;
bool visited;
int cost_here;
Dir came_from;
bool paths[d_end];
};
map<Pos,SearchMapItem> search_map;
typedef map<Pos,SearchMapItem>::iterator SMII;
void MakeMap()
{
search_map.clear();
Pos p;
for(p.y=0;p.y<MapHeight;++p.y) for(p.x=0;p.x<MapWidth;++p.x)
{
SearchMapItem smi;
smi.visited = false;
smi.cost_here = -1;
smi.came_from = d_end;
if( Map[p.y][p.x] == WALL )
{
smi.traversble = false;
}
else if( Map[p.y][p.x] == GOAL )
{
smi.traversble = true;
smi.goal = true;
}
else if( Map[p.y][p.x] == FLOOR )
{
smi.traversble = true;
smi.goal = false;
for( Dir d = d_beg; d != d_end; ++d )
{
Pos p2 = p + deltas[d];
smi.paths[d] = valid(p2) && (Map[p2.y][p2.x] != WALL) ;
}
}
search_map[p] = smi;
}
}
void FindGoalFrom( Pos start )
{
vector<SMII> found;
{
SMII smii = search_map.find(start);
if(smii==search_map.end()) { cout << "starting outside map\n"; return; }
if(smii->second.goal) { cout << "already at target\n"; return; }
if(!smii->second.traversble) { cout << "starting in a wall\n"; return; }
smii->second.visited = true;
smii->second.cost_here = 0;
found.push_back(smii);
}
int cost_so_far = 0;
bool did_find = false;
while(!did_find)
{
vector<SMII> candidates;
for( SMII smii : found )
{
for( Dir d = d_beg; d != d_end; ++d )
{
if( ! smii->second.paths[d] ) continue;
Pos p = smii->first + deltas[d];
if(!valid(p)) continue;
SMII cand = search_map.find(p);
if(cand==search_map.end()) continue;
if(cand->second.visited) continue;
cand->second.came_from=d;
candidates.push_back(cand);
}
}
++cost_so_far;
if( candidates.empty() ) break;
for( SMII smii : candidates )
{
smii->second.visited = true;
smii->second.cost_here = cost_so_far;
found.push_back(smii);
if( smii->second.goal ) { did_find = true; break; }
}
}
if( ! did_find ) { cout << "no goal reachable\n"; return; }
SMII pos = found.back();
vector<Dir> path;
while( pos->first != start )
{
Dir d = pos->second.came_from;
path.push_back(d);
Pos p = pos->first + deltas[ other(d) ];
pos = search_map.find(p);
}
for( auto itr = path.rbegin(); itr != path.rend(); ++itr )
{
const char* dir_names[] = { "Up", "Right", "Down", "Left" } ;
cout << "Walk " << dir_names[*itr] << endl;
}
cout << "Then you are at goal in total " << to_string(cost_so_far) << " steps" << endl;
}
int main()
{
MakeMap();
FindGoalFrom( Pos(5,9) );
cout << "\ndone\n";
}
您正在对 SearchNext 的递归调用中切换 X 和 Y 的顺序。
一般来说,您可以在调试器中或通过添加跟踪输出来分析这些类型的问题。您会在第二次调用 SearchNext 时发现问题:"huh, why is X equal to 8 while I subtracting 1 from Y?".
假设平均有 2.5 个方向可供选择,那么
您的算法将需要 2.5n 个步骤才能完成,其中 n 是
正方形的数量。那将是一个令人难以置信的大数字,甚至
对于相当小的 n。您需要查看 Djikstra's algorithm
假设您最终想找到到
的最便宜路线
一个目标,而不仅仅是任何路线。
或者写二维地图,标明可以割草的地方,用直线作为方向,然后根据方向隐藏离那条直线较远的地方。这样你就可以有地方去。