游戏开发论坛

 找回密码
 立即注册
搜索
12
返回列表 发新帖
楼主: bearhunter

我用 vb.2005写了一个A*寻路算法

[复制链接]

26

主题

537

帖子

537

积分

高级会员

Rank: 4

积分
537
发表于 2006-7-10 09:43:00 | 显示全部楼层

Re:我用 vb.2005写了一个A*寻路算法

A*算法已成为经典的寻路算法,在不少实现实例中还做了细节改进。

在本站的算法文章里,有一篇《寻路算法新思维》,作者提出了一种称为“矢量寻路算法”的设想,不过只有设想理论。好像没有人讨论过这种设想是否存在漏洞,但是可以肯定的是,如果没有理论漏洞,该算法肯定比任何形式的A*算法高效。

32

主题

1583

帖子

1589

积分

金牌会员

Rank: 6Rank: 6

积分
1589
发表于 2006-7-10 17:36:00 | 显示全部楼层

Re: Re: Re:我用 vb.2005写了一个A*寻路算法

逆火十三: Re: Re:我用 vb.2005写了一个A*寻路算法


A*算法不至于在这个地图上算错



那可不一定,A*算法的效率取决于它的估价函数,估价函数的不同导致寻路结果不同。(所以不要以为所有的A*算法都一样)
从算法上看A*其实是DFS搜索的优化,但众所周知DFS不一定能求得最优解。

楼主的估价函数应该是两点之间的距离吧(开始那几步很明显),我也常用这种方式,不过楼主的好像还有其它优化,后面几步没有直接走到障碍。不过确实在复杂地图上有很大问题,我正考虑其它更高效的A*。

32

主题

1583

帖子

1589

积分

金牌会员

Rank: 6Rank: 6

积分
1589
发表于 2006-7-10 17:43:00 | 显示全部楼层

Re: Re:我用 vb.2005写了一个A*寻路算法

griffin2006: Re:我用 vb.2005写了一个A*寻路算法

我喜欢!
不可达时需要较长的寻路时间,应该是一个bug吧。


这不是Bug,是算法本身的缺陷,当目的不可达时DFS会遍历每一个结点将这个地图全部搜索一遍以求找到可能的路径,当然会比较费时。地图越大越明显。

32

主题

1583

帖子

1589

积分

金牌会员

Rank: 6Rank: 6

积分
1589
发表于 2006-7-10 17:44:00 | 显示全部楼层

Re:我用 vb.2005写了一个A*寻路算法

楼主能否将程序改动一下,除了显示最终路径之外同时显示一下曾经搜索过的结点,这样对比可以看出算法的效率。

64

主题

855

帖子

856

积分

高级会员

Rank: 4

积分
856
QQ
发表于 2006-7-11 14:15:00 | 显示全部楼层

Re: Re:我用 vb.2005写了一个A*寻路算法

系统崩溃: Re:我用 vb.2005写了一个A*寻路算法

A*算法已成为经典的寻路算法,在不少实现实例中还做了细节改进。

在本站的算法文章里,有一篇《寻路算法新思维》,作者提出了一种称为“矢量寻路算法”的设想,不过只有设想理论。好像没有人讨论过这种设想是否存在漏洞,但是可以肯定的是,如果没有理论漏洞,该算法肯定比任何形式的A*算法高效。


这个理论已经有我的一个朋友做了实现,效率是很高的,问题是对于有面积大小的物体寻路有些困难,还在尝试。

可以参考一下他的BLOG:
http://blog.gameres.com/show.asp?BlogID=1721&column=0

0

主题

62

帖子

62

积分

注册会员

Rank: 2

积分
62
发表于 2007-4-4 20:02:00 | 显示全部楼层

Re:我用 vb.2005写了一个A*寻路算法

很不错啊,支持

1

主题

16

帖子

16

积分

新手上路

Rank: 1

积分
16
发表于 2007-4-4 20:35:00 | 显示全部楼层

Re:我用 vb.2005写了一个A*寻路算法

开始那几步肯定是有错误,我估计问题很可能因为没有考虑到斜跨一格和直走之间的长度差别,一般斜走的格子距离为直走的1.4倍就可以

1

主题

16

帖子

16

积分

新手上路

Rank: 1

积分
16
发表于 2007-4-4 21:05:00 | 显示全部楼层

Re: 我用 vb.2005写了一个A*寻路算法

我写过的一个
使用鼠标左键画障碍,右键清除障碍

sf_20074421525.rar

109.15 KB, 下载次数:

32

主题

1583

帖子

1589

积分

金牌会员

Rank: 6Rank: 6

积分
1589
发表于 2007-4-4 21:30:00 | 显示全部楼层

Re:我用 vb.2005写了一个A*寻路算法

楼上的不错。
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

作品发布|文章投稿|广告合作|关于本站|游戏开发论坛 ( 闽ICP备17032699号-3 )

GMT+8, 2026-4-12 17:45

Powered by Discuz! X3.4

Copyright © 2001-2021, Tencent Cloud.

快速回复 返回顶部 返回列表