推箱子解法演算
2019-08-16 12:28阅读：
第一部分
推箱子是个古老的游戏，几乎都忘了。近日偶然间从电视中看到，也不知怎地就萌发弄个求解的算法。想想无非就是个搜索，采用广度搜索，应该更好，可得到最佳走法。说干就干，大约化了3-4小时搞了个初稿。执行吧，当然首次就能通过那是神仙，这在情理之中，不过调试时还是发现想简单了。
箱子限定在狭小的空间内推动，通常也就在10*10方阵甚至更小的范围内，再加上墙的限制复杂度应该不大，时间和空间应该都不是问题。然调试发现，队列数量竟然近万，快照近20万，这比开始想的差太远了。当然后来发现，这还不是最大的，所以暂不管是否通过，先考虑优化设计免得以后作较大调整，毕景还只刚开始。
首先是地图的设计，起初单元格采用建立一个类，内设若干属性，如空地、墙壁和箱子是一个属性，是否目标位又是一个属性等等。这样的考虑用来设计推箱子游玩是没问题的，但用来求解显然不是最佳的。经思考最终觉得每个单元格完全可以采用一个字符来表示，约定如下：
0 表示空地 Space
1 表示墙壁 Wall
2 表示箱子 Box
3 表示人 People
4 表示目标 Desti
6 表示箱子和目标重叠 Box_Desti
7 表示人和目标重叠
People_Desti
如
此一来，地图占用空间得到了很大压缩。
其次快照的实现，快照记录人的位置、方向和当前地图。其实人的位置不同、方向不同，但地图可能是相同的，所以完全可以将地图独立出来贮存，快照只须对其引用即可。
经过以上两步，空间上得到了很大优化。当然还有进一步优化的空间，因为在演算时，地图实际仅用到Space、Wall和Box，即0、1、2，所以用2个位Bit即可。其实内存条便宜得很，没必要这样斤斤计较。事实上c#语言的字符char是16位而不是8位，节省的空间也没你想象的那么多。所以内存空间优化就此打住。
推箱子求解设计存在着4种地图，1是设计图，2是起始图，3是目标图，4是演算过程中产生的中间地图。其实从类型上讲只有2种，设计图和其他图。设计图中可能包含前面约定的6个属性值，而其他图仅包含Space、Wall和Box等3个属性值，可以从设计图中分离出起始图和目标图，演算的过程就是从起始图走到目标图的过程。
快照中记录了人的位置和方向，用于确定走过的路就不要走了。
下面是核心代码：
public void
ProMain()
{
MapSet.Group.Add(StartMap);
//起始图
Snapshot player =
new Snapshot() //Player
起始位置
{
Map = StartMap,
Player = new
Player()
{
Pos =
DesignMap.Player().Position()
//人的开始位置
}
};
PhotoSet.Add(player);
//首个快照
if
(BreadthSearch(player) == false)
//false
没有完成，继续
{
while (Queues.Count >
0)
//队列存在时处理
{
if
(Cancel == true)
//强行结束
break;
player = Queues.Dequeue();
//出队列
if
(BreadthSearch(player) == true)
//指定处理
break;
}
}
}
private bool
ExploreForward(Snapshot parent, People
direct)
{
parent.Player.DirectSet.Add(direct);
//记录方向
People front =
parent.Player.People + direct;
int
fv = parent.Map[front];
//获得当前位置值
if
(fv >= 0)
{
if (fv == Map.BOX)
//是
Box
{
#region
前面是 Box 时处理
People next =
new People(front)+direct;
//前面的前面next
int
nv = parent.Map[next];
if
(nv == Map.SPACE)
//可以往前推
{
#region 前面的前面是
Space 处理
Map map = parent.Map.Clone();
//采用复件
map[front] = Map.SPACE;
map[next] = Map.BOX;
if (map ==
DestiMap) //当前图已经和目标图相同
{
Result.Clear();
//清除以前内容
Result.Add(front);
Player player = parent.Player;
while
(player != null)
{
Result.Add(player.People);
player = player.Parent;
}
Result.Reverse();
//结果取反
Finish =
true;
//正常结束
return
true;
}
ProSnapshot(parent.Player, map, front.Position(),
direct);
#endregion 前面的前面是
Space 时处理
}
#endregion 前面是 Box
时处理
}
else if (fv
== Map.SPACE)
{
#region
前面是 Space 处理
ProSnapshot(parent.Player,
parent.Map, front.Position(), direct);
#endregion 前面是 Space
处理
}
}
return
false;
}
private void
ProSnapshot(Player parent, Map map,
ushort pos, People direct)
{
int
index = MapSet[map];
//存在旧地图时引用旧地图
if
(index >= 0)
map = MapSet.Group[index];
else
MapSet.Group.Add(map);
//不存在添加
index =
PhotoSet.FindSameIndex(map, pos);
//继续找
if
(index >= 0)
//找到位置和图皆相同的
return;
//出现重复，没必要继续
Snapshot snapshot =
new Snapshot()
//生成一个全新的快照
{
Main = this,
Map = map,
Player = new
Player()
{
Parent =
parent,
Pos = pos
}
};
Queues.Enqueue(snapshot);
//入队列
PhotoSet.Add(snapshot);
//加入快照
}
广度搜索需要借助队列，出现新情况时生成新快照加入队列Queues。
推箱子算法实现链接(百度盘):
https://pan.baidu.com/s/1r_kEV4nllcfzNE69i-2M0Q
