在 Unity 中开发HTN Planner (7)

华容道
1. Test
2. WorldStates
Tasks
Methodes
1. Actions

既然是要做一个通用的AI规划器，那么对于大多数的问题应该都可以给出一个合理的解决方案，因此，为了测试目前的HTN规划器是否可以满足，看看还有什么需要改进的地方，准备了几个例子来进行测试。第一个是前面的过河问题，第二个是华容道小游戏，第三个是模拟人生，第三个是小队战略决策。我们将一个个进行测试，并且不断改进规划器。

华容道

果然，在实现的过程发现了一些不足，在我们应用行动效果的时候，简单的情况我们可以和以前一样直接写在Effects列表上,如

action.Effects = {
		preoperties = {
			Substitute("[b].position.x = [b].position.x + x",env),
			Substitute("[b].position.y = [b].position.y + y",env)
		}
	}

但是，如果是复杂点的情况，如，我们想要，把分之前块所在位置上的标志位清空，然后关系分块移动后的标志位，因为方块的形状有多种，不同形状的分块所占位置都不一样，写在效果中的清空逻辑会比较难看。

因此，我们为世界状态添加新的成员，Utils,在里面编写辅助函数。然后在效果中调用该函数即可。

另外，在这个例子的测试中，得益于低估了这个问题的规模，发现了许多隐患，如之前使用table打印的字符串的秘钥做key,以为万无一失，谁知道漏了一个情况。就算是同一张表，打印出来的字符串也有可能是不一样的（因为lua内部实现导致），因此，除非是序列，否则不能相信每次的表打印的内容一样，因此，对于世界状态的保存要用序列来保存。调试了好久才发现是这个问题的锅。

下面是经过调试后成功输出解决方案的例子。不过，这并没有使用什么算法，而是简单的告诉它，任务目标是把曹操移动到门口，可以执行的操作只有对每个方块进行上下左右的移动，因此，它只会暴力去尝试所有可能的操作，并且记录每个操作到至的结果，以此来避免出现重复状态。

运行后知道这个问题规模的可怕了，不过还好可以得到答案。不过花的时间有点长，64秒左右，然后是499步。

找了一些简单的优化办法。（1）同质

如，对于形状相同的单位都统一看待，就算是它们位置对调也相当于相同的世界状态。 image-center

改完之后，卧槽，

关闭启发函数 9秒，99步
启用启发函数 3秒，57步

启发算法是，优先移动曹操，并且上下左右移动时，尽量选择越靠近出口的操作。然后其它单位则是优先选择远离出口的操作。

（2）对称对于任意对称的状态来说，它们的走法也都一样，因此，求解华容道问题时，可以将对称的状态视为相同的状态，从而直接减少一半的问题规模。 image-center

每添加一个状态表时，把状态表左右镜像也加入状态列表。

local t = {}
	for y=1,#self.Objects[1].flags do
		t[y] = {}
		local list = self.Objects[1].flags[y]
		for x=1,#list do
			t[y][x] = list[#list + 1 - x]
		end

	end
	return {t}

不过因为使用了表的打印字符串和哈希加密算法，检测左右对称后反而让加长了时间，变成4.7秒。因此，过于如何描述世界状态，以及保存出现过的状态这部分还有待改进。

参考链接

【浅析华容道之二】华容道问题搜索求解策略

Test

--====
--测试脚本
--====
package.path = package.path .. ";../?.lua"

require "HTN.Core.LocalParser"
require "HTN.Utils.SubstituteUtility"
require "HTN.Utils.LogUtil"

local methods = require 'HTN.Core.HRD.Methods'
local worldstates = require 'HTN.Core.HRD.WorldStates'
local tasks = require "HTN.Core.HRD.Tasks"
local actions = require "HTN.Core.HRD.Actions"
local planner = require "HTN.Core.Planner"
local planRunner = require "HTN.Core.PlanRunner"
local heuristic = require "HTN.Core.Heuristic"

worldstates:InitGrid()
--table.print(worldstates.Objects)
---[[
local plan = planner:TryGetSolution(worldstates,"GetOut()",tasks,actions,methods,heuristic)
--print(plan)
if plan == nil then
	print("plan == nil")
else
	--table.print(plan)
	PrintWorldState(worldstates,0)
	print("解决方案步数",#plan)
	planRunner:DoPlan(worldstates,plan)
end

WorldStates

--========================
-- WorldStates.lua
--========================
---------------------------------------------------------------------
-- Yimi_HTNs (C) CompanyName, All Rights Reserved
-- Created by: AuthorName
-- Date: 2019-12-05 13:05:58
---------------------------------------------------------------------

-- 约定某个单位的坐标为左下角
-- 坐标原点为左上角
-- 出口位置为(2,5)
---@class WorldStates
local WorldStates = {}

WorldStates.Objects = {
	{
		name = 'A',
		type = 4,
		position = {x = 2,y = 2},
		size = {x = 2,y = 2},
		preference = 0
	},
	{
		name = 'B',
		type = 3,
		position = {x = 1,y = 3},
		size = {x = 2,y = 1},
		preference = 2
	},
	{
		name = 'C',
		type = 3,
		position = {x = 1,y = 4},
		size = {x = 2,y = 1},
		preference = 2
	},
	{
		name = 'D',
		type = 3,
		position = {x = 1,y = 5},
		size = {x = 2,y = 1},
		preference = 2
	},
	{
		name = 'E',
		type = 3,
		position = {x = 3,y = 3},
		size = {x = 2,y = 1},
		preference = 2
	},
	{
		name = 'F',
		type = 3,
		position = {x = 3,y = 4},
		size = {x = 2,y = 1},
		preference = 2
	},
	{
		name = 'G',
		type = 1,
		position = {x = 1,y = 1},
		size = {x = 1,y = 1},
		preference = 1
	},
	{
		name = 'H',
		type = 1,
		position = {x = 1,y = 2},
		size = {x = 1,y = 1},
		preference = 1
	},
	{
		name = 'I',
		type = 1,
		position = {x = 3,y = 5},
		size = {x = 1,y = 1},
		preference = 1
	},
	{
		name = 'J',
		type = 1,
		position = {x = 4,y = 5},
		size = {x = 1,y = 1},
		preference = 1
	}
}
WorldStates.Utils = {
	UpdateFlags = function(_Grid,_tile,_Flags)
		for x = 1, _tile.size.x do
			for y = 1, _tile.size.y do
				local col = _tile.position.x + x - 1
				local row = _tile.position.y - (y - 1)

				_Grid.flags[row][col] = _Flags
			end
		end		
	end,
	IsCanHorizontalMove = function(_Grid,_t,_dir)

		local IsEmpty = function(_x,_y)
			if _x < 1 or _x > 4 or _y < 1 or _y > 5 then
				return false
			else
				return _Grid.flags[_y][_x] == 0
			end
		end

		for i = 1, _t.size.y do

			local px = 0
			local py = _t.position.y - (i - 1)

			if _dir > 0 then
				-- 测试右边会不会出界
				px = _t.position.x + (_t.size.x - 1) + _dir

			else
				-- 测试左边会不会出界
				px = _t.position.x + _dir
			end
			if not IsEmpty(px,py) then
				return false
			end
		end
		return true
	end,
	IsCanVertialMove = function(_Grid,_t,_dir)
		local IsEmpty = function(_x,_y)
			if _x < 1 or _x > 4 or _y < 1 or _y > 5 then
				return false
			else
				return _Grid.flags[_y][_x] == 0
			end
		end

		for i = 1, _t.size.x do
			local px = _t.position.x + (i - 1)
			local py = 0

			if _dir < 0 then
				-- 测试上边会不会出界
				py = _t.position.y - (_t.size.y - 1) + _dir
			else
				-- 测试下边会不会出界
				py = _t.position.y + _dir
			end
			if not IsEmpty(px,py) then
				return false
			end
		end
		return true
	end,
	TilePreference = function(_tile)
		local dis = math.abs (_tile.position.x - 2 + _tile.position.y - 5)
		return dis + _tile.preference
	end,
	DistanceFromGate = function(_tile,_x,_y)
		local dis = math.abs(_tile.position.x + _x - 2 + _tile.position.y + _y - 5)
		if(_tile.type == 4) then			
			return dis
		else
			return 100 - dis
		end
	end
}

function PrintWorldState(_ws,_depth)
	print(string.rep("=",_depth*4).."=============================")
	print(string.rep(" ",_depth*4)..table.concat(_ws.Objects[1].flags[1],",") )
	print(string.rep(" ",_depth*4)..table.concat(_ws.Objects[1].flags[2],",") )
	print(string.rep(" ",_depth*4)..table.concat(_ws.Objects[1].flags[3],",") )
	print(string.rep(" ",_depth*4)..table.concat(_ws.Objects[1].flags[4],",") )
	print(string.rep(" ",_depth*4)..table.concat(_ws.Objects[1].flags[5],",") )
	print(string.rep("=",_depth*4).."=============================")
end

function WorldStates:CacheMainData()
	return self.Objects[1]
	--return table.concat(self.Objects[1].flags[1],",")..
	--table.concat(self.Objects[1].flags[2],",")..
	--table.concat(self.Objects[1].flags[3],",")..
	--table.concat(self.Objects[1].flags[4],",")..
	--table.concat(self.Objects[1].flags[5],",")
end

function WorldStates:InitGrid()
	local grid = {
		name = "Grid",
		flags = {
			{0,0,0,0},
			{0,0,0,0},
			{0,0,0,0},
			{0,0,0,0},
			{0,0,0,0}
		}

	}

	for i, v in ipairs(self.Objects) do
		self.Utils.UpdateFlags(grid,v,v.type)
	end
	table.insert(self.Objects,1,grid)
end
return WorldStates

Tasks

local Tasks = {}


function Tasks:GetTask(_taskdecl)
	local name, p = splitFunc( _taskdecl)
	local task = self[name](table.unpack(p))
	task.taskDecl = _taskdecl
	return task
end
Tasks.GetOut = function ( ... )
	local input = {...}
	local env = setmetatable(
		{},
		{__index = _G}
	)
	local task = {}
	task.IsPrimitive = false
	task.Methods = {
		Substitute("MoveTile(A)",env),
		Substitute("MoveTile(B)",env),
		Substitute("MoveTile(C)",env),
		Substitute("MoveTile(D)",env),
		Substitute("MoveTile(E)",env),
		Substitute("MoveTile(F)",env),
		Substitute("MoveTile(G)",env),
		Substitute("MoveTile(H)",env),
		Substitute("MoveTile(I)",env),
		Substitute("MoveTile(J)",env),
		Substitute("End()",env)
	}
	return task
end
Tasks.TestDir = function ( ... )
	local input = {...}
	local env = setmetatable(
		{
			t = input[1]
		},
		{__index = _G}
	)
	local task = {}
	task.IsPrimitive = false
	task.Methods = {
		Substitute("Move_Vertical_2Step([t],1)",env),--Down
		Substitute("Move_Vertical_2Step([t],-1)",env),--Left
		Substitute("Move_Vertical_2Step([t],-1)",env),--Up
		Substitute("Move_Vertical_2Step([t],1)",env),--Right		
		Substitute("Move_Vertical_1Step([t],1)",env),--Down
		Substitute("Move_Horizontal_1Step([t],1)",env),--Right
		Substitute("Move_Vertical_1Step([t],-1)",env),--Up
		Substitute("Move_Horizontal_1Step([t],-1)",env)--Left		
	}
	return task
end

Tasks.Move = function ( ... )
	local input = {...}
	local env = setmetatable(
		{
			t = input[1],
			x = input[2],
			y = input[3]
		},
		{__index = _G}
	)
	local task = {}
	task.IsPrimitive = true

	return task
end

return Tasks

Methodes

local Methods = {}

function Methods:GetMethods ( _methoddecl )

	local name, p = splitFunc( _methoddecl)

	return self[name](table.unpack(p))
end

Methods.UseHeuristic = true

Methods.MoveTile = function(...)
	local input = {...}
	local env = setmetatable(
		{
			t = input[1]
		},
		{__index = _G}
	)
	local method = {}

	method.preconds = {
		valuelimits = {
			Substitute("not (A.position.x == 2 and A.position.y == 5)",env),
			Substitute("IsCanVertialMove(Grid,[t],1) or IsCanVertialMove(Grid,[t],-1) or IsCanHorizontalMove(Grid,[t],1) or IsCanHorizontalMove(Grid,[t],-1)",env)
		}
	}
	method.subtasks = {
		Substitute("TestDir([t])",env),
		Substitute("GetOut()",env)
	}
	method.score = Substitute("return TilePreference([t])",env)
	return method
end

Methods.Move_Vertical_1Step = function(...)
	local input = {...}
	local env = setmetatable(
		{
			t = input[1],
			d = input[2]
		},
		{__index = _G}
	)
	local method = {}

	method.preconds = {
		valuelimits = {
			Substitute("IsCanVertialMove(Grid,[t],[d])",env)
		}
	}
	method.subtasks = {
		Substitute("Move([t],0,[d])",env)
	}
	method.score = Substitute("return DistanceFromGate([t],0,[d])",env)
	return method
end
Methods.Move_Vertical_2Step = function(...)
	local input = {...}
	local env = setmetatable(
		{
			t = input[1],
			d = input[2]
		},
		{__index = _G}
	)
	local method = {}

	method.preconds = {
		valuelimits = {
			Substitute("IsCanVertialMove(Grid,[t],[d])",env),
			Substitute("IsCanVertialMove(Grid,[t],[d] * 2)",env)
		}
	}
	method.subtasks = {
		Substitute("Move([t],0,[d] * 2)",env)
	}
	method.score = Substitute("return DistanceFromGate([t],0,[d] * 2)",env)
	return method
end
--水平移动
Methods.Move_Horizontal_1Step = function(...)
	local input = {...}
	local env = setmetatable(
		{
			t = input[1],
			d = input[2]
		},
		{__index = _G}
	)
	local method = {}

	method.preconds = {
		valuelimits = {
			Substitute("IsCanHorizontalMove(Grid,[t],[d])",env)
		}
	}
	method.subtasks = {
		Substitute("Move([t],[d],0)",env)
	}
	method.score = Substitute("return DistanceFromGate([t],[d],0)",env)
	return method
end
Methods.Move_Horizontal_2Step = function(...)
	local input = {...}
	local env = setmetatable(
		{
			t = input[1],
			d = input[2]
		},
		{__index = _G}
	)
	local method = {}

	method.preconds = {
		valuelimits = {
			Substitute("IsCanHorizontalMove(Grid,[t],[d])",env),
			Substitute("IsCanHorizontalMove(Grid,[t],[d] * 2)",env)
		}
	}
	method.subtasks = {
		Substitute("Move([t],[d] * 2,0)",env)
	}
	method.score = Substitute("return DistanceFromGate([t],[d] * 2,0)",env)
	return method
end

Methods.End = function(...)
	--local input = {...}
	local env = setmetatable(
		{},
		{__index = _G}
	)
	local method = {}
	method.preconds = {		
		valuelimits = {
			Substitute("A.position.x == 2 and A.position.y == 5",env)
		}
	}
	method.score = Substitute("return 0",env)
	return method
end

return Methods

Actions

local Actions = {}
function Actions:GetAction(_actiondecl)
	local name, p = splitFunc( _actiondecl)
	return self[name](table.unpack(p))
end

Actions.Move = function(...)
	local input = {...}
	local env = setmetatable(
		{
			t = input[1],
			x = input[2],
			y = input[3]
		},
		{__index = _G}
	)
	local action = {}
	action.Effects = {
		preoperties = {
			Substitute("UpdateFlags(Grid,[t],0)",env),
			Substitute("[t].position.x = [t].position.x + [x]",env),
			Substitute("[t].position.y = [t].position.y + [y]",env),
			Substitute("UpdateFlags(Grid,[t],[t].type)",env)
		}
	}
	function action:Execute(_ws)
		-- TODO 实现
		self.End()
	end
	return action
end

return Actions

在 Unity 中开发HTN Planner (7)

Categories

Tags

Table of Contents

华容道

Test

WorldStates

Tasks

Methodes

Actions