轨迹

写了一个简单的拼图游戏

更新于

游戏地址： 拼图/Puzzle

早就想写一个拼图游戏了，以前被 生成的拼图没法还原 的问题唬住了，迟迟没能动手写。 今天抽了几个小时做了一个简单的拼图游戏。

随机生成的拼图不一定能还原，但是可以通过 从还原好的拼图随机打乱 的方式生成拼图。 这样，生成的拼图 100% 能还原，解决了 生成的拼图没法还原 的问题。

在 从还原好的拼图随机打乱 时遇到一个棘手的问题，白块总是「原地踏步」——白块平均概率向四个方向移动，走了一圈又回到了原位。 找到一个不是很完美的解决办法，通过白块当前的位置动态计算向四个方向移动的概率，然后按照四个方向不同的概率移动，终于走出起始点了。 但是，当白块移动到正中央的时候四个方向的概率又相同了，又有「原地踏步」的可能。 目前没有想到其他更好的办法。

没有 自动还原 功能时，总想着把这个功能加上，费劲实现这个功能后就不再想亲自好好玩一把拼图了。

自动还原 功能其实并不难，前期调研时候就知道可以用 A 星 算法实现，难在学习和实现这个算法上了，还有 A 星 依赖的 二叉堆 。

digraph AStar {
    bgcolor="transparent";

    S -> A[label=10]
    S -> B[label=10]
    S -> C[label=10]
    S -> D[label=10]
    A -> E[label=10,style=dashed]
    B -> E[label=20,style=dashed]
    C -> E[label=30,style=dashed]
}

A 星 算法是一个启发性寻路算法，是最有效的直接搜索算法。其他的寻路算法还有广度优先、深度优先和 DijKstra 算法。 算法不断从开放区域选取代价最小的节点，通过该节点再生成该节点的子节点并放到开放区域中，直到找到目标节点。 算法的关键在 选取代价最小的节点 ，这个操作需要预估该节点到目标节点的代价。 A 星算法实现

digraph BinaryHeap {
    bgcolor="transparent";

    7 -> 17
    7 -> 13
    17 -> 23
    17 -> 19
    13 -> 29
    List[shape=record,label="{<f0>7|<f1>17|<f2>13|<f3>23|<f4>19|<f5>29}"]
}

A 星 算法每次都需要选取代价最小的节点，这样的操作十分适合用 二叉堆 来实现。 二叉堆 是一种队列，不同于常见的先进先出、先进后出队列，它随意进队，最小的出队。进队出队的时间复杂队都是 O(log(n)) 。 它用线性的数组／列表抽象地构造出一个完全二叉树，树上每一个节点小于它的子节点。 二叉堆实现

变更历史

2018-05-05

2018-04-24

2018-04-14