转帖：A*寻路算法介绍
介绍
你是否在做一款游戏的时候想创造一些怪兽或者游戏主角，让它们移动到特定的位置，避开墙壁和障碍物呢？
如果是的话，请看这篇教程，我们会展示如何使用A寻路算法来实现它！
在网上已经有很多篇关于A寻路算法的文章，但是大部分都是提供给已经解基本原理的高级开发者的。
本篇教程将从最基本的原理讲起。我们会一步步讲解A寻路算法，幷配有很多图解和例子。
不管你使用的是什么编程语言或者操作平台，你会发现本篇教程很有帮助，因为它在非编程语言的层面上解释算法的原理。稍后，会有一篇教程，展示如何在Cocos2D iPhone 游戏中实现A算法。
现在找下到达一杯咖啡因饮料和美味的零食的最短路径，开始吧！
一只探路猫
让我们想象一下，有一款游戏，游戏中一只猫想要找到获取骨头的路线。
“为什么会有一只猫想要骨头？！”你可能会这么想。在本游戏中， 这是一只狡猾的猫，他想捡起骨头给狗，以防止被咬死！
现在想像一下下图中的猫想找到到达骨头的最短路径。
不幸的是，猫不能直接从它当前的位置走到骨头的位置，因为有面墙挡住去路，而且它在游戏中不是一只幽灵猫！
游戏中的猫同样懒惰，它总是想找到最短路径，这样当他回家看望它的女朋友时不会太累。
但是我们如何编写一个算法计算出猫要选择的那条路径呢？A*算法拯救我们！
简化搜索区域
寻路的第一步是简化成容易控制的搜索区域。
怎么处理要根据游戏来决定。例如，我们可以将搜索区域划分成像素点，但是这样的划分粒度对于我们这款基于方块的游戏来说太高（没必要）。
作为代替，我们使用方块（一个正方形）作为寻路算法的单元。其他的形状类型也是可能的（比如三角形或者六边形），但是正方形是最简单并且最适合我们需求的。
像那样去划分，我们的搜索区域可以简单的用一个地图大小的二维数组去表示。所以如果是25*25方块大小的地图，我们的搜索区域将会是一个有625个正方形的数组。如果我们把地图划分成像素点，搜索区域就是一个有640，000个正方形的数组（一个方块是32*32像素）！
现在让我们基于目前的区域，把区域划分成多个方块来代表搜索空间（在这个简单的例子中，7*6个方块 = 42 个方块）。