自动寻路贪吃蛇C++源码

// A寻路算法贪吃蛇.cpp : 定义控制台应用程序的入口点。 // #include "stdafx.h" #include<time.h> #include<iostream> #include<conio.h> #include<list> #include<windows.h> using namespace std; #define L 23 //定义多少行 #define C 18 //定义多少列 #define K 100 //定义平移大小 struct snake { int x, y; snake *p; }; struct OPOINT //坐标结构 { int l; //行 int c; //列 }; struct APOINT //用于粗存每个节点的信息计算最短路径 { int l; int c; int G; int H; int F; APOINT* p; }; typedef list<OPOINT> OBS; //储存障碍点坐标 typedef list<APOINT*> KAIQI; //开启列表 typedef list<APOINT*> GUANBI; //关闭列表 class Astar { private: OPOINT start; //储存起点坐标 OPOINT endpoint; //储存终点坐标 OBS obs; KAIQI kaiqi; GUANBI guanbi; OBS::iterator oi; KAIQI::iterator ki; GUANBI::iterator gi; public: Astar() { memset(&start, 0, sizeof(OPOINT)); memset(&endpoint, 0, sizeof(OPOINT)); } ~Astar() { if (!kaiqi.empty()) { APOINT* p = nullptr; for (ki = kaiqi.begin(); ki != kaiqi.end(); ki++) { p = (*ki); if (p != NULL) { delete p; } } kaiqi.clear(); } if (!guanbi.empty()) { APOINT* q = nullptr; gi = guanbi.begin(); gi++; for (; gi != guanbi.end(); gi++) { q = (*gi); if (q != NULL) { delete q; } } guanbi.clear(); } obs.clear(); } public: void initstart(snake* p) //初始化起点 { start.l = p->y-1; start.c = p->x/2-1; } void initend(int x,int y) //初始化终点 { endpoint.l = y-1; endpoint.c = x/2-1; } void initobs(snake *p) //初始化障碍点 { OPOINT temp = { 0 }; while (p->p != NULL) { temp.l = p->y-1; temp.c = p->x/2-1; p = p->p; obs.push_back(temp); } } void weiinitobs(snake *p) //初始化不包含尾巴的障碍点 { OPOINT temp = { 0 }; while (p->p != NULL) { temp.l = p->y - 1; temp.c = p->x / 2 - 1; p = p->p; obs.push_back(temp); } //obs.pop_back(); } bool isedge(APOINT *ap) //判断节点是否超出边界 { if (ap->l >= L || ap->l < 0 || ap->c >= C || ap->c < 0) return true; return false; } bool isobs(APOINT *ap) //判断节点是否在障碍点上 { for (oi = obs.begin(); oi != obs.end(); oi++) { if (ap->l == oi->l&&ap->c == oi->c) return true; } return false; } bool isguanbi(APOINT *ap) //判断节点是否在关闭列表 { for (gi = guanbi.begin(); gi != guanbi.end(); gi++) { if (ap->l == (*gi)->l&&ap->c == (*gi)->c) return true; } return false; } int iskaiqi(APOINT *ap) //判断节点是否在开启列表，如果在就返回节点的G值用于判断最优路径 { for (ki = kaiqi.begin(); ki != kaiqi.end(); ki++) { if (ap->l == (*ki)->l&&ap->c == (*ki)->c) return ap->G; } return -1; } void deletekaiqi(APOINT* ap) //从开启列表删除相应的点 { for (ki = kaiqi.begin(); ki != kaiqi.end();) { if (ap->l == (*ki)->l&&ap->c == (*ki)->c) { ki = kaiqi.erase(ki); break; } else { ki++; } } } void reckonH(APOINT *ap) //计算节点的H值 { int a = abs(ap->l - endpoint.l)*K; int b = abs(ap->c - endpoint.c)*K; ap->H = a + b; } void oppoint(APOINT* temp, APOINT* ap) //对一个点周围的能到达的点进行操作 { int yn = 0; if (isedge(temp) || isobs(temp) || isguanbi(temp)) { delete temp; } else { yn = iskaiqi(temp); if (yn == -1) { temp->G = ap->G + K; reckonH(temp); temp->F = temp->G + temp->H; temp->p = ap; kaiqi.push_back(temp); } else { if (temp->G < yn) { for (ki = kaiqi.begin(); ki != kaiqi.end(); ki++) { if (temp->l == (*ki)->l&&temp->c == (*ki)->c) { (*ki)->p = ap; } } } } } } void findpoint(APOINT *ap) //找出ap周围四个点将符合条件的放入开启列表，并把ap从开启列表删除放入关闭列表 { int yn = 0; APOINT* temp = new APOINT; temp->l=ap->l; temp->c=ap->c+1; temp->F = ap->F; temp->G = ap->G; temp->H = ap->H; temp->p = ap->p; oppoint(temp, ap); APOINT* temp1 = new APOINT; temp1->l = ap->l; temp1->c=ap->c-1; temp1->F = ap->F; temp1->G = ap->G; temp1->H = ap->H; temp1->p = ap->p; oppoint(temp1, ap); APOINT* temp2 = new APOINT; temp2->l=ap->l+1; temp2->c = ap->c; temp2->F = ap->F; temp2->G = ap->G; temp2->H = ap->H; temp2->p = ap->p; oppoint(temp2, ap); APOINT* temp3 = new APOINT; temp3->l=ap->l-1; temp3->c = ap->c; temp3->F = ap->F; temp3->G = ap->G; temp3->H = ap->H; temp3->p = ap->p; oppoint(temp3, ap); deletekaiqi(ap); guanbi.push_back(ap); } int maxH(snake *sna) { APOINT temp[4] = { 0 }; int maxh = 0; int fang = 0; bool y = false; for (int i = 0; i < 4; i++) { temp[i].l = sna->y-1; temp[i].c = sna->x/2-1; temp[i].H = 0; } temp[0].c--; temp[1].c++; temp[2].l--; temp[3].l++; for (int i = 0; i < 4; i++) { if (!isobs(&(temp[i])) && !isedge(&(temp[i]))) { reckonH(&(temp[i])); y = true; } } if (y = false) { return 0; } for (int i = 1; i < 4; i++) { if (temp[i].H > temp[i - 1].H) { maxh = i; } } switch (maxh) { case 0: fang = -1; break; case 1: fang = 1; break; case 2: fang = 2; break; case 3: fang = 4; break; } return fang; } APOINT* minF() //从开启列表中找出F值最小的节点 { APOINT *temp = nullptr; if (kaiqi.empty()) { return temp; } ki = kaiqi.begin(); temp = *ki; for (; ki != kaiqi.end(); ki++) { if (temp->F > (*ki)->F) { temp = *ki; } } return temp; } int minpath() //判断是否存最短路径，若果存在，-1表示左，1表示右，2表示上，4表示下 { APOINT as = { 0 }; APOINT ae = { 0 }; APOINT* temp = nullptr; int fang = 0; as.l = start.l; as.c = start.c; as.p = nullptr; ae.l = endpoint.l; ae.c = endpoint.c; ae.p = nullptr; if (as.l == ae.l && ((as.c - ae.c) == -1 || (as.c - ae.c) == 1)) { fang = ae.c - as.c; return fang; } if (as.c == ae.c && ((as.l - ae.l) == -1 || (as.l - ae.l) == 1)) { fang = ae.l - as.l + 3; return fang; } kaiqi.push_back(&as); findpoint(&as); do { temp = minF(); if (temp == nullptr) break; findpoint(temp); if (kaiqi.empty()) break; } while (iskaiqi(&ae) == -1); if ((iskaiqi(&ae) != -1)) //如果终点在开启列表中则存在最短路径 { APOINT* p = nullptr; APOINT* q = nullptr; for (ki = kaiqi.begin(); ki != kaiqi.end(); ki++) //从开启列表中找出最短路径 { if (ae.l == (*ki)->l&&ae.c == (*ki)->c) { p = (*ki)->p; break; } } if (p == &as) { if (q->l == as.l) { fang = q->c - as.c; } else { fang = q->l - as.l + 3; } return fang; } while (p != &as) //由p的父节点即p->p指向的节点索引到起点，从而输出最短路径 { q = p; p = p->p; } if (q->l == as.l) { fang = q->c - as.c; } else { fang = q->l - as.l + 3; } return fang; } else return 0; } void clear() //删除动态申请的内存以及清空list容器 { if (!kaiqi.empty()) { APOINT* p = nullptr; for (ki = kaiqi.begin(); ki != kaiqi.end(); ki++) { p = (*ki)