在项目中遇到了自动寻路的需求，于是决定开始学习一下A星，对于A星我也没有深究，只能说是勉强搞定了需求，在这和大家分享一下，相互进步，

A星有个公式 f(x) = g(x) + h(x) ,搞清楚这个公式就好办了，f(x)就是当前位置到下一个位置的总价值，g(x)表示实际价，这是说这一部分代价是确定的，h(x)表示估价值，就是说我从下一个位置到到终点的代价是未知的，所以叫估价值，如图中所示，黑色格子表示当前位置，绿色格子表示下一步可能到达的位置，即上、下、左、右这几个方向，红色格子表示终点，褐色表示障碍物，现在要从黑色格子到达红色格子，那么黑色格子的下一步肯定是绿色格子当中的一个，黑色格子到绿色格子之间是相挨着的，所以我们可以很明确的知道它的实际代价为1（移动一步的代价）即g(x)，绿色格子到红色格子之间隔着很长的距离，中间还有障碍物，所以这个代价是未知的，即h(x)，所以总的代价就为f(x) = g(x) + h(x)，我们看到周围有4个绿色的格子，到底走那一步比较好呢，所以我们要把这4个格子的f(x)值都求出来，然后进行排序，选择f(x)值最小的，即总代价最少的那个格子，以此方法继续下去，直到到达终点 或者 地图上没有绿色格子了

下面来看一下这个工具类，g(x)和h(x)要选的比较合适，一般就是采用的曼哈顿算法，即两点在x方向和y方向的距离之和，

-- Filename: PathUtil.lua
-- Author: bzx
-- Date: 2014-07-01
-- Purpose: 寻路

module("PathUtil", package.seeall)

local _map_data         -- 地图数据
local _open_list        -- 开放节点
local _open_map         -- 开放节点，为了提高性能而加
local _close_map        -- 关闭节点
local _deleget          -- 代理
local _dest_point       -- 目标点
local _start_point      -- 起点
local _path             -- 路径

-- 寻找路径
--[[
deleget = {
    g = function(point1, point2)
        -- add your code
        -- 返回点point1到点point2的实际代价
    end
    h = function(point1, point2)
        -- add your code
        -- 返回点point1到点point2的估算代价
    end
    getValue = http://www.mamicode.com/function(j, i)>
下面是工具类PathUtil的用法
   local deleget = {}
        deleget.g = function(point1, point2)
            return math.abs(point1.x - point2.x) + math.abs(point1.y - point2.y)
        end
        deleget.h = deleget.g
        deleget.getValue = http://www.mamicode.com/function(j, i)>
_path就是我们找到的路径，起点为最后一个元素，终点为第一个元素，由于项目中的地图比较简单，因此我也没有过于深究，关于A星的介绍网上的资料还有很多，我这一般就显得太简略了，初次接触自动寻路，希望大神们多多指教
另附广告一条：出售美容品的微店  如需详细了解可加我姐姐QQ：937893128    各路大神 给你的老婆，女朋友，小三，小四，小五......还有你的众多基友买点吧