注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

没有你的天堂

Cobra'Nails' Blog.

 
 
 

日志

 
 

Pathfinding... how in the f***?  

2011-01-06 10:36:00|  分类: 光明石碑 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

网上看来的:极速pathfinding


Re: Pathfinding... how in the f***? Posted by KMS on 21 Jul 2000 at 5:58 PM

First of all, I heard of something called A*, its supposed to be the de-facto algorithm for path finding, heres a link that will get you started:

http://theory.stanford.edu/~amitp/GameProgramming/

 

Now, a few years ago I was writing a Dune 2 clone, I managed to write a path finding code based on the seed fill algorithm that worked fine for me, testing showed it to be as good as Westwood's Dune and C&C (good pathfinding) and way much better than Blizzard's Warcraft and Startcraft (lousy pathfinding), here are the steps:

 

1. Go from source to target using a recursive seed fill code, no need to go in all 8 directions (or 6 for hexagons), just always go towards the best move -for example, if target is to the north east, go to x-1, y-1. 

2. When best direction is obstacle, just the 2 second best move, clock wise first.

3. Set a threshold to bang out when a path can not be found.

4. Clean up the path youve just found by walking through the grid points looking for straight lines short cuts to any other point that hasnt been moved on yet, thus eleminating zig-zags.

5. Save this path, PathOverhead = number of steps.

6. Repeat 1-4 this time from target to source with counter-clock wise always for 2.

7. Compare both pathes and take the one with less PathOverHead.

 

It seems like a lot of work, but it worked fine in my 12 mhz 286 machine, I had 100+ objects at the same time calculating their pathes at run time with no problem, the fill seed algo is a stack pig, so maybe implementing it using a de-queue is a wise thing to do.

 

Also my implementation used more than just number of steps to calculate PathOverHead, for example I had certain over head for each terrain block, is it close to enemy fire, etc.

 

Needless to say I kept refining the path algorithm and forgot about the rest of game!

 

Sorry this was too long, but it stroke a chord with me.

 

Good luck.

  评论这张
 
阅读(7)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018