关于随机生成路线图的一些策略讨论

虹色的祝福

【背景介绍及用途分析】在一些以节点为基础的路线生成中，对于矩阵式的节点分布图作随机性生成策略的分析，并加以推广用于应用在更广泛的地方。 【基本规则】Ø  整体的路线图由节点构成Ø  每个生成的节点视为可交互的每一个小关Ø  在节点和节点之间通过路线相连Ø  路线的连线遵循一定的规则 【情况分析】在此基本规则下，矩阵内行的个数决定了单次路径点内随机性的上限，同时也会影响路线复杂的程度，且这种随机性的成长是二阶幂指数式的增长（例如2：2的情况下一共有2^2^2=16种情况，而增加行数到4则为2^4^2=65536种，甚至已经到了某cel03版的行数上限了J，由于行数被固定，对于相邻的两列来说他们之间的连线情况是有限的，情况数为2^ij）而同样地，过大的随机数对于路线图来说是完全没有必要的，所以我们需要对某些特定情况或者是等价情况进行筛选，这里给出的做法是挑出适用的矩阵连线图案来加以筛选，同时测算出等价图案并转化为视觉上更容易接受的图案，然后对其赋予权重的方式，通过控表来实现路线图的随机生成。另外地，还有一种更简单的办法就是预设好几个图形方案，然后让他们完全随机或设定概率随机，但这种情况一般只适用于特定的项，且不具有推广性，这里就不做阐述了。 【连线规则】Ø  前一列的点只能朝向后一列去链接，即路线的指向性Ø  每个点可以朝后置的多个节点链接，反之亦然，即节点的散射性Ø  根据这些基础规则作出优化，我们希望的是路线的交叉点尽可能的少甚至于没有，且路线图尽量保证美观，保证从起点出发的任意一条路线都可以通往终点即无死路。 【数据结构建立】我们在excel里建立一张节点表来控制节点出现，大约需要这些参数file:///C:/Users/ADMINI~1/AppData/Local/Temp/msohtmlclip1/01/clip_image002.jpgØ  节点ID：索引Ø  列：节点所在列的序号Ø  层数：行号，以从上往下的顺序Ø  池ID和权重：要走的随机池子和对应的权重 图里的结构其实是通过控表来控制空值节点，如800000这个随机池子其实就是个空池，约定对空池做一个删选处理就行；但实际上根据不同的需求会有不同的方式来实现，如通过对整列分析来约定出现空点的最大最小值，继而再进行排列。由于这里的需求够用，且需要保证每个节点的体验，所以需要锁定掉某些节点，再根据权重来控制部分的随机性即可。 然后我们再建立一张对点图案表来控制图案元的连线和权重，如下file:///C:/Users/ADMINI~1/AppData/Local/Temp/msohtmlclip1/01/clip_image004.jpgØ  节点图案ID：索引Ø  对点图案类型：邻近的两列图形参数值Ø  权重：该图案ID的权重，统计对点图案类型相同的权重值来测算Ø  连接方法：每个内数组按顺序表示该列的所有行依次连接到下一列的位置值 例如22002和23003的图形：file:///C:/Users/ADMINI~1/AppData/Local/Temp/msohtmlclip1/01/clip_image005.png           file:///C:/Users/ADMINI~1/AppData/Local/Temp/msohtmlclip1/01/clip_image006.png

虹色的祝福

【况列举和拆分】
先分析最简单的情况1：1

共1种情况

同理1：2

共1种情况

同理，单一情况的还有1：3，3：1等，这里不再列出

再来看2：2的部分
先列出连线的最大值情况，记为Max线，记首列的行数为Ri，次列的行数为Rj，那么在2：2的情况下
Max线 = Ri * Rj =2*2=4
同样的，我们需要的最低线值记为Min线，则易得
Min线 = max(Ri,Rj) = 2
我们在最大的线值情况下依次减线，并根据线条数来筛选线性

--减0：
我们来分析从i列的每个节点出发链接到j列的线条数，依次来记为
I =｛第一个节点链接的线条数，第二个节点链接的线条数，……｝
则i列对应的情况值
i = {2,2}
满足此i值的所有情况数记为
P = 0C2*0C2 = 1
第一个0C2的意义是，从i列中的两个点中选取0个删除0条线，共有0C2种
第二个0C2的意义是，从点出发的两条线中选取0条删除，共有0C2种

--减1：
同样的方法对-1进行拆分，此时i列对应的情况值有，i={1,2},{2,1}两种情况，暂不考虑顺序记为i={1,2}
则满足此i值的所有情况数P
P = 1C2*1C1*1C2*0C2 = 4种
解释一下各值的意义：
1C2：从i列的两个点中选取1个点进行删线操作
1C1：再从i列剩余的1个点中选取1个点进行不删除线的操作
1C2：对于i列的删线点，从2条线中选取1条删除
0C2：从2条线中选取0条删除

同理减2的情况下：
i={0,2},{1,1}
P=1C2*1C1*2C2*0C2+2C2*1C2*1C2=2+4=6种

需要明确的是，情况列出的为所有的连线情况，但并不是所有的连线都是我们所需要的
诸如下图所列的线型，显然不满足我们非空点的需求。


所以需要对2：2的线型情况进行筛选，筛选结果如下图所示

其中，A0为连线的最大值情况，这种情况在视觉上可以保留，但依据交叉原则来说我们也可以删去，根据项目自行选择就好。
对于A1来说，如果将j列的黄色节点上下交换位置，其连线情况便等同于A3，同理对应的A2=A4，B1=B2；这种交换顺序的原理上来说，实际中黄色节点所代表的节点类型不同，且稀有度和难度也不尽相同，但对于路线生成来说，其本身就需要考量后续节点的关联性和难易度评价，所以其在价值上是等同的；简单来说，就是在生成节点的时候，是先生成的绿色i列，再生成的黄色j列，由于生成的随机性和盲目性，就算黄1黄2所代表的类型和难度不同，由于路线本身的可选择性，实际上到达的黄色节点是可控的。但如果对于是完成当前节点后再生成后续节点的项目来说，路线选择本身就显得不那么合理了，这种往往是完全通路的形式，而不需要考虑路线。

这样我们便确立了2：2情况下所筛选出的三种pattern如下图，最后来统计权重和概率。

这里有真实权重和修正两种做法，对于真实权重来说，比如2：2的情况一共有2^4=16种，除去不满足规则的情况，有效图形数共有
0C4+1C4+2C4-2*2-1=6种
将所有可能的转化情况算作概率权重，则
A3=A4=B2=2
最终概率即为
P1=P2=P3=1/3
修正则是在真实概率的基础上，增加人为的干预值，比如我们希望B2出现是小概率事件，又或者是对于A0和空点的情况出现，我们希望它能转化为A3或者A4其中的某个出现，那最终的修正概率可能为P1=P2=7/16，P3=2/16
修正的依据和做法可以有很多，这里不做赘述，下面都只分析真实概率的情况。