Project1

标题: ARPG助手→四叉树管理器1.0Base版 [打印本页]
作者: 九夜神尊    时间: 2010-10-24 01:38
标题: ARPG助手→四叉树管理器1.0Base版
一切的一切都归功于紫苏大人。
否则我不知道世界上有这玩意。

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



只是稍微性能上提升了，因为RM的卡不仅仅是在移动遍历事件上。
  1. #===================================================================
  2. # ■ Accelerator
  3. #--------------------------------------------------------------------
  4. # 四叉树管理器
  5. #====================================================================



  9. =begin

  11. 脚本名称：四叉树管理器

  13. 版本：1.0

  15. 作用：在有大量事件的地图上，增加获得目标点事件组的速度。
  16.       多用于ARPG，以及射击类游戏。

  18. 使用方法：插入脚本即可。

  20. 注意事项：事件较少，完全可以不需要此脚本。


  23. 原理/过程：

  25. 四叉树→
  26. 将地图先扩大到正方形，且边长为2**n，比如 32*32   64*64大小。（取名总地图）

  28. 将总地图田字平分为4等分，如32*32的，就分成4个16*16的子地图块

  30. 统计每一个地图块里拥有的事件总数，若超过6（6是自适应数，可更改）

  32. 则将该子地图块，再平分成4个子地图块，以此类推，最小能平分成4个1*1的地图块。



  36. 最顶层树（树干）Plane_Base类

  38. 该类拥有4个子块

  40.           ┌───┐
  41.           │      │
  42.           └─┬─┘
  43.               │
  44.         ┌─┬┴┬─┐
  45.         │  │  │  │
  46.         
  47. 子块可能为，数值，树叶两种结构。

  49. 树枝的结构    依旧拥有4个子块 Plane_Tree
  50.           ┌───┐
  51.           │      │
  52.           └─┬─┘
  53.               │
  54.         ┌─┬┴┬─┐
  55.         │  │  │  │

  57. 树叶的结构  Grouping

  59.           ┌───┐
  60.           │      │
  61.           └─┬─┘
  62.               │
  63.       ─┬─┬┴┬─┬─┬─┬
  64.         │  │  │  │  │  │
  65.        event    event  ……
  66.       

  68. 树叶为最底层，用于保存事件的位置。

  70. Plane_Base 类方法

  72. gro_xy(x,y) 直接获得x,y点最小事件范围组，直接遍历这个组，就能获得x,y点上的事件。


  75. move(event,xt,yt) 将event事件移动到xt,yt点（事件移动后，对树的重新操作）

  77. rect_events(x0,y0,xt,yt) 获得矩形区域内的所有事件


  80. =end

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

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

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


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

献上附件！！




四叉树管理器1.0.rar

247.32 KB, 下载次数: 319
作者: moy    时间: 2010-10-24 02:15
下下来看看能不能看懂
作者: DeathKing    时间: 2010-10-24 07:47
FSL吧。至于为什么

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


请看我签名中，FSL的细则。
作者: DeathKing    时间: 2010-10-24 07:47
FSL吧。至于为什么

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


请看我签名中，FSL的细则。
作者: 小幽的马甲    时间: 2010-10-24 08:53
= =这四叉树怎么看着像二维线段树{:nm_1:}
为何一定要把地图扩展到2**n……？这样 33*33的地图岂不是浪费大量空间= =
把直接把33*33竖着划分为16*16、16*17、17*16、17*17这样能节约点空间{:nm_3:}
作者: IamI    时间: 2010-10-24 09:44
LS + 1，四叉树不一定要完全均衡，基本保持均衡即可。
另外用Array管理真的让这个脚本失色呢（笑）
作者: 38571240    时间: 2010-10-24 09:45
试一下，我用防卡脚本的时候，如果有一个事件的位置需要随时记忆，那么每次进入地图都会出现事件从初始位置移动到记忆位置的灵异现象，去掉此脚本恢复正常。这个不用刷新图形的话应该不会出现此类问题吧
作者: 九夜神尊    时间: 2010-10-24 10:28
回5楼：多余的空间并不会占用很多内存，因为空间分配并不是均匀的。
           对于完全没有记录事件的空间就只保存了一个 []也不会在细分。
            用2的整数次幂，是为了取址更快捷如果是 16 +17 这样就会多一层条件分歧。
           每一个地图的层级矩形大小都个式各样。会降低一定的速度。

6楼：  此外，这东西也不是数组，听六折酱的话，改成了类。发现灵活性很高
         
7楼：为了测试，我把地图的刷新屏蔽掉了，在新工程内不会出现这种问题。
        但是这个脚本融入新工程需要做很多动作，主要是每个事件的移动都要告知四叉树。
        所以必须重写8方向移动、还有跳跃、场所移动（一个地图之间可能出现不爽的）
       事件交换。这些。不过所有用xy记录的对象都可以用这玩意管理。
作者: 沉影不器    时间: 2010-10-26 22:31
提示: 作者被禁止或删除 内容自动屏蔽
作者: 九夜神尊    时间: 2010-10-27 08:15
回复 沉影不器 的帖子

起初我也想的是用二维数组。写这个纯粹是为了练习。
   
作者: 冰蓝的马甲    时间: 2010-10-28 14:53
嗯，考虑一下写一个二维数组式的管理法吧
作者: 九夜神尊    时间: 2010-10-28 15:53
回复 冰蓝的马甲 的帖子
其实二维数组管理管理效率并不会高多少。
主要是这样，移动的时候经常要调动自己的位置，这样就导致不断复制清除数据。
在获取一定范围内的事件的时候，需要扫描整个范围。
比如
0,0,8,8 这样的矩形范围，那样就要整个矩形全部扫描（根据细分程度）

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

   
作者: 亿万星辰    时间: 2010-10-28 18:06
对于算法效率神马的倒是没咋研究过，我以前倒是特无奈的试过用两个数组来记录事件的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]
作者: yangff    时间: 2010-10-28 19:17
显然二维线段树是最快的……不过若是咱的AOE是圆形区域嘎嘎~
作者: 九夜神尊    时间: 2010-10-28 19:51
回复 yangff 的帖子

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

自由吧？
作者: 菜鸟飞呀飞    时间: 2010-10-28 21:45
提示: 作者被禁止或删除 内容自动屏蔽
作者: 九夜神尊    时间: 2010-10-28 22:10
回复 菜鸟飞呀飞 的帖子


   
作者: 沉影不器    时间: 2010-10-29 21:49
提示: 作者被禁止或删除 内容自动屏蔽
作者: yangff    时间: 2011-1-1 14:12
不过想做ARPG但是不想重写地图……



欢迎光临 Project1 (https://rpg.blue/) Powered by Discuz! X3.1