物品合成

actboy168

物品合成系统应该有很多人过了，这里只是想演示下hash表的用法。


利用hash表搜索合成公式。

[jass]
function GetHashTableValue takes integer key, integer ord returns integer
    local integer index = ModuloInteger(key, 8191)
    local integer inc   = ModuloInteger(key, 8189) + 1
    local integer step  = 0
   
    loop
        exitwhen step > 8191
        
        if udg_HashTableKey[index] == 0 then
            return 0
        elseif udg_HashTableKey[index] == key + 1000 then
            if ord == 0 then
                return udg_HashTableValue[index]
            else
                set ord = ord - 1
            endif
        elseif udg_HashTableKey[index] == key then
            if ord == 0 then
                return udg_HashTableValue[index]
            else
                return 0
            endif
        endif
        
        set index = index + inc
        if index >= 8191 then
            set index = index - 8191
        endif
        set step = step + 1
    endloop
   
    return 0
endfunction

function SetHashTableValue takes integer key, integer value returns nothing
    local integer index = ModuloInteger(key, 8191)
    local integer inc   = ModuloInteger(key, 8189) + 1
    local integer step  = 0
   
    loop
        exitwhen step > 8191
        
        if udg_HashTableKey[index] == 0 then
            set udg_HashTableKey[index]   = key
            set udg_HashTableValue[index] = value
            return
        elseif udg_HashTableKey[index] == key then
            exitwhen udg_HashTableValue[index] == value
            set udg_HashTableKey[index] = key + 1000
        elseif udg_HashTableKey[index] == key + 1000 then
            exitwhen udg_HashTableValue[index] == value
        endif
        
        set index = index + inc
        if index >= 8191 then
            set index = index - 8191
        endif
        set step = step + 1
    endloop
endfunction

function AddComList6 takes integer itemA, integer itemB, integer itemC, integer itemD, integer itemE, integer itemF, integer itemG returns boolean
    local integer count = 0
   
    if udg_ComListCount > 1000 then
        return false
    endif

    set udg_ComList[(udg_ComListCount-1)*8+1] = itemA
    set udg_ComList[(udg_ComListCount-1)*8+2] = itemB
    set udg_ComList[(udg_ComListCount-1)*8+3] = itemC
    set udg_ComList[(udg_ComListCount-1)*8+4] = itemD
    set udg_ComList[(udg_ComListCount-1)*8+5] = itemE
    set udg_ComList[(udg_ComListCount-1)*8+6] = itemF
    set udg_ComList[(udg_ComListCount-1)*8+7] = itemG
   
    if itemA != 0 then
        set count = count + 1
        call SetHashTableValue(itemA, udg_ComListCount)
    endif
   
    if itemB != 0 then
        set count = count + 1
        call SetHashTableValue(itemB, udg_ComListCount)
    endif
   
    if itemC != 0 then
        set count = count + 1
        call SetHashTableValue(itemC, udg_ComListCount)
    endif
   
    if itemD != 0 then
        set count = count + 1
        call SetHashTableValue(itemD, udg_ComListCount)
    endif
   
    if itemE != 0 then
        set count = count + 1
        call SetHashTableValue(itemE, udg_ComListCount)
    endif
   
    if itemA != 0 then
        set count = count + 1
        call SetHashTableValue(itemA, udg_ComListCount)
    endif
   
    if itemF != 0 then
        set count = count + 1
        call SetHashTableValue(itemF, udg_ComListCount)
    endif
   
    if count == 0 then
        return false
    endif
   
    set udg_ComListCount = udg_ComListCount + 1
  
    return true
endfunction

function AddComList2 takes integer itemA, integer itemB, integer itemG returns boolean
    return AddComList6(itemA, itemB, 0, 0, 0, 0, itemG)
endfunction

function AddComList3 takes integer itemA, integer itemB, integer itemC, integer itemG returns boolean
    return AddComList6(itemA, itemB, itemC, 0, 0, 0, itemG)
endfunction

function AddComList4 takes integer itemA, integer itemB, integer itemC, integer itemD, integer itemG returns boolean
    return AddComList6(itemA, itemB, itemC, itemD, 0, 0, itemG)
endfunction

function AddComList5 takes integer itemA, integer itemB, integer itemC, integer itemD, integer itemE, integer itemG returns boolean
    return AddComList6(itemA, itemB, itemC, itemD, itemE, 0, itemG)
endfunction

function GetComListValue takes integer ord, integer index returns integer
    if ord >= 1000 then
        return 0
    endif
        
    return udg_ComList[8*(ord-1)+index]
endfunction

function ComItem takes unit u, integer itemid returns nothing
    local integer ord = 0
    local integer i
    local integer j
    local integer id
    local integer listindex
    local integer array items
    local boolean array bools
   
    set i = 0
    loop
        set items = GetItemTypeId(UnitItemInSlot(u, i))
        set bools = false
        set i = i + 1
        exitwhen i >= 6
    endloop

    call BJDebugMsg("物品拿起："+I2S(itemid))
    loop
        set listindex = GetHashTableValue(itemid, ord)
        call BJDebugMsg("listindex："+I2S(listindex))
        exitwhen listindex == 0 or ord >= 8191
        
        set i = 1
        loop
            exitwhen i > 6
            set id = GetComListValue(listindex, i)
            if id != 0 then
                set j = 0
                loop
                    if items[j] == id and bools[j] == false then
                        set bools[j] = true

                        exitwhen true
                    endif
                    
                    set j = j + 1
                    exitwhen j >= 6
                endloop
                exitwhen j == 6
            endif
            set i = i + 1
        endloop
        
        if i == 7 then
            set i = 0
            loop     
                if bools == true then
                    call RemoveItem(UnitItemInSlot(u, i))
                endif
               
                set i = i + 1
                exitwhen i >= 6
            endloop
            call DestroyEffect(AddSpecialEffectTarget("Abilities\\Spells\\Items\\AIem\\AIemTarget.mdl", u, "origin"))
            call UnitAddItemById(u, GetComListValue(listindex, 7))
            return
        endif
        
        set i = 0
        loop
            set bools = false
            set i = i + 1
            exitwhen i >= 6
        endloop
        
        set ord = ord + 1
    endloop
endfunction

function InitComList takes nothing returns nothing
    local integer i = 0
   
    loop
        exitwhen i > 8191
        set udg_HashTableKey = 0
        set i = i + 1
    endloop
   
    set udg_ComListCount = 1
   
    call AddComList2('I000', 'I000', 'I001')
    call AddComList2('I001', 'I001', 'I002')
    call AddComList2('I002', 'I002', 'I003')
    call AddComList3('I002', 'I003', 'I004', 'I008')
    call AddComList3('I002', 'I003', 'I005', 'I007')
    call AddComList3('I002', 'I003', 'I006', 'I009')
endfunction
[/jass]

zhuzeitou

数据结构课上hash貌似没怎么讲，唉唉

用户名是虾米

lz有时间解释下hash表的原理吗

看不太明白 什么意思

actboy168

其实gamecache就是hash表，联系gamecache就比较好理解了。

hash表就是一张能根据关键字迅速定位一个元素的表，这里迅速的定义就是搜索元素的速度应该是与hash表里的元素总数无关。而在gamecache里，使用了两个关键字来定位元素，关键字的类型是字符串。事实上在gamecache的内部实现里字符串还是要被转换成整数的，因为整数才方便做加减乘除。所以我这里用的是整数的关键字，联系gamecache，就不难理解这两个函数的功能了。

function GetHashTableValue takes integer key, integer ord returns integer
function SetHashTableValue takes integer key, integer value returns nothing

hash表的内部实现并没有具体的规定，只要能正确实现上面的两个接口即可。
我这里用的是最简单的方法，用udg_HashTableKey和udg_HashTableValue两个数组记录关键字和值。而用key%8191的值来做数组的

下标。剩下的问题就是冲突的处理，由于key的取值范围很大，有可能不同的key会得到同样的下标，这就是冲突。这里处理冲突的方法是双重哈希法，index = (key%8191+step*(key%8189+1))%8191，这个公式是可以历遍整个hash表的，证明从略。一开始step取0，有冲突就加1，直到找到空位。

在物品合成里还是有些和hash表不一样的，这里是用合成素材作为关键字，合成公式序号作为值，一个关键字可能会对应几个值，这就是函数GetHashTableValue里ord的作用。ord就是相同素材，不同合成公式的序号。处理ord的办法和冲突的处理类似。

用户名是虾米

谢谢ls

明白了一点点

261001126

引用第3楼actboy168于2008-08-29 23:10发表的  :
其实gamecache就是hash表，联系gamecache就比较好理解了。

hash表就是一张能根据关键字迅速定位一个元素的表，这里迅速的定义就是搜索元素的速度应该是与hash表里的元素总数无关。而在gamecache里，使用了两个关键字来定位元素，关键字的类型是字符串。事实上在gamecache的内部实现里字符串还是要被转换成整数的，因为整数才方便做加减乘除。所以我这里用的是整数的关键字，联系gamecache，就不难理解这两个函数的功能了。

function GetHashTableValue takes integer key, integer ord returns integer
.......

学习了。Thanks

风之幽雅

没注解还是看不太懂 起码想知道 一个FUNCTION-ENFUNCTION起到的作用

风之幽雅

另外再补个教程 假如我要将两个物品合成 需要做的步骤 这样就简单多了