生活中的寻路是这样的↓
游戏中的寻路是这样的↓
我们要绕开障碍物，才能到达终点
我知道没有什么问题是百度解决不了的，于是我搜索‘自动寻路’
终于找到了一个牛逼的算法：A星寻路
把地图分成很多个格子，每个格子里都有一个数字，0代表可走，1代表不可走（还可以2代表遮挡，3代表某某某），如下图所示↓↓
哪里可走哪里不可走，都记录在了一个int型的二维数组里。当然，用一维数组也可以，只要你定好原点和一个方向。
A星算法就是利用了这个数组，当玩家处于某个格子的时候，判断它身边的8个格子里的值，是否可走，可走就继续再寻找格子身边的格子，直到终点。
为了节省时间我直接借鉴（抄）过来了！
抄完后，就这样的↓
很简短（选了个代码最少的- -!）
测试了下，效果还不错
但是马上就发现问题了- -!
如果去终点的路径上怪物太多，距离太远，就会计算好久，卡住不动了- -！
我决定优化下（偷懒的方法- -!）
我发现问题在于格子太多了
比如下图这个城池↓
用计算器算了下，有28万个格子
难道是格子太多，增加了计算时间？
我决定减少格子
于是格子边长从0.5增加到了0.75
格子数少了16万
再测试下，，，还是一样
不行，格子数还要少！ 但是...0.75已经是极限了，再改游戏体验就不好了
而且实际游戏中，障碍物会更多，因为怪物、玩家和宠物，是无法穿越的，会挡住你
更可恶的是它们还是一种会移动的障碍物
角色在事先规划好的路径上行走的时候，可能会被移动过来的怪物挡住了去路
我觉得单纯靠A星算法想节省时间不太容易！
毕竟走到很远的地方，如果地形太复杂，要计算的格子数确实是很多的
比如这张地图↓↓↓
根据算法，城中的格子应该都是要遍历一遍的，算下来有几万个格子吧！？
我整理了下需求，做任务不都是直接点下就传送过去吗？很少让他跑过去的吧！
而且，就算要跑，也可以配置固定的路点数组，就像新手教程一样，按着固定路径走就完事了，如果在跑的时候，路径上有怪物挡住了，再用A星算法绕开就可以了，距离不远，计算量也小，就不卡了。
但是，固定路径有一点不好，就是你必须先走到离你最近的那个路点上，然后才能按照之前定好的路径走，所以有时候走的不是最短距离，但是问题不大，为了游戏不卡，还是可以接受的。
我又打开了网页玩了下‘船新版本’，发现是可以穿越怪物的，这样就大大节省了计算量，是个优化的好方法。
同时还发现，所有人都在一条固定的路径上跑，也没见哪个玩家‘不走寻常路’，大家排成整齐的队列，你追我赶！这个大概就是上面提到的固定路径了。
还可以把地图做简单点，比如上图中的城池，就可以画4个城门。不然，只有一个城门的城池，当你要去城外的时候，就要绕一大圈。
暂时就这样了，最后具体是什么样，下次再更新吧。
