`
cenphoenix
  • 浏览: 162159 次
  • 性别: Icon_minigender_1
  • 来自: 大连
社区版块
存档分类
最新评论

四种寻路算法并比较

阅读更多
好久没搞这些东西了...想了十分钟才勉强回忆起来...
写了三个钟头...好累啊...
四种算法是DFS,BFS,Heuristic DFS, Heuristic BFS (A*)
用了两张障碍表,一张是典型的迷宫:

char Block[SY][SX]=
{{1,1,1,1,1,1,1,1,1,1,1 },
{1,0,1,0,1,0,0,0,0,0,1 },
{1,0,1,0,0,0,1,0,1,1,1 },
{1,0,0,0,1,0,1,0,0,0,1 },
{1,0,1,1,0,0,1,0,0,1,1 },
{1,0,1,0,1,1,0,1,0,0,1 },
{1,0,0,0,0,0,0,0,1,0,1 },
{1,0,1,0,1,0,1,0,1,0,1 },
{1,0,0,1,0,0,1,0,1,0,1 },
{1,1,1,1,1,1,1,1,1,1,1 }};

第二张是删掉一些障碍后的:

char Block[SY][SX]=
{{1,1,1,1,1,1,1,1,1,1,1 },
{1,0,1,0,1,0,0,0,0,0,1 },
{1,0,1,0,0,0,1,0,1,1,1 },
{1,0,0,0,0,0,1,0,0,0,1 },
{1,0,0,1,0,0,1,0,0,1,1 },
{1,0,1,0,0,1,0,1,0,0,1 },
{1,0,0,0,0,0,0,0,1,0,1 },
{1,0,1,0,0,0,1,0,1,0,1 },
{1,0,0,1,0,0,1,0,0,0,1 },
{1,1,1,1,1,1,1,1,1,1,1 }};

结果:
尝试节点数 合法节点数 步数
深度优先 416/133 110/43 19/25
广度优先 190/188 48/49 19/15
深度+启发 283/39 82/22 19/19
广度+启发 189/185 48/49 19/15

所以可以看出深度+启发是最好的,效率高路径也挺短。A*第一是不真实二是慢三是空间消耗较大。

附:dfs+heu的源程序,bc++ 3.1通过

#include <iostream.h>
#include <memory.h>
#include <stdlib.h>

#define SX 11 //宽
#define SY 10 //长

int dx[4]={0,0,-1,1}; //四种移动方向对x和y坐标的影响
int dy[4]={-1,1,0,0};

/*char Block[SY][SX]= //障碍表
{{ 1,1,1,1,1,1,1,1,1,1,1 },
{ 1,0,1,0,1,0,0,0,0,0,1 },
{ 1,0,1,0,0,0,1,0,1,1,1 },
{ 1,0,0,0,0,0,1,0,0,0,1 },
{ 1,0,0,1,0,0,1,0,0,1,1 },
{ 1,0,1,0,0,1,0,1,0,0,1 },
{ 1,0,0,0,0,0,0,0,1,0,1 },
{ 1,0,1,0,0,0,1,0,1,0,1 },
{ 1,0,0,1,0,0,1,0,0,0,1 },
{ 1,1,1,1,1,1,1,1,1,1,1 }};*/

char Block[SY][SX]= //障碍表
{{ 1,1,1,1,1,1,1,1,1,1,1 },
{ 1,0,1,0,1,0,0,0,0,0,1 },
{ 1,0,1,0,0,0,1,0,1,1,1 },
{ 1,0,0,0,1,0,1,0,0,0,1 },
{ 1,0,1,1,0,0,1,0,0,1,1 },
{ 1,0,1,0,1,1,0,1,0,0,1 },
{ 1,0,0,0,0,0,0,0,1,0,1 },
{ 1,0,1,0,1,0,1,0,1,0,1 },
{ 1,0,0,1,0,0,1,0,1,0,1 },
{ 1,1,1,1,1,1,1,1,1,1,1 }};

int MaxAct=4; //移动方向总数
char Table[SY][SX]; //已到过标记
int Level=-1; //第几步
int LevelComplete=0; //这一步的搜索是否完成
int AllComplete=0; //全部搜索是否完成
char Act[1000]; //每一步的移动方向,搜索1000步,够了吧?
int x=1,y=1; //现在的x和y坐标
int TargetX=9,TargetY=8; //目标x和y坐标
int sum1=0,sum2=0;

void Test( );
void Back( );
int ActOK( );
int GetNextAct( );

void main( )
{
    memset(Act,0,sizeof(Act)); //清零
    memset(Table,0,sizeof(Table));
    Table[y][x]=1; //做已到过标记
    while (!AllComplete) //是否全部搜索完
    {
        Level++;LevelComplete=0; //搜索下一步
        while (!LevelComplete)
        {
            Act[Level]=GetNextAct( ); //改变移动方向
            if (Act[Level]<=MaxAct)
                sum1++;
            if (ActOK( )) //移动方向是否合理
            {
                sum2++;
                Test( ); //测试是否已到目标
                LevelComplete=1; //该步搜索完成
            }
            else
            {
                if (Act[Level]>MaxAct) //已搜索完所有方向
                    Back( ); //回上一步
                if (Level<0) //全部搜索完仍无结果
                    LevelComplete=AllComplete=1; //退出
            }
        }
    }
}

void Test( )
{
    if ((x==TargetX)&&(y==TargetY)) //已到目标
    {
        for (int i=0;i<=Level;i++)
            cout<<(int)Act[i]; //输出结果
        cout<<endl;
        cout<<Level+1<<" "<<sum1<<" "<<sum2<<endl;
        LevelComplete=AllComplete=1; //完成搜索
    }
}

int ActOK( )
{
    int tx=x+dx[Act[Level]-1]; //将到点的x坐标
    int ty=y+dy[Act[Level]-1]; //将到点的y坐标
    if (Act[Level]>MaxAct) //方向错误?
        return 0;
    if ((tx>=SX)||(tx<0)) //x坐标出界?
        return 0;
    if ((ty>=SY)||(ty<0)) //y坐标出界?
        return 0;
    if (Table[ty][tx]==1) //已到过?
        return 0;
    if (Block[ty][tx]==1) //有障碍?
        return 0;
    x=tx;
    y=ty; //移动
    Table[y][x]=1; //做已到过标记
    return 1;
}

void Back( )
{
    x-=dx[Act[Level-1]-1];
    y-=dy[Act[Level-1]-1]; //退回原来的点
    Table[y][x]=0; //清除已到过标记
    Act[Level]=0; //清除方向
    Level--; //回上一层
}

int GetNextAct( ) //找到下一个移动方向。这一段程序有些乱,
//仔细看!
{
    int dis[4];
    int order[4];
    int t=32767;
    int tt=2;
    for (int i=0;i<4;i++)
    dis[i]=abs(x+dx[i]-TargetX)+abs(y+dy[i]-TargetY);
    for (i=0;i<4;i++)
    if (dis[i]<t)
    {
        order[0]=i+1;
        t=dis[i];
    }
    if (Act[Level]==0)
        return order[0];
    order[1]=-1;
    for (i=0;i<4;i++)
    if ((dis[i]==t)&&(i!=(order[0]-1)))
    {
        order[1]=i+1;
        break;
    }
    if (order[1]!=-1)
    {
        for (i=0;i<4;i++)
            if (dis[i]!=t)
            {
                order[tt]=i+1;
                tt++;
            }
    }
    else
    {
        for (i=0;i<4;i++)
        if (dis[i]!=t)
        {
            order[tt-1]=i+1;
            tt++;
        }
    }

    if (Act[Level]==order[0])
        return order[1];
    if (Act[Level]==order[1])
        return order[2];
    if (Act[Level]==order[2])
        return order[3];
    if (Act[Level]==order[3])
        return 5;
}
分享到:
评论

相关推荐

    四方向走迷宫&寻路算法C语言

    本项目基于C语言实现了四方向的走迷宫及寻路算法,同时该算法可以扩展为八方向。下面我们将深入探讨相关知识点。 1. **基本概念**: - **迷宫问题**:迷宫问题是一类经典的图论问题,涉及到在一个网格状结构中找到...

    常见的一些寻路算法

    本文将详细解析三种常见的寻路算法:深度优先搜索(DFS)、宽度优先搜索(BFS)以及A*算法,并结合提供的源码文件“寻路算法-4.11.cpp”进行分析。 1. 深度优先搜索(DFS) DFS 是一种用于遍历或搜索树或图的算法。...

    A星寻路算法案例

    A星寻路算法(A* Search Algorithm)是计算机科学中用于在图或网格中寻找从起点到终点最短路径的一种高效算法。它结合了最佳优先搜索(如Dijkstra算法)和启发式搜索策略,通过估计从起点到目标点的最优成本来指导...

    A星寻路算法&B星寻路算法 c++实现 MFC

    A星(AStar)和B星(BStar)寻路算法是计算机科学中用于解决最短路径问题的两种高效算法,尤其在游戏开发、图形界面、网络路由等领域广泛应用。这两种算法都是基于图的启发式搜索方法,旨在找到从起点到终点的最优路径。...

    java快速易懂寻路算法

    总结来说,"java快速易懂寻路算法"是指在Java中设计和实现的一种简单易懂的寻路算法,它可以快速地找出图中节点之间的路径,包括最短路径,并支持正查和逆查。这种算法的实现涉及到图的表示、路径搜索策略以及可能的...

    A*自动寻路算法实现(java)

    下载本程序仅可演示A*自动寻路算法实现(java),该程序是基于我写的网络版贪吃蛇基础上编写的(网络版贪吃蛇...wasd键控制太阳的方向,鼠标左击目的地,会根据A*自动寻路算法计算出一条最优路线,太阳按最优路线移动。

    A*寻路算法 源码

    A*寻路算法(A* Pathfinding Algorithm)是游戏开发、地图导航、机器人路径规划等领域广泛应用的一种高效路径搜索算法。它结合了Dijkstra算法的全局最优性和BFS(广度优先搜索)的效率,通过引入启发式函数来指导搜索,...

    连连看 寻路算法 源码

    在游戏设计中,实现高效、智能的寻路算法至关重要,它决定了玩家能否顺利找到并消除匹配对。本压缩包提供的源码着重展示了如何利用A*寻路算法来优化连连看的寻路过程。 A*(A-Star)寻路算法是一种启发式搜索算法,...

    寻路算法的详细类寻路算法的详细类

    本文将详细讲解寻路算法的原理和应用,特别是A*(A-star)算法,它是游戏开发中最常用的一种高效寻路算法。 一、寻路算法概述 寻路算法是计算机科学中解决网络或图结构中节点间最短路径问题的算法。在游戏场景中,...

    navmesh寻路算法源码

    本文将深入探讨NavMesh寻路算法的核心原理,并通过`navMeshTest-master`项目中的源码分析其具体实现。 NavMesh,顾名思义,是导航网格,是一种三维空间中用于路径规划的二维简化模型。它通过对场景进行细分和抽象,...

    b* 寻路算法

    而`PathCompare.rar`可能包含与其他寻路算法(如Dijkstra或A*)的比较代码或结果,帮助我们理解B*算法的优势和适用场景。 总的来说,B*寻路算法是一种适应性强、准确度高的路径规划方法,尤其适用于动态或不确定的...

    C#实现4种经典迷宫生成算法和迷宫寻路算法

    本项目涉及的是使用C#语言实现的4种经典迷宫生成算法和A*寻路算法。以下是对这些算法的详细解释: 1. **并查集算法生成迷宫**: 并查集是一种数据结构,用于处理一些不相交集合的合并与查询。在迷宫生成中,可以将...

    FLASH AS3 寻路算法

    其中,A*算法是AS3中经常采用的一种高效寻路算法,因为它结合了启发式信息以减少搜索空间,从而提高了性能。 A*算法的基本思想是结合了Dijkstra算法的全局最优性和贪婪最佳优先搜索算法的局部最优性。它通过使用一...

    iphone游戏 寻路算法

    寻路算法是计算机科学中的一种路径搜索算法,用于寻找图形或网格中的最短路径。在游戏场景中,地图通常被抽象为一个有向图或无向图,节点代表地图上的位置,边则表示相邻节点之间的连接。A*(发音为“A-star”)寻路...

    六边形A*寻路算法源码(As3版本)

    六边形A*寻路算法源码(As3版本)在六边形战棋类游戏中可以使用

    VB A星寻路算法 VB A*寻路算法

    VB 中的A星寻路算法 用了折半快速插入有序队列可以很快的添加结点数据 数组是以距离从大到小的一个有序队列 每次取数组中最后的数据,可以快速删除 例如:redim preserve A(ubound(A)-1)

    寻路算法

    在本主题中,我们将深入探讨几种常见的寻路算法,以及如何进行寻路算法的封装。 1. 广度优先搜索(BFS) 广度优先搜索是一种用于寻找两个节点之间最短路径的算法。它首先探索距离起点最近的节点,然后逐步扩展到更...

    a*算法 寻路算法 寻路寻路寻路寻路寻路寻路寻路寻路寻路寻路寻路

    a*(A-star)算法是一种在图形搜索中用于寻找从起点到终点最短路径的启发式搜索算法。它结合了Dijkstra算法的最优性和BFS(广度优先搜索)的效率,通过引入启发式函数来指导搜索方向,从而更快地找到目标。a*算法...

Global site tag (gtag.js) - Google Analytics