A星路径搜索

摘要:

  在人工智能中有一类问题是有确定解的,如路径、五子棋等,这样的问题非常适合使用搜索来解决。 路径搜索是一个很有趣的问题,在人工智能中算是很基础的问题。最近一直在读《Artificial Intelligence-A Modern Approach》,搜索部分看完印象最深的就是A星算法了,这个在游戏开发中也最常用。于是乎做个总结,明天就掀过这篇了。

路径搜索算法:

Dijkstra:

  Dijkstra 最短路径算法,大学数据结构教科书上都讲过,这里也不赘述了。但是为了及和一下几个算法做比较,我google 了一个图,非常直接的显示Dijkstra算法的搜索过程:

  图中以中心为起点,以辐射状不断向中心外搜索(每次取距离起点最近的点),一圈一圈向外扩张,直到逼近目标点,完成路径搜索。

Best-First-Search:

  BSF 每次扩张节点,都选择最接近目标的节点。Dijkstra 是每次都选择据起点最近的节点。区别是到起点的距离总是已知的,而都终点的距离只能是估计的。所以BSF 提供了启发式函数h。常见的启发式函数h有:

  • 基于绝对距离,计算当前节点到目标点的绝对距离(此时并不能知晓该路径是否可行,也许会有阻碍)
  • 基于方向的,如果目标在东方,那么只向东南、东、东北三个方向扩展,在障碍物少的情况下,BSF可以非常快、非常直接的搜索到目标。如果因障碍阻塞,改变了路径方向,BSF找到的不一定是最近的路径。

A 星算法

  A 星算法兼具Dijkstra 准确和 BSF 的快速,在搜索路径时,通过启发式函数h 计算当前节点到目标节点的距离,而起点到当前点距离已知,则每次选择f = g + h 最小的节点。A星总是尝试找到最短的路径,阻碍物少的情况下性能接近BSF。

A 星算法原理

A 星算法实现

主逻辑实现:

int astar_t::search_path(uint32_t from_index, uint32_t to_index, vector<uint32_t>& path_)
{
    //! open 表中保存待扩展的节点
    //! visited 保存此次搜索访问过的节点,待搜索完成,将其状态恢复到默认状态
    open_table_t        open;
    vector<map_node_t*> visited;

    search_node_t current;
    search_node_t neighbor_node;
    vector<map_node_t*> neighbors;

    //! 先将起始点加入到open 表中
    current.set_pos_index(from_index);
    open.insert(current);

    visited.push_back(m_map.get_node(current.get_pos_index()));

    //! 大循环,直到open为空(找不到目标) 或 找到目标
    while (false == open.empty()) {
        open.pop_first(current);
        
        if (current.get_pos_index() == to_index)
        {
            break;
        }

        //! 添加到close 表
        m_map.get_node(current.get_pos_index())->set_closed();
    
        //! 找到当前节点的所有邻居节点, 不同的游戏中该函数实现可能不同
        //! 有的游戏可以走斜线,而有些不能,如坦克大战就不能走斜线
        m_map.get_neighbors(current.get_pos_index(), neighbors);

        for (size_t i = 0; i < neighbors.size(); ++i)
        {
            map_node_t* neighbor_map_node = neighbors[i];
            neighbor_node.set_pos_index(neighbor_map_node->get_pos_index());
            
            //! 计算该点的 g 和 h 值
            neighbor_node.set_gval(m_map.distance(current.get_pos_index(), neighbor_map_node->get_pos_index()));
            neighbor_node.set_hval(m_map.heuristic(neighbor_map_node->get_pos_index(), to_index));

            //! 如果该点已经在open表中,检查g值,若g值更小,说明当前路径更近,更新open表
            if (true == neighbor_map_node->is_open())
            {
                if (neighbor_node.get_gval() < neighbor_map_node->get_gval())
                {
                    open.update(neighbor_map_node->get_fval(), neighbor_node);
                    neighbor_map_node->set_gval(neighbor_node.get_gval());
                    neighbor_map_node->set_hval(neighbor_node.get_hval());
                    neighbor_map_node->set_parrent(current.get_pos_index());
                }
            }
            //! 如果该点既没有在open,也没有在close中,直接添加到open
            else if (false == neighbor_map_node->is_closed())
            {
                open.insert(neighbor_node);
                neighbor_map_node->set_open();
                neighbor_map_node->set_parrent(current.get_pos_index());
                visited.push_back(neighbor_map_node);
            }
            //! 如果已经在close 中,简单跳过
            else {} //! closed ignore
        }
        neighbors.clear();
    }

    //! 找到了目标,逆序遍历,得到完整的路径
    if (current.get_pos_index() == to_index)
    {
        path_.push_back(current.get_pos_index());
        uint32_t next = m_map.get_node(current.get_pos_index())->get_parrent();
        while (next != from_index)
        {
            path_.push_back(next);
            next = m_map.get_node(next)->get_parrent();
        }
        path_.push_back(from_index);
    }
    
    //! 最后将所有的已访问过的节点状态清楚, 为下次搜索做准备
    for (size_t i = 0; i < visited.size(); ++i)
    {
        visited[i]->clear();
    }
    visited.clear();
    return 0;
}

A 星数据结构

  1. open 表,维护待扩展的节点,每次从其中找到f = g + h 最小的节点,由pop_first 实现

  open 表 是按照f = g + h 由大到小顺排序的,是一个multimap

typedef multimap<uint32_t, search_node_t> table_t;
    struct open_table_t
    {
        table_t nodes;
        bool empty() { return nodes.empty(); }
        int pop_first(search_node_t& ret)
        {
            table_t::iterator it = nodes.begin();
            ret = it->second;
            nodes.erase(it);
            return 0;
        }
        void insert(const search_node_t& node_)
        {
            nodes.insert(make_pair(node_.get_fval(), node_));
        }
        void update(uint32_t old_, const search_node_t& node_)
        {
            pair<table_t::iterator, table_t::iterator> ret = nodes.equal_range(old_);
            table_t::iterator it = ret.first;
            for (; it != ret.second; ++it)
            {
                if (it->second == node_)
                {
                    //! 可以优化, 如果前一个比该节点小,才需要删除
                    nodes.erase(it);
                }
            }
            this->insert(node_);
        }
    };

2. map 管理器

  map 管理器记录所有地图信息,记录某个坐标其相邻坐标信息,记录某个坐标是否可通行信息、地图的宽、高等、两点的距离等。map管理器中维护一个二维数组

 map_mgr_t(uint32_t width_, uint32_t height_):
            m_map_nodes(NULL),
            m_width(width_),
            m_height(height_)
        {
            m_map_nodes = (map_node_t*)malloc(m_width * m_height * sizeof(map_node_t));
            for (uint32_t i = 0; i < m_height; ++i)
            {
                for (uint32_t j = 0; j < m_width; ++j)
                {
                    new(m_map_nodes + i * m_width + j) map_node_t(i * m_width + j);
                }
            }
        }

3.  获取邻居节点方法如下,限制不能斜着走,不同的游戏可能有不同的实现

void get_neighbors(uint32_t pos_, vector<map_node_t*>& ret_)
        {
            map_node_t* tmp = m_map_nodes + pos_ - 1;
            if (tmp >= m_map_nodes && tmp < m_map_nodes + m_height * m_width && tmp->is_can_pass())
            {
                ret_.push_back(tmp);
            }
            tmp = m_map_nodes + pos_ + 1;
            if (tmp >= m_map_nodes && tmp < m_map_nodes + m_height * m_width && tmp->is_can_pass())
            {
                ret_.push_back(tmp);
            }
            tmp = m_map_nodes + pos_ - m_width;
            if (tmp >= m_map_nodes && tmp < m_map_nodes + m_height * m_width && tmp->is_can_pass())
            {
                ret_.push_back(tmp);
            }
            tmp = m_map_nodes + pos_ + m_width;
            if (tmp >= m_map_nodes && tmp < m_map_nodes + m_height * m_width && tmp->is_can_pass())
            {
                ret_.push_back(tmp);
            }
        }

4. 启发式函数

  由于不能斜着走,那么启发式函数h 只是获得x、y上偏移和。

uint32_t heuristic(uint32_t from_, uint32_t to_)
        {
            return this->distance(from_, to_);
        }

TODO:

  1. astar_t 应该模板化, heuristic、distance、get_neighbors都应该是可定制的
  2. 性能参数测试,如1000*1000地图上最坏情况的搜索开销
  3. open表更新还可以优化,当更新g值后若小于迭代器前一个节点,才需要执行删除再插入

源代码: http://ffown.googlecode.com/svn/trunk/fflib/ext/algorithm/astar2/

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏大数据挖掘DT机器学习

R语言数据处理:飞机航行距离与到达延误时间有什么关系??

数据分析有一半以上的时间会花在对原始数据的整理及变换上,包括选取特定的分析变量、汇总并筛选满足条件的数据、排序、加工处理原始变量并生成新的变量、以及分组汇总数...

3304
来自专栏SimpleAI

Hello,1024背后可爱的人儿

1014
来自专栏数据小魔方

创意雷达图(Round Rador Chart)

今天给大家分享的图表是创意雷达图! ▽▼▽ 既然是创意雷达图,肯定是有难度的啦,单纯的雷达图太没有挑战了! 首先看成品,怎么样,还不错吧,想不想自己也做一个,如...

4105
来自专栏Python数据科学

Seaborn从零开始学习教程(二)

在Seaborn的使用中,是可以针对数据类型而选择合适的颜色,并且使用选择的颜色进行可视化,节省了大量的可视化的颜色调整工作。

992
来自专栏生信宝典

R语言学习 - 线图绘制

线图 线图是反映趋势变化的一种方式,其输入数据一般也是一个矩阵。 单线图 假设有这么一个矩阵,第一列为转录起始位点及其上下游5 kb的区域,第二列为H3K27a...

1856
来自专栏算法channel

BAT面试题2:请简要介绍下Tensorflow的计算图

接下来,每天推送一道BAT的面试题,一般问到的这些知识点都是很重要的,所以知道的就再复习一下,不知道的希望这篇可以帮助到你。日积月累,你会在不知不觉中就步入机器...

872
来自专栏调侃编程学

C语言小游戏编程,最详细教程

首先感谢百忙之中你能从万千文章中点小编得专属页面。这不是娱乐篇,这是学习道场。开始前,小编就做一个简单得自我介绍:(开启装逼模式)

1044
来自专栏数据小魔方

仿经济学人——矩阵气泡图

本篇文章案例来源于经济学人2013年一幅关于家庭支出结构与国家间的交叉对比图。 该图信息量相当丰富,至少涵盖了四个维度的信息,支出结构信息(类别型字段)、国别信...

3245
来自专栏数据小魔方

图表中异常值的特殊截断处理

今天跟大家聊聊在图表制作中异常值的处理方式! 相信大家都遇到过这种情况 用一组数据作图 可是偏偏就遇到那么一两个特变态的异常值 不信自己感受一下 ? 其中有一...

3379
来自专栏锦小年的博客

Nilearn学习笔记3-提取时间序列建立功能连接体

在nilearn库中,提供了两种从fmri数据中提取时间序列的方法,一种基于脑分区(Time-series from a brain parcellation ...

2195

扫码关注云+社区