📄 astar.c
字号:
/*****************************************************************/
/*函数名称： GPS_Navigation.c */
/*函数功能： 小车导航，实现最短路径 */
/*有无返回： 无 */
/*修改记录： 无修改记录 */
/*编写作者： t483-4-19chenyong */
/*编写日期： 2008-3-12 */
/*****************************************************************/
#include "common.h"
#include "TS12864A.h"
#include "navigation.h "
#include "delay.h"
#include "map.h"
#include "key.h"
#include "astar.h"
#include "window.h"
/*****************************************************************/
/*
/----------GPS导航电子地图(测试版本)
/
/-------------------------------------------
| S,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*, |
| *,*,*,*,*,B,*,*,*,*,*,*,*,*,*,*, |
| *,*,*,*,*,*,*,*,*,*,*,*,*,*,E,*, |
| *,*,*,*,*,*,*,*,*,*,*,*,*,*,*,*, |
| *,*,*,A,*,*,*,*,*,*,*,*,*,*,*,*, |
| *,*,*,*,*,*,*,*,*,*,C,*,*,*,*,*, |
| *,*,*,*,*,*,F,*,*,*,*,*,*,*,*,*, |
| *,*,*,*,*,*,*,*,*,*,*,*,*,*,D,*, |
-------------------------------------------
说明： A，B，C，D，E，F为用户要到达的终点，S为起点。通过按键盘上的按键
实现小车的最短路径搜索，并通过液晶显示行驶的步数。
*/
struct MapData
{
unsigned char Gps_Map_Length[Map_Length];
unsigned char Gps_Map_Width[Map_Width];
};
xdata struct MapData;
extern unsigned char key;
extern unsigned int Position;
byte_t maze[MAZE_HEIGHT][MAZE_WIDTH] = {
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
1,0,1,0,1,1,1,0,1,1,1,0,0,1,0,1,
0,0,1,0,1,0,0,1,1,0,1,1,0,1,1,1,
1,0,1,1,1,1,1,1,1,1,1,1,1,0,1,1,
1,1,1,1,0,1,1,0,1,0,1,0,1,1,1,1,
1,1,0,1,1,1,1,1,1,0,1,0,1,1,0,0,
0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
};
byte_t maze0[MAZE_HEIGHT][MAZE_WIDTH] = {
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
1,0,1,0,1,1,1,0,1,1,1,0,0,1,0,1,
0,0,1,0,1,0,0,1,1,0,1,1,0,1,1,1,
1,0,1,1,1,1,1,1,1,1,1,1,1,0,1,1,
1,1,1,1,0,1,1,0,1,0,1,0,1,1,1,1,
1,1,0,1,1,1,1,1,1,0,1,0,1,1,0,0,
0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0
};
/*
方向信号量查询表
0x01(0000 0001) : 上
0x02(0000 0010) : 下
0x04(0000 0100) : 左
0x08(0000 1000) : 右
*/
byte_t d_signal[4] = {0x01, 0x02, 0x04, 0x08};
/*
方向信号量使用表
如果指定方向已经走过,那么使用“与”运算去处该方向
0x0E(0000 1110) : 上
0x0D(0000 1101) : 下
0x0B(0000 1011) : 左
0x07(0000 0111) : 右
*/
byte_t d_spend[4] = {0x0E, 0x0D, 0x0B, 0x07};
/* 指定方向移动偏量 */
int move[4][2] = { {0, -1}, {0, 1}, {-1, 0}, {1, 0} };
/* 打印迷宫用的符号 */
byte_t symbol[3] = {0,1,2};
/* 求两点间的距离 */
uint_t distance( uint_t pos1X, uint_t pos1Y, uint_t pos2X, uint_t pos2Y ) {
uint_t ret = 0;
/* 距离公式 */
ret = (uint_t)sqrt((pow((double)((int)pos1X - (int)pos2X),2) + pow((double)((int)pos1Y - (int)pos2Y),2)));
return ret;
}
/* 压缩坐标 */
uint_t create_pos( uint_t pX, uint_t pY ) {
uint_t ret = 0;
/* 将pX赋给ret,这样pX坐标在ret的低八位 */
ret = pX;
/* 将pX坐标移到高八位去,这样低位就能存放pY */
ret <<= 8;
/* 将pY存放放到ret的低八位,并保持高八位的数据不变 */
ret |= pY;
return ret;
}
/*
== 估计函数 ===========================================
-p : 当前移动到的节点指针
-quit_x
-quit_y : quit_x 和 quit_y表示迷宫出口坐标
-maze : 迷宫矩阵
=======================================================
*/
path_t * evaluate( path_t *p, uint_t quit_x, uint_t quit_y, byte_t maze[MAZE_HEIGHT][MAZE_WIDTH] ) {
uint_t pX, pY;
/* 用于接收四个方向离开出口的距离,以便选择最近的方向移动 */
int dis[4];
int minDis = 32767;
int minId = -1;
path_t *pnode = (path_t *)0;
register int i;
/* 计算当前节点的坐标 */
pX = p->pos >> 8;
pY = p->pos & 0x00FF;
memset(dis, (int)-1, sizeof(int)*4);
/* 计算每个方向离开出口的距离,一次存放到dis数组,若没有i方向,则dis[i]任保留-1 */
for( i = 0; i < 4; ++i ) {
if( (p->direct & d_signal[i]) >> i == 0x01 )
dis[i] =(int)distance(pX + move[i][0], pY + move[i][1], quit_x, quit_y);
}
/* 获得最短距离的方向 */
for(i = 0; i < 4; ++i) {
if(dis[i] != -1 && dis[i] < minDis) {
minId = i;
minDis = dis[i];
}
}
/* 若没有可用的方向,则通知寻径函数折回 */
if(minId == -1)
return (path_t *)0;
/* 用去最近距离方向的信号量 */
p->direct &= d_spend[minId];
/* 在移动到新位置之前,在旧位置处留下足迹 */
maze[pY][pX] = (byte_t)PATH_FOOTPRINT;
/* 构建新的路径节点 */
pnode = (path_t *)malloc(sizeof(path_t));
assert(pnode);
/* 计算下一个位置的坐标 */
pX += move[minId][0];
pY += move[minId][1];
pnode->pos = create_pos(pX, pY);
pnode->prev = p;
pnode->next = (path_t *)0;
pnode->direct = 0;
/* 在新位置处,计算下一个位置可用的移动方向 */
for(i = 0; i < 4; ++i) {
if(maze[pY + move[i][1]][pX + move[i][0]] != PATH_BLOCK && maze[pY + move[i][1]][pX + move[i][0]] != PATH_FOOTPRINT) {
/* 若尝试的下一个位置不是障碍物或自己走过的足迹,则视为可用方向,获得该方向的信号量 */
pnode->direct |= d_signal[i];
}
}
return pnode;
}
/*
== A*算法寻径函数 ===========================================
-eX
-eY :入口坐标
-qX
-qY :出口坐标
-maze :迷宫矩阵
=============================================================
*/
path_t * AStar(uint_t eX, uint_t eY, uint_t qX, uint_t qY, byte_t maze[MAZE_HEIGHT][MAZE_WIDTH]) {
register int i;
/* 压缩坐标 */
uint_t quit_pos = create_pos(qX, qY);
/* 构建入口路径节点,视为路径链的头 */
path_t *head = (path_t *)malloc(sizeof(path_t));
path_t *p = (path_t *)0;
path_t *back = (path_t *)0;
assert(head);
p = head;
p->direct = 0;
p->pos = create_pos(eX,eY);
p->next = (path_t *)0;
p->prev = (path_t *)0;
/* 创建入口处的可用方向 */
for(i = 0; i < 4; ++i) {
if(maze[eY + move[i][1]][eX + move[i][0]] != PATH_BLOCK)
/* 若无障碍物则获得该方向的信号量 */
p->direct |= d_signal[i];
}
do {
/* 获得下个路径的节点指针 */
back = evaluate(p, qX, qY, maze);
if(back) {
p->next = back;
p = p->next;
}
/* 无路可走则折回 */
if(p->direct == 0 && p != head && p->pos != quit_pos) {
back = p->prev;
back->next = (path_t *)0;
/* 清楚脚印 */
maze[p->pos & 0x00FF][p->pos >> 8] = (byte_t)PATH_WALKON;
free(p);
p = back;
}
/* 若走不出迷宫,即折回到入口,且入口处的可用方向全部尝试过 */
if(p == head && p->direct == 0) {
free(head);
return (path_t *)0;
}
} while( p->pos != quit_pos );
/* 在出口处留下脚印,便于打印 */
maze[p->pos & 0x00FF][p->pos >> 8] = (byte_t)PATH_FOOTPRINT;
return head;
}
/*****************************************************************/
/*****************************************************************/
/*函数名称： show_menu_DaoHang.c */
/*函数功能： GPS导航 */
/*有无返回： 无 */
/*修改记录： 无修改记录 */
/*入口参数：
start_x------------------------------------起点x坐标
start_y------------------------------------起点y坐标
end_x ------------------------------------终点x坐标
end_y ------------------------------------终点y坐标
*/
/*编写日期： 2008-5-01 */
/*****************************************************************/
//void show_menu_DaoHang(unsigned char start_x,unsigned char start_y,unsigned char end_x,unsigned char end_y)
void show_menu_DaoHang()
{
register unsigned char i=0,j=0;
path_t *pHead;
byte_t mazetemp[MAZE_HEIGHT][MAZE_WIDTH]={0};
for(i = 0; i < MAZE_HEIGHT; ++i)
{
for(j = 0; j < MAZE_WIDTH; ++j)
mazetemp[i][j]=maze[i][j];
}
pHead=AStar((uint_t)(Position/1000),(uint_t)(Position%1000/100),(uint_t)(Position%100/10),(uint_t)(Position%10),mazetemp);
/* 打印地图 */
for(i = 0; i < MAZE_HEIGHT; ++i)
{
for(j = 0; j < MAZE_WIDTH; ++j)
Display_Point(j,i,symbol[mazetemp[i][j]]);
/*
j-------代表x方向
i-------代表y方向
symbolic-路径显示
*/
}
}
void Show_Map()
{
register unsigned char point_x=0,point_y=0;
for(point_y = 0; point_y < MAZE_HEIGHT; ++point_y)
{
for(point_x = 0; point_x < MAZE_WIDTH; ++point_x)
// Display_Point(point_x,point_y,symbol[maze[point_y][point_x]]);
Display_Point(point_x,point_y,symbol[maze0[point_y][point_x]]);
/* i-------代表y方向
j-------代表x方向
symbolic-路径显示
*/
}
}
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -