A星算法(VC版源码)
源码不是我写的,如有侵权,请联系我,更改版权
使用方法:
对于空地左键单击后会产生障碍,对障碍左键单击会消除障碍,对于起点,两次左键盘单击会消除起点,如果不存在起点,单击右键会产生起点,如果存在起点不存在终点,单击右键会产生终点,如果既存在起点又存在终点,单击右键会消除终点,点击开始寻路回画出路径
效果图:
C++源码:
#include ".\astart.h"
#include "List.cpp"
#include
Astart::Astart(int a[37][64],int w,int l,int s,int e)
{for(int i=0; i=0 && (start+WIDTH)%WIDTH >= 0 && (start+WIDTH)%WIDTH < WIDTH && start/WIDTH != LENGTH-1){//此点不是障碍物if( map[(start+WIDTH)/WIDTH][(start+WIDTH)%WIDTH]!=1 ){//修改该节点的各个值rect[start+WIDTH].pre = &rect[start];rect[start+WIDTH].h_value = get_h_value(start+WIDTH);rect[start+WIDTH].g_value = get_g_value(start+WIDTH);//插入到开放节点open_list.Insert(open_list.Length(),start+WIDTH);}}//出发点上边的节点,此点必须在地图内,出发点上边还有路(不能是地图边界)if((start-WIDTH)/WIDTH < LENGTH && (start-WIDTH)/WIDTH >=0 && (start-WIDTH)%WIDTH >= 0 && (start-WIDTH)%WIDTH < WIDTH && (start/WIDTH) != 0){//此点不是障碍物if( map[(start-WIDTH)/WIDTH][(start-WIDTH)%WIDTH]!=1){//修改该节点的各个值rect[start-WIDTH].pre = &rect[start];rect[start-WIDTH].h_value = get_h_value(start-WIDTH);rect[start-WIDTH].g_value = get_g_value(start-WIDTH);//插入到开放节点open_list.Insert(open_list.Length(),start-WIDTH);}}//出发点右边的节点,此点必须在地图内,出发点右边还有路(不能是地图边界)if((start+1)/WIDTH < LENGTH && (start+1)/WIDTH >=0 && (start+1)%WIDTH >= 0 && (start+1)%WIDTH < WIDTH && start!= start/WIDTH * WIDTH + WIDTH-1){//此点不是障碍物if( map[(start+1)/WIDTH][(start+1)%WIDTH]!=1){//修改该节点的各个值rect[start+1].pre = &rect[start];rect[start+1].h_value = get_h_value(start+1);rect[start+1].g_value = get_g_value(start+1);//插入到开放节点open_list.Insert(open_list.Length(),start+1);}}//出发点左边的节点,此点必须在地图内,出发点左边还有路(不能是地图边界)if((start-1)/WIDTH < LENGTH && (start-1)/WIDTH >=0 && (start-1)%WIDTH >= 0 && (start-1)%WIDTH < WIDTH && start%WIDTH!=0){//此点不是障碍物if( map[(start-1)/WIDTH][(start-1)%WIDTH]!=1){//修改该节点的各个值rect[start-1].pre = &rect[start];rect[start-1].h_value = get_h_value(start-1);rect[start-1].g_value = get_g_value(start-1);//插入到开放节点open_list.Insert(open_list.Length(),start-1);}}//起始节点加入到关闭节点close_list.Insert(close_list.Length(),start);}////循环遍历所有在开放列表的所有节点int i = 0; //最小评估值在开放列表中的标号int rectMinEstimateValue = -1; //最小评估值int stepRectID = 0; //下一步选择的节点for(int z=1; z<=open_list.Length(); z++){int rectID; //节点代号int rectEstimateValue; //节点的评估值open_list.Find(z, rectID); //获得开放列表中的节点代号rectEstimateValue = rect[rectID].h_value + rect[rectID].g_value;if(rectMinEstimateValue == -1)//第一个节点{rectMinEstimateValue = rectEstimateValue;}if(rectEstimateValue <= rectMinEstimateValue)//获得更小节点{i = z;rectMinEstimateValue = rectEstimateValue;stepRectID = rectID;}}//没有找到节点if(i==0) return false;//从开放列表删除该节点,并插入到关闭列表里面int temp;open_list.Delete(i, temp);close_list.Insert(close_list.Length(),stepRectID);//最小评估值节点下边的节点,此点必须在地图内,该节点下边还有路(不能是地图边界)if((stepRectID+WIDTH)/WIDTH < LENGTH && (stepRectID+WIDTH)/WIDTH >=0 && (stepRectID+WIDTH)%WIDTH >= 0 && (stepRectID+WIDTH)%WIDTH < WIDTH && (stepRectID/WIDTH) != LENGTH-1){//该节点是目标节点if(stepRectID+WIDTH == end){rect[stepRectID+WIDTH].pre = &rect[stepRectID];return true;}//该节点不是障碍物if( map[(stepRectID+WIDTH)/WIDTH][(stepRectID+WIDTH)%WIDTH]!=1 ){//该节点不在关闭列表里面if(close_list.Search(stepRectID+WIDTH) == 0){//该节点不在开放节点里面,就加入到开放节点里if(open_list.Search(stepRectID+WIDTH) == 0){//修改该节点的值rect[stepRectID+WIDTH].pre = &rect[stepRectID];rect[stepRectID+WIDTH].h_value = get_h_value(stepRectID+WIDTH);rect[stepRectID+WIDTH].g_value = get_g_value(stepRectID+WIDTH);//加入到开放节点open_list.Insert(open_list.Length(),stepRectID+WIDTH);}else{//如果该节点已存在开放列表里面,并且,通过刚刚一路走过来的路要比以前的路更近,则更新该节点的值if(rect[stepRectID].g_value + 10 < rect[stepRectID+WIDTH].g_value){//设置该节点的父节点rect[stepRectID+WIDTH].pre = &rect[stepRectID];//刷新实际到这里的值rect[stepRectID+WIDTH].g_value = get_g_value(stepRectID+WIDTH);}}}}}//最小评估值节点上边的节点,此点必须在地图内,该节点上边还有路(不能是地图边界)if((stepRectID-WIDTH)/WIDTH < LENGTH && (stepRectID-WIDTH)/WIDTH >=0 && (stepRectID-WIDTH)%WIDTH >= 0 && (stepRectID-WIDTH)%WIDTH < WIDTH && (stepRectID/WIDTH) != 0){//该节点是目标节点if(stepRectID-WIDTH == end){rect[stepRectID-WIDTH].pre = &rect[stepRectID];return true;}//该节点不是障碍物if( map[(stepRectID-WIDTH)/WIDTH][(stepRectID-WIDTH)%WIDTH]!=1){//该节点不在关闭列表里面if(close_list.Search(stepRectID-WIDTH) == 0){//该节点不在开放节点里面,就加入到开放节点里if(open_list.Search(stepRectID-WIDTH) == 0){//修改该节点的值rect[stepRectID-WIDTH].pre = &rect[stepRectID];rect[stepRectID-WIDTH].h_value = get_h_value(stepRectID-WIDTH);rect[stepRectID-WIDTH].g_value = get_g_value(stepRectID-WIDTH);//加入到开放节点open_list.Insert(open_list.Length(),stepRectID-WIDTH);}else{//如果该节点已存在开放列表里面,并且,通过刚刚一路走过来的路要比以前的路更近,则更新该节点的值if(rect[stepRectID].g_value + 10 < rect[stepRectID-WIDTH].g_value){//设置该节点的父节点rect[stepRectID-WIDTH].pre = &rect[stepRectID];//刷新实际到这里的值rect[stepRectID-WIDTH].g_value = get_g_value(stepRectID-WIDTH);}}}}}//最小评估值节点右边的节点,此点必须在地图内,该节点右边还有路(不能是地图边界)if((stepRectID+1)/WIDTH < LENGTH && (stepRectID+1)/WIDTH >=0 && (stepRectID+1)%WIDTH >= 0 && (stepRectID+1)%WIDTH < WIDTH && stepRectID!= stepRectID/WIDTH * WIDTH + WIDTH-1){//该节点是目标节点if(stepRectID+1 == end){rect[stepRectID+1].pre = &rect[stepRectID];return true;}//该节点不是障碍物if( map[(stepRectID+1)/WIDTH][(stepRectID+1)%WIDTH]!=1){//该节点不在关闭列表里面if(close_list.Search(stepRectID+1) == 0){//该节点不在开放节点里面,就加入到开放节点里if(open_list.Search(stepRectID+1) == 0){//修改该节点的值rect[stepRectID+1].pre = &rect[stepRectID];rect[stepRectID+1].h_value = get_h_value(stepRectID+1);rect[stepRectID+1].g_value = get_g_value(stepRectID+1);//加入到开放节点open_list.Insert(open_list.Length(),stepRectID+1);}else{//如果该节点已存在开放列表里面,并且,通过刚刚一路走过来的路要比以前的路更近,则更新该节点的值if(rect[stepRectID].g_value + 10 < rect[stepRectID+1].g_value){//设置该节点的父节点rect[stepRectID+1].pre = &rect[stepRectID];//刷新实际到这里的值rect[stepRectID+1].g_value = get_g_value(stepRectID+1);}}}}}//最小评估值节点左边的节点,此点必须在地图内,该节点左边还有路(不能是地图边界)if((stepRectID-1)/WIDTH < LENGTH && (stepRectID-1)/WIDTH >=0 && (stepRectID-1)%WIDTH >= 0 && (stepRectID-1)%WIDTH < WIDTH && stepRectID%WIDTH!=0){//该节点是目标节点if(stepRectID-1 == end){rect[stepRectID-1].pre = &rect[stepRectID];return true;}//该节点不是障碍物if( map[(stepRectID-1)/WIDTH][(stepRectID-1)%WIDTH]!=1){//该节点不在关闭列表里面if(close_list.Search(stepRectID-1) == 0){//该节点不在开放节点里面,就加入到开放节点里if(open_list.Search(stepRectID-1) == 0){//修改该节点的值rect[stepRectID-1].pre = &rect[stepRectID];rect[stepRectID-1].h_value = get_h_value(stepRectID-1);rect[stepRectID-1].g_value = get_g_value(stepRectID-1);//加入到开放节点open_list.Insert(open_list.Length(),stepRectID-1);}else{//如果该节点已存在开放列表里面,并且,通过刚刚一路走过来的路要比以前的路更近,则更新该节点的值if(rect[stepRectID].g_value + 10 < rect[stepRectID-1].g_value){//设置该节点的父节点rect[stepRectID-1].pre = &rect[stepRectID];//刷新实际到这里的值rect[stepRectID-1].g_value = get_g_value(stepRectID-1);}}}}}//进行递归return FindFastWay();
}//距离目标的评估值
int Astart::get_h_value(int i)
{return ((abs(end/WIDTH - i/WIDTH) + abs(end%WIDTH - i%WIDTH)) * 10);
}//距离出发源的实际值
int Astart::get_g_value(int i)
{return (rect[i].pre->g_value + 10);
}//获取路线结果
void Astart::GetResult()
{Rect *p = &rect[end];while(p != NULL){value_list.Insert(value_list.Length(),*p);p = p->pre;}
}
#include "List.h"
#pragma once
class Rect
{
public:int map_x;int map_y;int h_value;int g_value;Rect *pre;
};class Astart
{
public:Astart(int a[37][64],int w,int l,int s,int e);~Astart(void);bool Find();int get_h_value(int i);int get_g_value(int i);void GetResult();int map[37][64];Rect *rect;List value_list;
private:int WIDTH;int LENGTH;int start;int end;List open_list;List close_list;
};
#include "list.h"
template List::~List()
{length = 0;delete pHead;pHead = NULL;
}
template List::List()
{length = 0;pHead = NULL;
}
template void List::Insert(int k, const Type & intnum)
{if(k==0){if(length == 0){pHead = new Node;pHead->contents = intnum;length++;}else{Node *p= new Node;p->contents = intnum;p->next=pHead;pHead=p;length++;}}else if(k==length){Node *temp = pHead;for (int i=0;inext;}Node *newNode = new Node;newNode->contents = intnum;newNode->next = NULL;temp->next = newNode;length++;}else{Node *temp = pHead;for (int i=0;inext;}Node *newNode = new Node;newNode->contents = intnum;newNode->next = temp->next;temp->next = newNode;length++;}
}template void List::ShowListNode()
{if(length == 0){cout<<"空表";}else{ Node *temp = pHead;for(int i=0;icontents<next;}}}
}template void List::Delete(int k, Type & intnum)
{Node *temp = pHead;if(k==1 && k==length){delete pHead;pHead = NULL;}else if(k==1){pHead = pHead->next;delete temp;}else if(k==length){for(int i=0; inext;}delete temp->next;temp->next = NULL;}else{for (int i=0; inext;}intnum = temp->contents;for(int i=k; icontents = temp->next->contents;if(i != length-1){temp = temp->next;}else{delete temp->next;temp->next = NULL;break;}}}length--;
}
template bool List::Find(int k, Type & intnum) const
{if(k > length)return false;else{Node *temp = pHead ;for (int i=0; inext;}intnum = temp->contents;return true;}
}
template int List::Search(const Type & intnum) const
{Node *temp = pHead;for (int i=0; icontents == intnum){return i+1;}if(i != length-1)temp = temp->next;}return 0;
}
template void List::Modify(int k,const Type &intnum)
{Node *temp = pHead ;for (int i=0; inext;}temp->contents = intnum;
}
#pragma once
#include "list.h"
#include
using namespace std;
template class List;
template class Node
{Type contents;Node * next;friend List;
};
template class List
{
public:List();~List();bool IsEmpty() const {return (pHead==NULL) ? true : false;}//判断链表是否为空int Length() const {return length;} //返回链表中的元素总数bool Find(int k, Type & intnum) const; //寻找链表中的第k个元素,并将其传送至intnumint Search(const Type & intnum) const; //寻找intnum,如果发现intnum,则返回intnum的位置,如果intnum不在链表中,则返回0void Delete(int k, Type & intnum); //把第k个元素取至intnum,然后从链表中删除第k个元素void Insert(int k, const Type &intnum); //在第k个元素之后插入intnumvoid Modify(int k,const Type &intum);//将第k个元素的值修改为intnumvoid ShowListNode(); //显示输出链表的所有数据
private:Node *pHead;int length;
};
// tt3.cpp : 定义应用程序的入口点。
//#include "stdafx.h"
#include "tt3.h"
#include
#include
#include "Astart.h"
#include "List.h"
#include "List.cpp"
using namespace std;#define MAX_LOADSTRING 100// 全局变量:
HINSTANCE hInst; // 当前实例
TCHAR szTitle[MAX_LOADSTRING]; // 标题栏文本
TCHAR szWindowClass[MAX_LOADSTRING]; // 主窗口类名// 此代码模块中包含的函数的前向声明:
ATOM MyRegisterClass(HINSTANCE hInstance);
BOOL InitInstance(HINSTANCE, int);
LRESULT CALLBACK WndProc(HWND, UINT, WPARAM, LPARAM);
INT_PTR CALLBACK About(HWND, UINT, WPARAM, LPARAM);///
HDC hdc; //设备描述
HWND hWnd; //窗口句柄
HPEN pen,bluepen,greenpen,redpen; //画笔
HBRUSH bluebrush,greenbrush,redbrush; //画刷
int map[37][64]; //地图数组
bool start = false,over = false; //开始结束是否被标记
int begin = 0,end = 0; //开始结束位置#define KEYDOWN(vk_code) ((GetAsyncKeyState(vk_code) & 0x8000) ? 1 : 0)
///
//读取上次地图
void ReadMap()
{ifstream in("try.map");for(int i=0;i<37;i++){for(int j=0;j<64;j++){in>>map[i][j];}}in.close();
}//刷新
void Update()
{SelectObject(hdc,pen);for(int i=0;i<=37*20;i+=20){MoveToEx(hdc,0,i,NULL);LineTo(hdc,1280,i);}for(int i=0;i<=1280;i+=20){if(i==1280){MoveToEx(hdc,i-1,0,NULL);LineTo(hdc,i-1,740);}else{MoveToEx(hdc,i,0,NULL);LineTo(hdc,i,740);}}for(int i=0;i<37;i++){for(int j=0;j<64;j++){int x = j*20;int y = i*20;if(map[i][j] == 1){SelectObject(hdc,bluepen);SelectObject(hdc,bluebrush);if(x == 63*20){Rectangle(hdc,x+1,y+1,x+19,y+20);}else{Rectangle(hdc,x+1,y+1,x+20,y+20);}}else if(map[i][j] == 2){SelectObject(hdc,greenpen);SelectObject(hdc,greenbrush);if(x == 63*20){Rectangle(hdc,x+1,y+1,x+19,y+20);}else{Rectangle(hdc,x+1,y+1,x+20,y+20);}start = true;begin = i*64 + j;}else if(map[i][j] == 3){SelectObject(hdc,redpen);SelectObject(hdc,redbrush);if(x == 63*20){Rectangle(hdc,x+1,y+1,x+19,y+20);}else{Rectangle(hdc,x+1,y+1,x+20,y+20);}over = true;end = i*64 + j;}}}
}int APIENTRY _tWinMain(HINSTANCE hInstance,HINSTANCE hPrevInstance,LPTSTR lpCmdLine,int nCmdShow)
{UNREFERENCED_PARAMETER(hPrevInstance);UNREFERENCED_PARAMETER(lpCmdLine);// TODO: 在此放置代码。MSG msg;HACCEL hAccelTable;// 初始化全局字符串LoadString(hInstance, IDS_APP_TITLE, szTitle, MAX_LOADSTRING);LoadString(hInstance, IDC_TT3, szWindowClass, MAX_LOADSTRING);MyRegisterClass(hInstance);// 执行应用程序初始化:if (!InitInstance (hInstance, nCmdShow)){return FALSE;}hAccelTable = LoadAccelerators(hInstance, MAKEINTRESOURCE(IDC_TT3));/////加载地图for(int i=0;i<37;i++){for(int j=0;j<64;j++){map[i][j] = 0;}}ReadMap();//背景绘制hdc = GetDC(hWnd);pen = ::CreatePen(PS_SOLID,1,RGB(255,255,255));bluepen = ::CreatePen(PS_SOLID,1,RGB(0,0,255));greenpen = ::CreatePen(PS_SOLID,1,RGB(0,255,0));redpen = ::CreatePen(PS_SOLID,1,RGB(255,0,0));bluebrush = ::CreateSolidBrush(RGB(0,0,255));greenbrush = ::CreateSolidBrush(RGB(0,255,0));redbrush = ::CreateSolidBrush(RGB(255,0,0));SelectObject(hdc,pen);for(int i=0;i<=37*20;i+=20){MoveToEx(hdc,0,i,NULL);LineTo(hdc,1280,i);}for(int i=0;i<=1280;i+=20){if(i==1280){MoveToEx(hdc,i-1,0,NULL);LineTo(hdc,i-1,740);}else{MoveToEx(hdc,i,0,NULL);LineTo(hdc,i,740);}}//刷新界面Update();// 主消息循环:
// while (GetMessage(&msg, NULL, 0, 0))
// {
// if (!TranslateAccelerator(msg.hwnd, hAccelTable, &msg))
// {
// TranslateMessage(&msg);
// DispatchMessage(&msg);
// }
// }while (true) {if(KEYDOWN(VK_ESCAPE)){SendMessage(hWnd,WM_DESTROY,0,0);}if( PeekMessage( &msg, NULL, 0,0 ,PM_REMOVE) ){if(msg.message==WM_QUIT)break;TranslateMessage( &msg );DispatchMessage( &msg );}}return (int) msg.wParam;
}//
// 函数: MyRegisterClass()
//
// 目的: 注册窗口类。
//
// 注释:
//
// 仅当希望
// 此代码与添加到 Windows 95 中的“RegisterClassEx”
// 函数之前的 Win32 系统兼容时,才需要此函数及其用法。调用此函数十分重要,
// 这样应用程序就可以获得关联的
// “格式正确的”小图标。
//
ATOM MyRegisterClass(HINSTANCE hInstance)
{WNDCLASSEX wcex;wcex.cbSize = sizeof(WNDCLASSEX);wcex.style = CS_HREDRAW | CS_VREDRAW;wcex.lpfnWndProc = WndProc;wcex.cbClsExtra = 0;wcex.cbWndExtra = 0;wcex.hInstance = hInstance;wcex.hIcon = LoadIcon(NULL, IDI_INFORMATION);wcex.hCursor = LoadCursor(NULL, IDC_ARROW);wcex.hbrBackground = (HBRUSH)GetStockObject(BLACK_BRUSH);wcex.lpszMenuName = MAKEINTRESOURCE(IDC_TT3);wcex.lpszClassName = "lujian";wcex.hIconSm = LoadIcon(wcex.hInstance, NULL);return RegisterClassEx(&wcex);
}//
// 函数: InitInstance(HINSTANCE, int)
//
// 目的: 保存实例句柄并创建主窗口
//
// 注释:
//
// 在此函数中,我们在全局变量中保存实例句柄并
// 创建和显示主程序窗口。
//
BOOL InitInstance(HINSTANCE hInstance, int nCmdShow)
{hInst = hInstance; // 将实例句柄存储在全局变量中hWnd = CreateWindow( "LuJian","windows",WS_POPUP,GetSystemMetrics(SM_CXSCREEN),GetSystemMetrics(SM_CYSCREEN),CW_USEDEFAULT,CW_USEDEFAULT,NULL,NULL,hInstance,NULL);if (!hWnd){return FALSE;}ShowWindow(hWnd, SW_MAXIMIZE);UpdateWindow(hWnd);return TRUE;
}//
// 函数: WndProc(HWND, UINT, WPARAM, LPARAM)
//
// 目的: 处理主窗口的消息。
//
// WM_COMMAND - 处理应用程序菜单
// WM_PAINT - 绘制主窗口
// WM_DESTROY - 发送退出消息并返回
//
//
LRESULT CALLBACK WndProc(HWND hWnd, UINT message, WPARAM wParam, LPARAM lParam)
{int wmId, wmEvent;PAINTSTRUCT ps;switch (message){case WM_COMMAND:wmId = LOWORD(wParam);wmEvent = HIWORD(wParam);// 分析菜单选择:switch (wmId){case IDM_ABOUT:DialogBox(hInst, MAKEINTRESOURCE(IDD_ABOUTBOX), hWnd, About);break;case IDM_EXIT:DestroyWindow(hWnd);break;case ID_SAVE:{ofstream out("try.map");for(int i=0; i<37; i++){for(int j=0; j<64; j++){out<
上面就是主要源码,但还不是全部工程,还有些资源文件。如有需要,请下载整个工程
http://download.csdn.net/detail/liujiayu2/8910871
本文来自互联网用户投稿,文章观点仅代表作者本人,不代表本站立场,不承担相关法律责任。如若转载,请注明出处。 如若内容造成侵权/违法违规/事实不符,请点击【内容举报】进行投诉反馈!
