Algorithm 版 (精华区)

发信人: shs (花雨飘), 信区: Algorithm
标  题: 游戏中最佳路径的问题
发信站: 哈工大紫丁香 (Sat Sep  9 12:56:37 2000), 转信

昨天朋友问我游戏中最佳路径的问题。我思考了一下，得出一些结果，自我
感觉不错。一时兴起就发在这儿。
首先给出几个概念：
   距离：两个点的距离是指由点A到点B的最少步数。
         如果没有障碍物，两个点的距离应该是 dx+dy ( dx=abs(x1-x2) , dy同 )
   凸域：凸域是指满足： 其中任何两个点的距离都等于dx+dy的 一个区域(*)。
   最大凸域：凸域的边界再扩大便是障碍物。或不能满足(*)
算法预备：
   1：在load地图时首先将地图划分为若干个最大凸域。(结果用每个点属于哪个凸域来描述)
   2：对得到的凸域两两之间建立若干条最佳路径。(如果不连通只好不键)
算法实现：
   从点s到点e的最佳路径这样获得：
   1：如果s,e同属于一个凸域，那么往x或y方向靠拢至少有一个可行 行之
   2：如果s,e不同属于一个凸域，对凸域S,E的所有已经建立的路径(s1,…,e1)
   ,……, (sn,…,en) 搜索找出使得 ( s,si,…,ei,e )最短的路径。
   ( 如果 n==0 返回不能到达 ) ;
完毕 


--
※ 来源:　武汉白云黄鹤站 bbs.whnet.edu.cn. [FROM: 202.114.113.240] 
※ 修改:．shs 于 Sep  9 12:54:21 修改本文．[FROM: as.hit.edu.cn]
--
※ 转寄:．武汉白云黄鹤站 bbs.whnet.edu.cn．[FROM: as.hit.edu.cn]

--
☆ 来源:．哈工大紫丁香 bbs.hit.edu.cn．[FROM: shs.bbs@bbs.whnet.ed]