【高分求算法】JS图形，找两点之间的最短路径以及自动避开障碍，帮顶有分

Question

http://www.51js.com/viewthread.php?fpage=1&tid=18944
看看星际的路径算法部分吧，呵呵干吗要折线啊

Answer 1

回复人： ttyp(愿赌服输) ( ) 信誉：105  2004-12-30 09:55:00  得分: 0  
 
 
   http://www.51js.com/viewthread.php?fpage=1&tid=18944
看看星际的路径算法部分吧，呵呵干吗要折线啊
  
＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝
他这个太复杂了，看不明白
我这个只要注意避开两样东西就可以了
一个是表格，一个是现有的线条

Answer 2

那可以用一个最简单的方法~~
我不清楚你现在如何绘制图象，所以我说的方法里关于绘制都需要你自己想办法了~首先找到直线的最短路径，然后让点延这个直线行走，同时绘制，当遇到另一条直线时（就是碰撞检测），绘制一个曲线，VISIO用过就知道什么意思。当遇到是图形时，就判断这个图形的边缘，而这个绘制的点就向最进的那个边缘移动，同时绘制，一直绘制到这个点可以再次不与图形碰撞，可向目标点运动为止，则继续直接向目标点运动。这个是最简单的路径查找方法，在你这里是可以用的，如果用在游戏里，可能就会出现《血狮》那个游戏里出现的卡死到某个地方出不来的情况。当然，用星际的A*算法是最好的，这样绘制出来的线条是最短而且最好看的~~~

Answer 3

我做过，这把发财了。几个问题先问清楚：
生成各表的方式，我是指，比如各表外面套了一个大table
各表是否可移动我用这个来画办公自动化的流程图，倒跟你这个类似

Answer 4

to 椅子：我这些表都是套在一个SPAN里面的，这些SPAN放在一个DIV里面，让他们自由排列
表不可以移动，都是固定的to 懒猫：
我用的是VML画线，VML里面有一个PATH，可以直接指定线的路径，就是我要得到的几个转折点坐标
现在没多少时间去研究什么A*算法
而且在网页里面还得考虑效率问题，搞不好网页就死在那里了
如果用点来追溯，这样在有几十个表，上百个关系的时候，速度可能会很慢

Answer 5

A(x1,y1) ,B(x2,y2),常量k1=k2=1（使线路美观）
1 根据两点坐标求出三角形两边
  有两种可能，随便哪种都可以
  C(x3,y3)
  x3=x2-k1 ,y3=y1
  相应可求出D(x4,y4)点
  x4=x3,y4=y2
 
2 在AC、BC中判断是否有障碍
  无障碍情况可根据C、D得出线路
  有障碍情况：
  计算障碍高度，根据障碍点居上还是居下来决定是爬升还是降落。
  设爬升点是A1(x5,y5)
  x5=障碍左边缘-k1,y5=x3+障碍上边缘+k1
 计算A1到B的，重复1我下午有课，得赶紧走了，我写了一个演示，但没写完，原理是利用table在网页中构造一个25*25的网格，利用合并单元格的操作生成出表（字段），线条用改变网格的bordercolor（上下左右）来实现。
这样的好处在于我判断障碍和得出障碍的四个边缘非常容易。
  

Answer 6

我说的点是虚拟的点，比如你将你的页面分成16X16的区，然后每个图形都会占有一个或几个区，但是因为是你自己划分的区，则区的边界位置已经知道。然后在绘制线条的时候通过判断来绕过这些区域，就是当碰到要通过区域的情况时，就在区域边界放置一个折线顶点。并延着不可通过的区域的边界绘制。直到可以直接向目标点（区域）绘制为止。当然这个区你划分越大，速度越快，但是越不精确~~~
不知道你理解我的意思没有~~~这里的点是一个抽象的点，并不是像素的点~~~如何绘制，采用任何方法都是一样的~~~和用VML还是组件无关~~

Answer 7

可以采用连续变形法来求最短路径：
  已知：初始点A和结束点B的坐标
  步骤：
   1  在A、B两点之间拉直线段AB
   2  求出跟所有障碍物边界的所有的交点，共有n个 (M1 ,M2,.....Mn)
   3  循环交点直到交点数目为0
      a）把第i个交点调整到两个障碍物之间，
      b) 计算新产生的交点，调整交点数组
   4  重复步骤3，直到交点数目为0