请选择 进入手机版 | 继续访问电脑版

GA地精研究院

 找回密码
 立即注册
查看: 3328|回复: 13

[讨论] 还是说数组存储系统续

[复制链接]
发表于 2009-4-2 00:00:52 | 显示全部楼层 |阅读模式
2009-4-5
重新编辑了下帖子,之前的叙述可能有些混乱,向大家道歉了。
这篇文章的重点是拉链法,实现上并不困难,最主要的大家要灵活运用它。
如若今后发现了帖子还有什么问题,会尽量第一时间修正。


目前我们知道的数组存储系统的方法主要分为DataSystem和Hash两种,但是若要保证它们的高效,都是以struct的原理为基础,所以需要大家很好的了解下它的结构。不了解的同学可以查看帖子http://www.islga.org/bbs/read.php?tid=18895,熟悉它之后我们要做的不是套用模板,而是灵活的应用它。


1,关于TimerDataSystem,我在一楼会有代码,同样论坛也有好多前辈的代码,这个是数组存储系统中最实用也是最简单的一类了,使用方法也很简单。整个DataSystem除了适用于计时器以外,也同样适用于单位和物品,这就要用到单位或者物品的自定义值了,这个我在帖子http://www.islga.org/bbs/read.php?tid=24648已经发出了代码,只是注解不是很详细,所以请大家看明白了1L的TimerDataSystem后再去查看。


2,第二个类别就是Hash表了,其最基本的思想就是取余,在处理碰撞问题上现在也有很多的解决方案。双重Hash法和eff的Time33都是不错的选择,但是我最推荐的是拉链Hash法。我会在1L给出拉链Hash法的代码,2L给出它的文本宏代码,方便大家调用。现在我重点介绍下拉链Hash是如何实现的,也就是本文的重点,拉链法,先看如下代码:

[codes=jass]globals
integer array LL_a
integer array LL_b
integer array LL_c
endglobals

//获取一个绑定于整数i的整数
function LL_get takes integer i returns integer
//我们在这里省略对i的处理过程,可能是取余(i-i/8191*8191),也可能是直接使用(i可能小于8191,于是我们直接使用它),又或者是其他的什么方法,经过处理,我们得到了整数n,n满足条件0<=n<8191,我们称之为拉链的“头”
local integer n←i
//由整数n这个“头”指向对应的拉链中的第一个节点,既起点
local integer x=LL_a[n]
loop
      //x==0说明现在处于拉链尾部了,有可能第一个节点就是0,那样的话表示“头”并        没有关联一个拉链,这两种情况我们都会跳出,并在最后返回0
      exitwhen x==0
      //当满足下式时,我们就获取到了绑定于整数i的整数,x
      exitwhen LL_c[x]==i
      //获取拉链中节点x的下一个节点
      set x=LL_b[x]
endloop
//这是是返回错误(0)或者是绑定于整数i的整数
return x
endfunction

//下面函数的作用是分配一个整数x绑定于整数i上,或者在整数i已经有绑定了的整数时返回该整数x,前面的几行和上面是一样的,所以我经常把它们合并起来
//这里的i只要是整数就可以了,它可以是句柄转化的Handle值,也可以只是普通的整数,但是要注意,一个整数i只能绑定一个整数。不管怎样,我们都需要用数组LL_c记录下它。
function LL_set takes integer i returns integer
local integer n←i
local integer x=LL_a[n]
//y的用途是记录下该小拉链的“头”
local integer y=x
loop
      exitwhen x==0
      exitwhen LL_c[x]==i
      set x=LL_b[x]
endloop
//x==0说明i还没存在于以整数n为“头”的拉链中呐
if x==0 then
      //下面的代码表示我们使用了某种方法,将x变为LL_b中未使用的下脚标,也就是分配了新的节点于拉链中,一般来说,是使用了struct
      set x←struct
      //这3行就看出了这3个数组的用途了
      //将整数i转化的整数n作为“头”,将其指向一个拉链的新的起点
      set LL_a[n]=x
      //将新的节点x指向之前的起点,由此形成了一个链表
      set LL_b[x]=y
      //将LL_c[x]的值变为i,用于我们之后获取x
      set LL_c[x]=i
endif
return x
endfunction

//下面函数的作用是消除整数i在拉链中的位置,这个代码有两个版本的,调用参数也不同,这个是使用单链表的方案,双向链表的请看1L拉链Hash法
//前面几行依然和之前一样,我们依然需要一一查找这个小链表的元素才行
function LL_des takes integer i returns nothing
local integer n←i
local integer x=LL_a[n]
//y的用途是记录x前一个节点
local integer y=0
loop
      exitwhen x==0
      exitwhen LL_c[x]==i
      set y=x
      set x=LL_b[x]
endloop
//如果x==0,那么我们就没有找到整数i绑定的整数x,所以这个调用是错误的,于是返回
if x==0 then
      return
//如果找到的x是拉链的起点,我们需要将拉链的起点设置为整数x的下一个节点
elseif x==LL_a[n] then
      set LL_a[n]=LL_b[x]
//下面这个就是一般的情况了,我们将整数x的前一个节点y指向x的下一个节点LL_b[x]
elseif y!=0 then
      set LL_b[y]=LL_b[x]
endif
//依据不同的方法要对LL_b进行一些操作,一般来说就是用了struct
set LL_b[x]←struct
//排泄还是要的,嗯...这个要看情况的,其实也可以不管的
set LL_c[x]=0
endfunction[/codes]

以上就是拉链法的代码了,我对整数i的处理过程和struct应用做了省略,以便不分散大家的注意力,下面说说我们一般是怎样获取了这个整数i或者是怎样处理它。
--------------------------分隔线----------------------------------------
当这个整数i是某个句柄的Handle值时,由于它远大于8191,所以我们对其进行了取余(set n=i-i/8191*8191),然后以整数n作为一个拉链的“头”,在这个拉链中我们使用struct获取一个整数x,然后使用整数x来记录下整数i,而这个x就是绑定于i的整数,我们可以使用x来作为我们数组存储系统的下脚标。这里我所介绍的方法就是拉链Hash法。它的作用就是为一个句柄分配一个整数x,不同的句柄将获得不同的x。

举个例子,我们要记录一个英雄的坐标和HP、MP,当这个英雄使用“时间回溯”技能时,将返回这个坐标并且HP、MP也要回复成那个数值。这样我们先创建4的数组
[codes=jass]real array Unit_x
real array Unit_y
real array Unit_hp
real array Unit_mp[/codes]
然后在游戏中使用拉链Hash法获取了这个英雄单位的整数x,再使用上面的4的数组来存储这4个数据,于是该技能就很方便的支持多人了。当然,这只是一个例子,我用它来介绍Hash法的使用方法,这个整数x你也完全可以使用struct来分配,然后使用单位自定义值来记录下来,只是Hash法可以适用于其他的句柄。
--------------------------分隔线----------------------------------------
有些时候,情况并不如上面的那样简单,在游戏中,我们可能并不知道我们将在一个句柄上绑定多少数据,所以像上面那样提前创建数组的做法就不再适用了。我将在2L提出一个解决方法,用来解决我们将不定数的数据绑定于一个整数或者句柄的问题,当然,这些数据最好是同类型的,我们将对它们依次进行相同或者类似的操作。

再举个例子,我在我的地图《山寨屠夫》里面,我需要将屠夫放出的钩链里面的单位全部绑定于一个计时器上面,但是,每个钩链的长度随时都在变化,而且我需要将这些单位按顺序依次移动,所以简单的使用单位组是不行的,所以我就使用了在2L介绍的方法。同样的,2L的例子也只是个例子,我通过它向大家介绍了拉链法的不同于Hash的其他的用途。
--------------------------分隔线----------------------------------------
然后我要说的是,上面的方法也并不是万能的,它只能解决一部分的问题,而它所遇到的困难我将在2L告诉大家,同时在4L提出一个并不成熟的解决方案,请大家耐心的看下去吧。

仅仅使用DataSystem和Hash是远远不够的,我希望大家可以明白拉链法的基本原理,因为拉链法可以将数组存储系统扩展到更广的范围。

评分

参与人数 1威望 +1 收起 理由
血戮魔动冰 + 1

查看全部评分

 楼主| 发表于 2009-4-2 00:01:07 | 显示全部楼层
我们先复习下之前的两段代码,第一个是TimerDataSystem,第二个是拉链Hash法,熟悉它们的同学可以直接去看下一楼了,而完全不了解的同学则需要仔细看一下下面的注解了。

[codes=jass]//这个是下面所有代码的头文件,是UnionBug所需要的全局变量
//当然,使用UnionBug也仅仅是笔者的习惯,以下所有的演示使用ReturnBug也完全可以,所引起的阅读的不便也请大家见谅
globals
constant handle H=null
constant code C=null
constant trigger T=null
constant timer Tm=null
constant triggercondition Tc=null
constant timerdialog Td=null
constant unit U=null
constant group G=null
constant item It=null
constant destructable D=null
constant effect E=null
constant boolexpr Bx=null
constant integer I=0
constant real R=0.0
constant string S=null
endglobals[/codes]

下面的代码就是TimerDataSystem了,它已经是一个很成熟的数组存储方案了,也就是说大家已经完全可以把它应用于地图当中了,列出这段演示是需要大家注意两点:1,函数Timer_cre请尽量在地图初始化时调用,但由于魔兽代码的执行上限的限制,大家可以创建一个Trigger,然后使用TriggerEvaluate来完成Timer_cre的运行。当然,方法并不限于此。2,这段代码中使用了VJass中struct中的方法,请大家找出是怎样的使用的并且做出了哪些修改,同时思考为什么这样的改动是可以的。

[codes=jass]globals
//这个记录了一个整数,系统中所有使用的计时器都是通过转化为整数后再减去它,获得了一个下脚标
integer Timer_F
//这个就是TimerDataSystem中用于分配整数的指针,我们根据需要将其初始值修改为1
integer Timer_ID=1
//这个数组用于存储和管理指针
integer array Timer_Data
endglobals


//下面一行我规定了在地图初始化时一共创建多少计时器,一般来说远远不需要到达3000个
//! define Timer_N 3000

//需要初始化时调用的函数,你如果是使用TriggerEvaluate来调用它的话请将返回类型修改为boolean
//它的作用是创建3000个计时器,制作一个用于分配指针的链表,同时剔除不符合条件的计时器
function Timer_cre takes nothing returns nothing
//下面两个变量用于记录下不符合条件的计时器,在创建完毕后删除
local timer array t
local integer bugs=-1
//下面两个变量使用了UnionBug的原理,创建了第一个计时器,并且获得了其handle值
local integer I
local timer Tm=CreateTimer()
//记录下第一个计时器的handle值,它将在代码的末尾赋值给Timer_F,为什么减1呢?
local integer fid=I-1
//这个id就是I-Timer_F的结果,同时也是在以后使用这个计时器时分配到你的手中的整数
local integer id=1
//用于传值
local integer id2
//n是第一个循环的初始值
local integer n=2
//进入循环
loop
    //创建了一个新的计时器,同时获得了其handle值
    set Tm=CreateTimer()
    //此id2亦I-Timer_F
    set id2=I-fid
    //判断最新生成的计时器是否符合条件
    if(id2>0 and id2<8191)then
        //是!将获得的id2记录在数组中,形成链表,等待分配
        set Timer_Data[id]=id2
        set id=id2
        //n++,大于3000时跳出
        set n=n+1
        exitwhen n>Timer_N
    else
        //否!用计时器变量组记录下不符合条件的计时器
        set bugs=bugs+1
        set t[bugs]=Tm
    endif
endloop
//进入循环,删除不符合条件的计时器(一般来说,只要保证Timer_cre是最先运行的,这段代码就是不需要的,但是严格来做的话,还是有的好)
loop
    exitwhen bugs<=-1
    call DestroyTimer(t[bugs])
    set t[bugs]=null
    set bugs=bugs-1
endloop
//给Timer_F赋值,使用方法见函数Timer_getid
set Timer_F=fid
//排泄。关于UnionBug的排泄方法大家可以在论坛搜索来了解下,但是我依然推荐大家不论在什么情况下都要在末尾set I=0,以免忘记。
set I=0
endfunction


//这个函数用于获取可以使用的下脚标。在使用过程中,若返回0,则代表是返回错误,这就是上面fid减去一的原因。
//方法同struct,但是做了一些修改,看看为什么。
function Timer_get takes nothing returns integer
local integer id=Timer_ID
if(id!=0)then
    set Timer_ID=Timer_Data[id]
    set Timer_Data[id]=-1
endif
//返回id,这个id+Timer_F就是一个计时器的handle值,使用UnionBug我们就可以使用该计时器了
return id
endfunction


//这个函数就是获得计时器对应的整数
//! define Timer_id(t) Timer_getid(0,t)
function Timer_getid takes integer I,timer Tm returns integer
return I-Timer_F
endfunction


//这个函数是将到期或者不需使用的计时器回收,同时将其续接入链表
function Timer_des takes integer id returns nothing
local timer Tm
local integer I
if(Timer_Data[id]==-1)then
    set Timer_Data[id]=Timer_ID
    set Timer_ID=id
    //使用了UnionBug,获得了计时器,然后暂停计时器就可以了,不需要删除
    set I=Timer_F+id
    call PauseTimer(Tm)
endif
//排泄。
set I=0
endfunction[/codes]

做了下注解,排除掉连续创建的计时器的handle值同样是连续的这个原理外,TimerDataSystem仅仅只使用了一个链表,可是说它是整个数组存储系统中最简单最容易理解的代码了,我希望大家可以看懂它,然后写出自己的TimerDataSystem。


接下来就是拉链Hash法了,请大家理解这里面4的数组的作用都是什么。
[codes=jass]globals
//这个数组用于记录拉链的起点
integer array Ha
//下面4个东西用途是节点的分配以及删除,具体来说,maxN、Hnf、Hb2是struct需要的,而Hb1、Hb2则一起构造了多个双向链表
integer maxN=1
integer Hnf=0
integer array Hb1
integer array Hb2
//存储句柄,用于指针的提取和句柄的比对
integer array Hc
endglobals

//调用此函数可以获取一个与上传句柄相关的唯一指针,用于数组的数据存取
//b=true就在句柄没有地址的情况下分配一个,b=false则在没有找到句柄位置的情况下返回0或者是句柄的位置
function hashget takes integer I,handle H,boolean b returns integer
//将句柄的值取余得到一个整数n,这个就是一个拉链的“头”
local integer n=I-I/8191*8191
//获取“头”指向的拉链的起点,为0则会直接跳出下面的循环
local integer x=Ha[n]
//使用y来记录的x的值
local integer y=x
loop
    //为0就代表是拉链的末尾了,跳出
    exitwhen x==0
    //判断该句柄是否已经有了对应的指针
    if Hc[x]==I then
    //是!返回该指针x
        return x
    endif
    //否!通过数组Hb2指向下一个节点
    set x=Hb2[x]
endloop
//在这里,x的值为0,下面判断是否为句柄分配一个地址
if b then
    //下面的10行代码就应用了struct的方法,具体不解释了
    set x=Hnf
    if x!=0 then
        set Hnf=Hb2[x]
    else
        set x=maxN
        if x>8191 then
            return 0
        endif
        set maxN=x+1
    endif
    //用于补足双链表,同时销毁Hb2之前的记录
    if y!=0 then
        set Hb1[y]=x
    endif
    set Hb2[x]=y
    //将n指向拉链的新起点
    set Ha[n]=x
    //存储句柄的handle值
    set Hc[x]=I
endif
//返回地址x
return x
endfunction
//这个函数用于销毁句柄在hash表中占据的位置,重点在于修复链表
function hashfree takes integer m returns nothing
//读取节点m的前一个与后一个节点
local integer x=Hb1[m]
local integer y=Hb2[m]
local integer n
//判断节点m是否为拉链的起点
if x!=0 then
      //否!则销毁节点m存储的前一节点数据,同时补足双链表
      set Hb1[m]=0
      set Hb2[x]=y
else
      //是!则获取m存储的句柄
      set n=Hc[m]
      //判断是否存储了句柄
      if n==0 then
            //否!错误,跳出
            return
      endif
      set n=n-n/8191*8191
      //将n指向新的起点
      set Ha[n]=y
endif
//补足双链表
if y!=0 then
      set Hb1[y]=x
endif
//销毁节点m存储的句柄,主要用于上面的纠错
set Hc[m]=0
//下面的代码就应用了struct的方法,具体不解释了
set Hb2[m]=Hnf
set Hnf=m
endfunction[/codes]

上面这个拉链Hash法与其说是一个模板,倒不如说只是演示了一个方法。在大家完全理解了以上代码的实现方法后,我们可以将思路扩展到更大的范围。当然,它在地图中是可以直接使用的,但是我们需要做一些改进,来发挥它最大的效能。

我在之前如所有人一样强调说TimerDataSystem和Hash方法只能在一定范围内代替缓存,但是前两者无法完全取代后者。那么,接下来,我们要做的就是在保证数组存储系统高效的前提下,进一步压缩缓存的使用范围,我会设想一些情况,然后使用数组来解决它。
回复 支持 反对

使用道具 举报

 楼主| 发表于 2009-4-2 00:01:34 | 显示全部楼层
现在我假设大家已经完全理解了拉链Hash法。我们知道,Hash法的特点就是查找速度快,但是在存储的句柄过多的情况下,效率是会下降的。拉链Hash中的每个小链子的长度在句柄增多的情况下也会越来越长从而影响效率。因此,我们要做的是多增加几个hash表,使得它们每个的存储量都不大,保持高效率,但是也要注意适量,并不是越多越好的。在写代码的时候,为了方便使用,我把拉链Hash法修改为一个文本宏封装起来,代码如下:
[codes=jass]//! textmacro Hash takes Func_name1,Func_name2,Array_name
globals
integer Hash$Array_name$0=0
integer Hash$Array_name$1=1
integer array Hash$Array_name$2
integer array Hash$Array_name$3
integer array Hash$Array_name$4
integer array Hash$Array_name$5
endglobals
function $Func_name1$ takes integer I,handle H,boolean b returns integer
local integer n=I-I/8191*8191
local integer x=Hash$Array_name$2[n]
local integer y=x
loop
    exitwhen x==0
    exitwhen Hash$Array_name$5[x]==I
    set x=Hash$Array_name$4[x]
endloop
if b and x==0 then
    set x=Hash$Array_name$0
    if x!=0 then
        set Hash$Array_name$0=Hash$Array_name$4[x]
    else
        set x=Hash$Array_name$1
        if x>8191 then
            return 0
        endif
        set Hash$Array_name$1=x+1
    endif
    set Hash$Array_name$2[n]=x
    if y!=0 then
        set Hash$Array_name$3[y]=x
    endif
    set Hash$Array_name$4[x]=y
    set Hash$Array_name$5[x]=I
endif
return x
endfunction
function $Func_name2$ takes integer m returns nothing
local integer x=Hash$Array_name$3[m]
local integer y=Hash$Array_name$4[m]
local integer n
if x!=0 then
    set Hash$Array_name$3[m]=0
    set Hash$Array_name$4[x]=y
else
    set n=Hash$Array_name$5[m]
    if n==0 then
        return
    endif
    set n=n-n/8191*8191
    set Hash$Array_name$2[n]=y
endif
if y!=0 then
    set Hash$Array_name$3[y]=x
endif
set Hash$Array_name$4[m]=Hash$Array_name$0
set Hash$Array_name$5[m]=0
set Hash$Array_name$0=m
endfunction
//! endtextmacro[/codes]

接下来,我会举出第一个例子,关于动态触发的一个问题,我们在它使用完毕以后如何删除掉它。最传统的方法是使用缓存,下面跟我一起使用数组存储系统来解决掉它吧。

我们从最简单的情况出发,假设每个触发只使用了一个TriggerCondition,依据我们已有的拉链Hash法,如下就可以了。
[codes=jass]//如下代码,生成了一个Hash表
//! runtextmacro Hash("Trghash_get","Trghash_free","00")
globals
//每个trigger只有一个triggercondition,只要一个数组就够了
integer array Trgcon_i
endglobals
//这个函数通过传参获取了触发和它的条件
function Trgcon_store takes trigger tg,triggercondition tgc returns nothing
local triggercondition Tc
local integer I
//调用了刚才生成拉链Hash,获取下脚标n
local integer n=Trghash_get(0,tg,true)
//判断是否在Hash表中获取了地址
if n!=0 then
    //是!使用Trgcon_i存储下条件
    set Tc=tgc
    set Trgcon_i[n]=I
endif
set I=0
endfunction

function Trgcon_del takes trigger tg returns nothing
local triggercondition Tc
local integer I
//调用了刚才生成拉链Hash,获取下脚标n
local integer n=Trghash_get(0,tg,false)
//判断是否在Hash表中获取了地址
if n!=0 then
    //是!通过Trgcon_i获取触发条件
    set I=Trgcon_i[n]
    //判断是否存储了条件
    if I!=0 then
        //是!删除条件
        call TriggerRemoveCondition(tg,Tc)
    endif
    //释放tg在Hash表中的位置
    call Trghash_free(n)
    //删除tg
    call DestroyTrigger(tg)
endif
set I=0
endfunction[/codes]

接下来,尽管我不太清楚一个触发配多个触发条件的用途是什么,但是我依然这么假设,假设我在地图中每个触发最多的情况下会有3个条件,简单来做,上面的代码可以在多申请两个全局数组来基本解决。
[codes=jass]globals
integer array Trgcon_i1
integer array Trgcon_i2
integer array Trgcon_i3
endglobals[/codes]
当然,这肯定不是最好的方法,现在我假设我不清楚我的地图中一个触发会有多少触发条件,最多可能是10,又或者是30,但却不是每个触发都如此,依然有触发与条件是一对一的关系存在。继续增多上面的全局数组只会造成浪费,下面我来展示数组存储系统在处理不定数数据的时候应当采取的方法(请大家比较一下下面的代码和拉链Hash法代码的异同)。
[codes=jass]//如下代码,生成了一个Hash表
//! runtextmacro Hash("Trghash_get","Trghash_free","00")
globals
//这个数组用于记录拉链的起点
integer array Trg_Ha
//下面3个东西用途是节点的分配以及删除,具体来说,Trg_maxN、Trg_F、Trg_Hb是struct需要的,而Trg_Hb独立构造了多个单向链表
integer Trg_maxN=1
integer Trg_F=0
integer array Trg_Hb
//存储句柄
integer array Trg_Hc
endglobals
//这个函数的第一个传参是掉用Trghash_get(tg)后获取的整数n,后面是触发条件
function Trgcon_store takes integer n,integer I,triggercondition Tc returns nothing
//获取Trg_Ha[n]指向的拉链的起点
local integer x=Trg_Ha[n]
//下面的10行代码就应用了struct的方法,具体不解释了
local integer y=Trg_F
if y!=0 then
    set Trg_F=Trg_Hb[y]
else
    set y=Trg_maxN
    if y>8191 then
        return
    endif
    set Trg_maxN=y+1
endif
//将n指向拉链的新起点
set Trg_Ha[n]=y
//将y值插入链表头部
set Trg_Hb[y]=x
//存储句柄的handle值
set Trg_Hc[y]=I
endfunction
//这个函数的传参是待销毁的触发
function Trgcon_del takes trigger tg returns nothing
local triggercondition Tc
local integer I
//通过函数Trghash_get获取tg在Hash表中的下脚标
local integer n=Trghash_get(0,tg,false)
local integer x
local integer y
//判断触发是否有关联数据
if n!=0 then
    //是!获取链表的头部
    set x=Trg_Ha[n]
    //判断链表中是否有数据
    if x!=0 then
        //是!进入循环,依次删除触发条件
        loop
            set I=Trg_Hc[x]
            call TriggerRemoveCondition(tg,Tc)
            //y的作用就是记录下链表最后一个整数
            set y=x
            set x=Trg_Hb[y]
            //链表末尾则跳出
            exitwhen x==0
        endloop
        //获取链表的头部
        set x=Trg_Ha[n]
        //下面的代码就应用了struct的方法,想想是怎样的
        set Trg_Hb[y]=Trg_F
        set Trg_F=x
        //销毁链表的头部
        set Trg_Ha[n]=0
    endif
    //清除tg在Hash表中的位置,并删除之
    call Trghash_free(n)
    call DestroyTrigger(tg)
endif
//排泄
set I=0
endfunction[/codes]

好了,可能你会说,我们使用了4个变量加7个数组就实现了这个没用的东西?其实这只是一个例子,我只是写出代码,而它的用处嘛,听我说。当我们要对一些不定数量的同类型句柄依次采取相同或者类似的动作时,你就发现你会需要上面的代码的,而且这些句柄已经绑定了一个整数。比如我们可以将一堆不定数的特效或者闪电效果绑定于一个计时器,或者模拟一个可以传参的单位组,或者其他我还未想到的用途。

那么,我简单的总结下,拉链Hash的代码中用的方法是使用Hb1、Hb2构造了双向链表,这是因为Hash表中会经常删除一些节点,使用这个方法可以更快的修复链表。而在后面的代码中,因为并不经常会这样,所以只使用单向链表就可以了。
TimerDataSystem、拉链Hash和上面的代码中,struct的用法都发生了一些小改变,变得更适合我们的代码。


这个方法有它的缺陷,例如我上面所说的,当你使用它来模拟单位组时,你可以很方便的向这个单位组中添加和删除单位,但是你不能很方便的判断某个单位是否已经存在于单位组中。所以,使用这个模拟的单位组最好是你的代码允许重复添加单位,但是这样的约定并不合理,因为在很多场合我们需要这样的功能,我现在有一个解决这个缺陷的不成熟的方法,请继续看下去。
回复 支持 反对

使用道具 举报

 楼主| 发表于 2009-4-2 00:01:52 | 显示全部楼层
很抱歉,我的本意只是先贴出缓存版的物品合成,然后在贴出数组版的,但是失控了,我没想到会有这么多字数...大家可以选择性的看一下,对此不感兴趣的可以直接去下一楼了。


以上说了拉链法中遇到的一个困难,我将在4L给出的物品合成的代码中初步的解决这个问题。接下我先贴出我的使用缓存的物品合成代码,是我在刚接触Jass时自己写的代码,书写习惯和现在略有不同,而且在代码的缩进方面也做的不太对,请大家见谅了。代码的思路如果和现在大家使用的物品合成的代码一样的话那是最好了,如果不一样也没关系,我会做一些注解帮助大家理解。

[codes=jass]//这个是物品合成代码的头文件,其实是我以前使用的Gc+ReturnBug系统的头文件,在这里我只留下目前所需要的。
globals
constant gamecache RGC=InitGameCache("|cffc5d43ecccty1l|r")
endglobals
//! define DEff(e) DestroyEffect(e)
//! define AEff(mod,x,y) AddSpecialEffect(mod,x,y)
//! define AEffT(mod,target,point) AddSpecialEffectTarget(mod,target,point)
//! define Eff(mod,x,y) DestroyEffect(AEff(mod,x,y))
//! define EffT(mod,target,point) DestroyEffect(AEffT(mod,target,point))
//! define If(b) if(b)then
//! define Or(b) elseif(b)then
//! define SetInt(arr,s,val) StoreInteger(RGC,arr,s,val)
//! define SetInts(arr,s,i) StoreInteger(RGC,arr,s,i+GetStoredInteger(RGC,arr,s))
//! define SetBoolean(arr,s,val) StoreBoolean(RGC,arr,s,val)
//! define SetReal(arr,s,val) StoreReal(RGC,arr,s,val)
//! define SetString(arr,s,val) StoreString(RGC,arr,s,val)
//! define GetInt(arr,s) GetStoredInteger(RGC,arr,s)
//! define GetBoolean(arr,s) GetStoredBoolean(RGC,arr,s)
//! define GetIf(arr,s) if(GetStoredBoolean(RGC,arr,s))then
//! define GetOr(arr,s) elseif(GetStoredBoolean(RGC,arr,s))then
//! define GetReal(arr,s) GetStoredReal(RGC,arr,s)
//! define GetString(arr,s) GetStoredString(RGC,arr,s)
//! define FreeString(s) FlushStoredMission(RGC,s)
//! define Freei(arr,s) FlushStoredInteger(RGC,arr,s)
//! define Freer(arr,s) FlushStoredReal(RGC,arr,s)
//! define Frees(arr,s) FlushStoredString(RGC,arr,s)
//! define Freeb(arr,s) FlushStoredBoolean(RGC,arr,s)
//! define IsI(arr,s) HaveStoredInteger(RGC,arr,s)
//! define IsR(arr,s) HaveStoredReal(RGC,arr,s)
//! define IsS(arr,s) HaveStoredString(RGC,arr,s)
//! define IsB(arr,s) HaveStoredBoolean(RGC,arr,s)[/codes]
好了,代码正式开始
[codes=jass]
globals
//这个整数变量记录的是合成公式的总数,每调用一次函数ComItem它都会作为该合成公式的编号,最后会增加1
integer ComItem_maxN=1
//创建一个函数,在下面应该使用下面的语句来使得物品合成代码生效
//call TriggerAddCondition(Trg_ComItem,Condition(function ComItem_trg))
//call TriggerRegisterUnitEvent(Trg_ComItem,XXXX,EVENT_UNIT_PICKUP_ITEM)
//函数ComItem_trg在代码的最下面
constant trigger Trg_ComItem=CreateTrigger()
endglobals
//! define ComItem_s "|cff123456ComItem|r"
//! define ComItem_sID "ITEM"
//! define ComItem1_1(a,h) ComItem(a,0,0,0,0,0,h,0,0,0,0,0,0)
//! define ComItem2_1(a,b,h) ComItem(a,b,0,0,0,0,h,0,0,0,0,0,0)
//! define ComItem2_2(a,b,h,j) ComItem(a,b,0,0,0,0,h,j,0,0,0,0,0)
//! define ComItem3_1(a,b,c,h) ComItem(a,b,c,0,0,0,h,0,0,0,0,0,0)
//! define ComItem3_2(a,b,c,h,j) ComItem(a,b,c,0,0,0,h,j,0,0,0,0,0)
//! define ComItem3_3(a,b,c,h,j,k) ComItem(a,b,c,0,0,0,h,j,k,0,0,0,0)
//! define ComItem4_1(a,b,c,d,h) ComItem(a,b,c,d,0,0,h,0,0,0,0,0,0)
//! define ComItem4_2(a,b,c,d,h,j) ComItem(a,b,c,d,0,0,h,j,0,0,0,0,0)
//! define ComItem4_3(a,b,c,d,h,j,k) ComItem(a,b,c,d,0,0,h,j,k,0,0,0,0)
//! define ComItem5_1(a,b,c,d,e,h) ComItem(a,b,c,d,e,0,h,0,0,0,0,0,0)
//! define ComItem5_2(a,b,c,d,e,h,j) ComItem(a,b,c,d,e,0,h,j,0,0,0,0,0)
//! define ComItem5_3(a,b,c,d,e,h,j,k) ComItem(a,b,c,d,e,0,h,j,k,0,0,0,0)
//! define ComItem1_u(a,h,unitID) ComItem(a,0,0,0,0,0,h,0,0,0,0,0,unitID)
//! define ComItem2_u(a,b,h,unitID) ComItem(a,b,0,0,0,0,h,0,0,0,0,0,unitID)
//! define ComItem3_u(a,b,c,h,unitID) ComItem(a,b,c,0,0,0,h,0,0,0,0,0,unitID)
//! define ComItem4_u(a,b,c,d,h,unitID) ComItem(a,b,c,d,0,0,h,0,0,0,0,0,unitID)
//! define ComItem5_u(a,b,c,d,e,h,unitID) ComItem(a,b,c,d,e,0,h,0,0,0,0,0,unitID)
//! define ComItem6_u(a,b,c,d,e,f,h,unitID) ComItem(a,b,c,d,e,f,h,0,0,0,0,0,unitID)


//这个函数是注册叠加物品的,用法如下
//call ComItemS('I000',12,'I001')
//call ComItemS('I001',3,'I002')
//这样物品'I000'会在叠加数量达到12时合成一个'I001',而物品'I001'在达到3时合成一个'I002'
//注意:在我的代码中,物品种类是ITEM_TYPE_PURCHASABLE才会叠加,并且只能参与叠加
function ComItemS takes integer a,integer num,integer h returns nothing
local item i=CreateItem(h,0,0)
local string s=I2S(a)+ComItem_sID
    If(num>1)
    //使用缓存记录下需要的数量和要合成的物品
    call SetInt(s,"num",num)
    call SetInt(s,"ComI",h)
        //创建物品,然后判断它的种类是否是ITEM_TYPE_PURCHASABLE,用法见函数ComItem_trg2
        If(GetItemType(i)==ITEM_TYPE_PURCHASABLE)
        call SetBoolean(s,"boolean",true)
        endif
    endif
call RemoveItem(i)
set i=null
set s=null
endfunction

//这个函数是注册物品合成的,用法如下(配合上面的define,调用起来还是比较方便的)
//call ComItem1_1('I010','I011')
//↑可以由一个物品直接变成另外一个,一般处理东西的是合成卷轴
//call ComItem2_1('I014','I013','I020')
//↑最简单的,两个物品合成一个
//call ComItem3_1('I011','I013','I013','I021')
//↑三个物品合成一个,支持同一配方中的同类物品
//call ComItem5_2('I015','I017','I016','I018','I015','I022','I023')
//↑5合2,传参的顺序是无所谓的,可以合成多个物品,多物品合成多物品是为装备分解等功能做出来的
//call ComItem3_u('I021','I020','I022','I030','H001')
//↑支持合成专属,上例是为单位ID为'H001'合成专属的配方
//函数支持最多6物品合成6物品,如果搞不错传参的位置的话,可以直接调用函数ComItem
//注意,下面的调用是非法的
//call ComItem('I010',0,'I020',0,0,0,'I023',0,0,'I024',0,0,0)
//在读取物品ID时,函数会在遇到第一个0处停止,一次上一函数相当于↓
//call ComItem1_1('I010','I023')
function ComItem takes integer a,integer b,integer c,integer d,integer e,integerf,integer g,integer h,integer j,integer k,integer l,integer m,integerunitID returns nothing
local integer array i
local integer n=1
local integer z
local string s=I2S(ComItem_maxN)+ComItem_s
local string ItemID_s
//记录上传的原料物品ID,用循环处理
set i[1]=a
set i[2]=b
set i[3]=c
set i[4]=d
set i[5]=e
set i[6]=f
    loop
    exitwhen i[n]==0 or n>6
    set ItemID_s=I2S(i[n])
        //判断在该编号(ComItem_maxN)的合成配方中,该物品(i[n])是否已经添加了
        if IsI(s,ItemID_s) then
        //是!将该物品的编号加一
        call SetInts(s,ItemID_s,1)
        else
        //否!生成该物品的编号,个位表示所需的数量,十位表示其顺序
        call SetInt(s,ItemID_s,n*10+1)
        //这个记录的该物品(i[n])参与的合成公式的编号
        set z=GetInt(ComItem_sID,ItemID_s)+1
        call SetInt(ItemID_s+ComItem_sID,I2S(z),ComItem_maxN)
        call SetInt(ComItem_sID,ItemID_s,z)
        endif
        
    set n=n+1
    endloop
//记录该合成公式的原料数量
call SetInt(s,"num",n-1)
//记录上传的生成物品ID,用循环处理
set n=1
set i[1]=g
set i[2]=h
set i[3]=j
set i[4]=k
set i[5]=l
set i[6]=m
    loop
    exitwhen i[n]==0 or n>6
    call SetInt(s,I2S(n),i[n])
    set n=n+1
    endloop
    //判断生成的物品是否是专属
    If(unitID>0)
    //是!记录下单位ID
    call SetBoolean(s,"onlyone",true)
    call SetInt(s,"unitID",unitID)
    endif
//公式的编号加一,等待下次函数运行
set ComItem_maxN=ComItem_maxN+1
set s=null
set ItemID_s=null
endfunction
//上面的注册函数是在地图初始化后运行的,请在注册的时候注意代码执行上限的限制

//下面的函数就是动作函数了,单位在获取了物品之后会运行ComItem_trg1或ComItem_trg2
//这个函数是处理物品叠加的,可能看起来有些冗余,但是我觉得都是必须的
function ComItem_trg2 takes unit u,item i returns nothing
local item it
local integer id=GetItemTypeId(i)
local integer z=0
local integer n=GetItemCharges(i)
local integer maxN
local string s
    loop
    set it=UnitItemInSlot(u,z)
        //判断各个物品栏中的物品是否是上传物品的同类型物品
        If(it!=i and GetItemTypeId(it)==id)
        //是!则删除物品i
        call RemoveItem(i)
        set i=it
        //记录下能叠加的数量
        set n=n+GetItemCharges(i)
        endif
   
    set z=z+1
    exitwhen z>=6
    endloop
//获取之前注册的叠加数量的上限
set s=I2S(id)+ComItem_sID
set maxN=GetInt(s,"num")
        //判断是否能生成新的物品
        If(n<maxN or maxN==0)
        //否!设置物品i的数量,函数就此完成任务。
        call SetItemCharges(i,n)
        Or(n>=maxN)
        //是!计算可以生成的新物品的数量以及合成后物品i的剩余数量
        //这里的设计就是考虑到得到的物品的叠加数可能本身就是大于maxN的,这样z的值就会大于一
        set z=n/maxN
        set n=n-z*maxN
            //判断物品i是否有剩余
            If(n!=0)
            //是!设置物品i的数量
            call SetItemCharges(i,n)
            else
            //否!删除物品i
            call RemoveItem(i)
            endif
        
        set id=GetInt(s,"ComI")
            //判断生成物品的(叠加)数量是否大于1
            If(z>1)
                //是!
                //判断生成的物品是否可以叠加
                GetIf(s,"boolean")
                //是!创建物品,设置好数量后送给单位
                set i=CreateItem(id,0,0)
                call SetItemCharges(i,z)
                call UnitAddItem(u,i)
                else
                    //否!则生成相应数量的物品给单位
                    loop
                    call UnitAddItemById(u,id)
                    set z=z-1
                    exitwhen z<=0
                    endloop
                endif
            Or(z==1)
            //否!不需要别的考虑了,直接创建物品
            call UnitAddItemById(u,id)
            endif
        endif
set s=null   
set it=null
endfunction
//这个函数是处理物品合成的
function ComItem_trg1 takes unit u,integer n returns boolean
local string s=I2S(n)+ComItem_s
local integer array i
local item array it
local item it0=null
local integer z=0
local integer a
local integer b
local string ItemID_s=null
local boolean bo=false
    //判断该合成公式是否是某些单位的专属
    GetIf(s,"onlyone")
        //是!
        //判断获取物品的单位的ID是否符合条件
        if GetUnitTypeId(u)!=GetInt(s,"unitID") then
        //否!返回false
        set s=null
        return bo
        endif
    endif
//获取合成公式的原料物品数量
set n=GetInt(s,"num")
    loop
    set it0=UnitItemInSlot(u,z)
    set ItemID_s=I2S(GetItemTypeId(it0))
        //判断单位物品栏中第z个物品是否参与了该合成公式
        if IsI(s,ItemID_s) then
        //是!
        //获取该物品在该公式中的编号和所需数量
        set a=GetInt(s,ItemID_s)
        set b=a/10
            //判断该物品是否已经够用了
            If(i<a)
                //否!下面的代码就是修改i的值来用于上面一行的判断
                If(i==0)
                set i=b*10+1
                else
                set i=i+1
                endif
            //记录下物品,以后若能合成就删除它们
            set it[n]=it0
            set n=n-1
            endif
        endif
    set z=z+1
    //搜完所有的物品栏或者找齐了所有原料则跳出
    exitwhen z>=6 or n<=0
    endloop
    //判断原料是否齐备了
    If(n==0)
    //是!
    set bo=true
    set n=1
        //删除所有的原料
        loop
        exitwhen it[n]==null
        call RemoveItem(it[n])
        set it[n]=null
        set n=n+1
        endloop
        //如果原料超过1则创建合成特效,排除掉了单个物品的转化
        If(n>=2)
        call EffT("Abilities\\\\Spells\\\\Items\\\\AIsm\\\\AIsmTarget.mdl",u,"origin")
        endif
        //如果专属只能合成一个,那么在此消除掉单位ID
        GetIf(s,"onlyone")
        call SetInt(s,"unitID",-1)
        endif
    //依次创建生成的物品
    set n=1
        loop
        exitwhen not IsI(s,I2S(n))
        call UnitAddItemById(u,GetInt(s,I2S(n)))
        set n=n+1
        endloop
    endif
set s=null
set it0=null
set ItemID_s=null
//如果成功了会返回true,不然就是false,下面的循环会继续
return bo
endfunction

function ComItem_trg takes nothing returns boolean
local unit u=GetTriggerUnit()
local item it=GetManipulatedItem()
local string s=null
local integer i=1
    //判断物品是否是用于叠加的
    if GetItemType(it)==ITEM_TYPE_PURCHASABLE then
    //是!调用ComItem_trg2
    call ComItem_trg2(u,it)
    else
    //否!
    set s=I2S(GetItemTypeId(it))+ComItem_sID
        //历遍单位参与的所有的合成公式直到合成成功或找到最后
        loop
        exitwhen not IsI(s,I2S(i))
        exitwhen ComItem_trg1(u,GetInt(s,I2S(i)))
        set i=i+1
        endloop
    set s=null
    endif
set u=null
set it=null
return false
endfunction[/codes]

不太习惯做注解,也不知道弄成这样有没影响大家查看,这个是很早之前做的模板了,基本上都忘了思路是怎样的了,这次一个一个做注解看下来,也算是给自己做数组版的一点思路吧。
下面看修改为数组版本的代码吧。
回复 支持 反对

使用道具 举报

 楼主| 发表于 2009-4-2 00:02:01 | 显示全部楼层
这就是物品合成的代码了,根据这个例子,我们并不要求删除合成配方,所以我就把删除节点的功能全部给去掉了。同时为了简练,我把物品叠加的功能取消了,那个的实现很简单的,参考上面的缓存版吧。由于在注册合成公式的时候,代码生成了一系列的链表,所以更加的需要大家注意魔兽的代码的执行上限。

关于上面提到的如何解决拉链法的缺陷问题,在这里我说我们依然依据拉链法来解决这个问题。在物品合成这个例子中,我们将拉链Hash做一些修改,之前的Hash法只是将一个整数转为成为一个拉链的“头”,而现在我们将物品ID与合成公式的编号j和在一起转化为整数n,将其作为一个拉链的“头”,当我们要判断任意一物品是否参与了合成公式j时,我们需要上传参数物品ID和合成公式j,等我们得到一个非0的整数时,我们便得知该物品参与了该合成公式了。

比起初个版本,我现在做了详细的注解,希望大家可以理解拉链法在各个方面的应用方法。最主要的灵活应用,所以一定要先熟悉它,试着比较我在上面列举出来的代码的不同,然后自己编写出适合自己的代码,多多练习才行的。

[codes=jass]//这个就是拉链Hash法获取的一部分,单链表版的。看了上面的帖子,我想这里应该不需要注解了。
globals
integer CI_maxNa=1
integer array CI_Ha
integer array CI_Hb
integer array CI_Hc
endglobals
function CI_Fa takes integer i returns integer
local integer x=CI_Ha[i-i/8191*8191]
loop
    exitwhen x==0
    exitwhen CI_Hc[x]==i
    set x=CI_Hb[x]
endloop
return CI_Hh[x]
endfunction
//这个就是我所说的拉链Hash法变体版获取的一部分,注意比较它们的异同
globals
integer CI_maxNb=1
integer array CI_Hd
integer array CI_He
integer array CI_Hf
integer array CI_Hg
endglobals
function CI_Fb takes integer i,integer j returns integer
//注意这个算法,不知道大家是否还记得双重Hash法呢?它使用了类似的思路,因为j是一个小于8191的整数,说实话我不清楚这个方法是否是高效的,如有更好的方法还请赐教
//类似的,当i和j都是句柄的时候,我想我们可以这样,但同样不保证是最好的方法
//local integer x=i-i/8191*8191+(j-j/8191*8191+1)*33
local integer x=i-i/8191*8191+(i-i/8189*8189+1)*j
set x=CI_Hd[x-x/8191*8191]
loop
    exitwhen x==0
    if CI_Hf[x]==i then
        exitwhen CI_Hg[x]==j
    endif
    set x=CI_He[x]
endloop
return CI_Hk[x]
endfunction
//下面这个函数具体来说实现了4个功能
//1,将上传的整数i经过拉链Hash处理后获取了一个绑定的整数n
//2,将n作为一个拉链的“头”,记录该ID的物品参与了哪些合成公式
//3,将整数i和整数j一起处理后得到新的整数n,
//4,将n用来记录该ID的物品在公式j中的编号和需要的数量,注意这个编号并不是连续的也不需要是
globals
//这几个用来实现功能2
integer CI_maxNc=1
integer array CI_Hh
integer array CI_Hi
integer array CI_Hj
//这个用来实现功能4
integer array CI_Hk
endglobals
function CI_Fc takes integer i,integer j,integer b returns nothing
//对比顶楼看看吧,很标准的拉链法,这个用来实现功能1
local integer n=i-i/8191*8191
local integer x=CI_Ha[n]
local integer y=x
local integer z
loop
    exitwhen x==0
    exitwhen CI_Hc[x]==i
    set x=CI_Hb[x]
endloop
if x==0 then
    set x=CI_maxNa
    set CI_maxNa=x+1
    set CI_Ha[n]=x
    set CI_Hb[x]=y
    set CI_Hc[x]=i
endif
//Hmmm...再对比顶楼看看吧,又是很标准的拉链法,这里的x就是另一个拉链的“头”了,实现了功能2
set z=CI_Hh[x]
set y=z
if CI_Hj[z]!=j then
    set z=CI_maxNc
    set CI_maxNc=z+1
    set CI_Hh[x]=z
    set CI_Hi[z]=y
    set CI_Hj[z]=j
endif
//下面的代码请参考函数CI_Fb,用来实现功能3
set n=n+(i-i/8189*8189+1)*j
set n=n-n/8191*8191
set x=CI_Hd[n]
set y=x
loop
    exitwhen x==0
    if CI_Hf[x]==i then
        exitwhen CI_Hg[x]==j
    endif
    set x=CI_He[x]
endloop
if x==0 then
    set x=CI_maxNb
    set CI_maxNb=x+1
    set CI_Hd[n]=x
    set CI_He[x]=y
    set CI_Hf[x]=i
    set CI_Hg[x]=j
endif
//这个用来实现功能4,在之后的判断中,如果得到了0,则说明该ID的物品未参与到公式j中,在
if CI_Hk[x]==0 then
    set CI_Hk[x]=b*6
else
    set CI_Hk[x]=CI_Hk[x]+1
endif
endfunction
//注册合成公式就调用它了
globals
//这个是合成公式的编号
integer CI_maxNd=1
//记录合成公式需要的原料个数
integer array CI_Hl
//记录被合成的物品ID
integer array CI_Hm
//记录被合成物品在数组CI_Hm对应的下脚标起始点m和数量n,=m*7+n
integer array CI_Hn
//记录被合成物品的个数,大于8191就不能继续存储了
integer CI_maxNe=0
//记录是否是专属,为0则无限制
integer array CI_Ho
endglobals
//调用的参数是6原料+6成品+单位ID
function CI_Fd takes integer a,integer b,integer c,integer d,integer e,integer f,integer g,integer h,integer j,integer k,integer l,integer m,integer unitID returns nothing
local integer array i
local integer x=0
local integer y=1
local integer z=0
local integer maxN=CI_maxNd
//在这个例子中,CI_maxNc是与CI_maxNb相等的,CI_maxNc和CI_maxNe是所有的整数变量中增长最快的,所以当它们超出8191时,代码就不能再存储合成公式了
//因为每次原料或者成品最多是6个,所以我将它们限制在8191-6了
if CI_maxNc>=8185 or CI_maxNe>=8185 then
    return
endif
//将原料的ID记录于数组中,方便循环处理
set i[1]=a
set i[2]=b
set i[3]=c
set i[4]=d
set i[5]=e
set i[6]=f
//与缓存版不同,我这里不再限制所有的原料都必须写在一起了,中间有0也无所谓了
loop
    exitwhen y>6
    set x=i[y]
    if x!=0 then
        set z=z+1
        //注解请看函数CI_Fc
        call CI_Fc(x,maxN,z)
    endif
    set y=y+1
endloop
set CI_Hl[maxN]=z

set x=CI_maxNe
set y=1
set i[1]=g
set i[2]=h
set i[3]=j
set i[4]=k
set i[5]=l
set i[6]=m
loop
    exitwhen y>6
    set z=i[y]
    if z!=0 then
        set CI_Hm[x]=z
        set x=x+1
    endif
    set y=y+1
endloop
set CI_Hn[maxN]=CI_maxNe*6+x//=CI_maxNe*6+CI_maxNe+n=CI_maxNe*7+n
set CI_Ho[maxN]=unitID
set CI_maxNe=x
set CI_maxNd=maxN+1
endfunction

//这个就是负责物品合成了,通过下面的方法使用
globals
trigger Trg_ComItem=CreateTrigger()
endglobals
//call TriggerAddCondition(Trg_ComItem,Condition(function CI_Fh))
//call TriggerRegisterUnitEvent(Trg_ComItem,XXX,EVENT_UNIT_PICKUP_ITEM)
function CI_Fe takes nothing returns boolean
local item It
local integer I
local unit u=GetTriggerUnit()
local item mi=GetManipulatedItem()
local integer uid=GetUnitTypeId(u)
local integer x=0
local integer y=1
local integer z=0
local integer n
local integer j
local integer m
local integer p
local integer k
local integer array id
local integer array id2
local integer array id3
local integer array id4
//记录下单位所拥有的所有物品,避免以后循环中反复调用,提高效率
loop
    set It=UnitItemInSlot(u,x)
    if It!=null and It!=mi then
        set id[y]=I
        set id2[y]=GetItemTypeId(It)
        set y=y+1
    endif
    set x=x+1
    exitwhen x>=5
endloop
set It=mi
set id[y]=I
set id2[y]=GetItemTypeId(It)
//获取拾取物品所指向的合成公式拉链的起点
set n=CI_Fa(id2[y])
loop
    //位于拉链的末尾则跳出
    exitwhen n==0
    //获取合成公式的编号
    set j=CI_Hj[n]
    //检查是否是专属物品或者触发单位是否符合合成专属条件
    if CI_Ho[j]==0 or uid==CI_Ho[j] then
        //符合条件!获取该公式中需要的原料数目
        set x=CI_Hl[j]
        set z=y
        loop
            //如果现有的物品数量小于所需数量,则跳出
            exitwhen z-x<0
            //获取当前物品在公式j中的编号以及数量
            set m=CI_Fb(id2[z],j)
            //判断该物品是否参与的该合成公式
            if m>0 then
                //是!则获取到编号
                set p=m/6
                set k=id3[p]
                //判断这次的合成是否还需要该类型的物品
                if k<m then
                    //是!需要,则对id3[p]进行一些运算
                    if k==0 then
                        set id3[p]=p*6
                    else
                        set id3[p]=k+1
                    endif
                    //记录下该物品,若可以合成则在后面删除之
                    set id4[x]=id[z]
                    set x=x-1
                endif
            endif
            //在检查完所有单位持有的物品或者是原料查找齐备后跳出循环
            set z=z-1
            exitwhen z<=0 or x<=0
        endloop
        //x==0说明所有需要的原料都齐备了,跳出
        exitwhen x==0
        set z=1
        //清除id3的数据
        loop
            set id3[z]=0
            set z=z+1
            exitwhen z>6
        endloop
    endif
    //获取下一个公式编号
    set n=CI_Hi[n]
endloop
//检查循环是因何跳出的,若n==0则说明物品参与的合成公式历遍了依然未成功合成
if n!=0 then
    //n不等于0而跳出,则说明x==0
    set x=CI_Hl[j]
    //去掉下面的几行,则单位可以一直都合成专属,默认是只合成一个
    if CI_Ho[j]!=0 then
        set CI_Ho[j]=-1
    endif
    //公式需要的原料数大于2则创建特效
    if x>=2 then
        call DestroyEffect(AddSpecialEffectTarget("Abilities\\\\Spells\\\\Items\\\\AIsm\\\\AIsmTarget.mdl",u,"origin"))
    endif
    //依次删除原料
    loop
        set I=id4[x]
        call RemoveItem(It)
        exitwhen x<=1
        set x=x-1
    endloop
    //依次创建成品
    set y=CI_Hn[j]
    set z=y/7
    set y=y-z*6
    loop
        call UnitAddItemById(u,CI_Hm[z])
        set z=z+1
        exitwhen z>=y
    endloop
endif
set u=null
set mi=null
set I=0
return false
endfunction[/codes]

以上!
回复 支持 反对

使用道具 举报

发表于 2009-4-2 00:47:36 | 显示全部楼层
楼主这种精神!


-这不应该是jass区内容么。。。不懂j的人看不来的
回复 支持 反对

使用道具 举报

发表于 2009-4-2 01:13:49 | 显示全部楼层
jass区 人比这少..

注释好详细~~~好长..大概浏览了下~~以后别人问我 就拉他来看这个
回复 支持 反对

使用道具 举报

发表于 2009-4-2 05:25:51 | 显示全部楼层
做研究不容易啊  支持下~
回复 支持 反对

使用道具 举报

发表于 2009-4-2 12:08:15 | 显示全部楼层
囧,橙子这话.....真的好长..
回复 支持 反对

使用道具 举报

发表于 2009-4-2 13:38:21 | 显示全部楼层
越来越长越变态了。。。

ms扫了便没看出原理。。。明天再看吧。。。
回复 支持 反对

使用道具 举报

 楼主| 发表于 2009-4-6 00:38:03 | 显示全部楼层
下午重新编辑了下帖子,修改了很多地方。关于顶楼所说的“时间回溯”貌似在Dota里面有相似的技能,我在之前有看过一个演示,思路隐约记得一点,晚上就顺便写写出来了,也做了一个演示地图。
注解就不做了,大家主要看看函数SJ_funa这个拉链法是如何与TimerDataSystem配合使用的,它自己形成了一个循环单链,这正是“时间回溯”技能所需要的效果,这也是拉链法灵活应用的一个例子吧。
技能的效果是:单位使用了“添加”技能后,添加一个“回到过去”技能,使用可以回到n秒前的位置。这个效果也可以删除的,并且n是随机的一个数。
看不懂的同学下载演示研究研究吧,进入游戏使用技能有相关的提示,应该有助于大家理解吧。
[codes=jass]//Hash↓
//! runtextmacro Hash("Trgunit_get","Trgunit_free","00")
//TimerDataSystem↓
globals
integer Timer_F
integer array Timer_Data
integer Timer_ID=1
endglobals
//! define Timer_N 3000
function Timer_cre takes nothing returns boolean
local timer array t
local integer bugs=-1
local integer n=2
local integer I
local timer Tm=CreateTimer()
local integer fid=I-1
local integer id=1
local integer id2
loop
    set Tm=CreateTimer()
    set id2=I-fid
    if(id2>0 and id2<8191)then
        set Timer_Data[id]=id2
        set n=n+1
        set id=id2
        exitwhen n>Timer_N
    else
        set bugs=bugs+1
        set t[bugs]=Tm
    endif
endloop
loop
    exitwhen bugs<=-1
    call DestroyTimer(t[bugs])
    set t[bugs]=null
    set bugs=bugs-1
endloop
set Timer_F=fid
set I=0
return false
endfunction

globals
integer SJ_maxN=1
integer SJ_F=1
integer array SJ_a1
endglobals
function SJ_funa takes integer i,integer n returns integer
local integer x=SJ_F
local integer y=x
local integer z
local integer max=SJ_maxN
loop
    set z=SJ_a1[x]
    if z==0 then
        set max=max+1
        set z=max
        set SJ_a1[x]=z
    endif
    set n=n-1
    exitwhen n<=1
    set x=z
endloop
set x=SJ_a1[z]
set SJ_a1[z]=y
if x!=0 then
    set SJ_F=x
else
    set max=max+1
    set SJ_F=max
endif
set SJ_maxN=max
set Timer_Data=y
return y
endfunction

globals
integer array SJ_a2
real array SJ_x
real array SJ_y
endglobals
function SJ_funb takes nothing returns nothing
local integer I
local unit U
local timer Tm=GetExpiredTimer()
local integer n=I-Timer_F
local integer m=Timer_Data[n]
set I=SJ_a2[n]
set SJ_x[m]=GetUnitX(U)
set SJ_y[m]=GetUnitY(U)
set Timer_Data[n]=SJ_a1[m]
set I=0
endfunction

function SJ_func takes nothing returns nothing
local integer I
local unit U
local timer Tm=GetExpiredTimer()
local integer n=I-Timer_F
set I=SJ_a2[n]
call UnitAddAbility(U,'A001')
call UnitAddAbility(U,'A002')
set Timer_Data[n]=Timer_ID
set Timer_ID=n
set I=0
endfunction

globals
integer array SJ_a3
endglobals
function SJ_fund takes nothing returns boolean
local integer I
local timer Tm
local unit U=GetTriggerUnit()
local integer n=Trgunit_get(0,U,true)
local integer id=GetSpellAbilityId()
local integer m
local integer x
local integer y
if id=='A000' then
    set m=Timer_ID
    if m!=0 then
        set x=GetRandomInt(5,15)
        set y=Timer_Data[m]
        if SJ_maxN+x<=8191 and y!=0 then
            call SJ_funa(m,x)
            set SJ_a2[y]=I
            set SJ_a2[m]=I
            set SJ_a3[n]=m
            set Timer_ID=Timer_Data[y]
            call UnitRemoveAbility(U,'A000')
            set I=m+Timer_F
            call TimerStart(Tm,1,true,function SJ_funb)
            set I=y+Timer_F
            call TimerStart(Tm,x+1,false,function SJ_func)
        endif
    endif
elseif id=='A001' then
    set m=SJ_a3[n]
    set x=Timer_Data[m]
    set y=SJ_a1[x]
    set SJ_a1[x]=SJ_F
    set SJ_F=y
    set Timer_Data[m]=Timer_ID
    set Timer_ID=m
    call UnitRemoveAbility(U,'A001')
    call UnitRemoveAbility(U,'A002')
    call UnitAddAbility(U,'A000')
    set I=Timer_F+m
    call PauseTimer(Tm)
elseif id=='A002' then
    set m=Timer_Data[SJ_a3[n]]
    call SetUnitX(U,SJ_x[m])
    call SetUnitY(U,SJ_y[m])
endif
set I=0
return false
endfunction[/codes]

aaaaa.w3x

28 KB, 下载次数: 17

回到过去

回复 支持 反对

使用道具 举报

发表于 2009-4-7 16:44:48 | 显示全部楼层
恩恩~~不错~加分~~
其实只要教双拉链就行了,剩下的让他们自己去发掘,具体的优化~还可以啦。
恩恩……
回复 支持 反对

使用道具 举报

 楼主| 发表于 2009-4-7 20:19:45 | 显示全部楼层
估计这帖子大段大段的代码大家看的都有些烦躁吧,嗯,其实我也没有办法。

其实在发这个主题贴的时候我就在想如何把数组存储系统给模板化了,其实这个模板化和我之前提倡的大家自己写出自己的代码是有点小冲突呢。但是没有关系,其实原理什么的不重要,最重要的是大家知道如何使用它,将它应用到地图中去,并能该掉之前使用缓存的时候的一些习惯。虽然这样想了,但是结果是我在这个帖子中自己提出了一些问题,虽然解决了,在帖子的最终却没有找到模板化的方法。

简单说一下目前的情况吧,现在试图使用数组存储系统的大家或多或少的都发现了这个系统的一些小毛病。因为使用的是拉链法,所以在需要寻找一个小链表中的某个元素时,我们必须历遍这个链表,这个毛病在拉链Hash中就有所体现了,不过因为拉链Hash中碰撞的几率较小,所以拉链不是很长,即使是历遍也不是很影响效率。但是将拉链法应用在其他地方就不是这样了,很多时候我们需要一个长度为N的链表,这时候我们需要获取链表中某一节点的值的时候采取历遍的方式确实是一个很愚蠢的方法。我在写帖子之前隐约有了一些解决这个问题的思路,但是不是很明确,于是就有了4楼和10楼的两种代码,那么现在我就把这两楼的代码整合起来。需要注意的是,下面的代码对于熟悉拉链法的同学,写出来并不困难,比较难的是使用它的过程,我将在末尾向大家说明。

哦,忘了,有一点需要说明一下,可能是我的习惯问题吧,我总是喜欢在无聊的时候把之前写下来的代码拿出来看看,经常看也就经常会发现一些问题,所以细心的同学应该会发现我每次放出代码的时候这些代码总是会变化一些的。嗯,能如此频繁的变动也说明了我的代码总是或多或少有一些问题的,但总之了,一定是越改越好的,所以啊,请在看的帖子的时候注意一下发表日期,越靠后的越是值得采纳的。

于是我想说的是我的拉链Hash法的文本宏代码有了一点小改变,嗯,之前的版本并没有什么问题,只是这个版本在运行文本宏的时候上传的参数减少了,嗯,稍微方便了一些。
[codes=jass]//! textmacro Hash takes N
globals
integer $N$_h0=0
integer $N$_h1=1
integer array $N$_h2
integer array $N$_h3
integer array $N$_h4
integer array $N$_h5
endglobals
function $N$_get takes integer I,handle H returns integer
local integer x=$N$_h2[I-I/8191*8191]
loop
    exitwhen x==0 or $N$_h5[x]==I
    set x=$N$_h4[x]
endloop
return x
endfunction
function $N$_sto takes integer I,handle H returns integer
local integer n=I-I/8191*8191
local integer x=$N$_h2[n]
local integer y=x
loop
    exitwhen x==0
    if $N$_h5[x]==I then
        return x
    endif
    set x=$N$_h4[x]
endloop
set x=$N$_h0
if x!=0 then
    set $N$_h0=$N$_h4[x]
else
    set x=$N$_h1
    if x>8191 then
        return 0
    endif
    set $N$_h1=x+1
endif
set $N$_h2[n]=x
if y!=0 then
    set $N$_h3[y]=x
endif
set $N$_h4[x]=y
set $N$_h5[x]=I
return x
endfunction
function $N$_del takes integer m returns nothing
local integer x=$N$_h3[m]
local integer y=$N$_h4[m]
local integer n
if x!=0 then
    set $N$_h3[m]=0
    set $N$_h4[x]=y
else
    set n=$N$_h5[m]
    if n==0 then
        return
    endif
    set n=n-n/8191*8191
    set $N$_h2[n]=y
endif
if y!=0 then
    set $N$_h3[y]=x
endif
set $N$_h4[m]=$N$_h0
set $N$_h5[m]=0
set $N$_h0=m
endfunction
//! endtextmacro[/codes]

还有关于UnionBug,linzefei在论坛发过两个帖子分别说了UnionBug在使用中应当注意的两个问题,并且也提到了实现UnionBug对全局变量的类型并没有限制,于是之前的我写的UnionBug的头文件可以修改一下了。因为在一段代码中,需要强制转化的句柄类型并不是很多,一般不会超过3或者4个的吧,于是代码如下:
[codes=jass]globals
//以下所有的变量其实都是等同的了,但是我们选用这些字母只是为了方便记忆
//比如这个,我们就用H代表了所有的句柄,用I代表了整数,U表示单位,T可以是触发或者计时器或者计时窗口或者触发条件,这些都是常用的句柄了,当然不够的话就使用下面的备用的。当然,这只是我的习惯,这个大家可以随意。
constant integer H=0
constant integer I=0
constant integer U=0
constant integer T=0
constant integer UB1=0
constant integer UB2=0
endglobals[/codes]

好了,插曲结束,下面我将介绍拉链法的改进意见。
回复 支持 反对

使用道具 举报

 楼主| 发表于 2009-5-4 06:56:18 | 显示全部楼层
首先声明下,以下的部分代码参考了cctvfive在帖子http://www.islga.org/bbs/read.php?tid=26840中的代码。

[codes=jass]globals
integer F1=1
integer array Ha

integer F=1
integer maxN=0
integer array Hb
integer array Hc
integer array Hd

integer array He
integer array Hf1
integer array Hf2
integer array Hg
integer array Hh
endglobals

function HashLL1 takes integer m,integer n,integer x returns nothing
    local integer z=n*20101
    local integer y
    set z=m+z-z/8191*8191
    if z>8191 then
        set z=z-8191
    endif
    set y=He[z]
    set Hf1[x]=y
    if y!=0 then
        set Hf2[y]=x
    endif
    set He[z]=x
    set Hg[x]=m
    set Hh[x]=n
endfunction

function HashLL2 takes integer x returns nothing
    local integer y=Hf2[x]
    local integer z=Hf1[x]
    local integer m
    if y!=0 then
        set Hf2[x]=0
        set Hf1[y]=z
    else
        set m=Hh[x]*20101
        if m==0 then
            return
        endif
        set m=Hg[x]+m-m/8191*8191
        if m>8191 then
            set m=m-8191
        endif
        set He[m]=z
    endif
    if z!=0 then
        set Hf2[z]=y
    endif
    set Hg[x]=0
    set Hh[x]=0
    set Hc[x]=0
endfunction

function CreateLL takes integer n returns integer
    local integer x=F
    local integer y=1
    local integer z
    local integer m=0
    local integer max=maxN+n
    if max<=8191 and n>0 then
        set maxN=max
        set m=F1
        if Ha[m]!=0 then
            set F1=Ha[m]
        else
            set F1=m+1
        endif
        set Ha[m]=x
        set Hd[m]=n
        loop
            call HashLL1(m,y,x)
            set y=y+1
            exitwhen y>n
            if Hb[x]!=0 then
                set x=Hb[x]
            else
                set Hb[x]=x+1
                set x=x+1
            endif
        endloop
        set y=F
        if Hb[x]!=0 then
            set F=Hb[x]
        else
            set F=x+1
        endif
        set Hb[x]=y
    endif
    return m
endfunction

function StoreLL1 takes integer m,integer i returns nothing
    local integer x=Ha[m]
    set Hc[x]=i
    set Ha[m]=Hb[x]
endfunction

function GetLL1 takes integer m returns integer
    local integer x=Ha[m]
    set Ha[m]=Hb[x]
    return Hc[x]
endfunction

function StoreLL2 takes integer m,integer n,integer i returns nothing
    local integer z
    if n>0 and n<=Hd[m] then
        set z=n*20101
        set z=m+z-z/8191*8191
        if z>8191 then
            set z=z-8191
        endif
        set z=He[z]
        loop
            exitwhen Hg[z]==m and Hh[z]==n
            set z=Hf1[z]
        endloop
        set Hc[z]=i
    endif
endfunction

function GetLL2 takes integer m,integer n returns integer
    local integer z
    if n>0 and n<=Hd[m] then
        set z=n*20101
        set z=m+z-z/8191*8191
        if z>8191 then
            set z=z-8191
        endif
        set z=He[z]
        loop
            exitwhen Hg[z]==m and Hh[z]==n
            set z=Hf1[z]
        endloop
        return Hc[z]
    endif
    return 0
endfunction

function DestroyLL takes integer m returns nothing
    local integer n=Hd[m]
    local integer x=Ha[m]
    local integer y=x
    if n>0 then
        loop
            call HashLL2(x)
            set x=Hb[x]
            exitwhen x==y
        endloop
        set y=Hb[x]
        set Hb[x]=F
        set F=y
        set Ha[m]=F1
        set F1=m
        set maxN=maxN-n
    endif
endfunction[/codes]

晕了,写了两个多小时,天已经亮啦,我去睡觉啦。
心急的同学就凑合着看吧,没心情写注解了,等这个周末我再来编辑下吧。
呃,不保证没有Bug,毕竟写出来还没有仔细检查呢,话说思路也就是如此了。
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

Archiver|移动端|小黑屋|地精研究院

GMT+8, 2019-10-24 04:20 , Processed in 0.329683 second(s), 29 queries , Gzip On.

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表