您现在的位置: 天下网吧 >> 网吧天地 >> 天下码农 >> 微信小程序 >> 正文

A*寻径算法

2011-2-10vczx佚名

  下面我来说说我理解的A*算法的原理:
  A*算法是一个求最短路径的函数,为许多即时战略游戏所用刀(或许人家大型的即时战略游戏笔者算法更好,不管它)。它由两个函数组成,一个是评估函数,也就是确定人物移动的下一个位置必须离目标位置最近,评估函数评估的结果越精确,则寻径的速度越快;另一个就是寻径函数,也就根据评估的结果做出响应,然后从新位置继续评估下一个位置,若无路可走(四周都是障碍什么的),那么折回一个路径节点,尝试其他方向,这个算法有个缺点,随着游戏中人物增多,相应的处理节点就增多了,会影响处理速度,而且占用大量的内存。

  有兴趣的朋友可以改成动态的寻径,就是当入口和出口位置都在变化的时候进行寻径,这个代码也只有200多行。
我的算法还不能算是最优的,因为评估函数只不过是简单的测试两点距离(这会带来误差),选择离出口最短的且非障碍物的方向,进行下一个路径节点的移动。

  这里说一句,我希望大家将我的代码用于学习目的,不希望看见是为了交作业而拷贝过去,我会很伤心的。
/* AStar.cpp */
/* 设计者: yuki */

typedef unsigned char    byte_t;
typedef unsigned int    uint_t;

/* 路径节点 */
typedef struct footprint {
    
    /* 存放在数组中的位置 */
    uint_t    pos;

    /* 存放方向信号量 */
    byte_t    direct;

    struct footprint *next;
    struct footprint *prev;

} path_t;


/*
    方向信号量查询表
    0x01(0000 0001) : 上
    0x02(0000 0010) : 下
    0x04(0000 0100) : 左
    0x08(0000 1000) : 右
*/

static byte_t d_signal[4]  = {0x01, 0x02, 0x04, 0x08};

/*
    方向信号量使用表
    如果指定方向已经走过,那么使用“与”运算去处该方向
    0x0E(0000 1110) : 上
    0x0D(0000 1101) : 下
    0x0B(0000 1011) : 左
    0x07(0000 0111) : 右
*/

static byte_t d_spend[4]   = {0x0E, 0x0D, 0x0B, 0x07};

/* 指定方向移动偏量 */
static int      move[4][2]   = { {0, -1}, {0, 1}, {-1, 0}, {1, 0} };

/* 打印迷宫用的符号 */
static byte_t symbolic[3]   = {'#',0x20,'*'};

/* 求两点间的距离 */
inline 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;

}

/* 压缩坐标 */
inline 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       : 迷宫矩阵
=======================================================
*/
inline 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              :迷宫矩阵
=============================================================
*/

inline 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;

}

/* AStar.h */
/* 设计者: yuki */

#ifndef __ASTAR_H
#define __ASTAR_H

#define MAZE_WIDTH        10            /* 迷宫宽度 */
#define MAZE_HEIGHT        10            /* 迷宫高度 */

#define PATH_BLOCK         0            /* 障碍物   */
#define    PATH_WALKON         1            /* 可行走   */
#define PATH_FOOTPRINT   2            /* 脚印     */

#include "AStar.cpp"

#endif

/* main.cpp */
/* 设计者: yuki */

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <conio.h>
#include <math.h>
#include <assert.h>

#include "AStar.h"

static byte_t    maze[MAZE_HEIGHT][MAZE_WIDTH] = {
            0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
            0, 1, 1, 0, 1, 1, 1, 0, 1, 0,
            0, 1, 1, 0, 1, 1, 1, 0, 1, 0,
            0, 1, 1, 1, 1, 0, 0, 0, 1, 0,
            0, 1, 0, 0, 0, 1, 1, 0, 1, 0,
            0, 1, 1, 1, 0, 1, 1, 0, 1, 0,
            0, 1, 0, 1, 1, 1, 0, 1, 1, 0,
            0, 1, 0, 0, 0, 1, 0, 0, 1, 0,
            0, 0, 1, 1, 1, 1, 1, 1, 1, 0,
            0, 0, 0, 0, 0, 0, 0, 0, 0, 0
};

int main() {
    register int i,j;

    path_t *pHead = AStar((uint_t)1,(uint_t)1,(uint_t)2,(uint_t)8,maze);
    path_t *p = pHead;
    path_t *bak;
    if(p) {
        bak = p->next;
        printf("(%u,%u)",p->pos >> 8, p->pos & 0x00FF);
        free(p);
        p = bak;
        while(p) {
            bak = p->next;
            printf("->(%u,%u)",p->pos >> 8, p->pos & 0x00FF);
            free(p);
            p = bak;
        }
        printf("\n");
    }
    else
        printf("No path to get out of the maze\n");
    
    pHead = p = bak = (path_t *)0;
    
    /* 打印迷宫 */
    for(i = 0; i < MAZE_HEIGHT; ++i) {
        for(j = 0; j < MAZE_WIDTH; ++j)
            printf("%c",symbolic[maze[i][j]]);
        printf("\n");
    }

    getch();

    return 0;
}

欢迎访问最专业的网吧论坛,无盘论坛,网吧经营,网咖管理,网吧专业论坛 https://bbs.txwb.com

关注天下网吧微信/下载天下网吧APP/天下网吧小程序,一起来超精彩

本文来源:vczx 作者:佚名

相关文章
没有相关文章
声明
声明:本站所发表的文章、评论及图片仅代表作者本人观点,与本站立场无关。若文章侵犯了您的相关权益,请及时与我们联系,我们会及时处理,感谢您对本站的支持!联系邮箱:support@txwb.com,系统开号,技术支持,服务联系QQ:1175525021本站所有有注明来源为天下网吧或天下网吧论坛的原创作品,各位转载时请注明来源链接!
天下网吧 网吧天下