module('Point',package.seeall)
-- require("script/battle/BattleCommon")
--计算F值
function CalcF( point )
	point.F = point.G + point.H
end

function create( posId )
	local point = {}
	point.parentPoint = {}
	point.step = 1 --用于计算h值
	local x,y = BattleCommon.convertPosIdToCoord(posId)
	point.F = 0
	point.G = 0
	point.H = 0
	point.X = y            --point.X范围[1,5]
	point.Y = x            --point.Y范围[1,8]
	point.posId = posId
	point.CalcF = CalcF
	
	return point
end

return Point

--根据一个table创建一个地形
function create( tb )
	local maze = {}
	maze.step = 1 --格子与格子的基本距离,用于计算H值
	maze.mazeArray = tb
	maze.openList = TabledArray.create() --开启列表
	maze.closeList = TabledArray.create() --关闭列表
	maze.findPath = findPath
	return maze
end

module('Maze',package.seeall)
require("script/battle/TabledArray")
require("script/battle/BattleCommon")
require ("script/battle/Point")

-- --获取列表中F值最小的点
function getMinPoint( pointsList )
	local minPoint = pointsList.tbl[1]
	for i = 1,pointsList:getSize() do
		if minPoint.F > pointsList.tbl[i].F then
			minPoint = pointsList.tbl[i]
		end
	end
	return minPoint
end

-- --检测是否有阻挡,没有阻挡为true
function checkBlock( maze,x,y,roleFlag)              --x范围[1,5]  y范围[1,8]
	if roleFlag == BattleCommon.BATTLE_GROUP_ALLIES then --我方阵营
		if maze.mazeArray[x][y][1] == 0 or maze.mazeArray[x][y][1] == 1 then
			return true  --没有阻挡
		else
			return false   
		end
	elseif roleFlag == BattleCommon.BATTLE_GROUP_ENEMY then
		if maze.mazeArray[x][y][1] == 0 or maze.mazeArray[x][y][1] == 2 then
			return true  --没有阻挡
		else
			return false   
		end
	end
end

-- --列表中是否包含x,y的点
function existsXY( list,y )
	if list:getSize()>0 then
		for i,point in pairs(list.tbl) do
			if point.X == x and point.Y == y then
				return true
			end
		end
	end
	return false
end

--列表中是否包含某个点
function existsPoint( list,point )
	for i,p in pairs(list.tbl) do
		if (p.X == point.X) and (p.Y == point.Y) then
			return true
		end
	end
	return false
end


-- --检测能达到的点
function canReach( maze,startPoint,roleFlag)
	if (not checkBlock(maze,roleFlag)) or  existsXY(maze.closeList,y) then --关闭列表中包含这个点或者有阻挡
		return false
	else
		if (math.abs(x-startPoint.X)+math.abs(y-startPoint.Y) == 1 ) then
			return true
		end
	end
end

-- --获取相邻的点
function getSurroundPoints( maze,point,roleFlag )
	local surroundPoints = TabledArray.create()
	for i = point.X - 1,point.X + 1 do
		for j=point.Y - 1,point.Y + 1 do
			if i>0 and i<6 and j > 0 and j < 9 then  --排除超过表姐
				if BattleCommon.distanceFromTo(point.posId,BattleCommon.convertToPositionId(j-1,i-1)) < 2 then
					if canReach(maze,i,j,roleFlag) then
						surroundPoints:append(maze.mazeArray[i][j][2])
					end
				end
			end
		end
	end
	return surroundPoints   --返回point点的集合
end

-- --计算G值
function CalcG( point )
	local G = point.G
	local parentG = 0
	if point.parentPoint then
		parentG = point.parentPoint.G
	end
	return G + parentG
end

function foundPoint( tempStart,point )
	local G = CalcG(point)
	if G < point.G then
		point.parentPoint = tempStart
		point.G = G
		point:CalcF()
	end
end


function notFoundPoint( maze,tempStart,point )
	point.parentPoint = tempStart
	point.G = CalcG(point)
	point:CalcF()
	maze.openList:append(point)
end

function getPoint( list,data )
	for i,point in pairs(list.tbl) do
		if point.posId == data.posId then
			return point
		end
	end
	return nil
end

-- --寻找路径(起始路径)
local function findPath( maze,endPoint,roleFlag)
	maze.openList:append(startPoint)
	while maze.openList:getSize() ~= 0 do
		--找出F的最小值
		local tempStart = getMinPoint(maze.openList)
		maze.openList:removeById(1)
		maze.closeList:append(tempStart)
		--找出它相邻的点
		local surroundPoints = getSurroundPoints(maze,roleFlag)
		for i,point in pairs(surroundPoints.tbl) do
			if existsPoint(maze.openList,point) then
				--计算G值,如果比原来大,就什么都不做,否则设置他的父节点为当前节点,并更新G和F
				foundPoint(tempStart,point)
			else
				--如果他们不再开始列表里面,就加入,并设置父节点,并计算GHF
				notFoundPoint(maze,point)
			end
		end
		--如果最后一个存在则返回
		if getPoint(maze.openList,endPoint) then
			return getPoint(maze.openList,endPoint)
		end
	end
	return getPoint(maze.openList,endPoint)
end


--根据一个table创建一个地形
function create( tb )
	local maze = {}
	maze.step = 1 --格子与格子的基本距离,用于计算H值
	maze.mazeArray = tb
	maze.openList = TabledArray.create() --开启列表
	maze.closeList = TabledArray.create() --关闭列表
	maze.findPath = findPath
	return maze
end


return Maze

function printPath( presentPoint )
	local pathArray = TabledArray.create()
	while presentPoint do
		pathArray:preppend(presentPoint.posId)
		presentPoint = presentPoint.parentPoint
	end
	local startPoint = pathArray:get(2)
	local endPoint = pathArray:getLast()
	
	cclog(startPoint)
	cclog(endPoint)
	cclog("从"..startPoint.."到"..endPoint.."的路径是:")
	for i,p in pairs(pathArray.tbl) do
		cclog(p)
	end
end

	local array = battleBoard:createBoxPoints(cRole:getFlag(),40)
	local maze = Maze.create(array)
	local startPoint = Point.create(cRole:getPositionId())
	local endPoint = Point.create(40)
	local presentPoint = maze:findPath(startPoint,cRole:getFlag())
	printPath(presentPoint)