谁会游戏中寻路的算法？

Question

谁会游戏中寻路的算法？
地图是一张BMP图片，2色的，黑表示不能通过，白表示可以通过。
地图内容是很不规则的，给定起点和终点,找出最短的路径。谁知道这种寻路的算法？
最好是DELPHI的。

Answer 1

缺少了
TSeSkinScrollBox
TSeSkinPanel不是说它没用，是不实用。只能用小范围的地图。

Answer 2

看看数据结构的图的最短路径
5.5 最短路径问题 用Dijkstra算法,还是很简单的
http://www.cs.ecnu.edu.cn/assist/js04/ZJS045/ZJS04505/zjs0450500.htm
这里有讲解,很简单void dijkstra (int ad[ ][], int k, int pre[ ], int dist[ ], int n) { // 求有向图以顶点Vk为始点到其他各项顶点间的最短路径的dijkstra算法 int , j, p,min; k=k－1; for (i=0; i<n; i++) // 初始化 { dist[i]=ad[k][i]; if (dist[i]<MAX) pre[i]=k+1; else pre[i]=0; } pre[k]=0; dist[k]=0; // 数组dist和pre初始化 ad[k][k]=1; // Vk加入到第一组 for (j=0; j<=(n－1); j++) { min=MAX; p=－1; for(i=0;i<=(n-1);i++)if(ad[i][i]= =0 && dist[i]<min) { p=i; min=dist[i]; } // 在第二组中选距离值最小的顶点 if (p = = －1) break; // 以没有顶点可往第一组加 else 
ad [p][p]=1; // 把第二组中选出的距离最小的顶点加到第一组中 for {i=0; i<m; i++} if (ad[i][i] = =0 && (min+ad[p][i]<dist[i]) { dist[i]=min+ad[p][i]; pre[i]=p+1; } // 更新第二组中的当前距离值和路径上前以顶点序号} } 

Answer 3

Dijkstra算法
好像也不行！
因为它要有一个现成的点的列表。但这里没有。还有它没考虑两个点之间是否有阻碍物的情况。
有时尽管两点距离短，但中间有阻碍物则仍无效。

Answer 4

可用盲目搜索中的深度优先算法，即一般迷宫问题的延单边行走方法。这样比较费时间但算法简单。也可用A*算法，求解速度快但算法麻烦。
    delphi的算法稍后给你。

Answer 5

本来我也想在主页中放个A*寻径的教程的，无奈实在没时间写那些文字：P
我完成了例程，可以从这里下载：http://www.17delphi.org/download/sample/SimplePathing.rar这是很基本的AI技术，已经被人用烂了：）
用google可以搜出一大堆相关资料的，我在seabug大人处找到了一些：
http://www.gameres.com/Articles/Program/Abstract/a8first_2.htm
http://www.gameres.com/Articles/articles.asp?style=f
自己慢慢研究吧：）ps: 我的例程中基本上是没有注释的:p enjoy it :)

Answer 6

刚才才仔细看了你的贴，呵呵，原来你觉得A*慢。
A*并不慢，关键是看你如何优化，更关键是看你如何运用。
地图太大可以考虑先把地图拆成小块，先确定目的地在哪个小块，然后找出从本小块到该目的小块的路径，最后就是小块之内的A*了。
——临时想到的，希望对你有所启发:P

Answer 7

倒，原来你用来做外挂的后悔ing >~<