ARPG助手→四叉树管理器1.0Base版

九夜神尊

一切的一切都归功于紫苏大人。
否则我不知道世界上有这玩意。

四叉树管理器，用于快速取得指定范围内的事件，指定位置的事件。无需遍历所有事件



只是稍微性能上提升了，因为RM的卡不仅仅是在移动遍历事件上。

1. #===================================================================
   
2. # ■ Accelerator
   
3. #--------------------------------------------------------------------
   
4. # 四叉树管理器
   
5. #====================================================================
   
6. 
   
7. 
   
8. 
   
9. =begin
   
10. 
    
11. 脚本名称：四叉树管理器
    
12. 
    
13. 版本：1.0
    
14. 
    
15. 作用：在有大量事件的地图上，增加获得目标点事件组的速度。
    
16.       多用于ARPG，以及射击类游戏。
    
17. 
    
18. 使用方法：插入脚本即可。
    
19. 
    
20. 注意事项：事件较少，完全可以不需要此脚本。
    
21. 
    
22. 
    
23. 原理/过程：
    
24. 
    
25. 四叉树→
    
26. 将地图先扩大到正方形，且边长为2**n，比如 32*32   64*64大小。（取名总地图）
    
27. 
    
28. 将总地图田字平分为4等分，如32*32的，就分成4个16*16的子地图块
    
29. 
    
30. 统计每一个地图块里拥有的事件总数，若超过6（6是自适应数，可更改）
    
31. 
    
32. 则将该子地图块，再平分成4个子地图块，以此类推，最小能平分成4个1*1的地图块。
    
33. 
    
34. 
    
35. 
    
36. 最顶层树（树干）Plane_Base类
    
37. 
    
38. 该类拥有4个子块
    
39. 
    
40.           ┌───┐
    
41.           │      │
    
42.           └─┬─┘
    
43.               │
    
44.         ┌─┬┴┬─┐
    
45.         │  │  │  │
    
46.         
    
47. 子块可能为，数值，树叶两种结构。
    
48. 
    
49. 树枝的结构    依旧拥有4个子块 Plane_Tree
    
50.           ┌───┐
    
51.           │      │
    
52.           └─┬─┘
    
53.               │
    
54.         ┌─┬┴┬─┐
    
55.         │  │  │  │
    
56. 
    
57. 树叶的结构  Grouping
    
58. 
    
59.           ┌───┐
    
60.           │      │
    
61.           └─┬─┘
    
62.               │
    
63.       ─┬─┬┴┬─┬─┬─┬
    
64.         │  │  │  │  │  │
    
65.        event    event  ……
    
66.       
    
67. 
    
68. 树叶为最底层，用于保存事件的位置。
    
69. 
    
70. Plane_Base 类方法
    
71. 
    
72. gro_xy(x,y) 直接获得x,y点最小事件范围组，直接遍历这个组，就能获得x,y点上的事件。
    
73. 
    
74. 
    
75. move(event,xt,yt) 将event事件移动到xt,yt点（事件移动后，对树的重新操作）
    
76. 
    
77. rect_events(x0,y0,xt,yt) 获得矩形区域内的所有事件
    
78. 
    
79. 
    
80. =end
    
81. 
    

复制代码

为了演示，所以将4叉树插入四方向移动里。

该脚本还估计还有20%的优化空间

该脚本绝非为伸手党而作，只是为了研究。
别拿它跟防卡脚本比，不是一回事。


付费求高手指处其中缀余代码，以及可以优化的地方。

献上附件！！

yangff

不过想做ARPG但是不想重写地图……

九夜神尊

回复 菜鸟飞呀飞 的帖子


   

九夜神尊

回复 yangff 的帖子

我倒是发明了一种新的表示区域的方法。
scope = ?
如果是一个数比如 5，就代表主角周围5格范围
如果是两个数，比如 5，6就代表一个点。
如果是三个数，比如5，6，3，就代表以5，6为中心向外3格范围
四个数=>2，2，6，8。这代表一个矩形区域
如果是数组  =>[4,6],[3,3,5,5] 这样就代表这数组里的元素的区域之和。

自由吧？

yangff

显然二维线段树是最快的……不过若是咱的AOE是圆形区域嘎嘎~

亿万星辰

对于算法效率神马的倒是没咋研究过，我以前倒是特无奈的试过用两个数组来记录事件的id
evpos_x[0] = [1,3,4]
evpos_x[1] = []
evpos_x[2] = [2,5]
evpos_y[0] = [1,2]
evpos_y[1] = [4,5]
evpos_y[2] = [3]

九夜神尊

回复 冰蓝的马甲 的帖子
其实二维数组管理管理效率并不会高多少。
主要是这样，移动的时候经常要调动自己的位置，这样就导致不断复制清除数据。
在获取一定范围内的事件的时候，需要扫描整个范围。
比如
0,0,8,8 这样的矩形范围，那样就要整个矩形全部扫描（根据细分程度）

而四叉树，是根据怪物分布的不同，平分的密度也不同。比如一大块地图上只有1-2个事件。
那么四叉树记录这整个区域只有两个事件。这两个事件只要不走出去着整个区域。
就不用改变树结构，总的来说差不多。

   

冰蓝的马甲

嗯，考虑一下写一个二维数组式的管理法吧