0.摘要
1.效果圖
其中正方形代表障礙物，實心菱形代表移動者（人），空心菱形代表目標位置（都是可以在代碼中修改的）
2.本例使用佇列(鏈表實作)，以廣度優先進行自動尋路，
1.實作代碼
1.佇列方法類
#pragma once #include <iostream> using namespace std; //佇列 //坐標結構體 struct Point { int x; int y; Point() { x = 0; y = 0; } Point(int in_x, int in_y) { x = in_x; y = in_y; } Point& operator=(const Point& right_p) { this->x = right_p.x; this->y = right_p.y; return *this; } }; //佇列結構體 struct coolQueue { int data; Point cool_p; coolQueue* next_p; coolQueue(int in_data) { data = in_data; next_p = NULL; } coolQueue(int in_x, int in_y, int in_data = https://www.cnblogs.com/coolight7/p/0) { cool_p.x = in_x; cool_p.y = in_y; data = in_data; next_p = NULL; } }; //佇列方法類，限制訪問方式 class queueClass { protected: coolQueue* Head_p = NULL; coolQueue* End_p = NULL; public: queueClass() {} void push(int data); //入隊 void push(int in_x, int in_y, int in_data = https://www.cnblogs.com/coolight7/p/0); bool pop(int& re_data); //出隊 bool pop(coolQueue& in_coolQueue); void reverse_order(); //翻轉 void clear() { for (int data; pop(data);); } ~queueClass() { clear(); } };coolQueue.h
#include "coolQueue.h" /*入隊函式 * 傳參： * in_data：入隊的資料 */ void queueClass::push(int in_data) { if (Head_p == NULL) //佇列為空 { Head_p = new coolQueue(in_data); End_p = Head_p; } else if(Head_p == End_p) //佇列只有一個元素 { End_p = new coolQueue(in_data); Head_p->next_p = End_p; } else { coolQueue* temp_p = new coolQueue(in_data); End_p->next_p = temp_p; End_p = temp_p; } } /*出隊 * 傳參： * re_data：接收出隊回傳值 * 回傳值： * 成功回傳true，佇列為慷訓傳false * * 把值寫入re_data中回傳 */ bool queueClass::pop(int& re_data) { if (Head_p == NULL) //佇列為空 return false; re_data = Head_p->data; coolQueue* temp_p = Head_p; if (Head_p == End_p) //佇列只有一個元素 { Head_p = NULL; End_p = NULL; } else Head_p = Head_p->next_p; delete temp_p; return true; } /*同鏈表采用以尾指標為頭的頭插法實作倒序 */ void queueClass::reverse_order() { if (Head_p == NULL || Head_p == End_p) return; coolQueue* p = Head_p, * temp_p; do { temp_p = p; p = p->next_p; temp_p->next_p = End_p->next_p; End_p->next_p = temp_p; } while (p != End_p); p = Head_p; Head_p = End_p; End_p = p; } //以下多載用于輔助自動尋路實作 //in_data = https://www.cnblogs.com/coolight7/p/0 void queueClass::push(int in_x, int in_y, int in_data) { if (Head_p == NULL) { Head_p = new coolQueue(in_x, in_y, in_data); End_p = Head_p; } else if (Head_p == End_p) { End_p = new coolQueue(in_x, in_y, in_data); Head_p->next_p = End_p; } else { coolQueue* temp_p = new coolQueue(in_x, in_y, in_data); End_p->next_p = temp_p; End_p = temp_p; } } bool queueClass::pop(coolQueue& in_coolQueue) { if (Head_p == NULL) return false; in_coolQueue.data = Head_p->data; //不直接使用復制是因為可能把Head_p的next_p也復制出去導致限制訪問權限失效 in_coolQueue.cool_p = Head_p->cool_p; coolQueue* temp_p = Head_p; if (Head_p == End_p) { Head_p = NULL; End_p = NULL; } else Head_p = Head_p->next_p; delete temp_p; return true; }coolQueue.cpp
2.地圖方法類
#pragma once #include "coolQueue.h" #include "windows.h" #include <cmath> using namespace std; #ifndef PI #define PI 3.14159265358979323846 #endif // !PI #ifndef Sleep_num #define Sleep_num 500 #endif // !列印輸出地圖時的暫停時間 #ifndef Map_size #define Map_size 10 #endif // !地圖大小 /*地圖操作類 * 保護繼承佇列，防止外部呼叫佇列的函式 */ class mapClass : protected queueClass { protected: int map[Map_size][Map_size]; //地圖 Point persion_p; //起點位置坐標 void new_map(); void reflash_map(); bool auto_find_way(Point& target_p); void auto_move(int in_x, int in_y); public: mapClass(const Point& in_p); bool auto_main(); void into_map(int in_data, int num = 1); bool into_map(int in_x, int in_y, int in_data); void show_map(); void clear_map(const Point& in_p); };mapClass.h
#include "mapClass.h" /*初始化地圖 * * 把map置零后設定邊界 */ void mapClass::new_map() { memset(map, 0, Map_size * Map_size);//清零 for (int num = Map_size; num--;) //設定邊緣障礙物 { map[num][0] = 1; map[0][num] = 1; map[num][Map_size - 1] = 1; map[Map_size - 1][num] = 1; } } /*重繪地圖 * * 由于在auto_find_way()中會修改地圖中的值作為方向標記 * 移動后會殘留一些標記，此函式將會把這些標記清理（即把標記置回0） */ void mapClass::reflash_map() { for (int x = Map_size - 1; --x;) for (int y = Map_size - 1; --y;) map[x][y] = map[x][y] % 1000; /*方向標記為1000，2000，3000 和 4000，故 %1000 即可保留其他東西并清理標記*/ } /*自動尋路 * * 傳參： * &target_p：傳出引數，找到路徑后寫入目標的坐標 * 回傳值： * 有路徑回傳true，沒有回傳false * * 基于佇列尋找到達目標的最優路徑，會在地圖上留下方向標記 * 如果找到，在其他函式可以 以目標位置開始，通過方向標記倒推回起點，即為路徑 */ bool mapClass::auto_find_way(Point& target_p) { coolQueue out_queue(0, 0, 0); for (int push_num = 1; push_num;) { push_num = 0; //如果push_num在while回圈后仍然為0，說明佇列空且無路可走了 while (this->pop(out_queue)) { for (int i = 1, temp_x, temp_y; i <= 4; ++i)//判斷它的旁邊4個位置 { //此處使用sin()是為了在不同i時(temp_x, temp_y)指向以out_queue為中心的不同方向 //效果同auto_move()中的switch()的使用 temp_x = out_queue.cool_p.x + int(sin(PI / 2 * (i - 2.0))); temp_y = out_queue.cool_p.y + int(sin(PI / 2 * (i - 3.0))); switch (map[temp_x][temp_y]) { case 0: //可走 { map[temp_x][temp_y] = i * 1000; //寫入方向標記 this->push(temp_x, temp_y, 0); //入隊 ++push_num; }break; case 10: //抵達目標位置 { map[temp_x][temp_y] += i * 1000; target_p.x = temp_x; //寫入目標位置 target_p.y = temp_y; this->clear(); //清空佇列 return true; }break; } } if (out_queue.data =https://www.cnblogs.com/coolight7/p/= -1) //每一輪佇列的最后一個的data標記為-1 break; //以起點位置往外一步為一輪 } if (this->End_p != NULL) this->End_p->data = https://www.cnblogs.com/coolight7/p/-1; } this->clear(); return false; } /*自動移動（遞回函式） * 傳參： * * 后序遞回：先呼叫遞回，再移動地點 * 因此此函式目的是一開始傳入目標位置， * 再以地圖上的方向標記倒推上一個位置， * 直到回到起點位置則開始移動，每次移動呼叫show()重繪地圖顯示 * 即可實作從起點到終點移動的效果 */ void mapClass::auto_move(int in_x, int in_y) { /*switch ()可替換為 * temp_x = in_x + int(sin(PI / 2 * (map[in_x][in_y] / 1000)); * temp_y = in_y + int(sin(PI / 2 * (map[in_x][in_y] / 1000 - 1.0)); */ int temp_x = in_x, temp_y = in_y; switch (map[in_x][in_y] / 1000) //決議地圖示記 { case 0:return; break; case 1:++temp_x; break; case 2:++temp_y; break; case 3:--temp_x; break; case 4:--temp_y; break; } /*由于函式是從終點位置遞回回起點的，所以上一個呼叫此函式的應該是更接近終點的 * 因此此函式接受的傳入值（in_x, in_y）是下一個移動點 * （temp_x,temp_y）為本次的移動點 */ auto_move(temp_x, temp_y); //遞回呼叫，讓起點移動到本位置（即temp_x, temp_y） map[temp_x][temp_y] = 0; //把現在的位置清零 map[in_x][in_y] = 100; //把下一個移動點置100，即可實作從現在的位置移動到下一個位置的效果 show_map(); //顯示列印 Sleep(Sleep_num); return; } /*建構式 * 傳參： * in_p：起點位置 */ mapClass::mapClass(const Point& in_p) { new_map(); persion_p = in_p; } /*自動尋路主導函式 */ bool mapClass::auto_main() { show_map(); //顯示地圖 Sleep(Sleep_num); this->clear(); //清空佇列 this->push(persion_p.x, persion_p.y, -1);//把起點入隊 Point target_p; //目標坐標 if (auto_find_way(target_p) == false) //呼叫自動尋路 { reflash_map(); return false; } auto_move(target_p.x, target_p.y); //移動 reflash_map(); //清理地圖殘留標記 persion_p = target_p; //重置起點位置，抵達終點后起點即為終點 return true; } /*對地圖寫入資料標記 * * 傳參： * in_data：寫入的資料值 * num： 次數 * * 在地圖的隨機空位置上寫入 num 次 in_data 標記 * * 存在bug： * 如果地圖坐標已滿，寫入次數不夠會陷入死回圈 * 可考慮加入回圈次數限制解決 */ void mapClass::into_map(int in_data, int num) { if (num <= 0) return; for (int i = 0, j = 0; num--;) { i = rand() % Map_size; j = rand() % Map_size; if (map[i][j] == 0) map[i][j] = in_data; else ++num; } } /*對地圖寫入資料標記 * * 傳參： * in_x,in_y：寫入的地圖位置 * in_data： 寫入的資料值 * * 回傳值： * 如果(in_x, in_y)位置為空則寫入成功回傳true，否則回傳false * * 在地圖的(in_x, in_y)位置寫入 in_data */ bool mapClass::into_map(int in_x, int in_y, int in_data) { if (map[in_x][in_y] == 0) { map[in_x][in_y] = in_data; return true; } return false; } /*列印顯示地圖 */ void mapClass::show_map() { system("cls"); //清空控制臺輸出 for (int i = 0; i < Map_size; ++i) { for (int j = 0; j < Map_size; ++j) switch (map[i][j] % 1000) { case 0: cout << " "; break;//空白位置 case 1: cout << "□"; break;//障礙物 case 10: cout << "◇"; break;//目標 case 100: cout << "◆"; break;//自己 default: cout << " "; break; } cout << endl; } } /*重置地圖 * 傳參： * in_p：起點位置 * * 清空地圖，僅保留 起點 和 邊界 標記 * 用于輔助回圈重繪障礙物尋路的實作 */ void mapClass::clear_map(const Point& in_p) { for (int x = Map_size - 1; --x;) //把地圖中的所有位置置零 for (int y = Map_size - 1; --y;) map[x][y] = 0; persion_p = in_p; //重新設定起點 map[in_p.x][in_p.y] = 100; }mapClass.cpp
3.main函式
#include <iostream> #include <time.h> #include <cmath> #include "mapClass.h" using namespace std; int main() { srand(int(time(0))); Point persion_p(1, 1), target_p(1, 1); mapClass test_map(persion_p); test_map.into_map(1, 1, 100); //寫入起點 test_map.into_map(1, 20); //寫入障礙物 while (1) { //重置障礙物位置, 取消下面兩句的注釋即可啟用 //test_map.clear_map(target_p); //清空地圖 //test_map.into_map(1, 20); //生成障礙物 do { target_p.x = rand() % (Map_size - 2) + 1; target_p.y = rand() % (Map_size - 2) + 1; } while (test_map.into_map(target_p.x, target_p.y, 10) == false); if (test_map.auto_main() == false) { cout << endl << "<< 走不了！" << endl; Sleep(1500); } } return 0; }main.cpp
2.思路
總體和資料結構的教科書上的大差不差：以起點為中心，每向外一步作為一輪回圈，回圈中把可走的位置入隊，下一輪回圈把上一輪入隊的位置出隊并再以這些位置為中心往外走一步，把可走位置入隊，一直這樣回圈，直到遇到終點位置或者佇列中為空（因為每一個方向都走不了則佇列回圈后為空），
（想象一下在沒有障礙物的地圖中，以起點為中心向外擴散）
在上述程序中，把可走位置入隊的同時留下方向標記（上一個位置走到此位置的方向），在回圈結束后從終點位置倒推即可找到一潭訓到起點的路徑，
此路徑為最優解（最優解可能不止一條），因為演算法中是從起點往外每一步進行一輪判斷，因此如果找到了終點，那么就是在最少的步數內找到了終點，此時即可結束回圈，此為最優解，如果不結束，繼續找下去可能可以找到用更多步數的路徑，
本例與書中的不同：
1.在找到路徑后利用system("cls")清屏重新輸出，來實作逐步走向終點的效果，
2.在一些細節的實作上使用不同的嘗試(例如 mapClass::auto_find_way()中使用sin()，直接使用地圖做方向標記等)
3.支持回圈多次尋路，支持重置障礙物位置
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/351900.html
標籤：C++
上一篇：添加華為套件時出現“Couldnotfindcom.huawei.hms:location:6.0.0.302”錯誤