Hash表所做的“野怪刷新”的演示

cccty1l

昨天看了actboy168所做的应用Hash表制作的物品合成，感觉可以把它应用到更多的方面。如下：

[codes=jass]globals
integer array hashi
endglobals
function hash takes integer I,handle H,boolean b returns integer
local integer ha=I-I/8191*8191
local integer hb=I-I/8179*8179+1
local integer n=0
local integer val
if(b)then
    set val=0
else
    set val=I
endif
loop
    exitwhen(hashi[ha]==val)or(n>499)
    set ha=ha+hb
    set n=n+1
    if(ha>=8191)then
        set ha=ha-8191
    endif
endloop
if(n>499)then
    return -1
else
    if(b)then
        set hashi[ha]=I
    endif
endif
return ha
endfunction[/codes]


在地图中每个Hash函数可以对应一个数组变量用于记录，这样可以给一个单位或者计时器绑定多个数值。
发一个应用Hash所做的野怪的刷新演示，希望大家可以交流下。

2008-12-22
修改了代码，添加了纠错和及时的跳出。
经测试循环里面可以跑到8500次以上，限制在500留有了很大余地。
PS，演示并没有修改，因为没必要，呵呵。

2009-1-8
在actboy168的指导下，再次更新了Hash函数，进一步提高了函数的效率。

cccty1l

二楼我占了。

对于4楼的疑问，你可以看下Renee大人的Union Bug，地址是：
http://www.islga.org/bbs/read.php?tid=8722

然后是5楼的，野怪刷新也许可以用单位组。就本演示里面来说，地图初始化时，触发选取了地图上所有的
Player(12)的单位，Hash后获取了整数(this)的编号，然后赋予ye_n[this]值n，再然后分别用ye_id[n],ye_x[n],
ye_y[n],ye_f[n]记录了单位的ID，XY坐标和面向角度。

当某个单位死亡后，根据其handle值获取上段所说的n值，一定时间后依据所记录的上述的数据创造新的单位，
同时再将新的单位Hash后，赋值ye_n[Hash(0,(新创建单位,true))]=n。

上面所说的总的意思是将n值绑定到某个单位上，然后我们来看将一个值绑定在一个单位上有几种方法：

现假定单位为U.
1。缓存，大家可能都会，利用return bug可以获取u的handle值，转化为字符串，存储n，如下：
[codes=jass]local string s=I2S(H2I(u))
call StoreInteger(GC,s,"bianhao",n)[/codes]
除了可以记录n以外，当然也可以记录很多数据，但是不得不提的就是较低的运行速度和字符串生成过多的问题。

2。单位自定义值，这个法子不知道大家是否舍弃了，如下：
[codes=jass]call SetUnitUserData(u,n)[/codes]
缺点多多，比如只能记录一个数值，倘若你还将自定义值用于其他用途，很容易出现冲突。

3。vjass我不太懂，说错了大家就批评我吧，如下：
[codes=jass]struct ujl
unit u
integer n
endstruct[/codes]
这样子就有一个自定义变量ujl了，优点是可以绑定多个数据，同时编写当然方便，但是却生成了一大堆的函数和
全局变量。

4。哈哈就是本帖的Hash方法了。演示里面只绑定了一个数据，但是它可以做更多，如下：
先罗列出需要的数组
[codes=jass]globals
integer array ye_n
//记录单位的编号
real array ye_l
//记录单位复活时间
.....
endglobals[/codes]
这些都可以通过Hash了u以后得到了this指针记录下来。同时如果把它用于缓存的话，如下：
[codes=jass]local string s=I2S(Hash(0,u,true))
call StoreInteger(GC,s,"bianhao",n)[/codes]
其生成的字符串只有8190个，缺点是需要存储的单位不能超过8191，其实注意排泄就可以啦。

thody

hash表的对应算法很晕。

thody

而且，函数第二个参数好像没有使用呢？

狡猾的兔子

用单位组不行么？有点脱裤子放屁吧？

cccty1l

再举个例子吧，像我这类的新手们初次接触jass的时候都会遇到做单位移动的难题，需要用到return bug和缓存，举个例子，
就是推人，单位U1对单位U2施法后，U2开始向后移动，我们现在多一个要求，U2每次移动都要受到来自U1的伤害，移动
速度（R1）、距离（R2）伤害（D）是随机的，同时它要支持多个单位移动。好了，缓存方法如下：

[codes==jass]globals
gamecache udg_GC
endglobals

function H2I takes handle h returns integer
return h
return 0
endfunction

function I2U takes integer i returns unit
return i
return null
endfunction

function I2T takes integer i returns timer
return i
return null
endfunction
以上是预备。

function yd_tm takes nothing returns nothing
local timer t=GetExpiredTimer()
local string s=I2S(H2I(t))
local unit U1=I2U(GetStoredInteger(udg_GC,s,"U1"))
local unit U2=I2U(GetStoredInteger(udg_GC,s,"U2"))
local real R1=GetStoredReal(udg_GC,s,"R1")
local real D=GetStoredReal(udg_GC,s,"D")
local real F=GetStoredReal(udg_GC,s,"F")
local integer i=GetStoredInteger(udg_GC,s,"i")
local real x=GetUnitX(U2)+Cos(F)*R1
local real y=GetUnitY(U2)+Sin(F)*R1
local boolean b=IsTerrainPathable(x,y,PATHING_TYPE_WALKABILITY)
if not b then
call SetUnitX(U2,x)
call SetUnitY(U2,y)
call UnitDamageTarget(U1,U2,D,true,true,ATTACK_TYPE_MELEE,DAMAGE_TYPE_NORMAL,WEAPON_TYPE_WHOKNOWS)
call DestroyEffect(AddSpecialEffectTarget("Abilities\\\\Weapons\\\\SteamTank\\\\SteamTankImpact.mdl",U2,"origin"))
set i=i-1
endif
if b or i==0 then
call PauseTimer(t)
call DestroyTimer(t)
call FlushStoredMission(udg_GC,s)
else
call StoreInteger(udg_GC,s,"i",i)
endif
set t=null
set U1=null
set U2=null
endfunction
function yd_tr takes nothing returns nothing
local unit U1=GetTriggerUnit()
local unit U2=GetSpellTargetUnit()
local real R1=GetRandomReal(10,35)
local real R2=GetRandomReal(1000,1800)
local real D=GetRandomReal(.5,3)
local integer i=R2I(R2/R1)
local timer t=CreateTimer()
local string s=I2S(H2I(t))
local real F=Atan2(GetUnitY(U2)-GetUnitY(U1),GetUnitX(U2)-GetUnitX(U1))
call StoreInteger(udg_GC,s,"U1",H2I(U1))
call StoreInteger(udg_GC,s,"U2",H2I(U2))
call StoreReal(udg_GC,s,"R1",R1)
call StoreReal(udg_GC,s,"D",D)
call StoreReal(udg_GC,s,"F",F)
call StoreInteger(udg_GC,s,"i",i)
call TimerStart(t,.02,true,function yd_tm)
set U1=null
set U2=null
set t=null
endfunction[/codes]

嗯，大家应该可以看出使用缓存时存取都会很麻烦。然后看使用Hash的方法。如下：

[codes==jass]globals
constant integer Ha=8191
constant integer Hb=1987
integer I
handle H
integer array Hi
endglobals
function Hash takes integer I,handle H,boolean b returns integer
local integer ha=I-I/Ha*Ha
local integer hb=(I/Hb+1)*Hb-I
loop
exitwhen (b and Hi[ha]==0)or(not b and Hi[ha]==I)
set ha=ha+hb
if ha>Ha then
set ha=ha-Ha-1
endif
endloop
if b then
set Hi[ha]=I
endif
return ha
endfunction
以上是预备。

globals
unit array yd_u1
unit array yd_u2
real array yd_r
real array yd_d
real array yd_f
integer array yd_i
endglobals
function yd_tm2 takes nothing returns nothing
local timer t=GetExpiredTimer()
local integer this=Hash(0,t,false)
local unit u=yd_u2[this]
local real x=GetUnitX(u)+Cos(yd_f[this])*yd_r[this]
local real y=GetUnitY(u)+Sin(yd_f[this])*yd_r[this]
local boolean b=IsTerrainPathable(x,y,PATHING_TYPE_WALKABILITY)
if not b then
call SetUnitX(u,x)
call SetUnitY(u,y)
call UnitDamageTarget(yd_u1[this],u,yd_d[this],true,true,ATTACK_TYPE_MELEE,DAMAGE_TYPE_NORMAL,WEAPON_TYPE_WHOKNOWS)
call DestroyEffect(AddSpecialEffectTarget("Abilities\\\\Weapons\\\\SteamTank\\\\SteamTankImpact.mdl",u,"origin"))
set yd_i[this]=yd_i[this]-1
endif
if b or yd_i[this]==0 then
call PauseTimer(t)
call DestroyTimer(t)
set Hi[this]=0
endif
set t=null
set u=null
endfunction
function yd_tr2 takes nothing returns nothing
local timer t=CreateTimer()
local unit U1=GetTriggerUnit()
local unit U2=GetSpellTargetUnit()
local integer this=Hash(0,t,true)
local real r2=GetRandomReal(1000,1800)
set yd_r[this]=GetRandomReal(10,35)
set yd_i[this]=R2I(r2/yd_r[this])
set yd_d[this]=GetRandomReal(.5,3)
set yd_f[this]=Atan2(GetUnitY(U2)-GetUnitY(U1),GetUnitX(U2)-GetUnitX(U1))
set yd_u1[this]=U1
set yd_u2[this]=U2
call TimerStart(t,.02,true,function yd_tm2)
set U1=null
set U2=null
set t=null
endfunction[/codes]

嗯，大家可以比较一下区别。

kook

palapala~

白银の式神

[codes=jass]//參數說明:
//I:要set的值或者要查詢的值
//b:true->set值 false->查詢值
//H:這個參數居然沒有用到？真神奇
//返回值:查詢或set的index
function Hash takes integer I,handle H,boolean b returns integer
//接下來兩行中的I也許應該是H2I(H)?
local integer ha=I-I/Ha*Ha
local integer hb=(I/Hb+1)*Hb-I
//雖然說n爲了防止超過8191個數據，但實際上沒實際用途，不如去掉
//1- 黨數據量接近8191時，尋址會變得很慢
//2- 黨數據量超過8191時，此函數并沒有進行有效的錯誤處理
local integer n=0
loop
//算法就不多說了，看不懂的同學自行學習去
exitwhen (b and Hi[ha]==0)or(not b and Hi[ha]==I)or(n>Ha)
set ha=ha+hb
if ha>Ha then
set ha=ha-Ha-1
endif
set n=n+1
endloop
//由於n超過8191的原因跳出時未作處理~
if b then
set Hi[ha]=I
endif
//返回實際查到的index
return ha
endfunction[/codes]

cccty1l

回LS，首先说下handle H没有被用到的疑问，其实是用到了，参考一楼Hash函数的调用方法，
原理是Renee大人的之前说过的Union Bug。接下来的integer I确实是如同H2I(H)之后的值。

关于函数中n，我也只是为求完全而做，确实完全不需要，而n超过8191之后也不需要处理方法，
因为经我测试，n在1000前后时，函数就不再运行了，超过行数限制了...

另一方面，理论上记录的变量只要在4000以下，函数完全没有问题，n一般不会跑过10~20的，
同时，因为该方法只有一个函数和一个对应的数组，其实可以在map里面多弄几个这样的东
西...，就不会有问题啦。

这是第一次做演示，还不太习惯给函数做注解，谢谢LS了哈。

blackiso

不错，很好，就是算法让我彻底迷糊了

狡猾的兔子

local integer this=Hash(0,t,false)
local unit u=yd_u2[this]

我关注的是这两行. 其实 this 不需要专门用个Hash来保存, 用一个专门全局整数变量就可以. 还有 timer 我还是那个态度, 不需要频繁 create和 destroy, 用个全局的, 用的时候启动, 不用的时候暂停就可以, 这样游戏会比较顺畅.

cccty1l

引用第10楼狡猾的兔子于2008-10-28 11:22发表的  :
local integer this=Hash(0,t,false)
local unit u=yd_u2[this]

我关注的是这两行. 其实 this 不需要专门用个Hash来保存, 用一个专门全局整数变量就可以. 还有 timer 我还是那个态度, 不需要频繁 create和 destroy, 用个全局的, 用的时候启动, 不用的时候暂停就可以, 这样游戏会比较顺畅.

关于timer的使用，确实应当如LS所说，用的全局的就可以了，然后在timer的函数里面使用循环顺序执行所有的动作，而此时由自己排序而来的连续的变量更加的适合这种方法。

需要注意的是，上述的方法运行时也有一些较为麻烦的方法。就移动为例。

循环最大数为maxN，循环执行到整数N时对应单位的移动应当停止，应有如下操作：
set u[N]=u[maxN]      //此处记录的单位也可以使用整数来记录单位的handle值
set i[N]=u[maxN]       //假设这个是移动应运行的剩余次数
.......
set maxN=maxN-1   //最大数减少
诸如此类，需要记录的数据越多，此时也就需要同样多的设置。
如果使用Hash的方法，先将要被移动的单位作为key来Hash(假设其对应数组为 integer array Hi)得到一个this指针，然后使用一个全局整数变量(例 integer array I)进行如下设置：

set I[maxN]=this   //只记录this指针
set maxN=maxN+1  //最大数增加

而需要读取的数据使用this来记录：

Hi[this]      //这个就是待移动单位，不需要赋值
set i[this]=***     //移动的剩余次数
set d[this]=***   //伤害值

等等此类，在单位移动需要停止的时候，只需要：

set I[N]=I[maxN]   //重赋值
set maxN=maxN-1
set Hi[this]=0   //排泄

就完成了，需要重新赋值的变量减少了。当然这样的代价是多出了一个Hash函数和两组用来记录的整数变量，呵呵，确实这个方法没什么优势可言。

另：local unit u=yd_u2[this]
这个局域变量也可不需要，只是下面的函数动作中多次用到了这个单位，我设置一个局域变量u，只是以期许可以增加点速度而已。

blackiso

感觉还是楼主的方法比较不错，一个是全局整数变量组 ，一个是全局整数变量（n个），如果要是使用vjass的时候倒是可以随时定义，但是使用jass的时候还是按照双重hash法提取指针比较方便一些，只要不用定义那么多的全局变量，一个handle对应一个index，最好的是还能清零可以循环利用。在一个地图里同一时间内存储8191个handle数值或者连续出现1000次指针被占用的情况用该是相当小吧，
另外觉得timer或者临时的trigger还是应该用一个删除一个，不少的时候都要向它身上绑定数据，确保handle值的唯一性还是很重要的，大不了就删除呗

顺便问一下楼主才用union bug时候如果直接采用returnbug就不用额外的那个i的参数调用了，当然了那个i无论去什么值无所谓，如果用returnbug是不是会大幅度影响运算速度？   [s:186]

狡猾的兔子

这也是我基本已经不用Jass，而使用vJ的原因。至于所谓的“指针”，在使用计时器的情况下，基本不需要记录；如果不使用计时器，则只需要用SetUnitUserData或 SetItemUserData来保存即可，除非和单位和物品都无关，否则很少要用到return bug保存的情况。

thody

returnbug，速度影响应该是在对硬盘的读写上。
而这个Unionbug的使用，速度主要影响在求索引值上。

cccty1l

回12L，关于函数运行速度方面的问题，其实我不太擅长这个。
嗯，函数的访问速度应该是要比全局和局域变量要慢好多的吧。
而对于union bug，我的了解也不是很多，期待有人有更多研究。

还有13L，应该是每人的编写习惯不一样的问题，我倒觉得使用循环的话一般会遇到我在
11L提出的问题，而自定义值的使用范围太受限了。

回14L，这个Hash函数的运行速度不代表union bug的赋值速度，因为求取this指针的运算是在
得到handle值之后的事，这个函数只是在被调用的时候使用了union bug。

狡猾的兔子

LZ不妨往需要使用局部数组变量的方向上研究研究。

拿刚才你说的移动举例，如果我需要给移动单位加上个拖影效果（比如说，6个影子），然后移动单位每做一个动作，后面的影子1，影子2……就要挨个重复一便这个动作，而且要支持多人。

这种效果用vJass来做是相当麻烦的，因为struct里不能使用变量数组，只能每个影子都分配一个独立的变量，还要记录真身与每个影子的动作和位置，以便让后面的影子重复。相反这种情形下用缓存就非常方便，用数组就可以方便控制。如果这个问题能有比缓存更好的解决方案，将是对Jass界的一个贡献。

[功夫3C_-_v0.09版里的鸣人技能-鸣人连弹就是这样的效果]

cccty1l

引用第16楼狡猾的兔子于2008-10-29 10:09发表的  :

给移动单位加上个拖影效果（比如说，6个影子），然后移动单位每做一个动作，后面的影子1，影子2……就要挨个重复一便这个动作，而且要支持多人。

.......

嗯，先简单说下吧。
演示里面有个函数   yd_tr2
[codes=jass]function yd_tr2 takes unit u,integer i,integer i2,real i3,real i4,real r,integer n,real m returns nothing
其中
u=要有幻影的单位，意即施法单位
i=要创建i个幻影
i2=u的单位ID
i3=创建幻影的时间间隔
i4=效果持续时间
r=秒移动距离，就是速度
n=单位的动作的编号
m=单位的动画的播放速度
[/codes]

以上，调整下就可以出效果了，演示里面默认有两个效果，移动的单位和幻影都在一个单位组里面并被Hash记录，所以请不要超过8191。
但是还是半成品，因为目前中途还不能换动作，思路有了，我得找个更好更有效的方法。
嗯，现在十分想去玩游戏...
明天继续吧！
Hash移动幻影.w3x (28 KB, 下载次数: 45)

2008-10-30 11:06 上传

点击文件名下载附件
半成品演示

2008年10月30日11:00:42
将之前的地图稍做修改，没有本质变化。
添加了另外一个单位，一直都有影子缠着...效果完全不行。说下思路吧，就是主单位的每一个命令都要侦测，然后稍隔一段时间后依次发给后面的小弟，但是这样做动作依然不能统一。当然这还只是思路，地图里面还没按照这么做...
想看看同学就下载看吧，参考价值不大。

狡猾的兔子

首先感谢LZ的辛苦劳动。

这是个多人跳砍的演示，虽然用的是和缓存的类似方法（把影子在队列中的位置保存在单位里），但能做到这样已经很不错了。如果是我，单纯做这个效果，我会把单位组也做成数组，然后把队列序号用 SetUnitUserData保存起来。

另外还有一个笨方法，就是利用 maxN，把影子数组变量的下标写成 [maxN * I + n]，n标示第n个影子，I标示影子的总数量，只要影子数保证小于 I，就可以通过 maxN换算出n来了。

其实我提的那个问题不是没有解决方案，只是每种方法都特麻烦，而且估计很难通过Jass自己本身来解决，除非有人再弄出一种再编译语言，类似vJass那样的。

期待LZ有更精彩的演示。

用户名是虾米

结构里应该是可以使用变量数组的，

有个局限就是  必须声明下数组的长度