本发明涉及游戏设计，特别是指一种随机技能树的生成与布局计算方法。
背景技术：
1、在现代游戏中，技能树有着十分广泛的应用，它从形状上通常类似于计算机科学中的数据结构“多叉树”，由一个个节点组成，每个节点后可以包含任意个子节点，各节点通常有着代表游戏内容的信息，例如属性加成、能力提升、技能的获得和特殊道具的获得等等，玩家可以随着游戏进度，逐步按序地选择解锁哪些节点以获得需求的奖励。
2、通常，在制作技能树时，所有点之间的关系都要预先配置好，一个节点有多少子节点，通常在制作时就已经确定，这样程序只需要处理绘制固定形状的技能树即可。但是这给策划额外增加许多限制，尤其在实现roguelike类型的玩法时，希望有动态生成的技能树，这样的技能树形状是无法确定的，具有一定的随机性，它可能有任意的深度，每个节点都有不确定的子节点数量，导致难以预先设定布局信息。如果将所有可能的情况都穷举出来，预先配置好布局信息，这个工作量将是巨大的，这给我们把随机生成的技能树可视化呈现给玩家带来了很大的挑战。
3、现有的解决方案主要有以下两种：
4、(一)采用固定形状的技能树。这一方案实施起来较为简单，由策划人员设定好技能树的参数，从开始节点，到它的各个节点的分支，都明确定义好，形状完全固定；再由美术根据策划的设定，制作好节点效果图，此时布局就已经固定在美术出的图上了；之后，程序只需要按逻辑构建好技能树即可，无需任何关于布局信息的计算。该方案由于技能树的形状固定，在制作上不够灵活，当策划需要对技能树进行调整时比较费时费力，而且往往还会需要美术、程序等相关工作同时进行调整，改动周期长，成本高。
5、(二)采用部分随机的生成方式。这种方式还是要预先设定好整个技能树，但是可以随机确定某一些节点出现或是不出现。当一个节点被消除后，它的子节点及所有后续节点都会被消除，在界面布局上，给这些位置留下无效标记。这种方式，整体上布局也是固定的，消除节点后，界面布局上这些节点并没有消除。该方案仅仅能实现逻辑节点消除与否的随机，但是它的固定技能树布局，在一些情况下会出现不好的表现，由于逻辑节点可能会被消除，没有重新计算技能树的布局，在界面上留下空白，极端情况下会出现大片空白区域而其它区域的节点却拥挤不堪的情形。
6、现有一些树形结构的自动布局算法，往往是针对别的技术领域，例如思维导图，其时间复杂度过高，通常达到o(n2)，而游戏领域的技能树结构多样、节点数量多，并且对于实时性的要求极高，显然高达o(n2)的时间复杂度是无法被忍受的。
技术实现思路
1、本发明的目的在于提供一种随机技能树的生成与布局计算方法，解决现有技术中存在的问题，能够完全随机地实现技能树的生成与布局，无需任何预先设定的布局形状，即可将一个多叉树结构的技能树布局实时计算出来，并且在调整技能树时，仅需策划改动相关配置即可完成修改，不需要美术和程序修改技能树的布局，就能自动呈现出最优的技能树布局。
2、为了达成上述目的，本发明的解决方案是：
3、一种随机技能树的生成与布局计算方法，包括以下步骤：
4、步骤1.技能树的随机生成
5、1.1技能节点表的配置
6、配置技能节点表，该表中包含若干个节点，每个节点包含的数据为节点id、对应的技能内容和子节点随机池；
7、1.2节点随机表的配置
8、配置节点随机表，该表中包含若干个节点随机池，每个节点随机池包含的数据为由技能节点表中抽取的随机或预设数量的节点及其在该节点随机池中对应的权重；
9、1.3随机生成技能树
10、1.3.1从节点随机池表中随机选择一个节点随机池；
11、1.3.2采用随机数生成方法确定所要生成的技能树数量n，n的随机范围是预设的最小数量min到当前选择的节点随机池的节点最大数量max；
12、1.3.3从当前选择的节点随机池中以加权随机的方式获取n个节点，确定为初始节点集合nodes；
13、1.3.4取出集合nodes中的一个节点，记为节点n；
14、1.3.5以加权随机的方式从节点n的子节点随机池中随机生成m个子节点，将这m个子节点设置为节点n的子节点，并将这m个子节点将入集合nodes；
15、1.3.6循环重复1.3.4至1.3.5，直至集合nodes为空，完成整棵技能树的随机生成；
16、步骤2.技能树的布局计算
17、定义节点位置为(x,y)，x为横向坐标，y为纵向坐标，x、y均从0开始，相邻节点之间预设一个间距distance；
18、2.1从根节点开始，执行第一次后序遍历整个技能树，对于叶节点leaf执行2.1.1，对于非叶节点un-leaf执行2.1.2：
19、2.1.1如果叶节点leaf没有左兄弟节点，就暂时将该叶节点leaf的横向坐标xleaf设为0；如果叶节点leaf有左兄弟节点，则将该叶节点leaf的横向坐标xleaf设为其左兄弟节点的横向坐标xleaf-left与间距distance之和；
20、2.1.2如果非叶节点un-leaf没有左兄弟节点，将该非叶节点un-leaf的横向坐标xun-leaf设为其子节点的居中位置xmid，其中xmid＝(x1-x2)/2，x1为xun-leaf最右侧子节点的横向坐标，x2为xun-leaf最左侧子节点的横向坐标；如果非叶节点un-leaf有左兄弟节点，首先将该非叶节点un-leaf的横向坐标xun-leaf设为其左兄弟节点的横纵坐标xun-leaf-left与间距distance之和，然后计算出该非叶节点un-leaf的子节点的居中位置xmid；记录以该非叶节点un-leaf为根的子树根据其横向坐标xun-leaf向右移的右移量modifier＝xun-leaf-xmid；
21、2.2解决子树的重叠
22、2.3执行第二次遍历，从根节点先序遍历整棵技能树；初始化时，记累加的modifier为accumulatemodifier＝0，初始化depth＝0：
23、2.3.1对处理的每个节点，更新其坐标(x,y)，其中x+＝accumulatemodifier，y＝depth；
24、2.3.2如果当前节点有子节点，更新accumulatemodifier和depth，其中accumulatemodifier+＝modfier，depth+＝1；然后对所有子节点用更新后的accumulatemodifier和depth重复步骤2.3.1，直到叶节点；
25、步骤3.技能树的绘制
26、根据计算得出的各节点坐标和实际配置的各节点的大小，使用已有的ui绘制功能进行绘制即可。
27、所述步骤2.2具体包括以下步骤：
28、2.2.1定义特殊的子节点shorcut，当一个节点没有子节点，该节点shorcut为该节点的兄弟子树下一层的最靠近该节点的子节点，优先考虑左边兄弟子树；
29、2.2.2在处理当前节点的每个子节点时，当前节点的子节点数组记为childrennodes，初始化defaultancestor为childrennodes[0]，defaultancestor表示在分摊处理子树时潜在的左兄弟树根节点，然后从childrennodes中的第一个节点开始处理，记每次处理的节点为node，以它为根的子树记为子树t；
30、2.2.3定义nodeinnerright为当前处理的子树t的最内侧节点，modinnerright为它的modifier值；nodeouterright为当前处理的子树t的最外侧节点，modouterright为它的modifier值；
31、2.2.4定义nodeinnerleft子树t左边子树的最内侧节点，modinnerleft为它的modifier值；nodeouterleft为子树t左边子树的最外侧节点，modouterleft为它的modifier值；
32、2.2.5初始化nodeinnerright＝nodeouterright＝node，且modinnerright＝modouterright＝node.modifier；初始化nodeinnerleft为node最近的左兄弟节点，且modinnerleft的modifier值等于nodeinnerleft的modifier值；nodeouterleft为node最左边的兄弟节点，且modouterleft＝nodeouterleft.modifier；
33、2.2.6如果节点nodeinnerleft和nodeinnerright都有子节点，则将四个节点指针都向下移动一层，进入2.2.6.1，否则返回2.2.4；
34、2.2.6.1更新nodeinnerleft为它最右边的子节点，nodeinnerright为它最左边的子节点，nodeouterleft为它最左边的子节点，nodeouterright为它最右边的子节点；
35、2.2.6.2计算下一层重叠的偏移值shift＝nodeinnerleft.x+modinnerleft-(nodeinnerright.x+modinnerright)；
36、2.2.6.3如果shift大于0，则说明有重叠，需要处理node节点的偏移，累计node节点因为子树冲突需要的偏移量node.shift+＝shift，移动node节点本身node.x+＝shift，累加node节点子树应该右移的量node.modifier+＝shift；
37、2.2.6.4更新四个节点的modifier累计值，modinnerleft+＝nodeinnerleft.modifier，modinnerright+＝nodeinnerright.modifier，modouterleft+＝nodeouterleftmodifier，modouterright+＝nodeouterright.modifier；
38、2.2.7连接shortcut，如果nodeinnerleft节点有子节点，但是nodeouterright节点没有子节点，则连接nodeouterright的shortcut，令nodeouterright.shortcut为nodeinnerleft的最右边子节点；同时，nodeouterright.modifier需要加上modinnerleft-modouterright；
39、2.2.8如果nodeinnerright节点有子节点，但是nodeouterleft没有子节点，则连接nodeouterleft的shortcut，令nodeouterleft.shortcut为nodeinnerright的最左边子节点；同时，nodeouterleft.modifer的值加上modinnerright-modouterleft。
40、采用上述技术方案后，本发明具有以下技术效果：
41、本发明采用完全随机的技能树生成，可以减轻策划配表的工作量，同时由于随机结果的不确定性，不同的技能树结果可以持续给玩家带来新的体验；本发明还实现了实时高效的技能树布局计算方法，引入shortcut连接，高效处理了自动计算布局时容易出现的节点重叠问题，避免嵌套遍历子树，使算法的时间复杂度仍然保持在o(n)；由于实现了计算任意技能树的布局，避免了预先制作技能树布局，极大降低了美术及程序的工作量，且极大方便了策划迭代修改技能树的成本，无需美术和程序做任何后续修改。
1.一种随机技能树的生成与布局计算方法，其特征在于包括以下步骤：
2.如权利要求1所述的随机技能树的生成与布局计算方法，其特征在于所述步骤2.2具体包括以下步骤：
