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

九夜神尊 · 发表于 2010-10-24 01:38:32

加入我们，或者，欢迎回来。

您需要登录才可以下载或查看，没有帐号？注册会员

x

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

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

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

#===================================================================
# ■ Accelerator
#--------------------------------------------------------------------
# 四叉树管理器
#====================================================================
=begin
脚本名称：四叉树管理器
版本：1.0
作用：在有大量事件的地图上，增加获得目标点事件组的速度。
多用于ARPG，以及射击类游戏。
使用方法：插入脚本即可。
注意事项：事件较少，完全可以不需要此脚本。
原理/过程：
四叉树→
将地图先扩大到正方形，且边长为2**n，比如 32*32 64*64大小。（取名总地图）
将总地图田字平分为4等分，如32*32的，就分成4个16*16的子地图块
统计每一个地图块里拥有的事件总数，若超过6（6是自适应数，可更改）
则将该子地图块，再平分成4个子地图块，以此类推，最小能平分成4个1*1的地图块。
最顶层树（树干）Plane_Base类
该类拥有4个子块
┌───┐
│ │
└─┬─┘
│
┌─┬┴┬─┐
│ │ │ │
子块可能为，数值，树叶两种结构。
树枝的结构依旧拥有4个子块 Plane_Tree
┌───┐
│ │
└─┬─┘
│
┌─┬┴┬─┐
│ │ │ │
树叶的结构 Grouping
┌───┐
│ │
└─┬─┘
│
─┬─┬┴┬─┬─┬─┬
│ │ │ │ │ │
event event ……
树叶为最底层，用于保存事件的位置。
Plane_Base 类方法
gro_xy(x,y) 直接获得x,y点最小事件范围组，直接遍历这个组，就能获得x,y点上的事件。
move(event,xt,yt) 将event事件移动到xt,yt点（事件移动后，对树的重新操作）
rect_events(x0,y0,xt,yt) 获得矩形区域内的所有事件
=end

复制代码

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

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

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

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

献上附件！！

moy · 发表于 2010-10-24 02:15:07

下下来看看能不能看懂

DeathKing · 发表于 2010-10-24 07:47:33

FSL吧。至于为什么

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

请看我签名中，FSL的细则。

DeathKing · 发表于 2010-10-24 07:47:55

FSL吧。至于为什么

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

请看我签名中，FSL的细则。

小幽的马甲 · 发表于 2010-10-24 08:53:02

= =这四叉树怎么看着像二维线段树{:nm_1:}
为何一定要把地图扩展到2**n……？这样 33*33的地图岂不是浪费大量空间= =
把直接把33*33竖着划分为16*16、16*17、17*16、17*17这样能节约点空间{:nm_3:}

IamI · 发表于 2010-10-24 09:44:26

LS + 1，四叉树不一定要完全均衡，基本保持均衡即可。
另外用Array管理真的让这个脚本失色呢（笑）

38571240 · 发表于 2010-10-24 09:45:07

试一下，我用防卡脚本的时候，如果有一个事件的位置需要随时记忆，那么每次进入地图都会出现事件从初始位置移动到记忆位置的灵异现象，去掉此脚本恢复正常。这个不用刷新图形的话应该不会出现此类问题吧

九夜神尊 · 发表于 2010-10-24 10:28:53

回5楼：多余的空间并不会占用很多内存，因为空间分配并不是均匀的。
         对于完全没有记录事件的空间就只保存了一个 []也不会在细分。
         用2的整数次幂，是为了取址更快捷如果是 16 +17 这样就会多一层条件分歧。
         每一个地图的层级矩形大小都个式各样。会降低一定的速度。

6楼：  此外，这东西也不是数组，听六折酱的话，改成了类。发现灵活性很高

7楼：为了测试，我把地图的刷新屏蔽掉了，在新工程内不会出现这种问题。
      但是这个脚本融入新工程需要做很多动作，主要是每个事件的移动都要告知四叉树。
      所以必须重写8方向移动、还有跳跃、场所移动（一个地图之间可能出现不爽的）
   事件交换。这些。不过所有用xy记录的对象都可以用这玩意管理。

沉影不器 · 发表于 2010-10-26 22:31:17

提示: 作者被禁止或删除内容自动屏蔽

九夜神尊 · 发表于 2010-10-27 08:15:46

回复 沉影不器 的帖子

起初我也想的是用二维数组。写这个纯粹是为了练习。

帐号		自动登录	找回密码
密码			注册会员

[RMVX发布] ARPG助手→四叉树管理器1.0Base版

加入我们，或者，欢迎回来。

评分

开拓者

贵宾

第1届Title华丽大赛新人奖