博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
Astar算法框架
阅读量:5876 次
发布时间:2019-06-19

本文共 1992 字,大约阅读时间需要 6 分钟。

首先本文并不打算详细的介绍A*算法,要想大致的了解A*算法可参看下面两篇文章:

http://wenku.baidu.com/view/d39faba1284ac850ad02425d.html

其次,不用太纠结算法的效率,例如remove_min_pnode函数使用线性探索寻找最小值,实际上可以使用

二叉堆或别的方法提高执行效率.

本文的目的是提供一个较通用的A*框架,用于解决游戏中的寻路问题.

首先看下结构的定义:

//一个地图块节点struct map_node{};//路径节点struct path_node{        struct list_node l_node;        struct double_link_node _open_list_node;    struct double_link_node _close_list_node;    struct path_node *parent;    struct map_node  *_map_node;    double G;//从初始点到当前点的开销    double H;//从当前点到目标点的估计开销    double F;};

map_node用于表示地图上一块区域节点,用户可继承自map_node并实现自己的地图表示,path_node表示一个路径搜索节点,通过parent连接在

一起,当路径被搜索到之后,可通过parent从目标节点遍历到起始节点。

将地图表示与路径表示分离的最主要目的是,使应用可以在同一个地图表示上高效的开启多线程执行路径搜索任务.

下面再看下A*搜索过程:

//由使用者提供的3个函数//get_neighbors约定:如果一个map_node*是阻挡点,将不会被返回typedef struct map_node** (*get_neighbors)(struct map_node*);typedef double (*cost_2_neighbor)(struct path_node*,struct path_node*);typedef double (*cost_2_goal)(struct path_node*,struct path_node*);//一次路径搜索的过程对象struct A_star_procedure{    get_neighbors _get_neighbors;    cost_2_neighbor _cost_2_neighbor;//用于计算两个路径点G值的函数指针    cost_2_goal _cost_2_goal;//用于计算两个路径点H值的函数指针    struct double_link open_list;    struct double_link close_list;    hash_map_t mnode_2_pnode;//map_node到path_node的映射    struct link_list *pnodes;//所有临时path_node列表};struct A_star_procedure *create_astar(get_neighbors,cost_2_neighbor,cost_2_goal);//寻找从from到to的路径,找到返回路径点,否则返回NULLstruct path_node* find_path(struct A_star_procedure *astar,struct map_node *from,struct map_node *to);void   destroy_Astar(struct A_star_procedure**);

 

A_star_procedure代表了一个A*搜索过程,创建这个过程的时候,用户需要提供三个回调函数:

get_neighbors:用于获得一个节点的临接节点,这里约定,如果一个节点是阻挡点,那么不被认为是临接节点.

例如:对于一个用格子表示的地图,其临接节点可以是当前格子周围的8个格子,如果节点是一个3角形,
则其临接节点是于其相接的其它三角形.
cost_2_neighbor:用于计算从当前节点到其临接节点的代价.

cost_2_goal:用于估算从当前节点到达目标节点的代价.

用户定义好这三个函数之后,调用create_astar创建一个搜索过程对象,然后通过find_path搜索从开始点到目标点的路径.

下面提供了两个测试用例,在一个用格子表示的迷宫中搜索路径和解决8码问题:

https://github.com/sniperHW/kendylib/blob/master/Astar/testmaze.c

对于8码问题,预先判断两个状态是否可达的可参看:

转载地址:http://gfzix.baihongyu.com/

你可能感兴趣的文章
ubuntu 12.04 下面安装vmware workstation 8.0.4
查看>>
[原创]FineUI秘密花园(二十三) — 树控件概述
查看>>
【Java学习笔记】如何写一个简单的Web Service
查看>>
如何解决This system is not registered with RHN.
查看>>
Cocos2d-x学习笔记(两)Cocos2d-x总体框架
查看>>
拆解探索MagSafe电源接口结构和指示灯变颜色原理
查看>>
Android中EditText,Button等控件的设置
查看>>
lintcode:Remove Nth Node From End of Lis 删除链表中倒数第n个节点
查看>>
POJ 1915-Knight Moves (单向BFS && 双向BFS 比)
查看>>
java中在linux下利用jstack检测死锁
查看>>
linux编译安装LAMP
查看>>
php中的continue用法
查看>>
Android小游戏应用---撕破美女衣服游戏
查看>>
TextKit简单示例
查看>>
网格最短路径算法(Dijkstra & Fast Marching)(转)
查看>>
最短路径算法-Dijkstra算法的应用之单词转换(词梯问题)
查看>>
软链接和硬链接详解
查看>>
HTML5 video 视频标签 常用属性
查看>>
深入理解javascript对象系列第一篇——初识对象
查看>>
Redis_master-slave模式
查看>>