你是不是想找相關Flash動畫公司: 二維動畫公司 Flash課件制作 宣傳片制作 還是要找北京、上海、西安、廣州、南京的動畫制作公司

flash游戲優化之四叉樹

編輯:翼虎動漫          操作時間:2010/9/19

 

 

 

四叉樹 (QuadTrees)可以說是2叉樹的擴展形式。

為什么在游戲中我們要用4叉樹代替一般的遍歷查找呢?它的優越性主要在于能在大規模對象隊列中快速的查找到你想要的內容,而他的消耗卻跟對象數的數目沒有太直接的關系;

如圖,你可以看到,如果在程序中通過遍歷查找對象,那是相當消耗資源的,而且會隨著數目的增加而呈正比例消耗;但4叉樹則不同,他通過預先建樹的過程把對象整理到一個完整的樹狀結構中去。查詢的時候只要根據要求的范圍,通過遍歷樹節點的方法即可得到想要的數據,快速而簡潔。

可能很多人會認為4叉樹只適用于靜態搜索,對于動態四叉樹效率則要相對減慢,本人起初也是這樣的想法,但經過驗證發現,確實如果你每次都重新遍歷樹的話,那消耗絕對是要比遍歷慢的,但是如果方法得當,像我上圖的就是一個動態四叉樹,叉用的方法是覆寫x跟y的設置,在賦值時驗證樹狀結構是否發生變化,這這樣做的好處是我們只需要很小的消耗即可完成修正過程,效率上可以說沒有太大改變。

下邊說說4叉樹的大致原理:

首先我們以屏幕中心將區域等分成4等分,然后以這4個區間(紅線區間)分支點把在各自區間的對象添加到對應支點的哈希表里邊;然后再分別對這4個區間各自進行4等分,重復上邊的步驟,(黃線區間),然后在如此類推,一般說只要進行5-6個層級的等分足以分到1像素大小左右了,這個過程稱之為建樹;建樹完畢接下來就是用樹;

為什么說4叉樹遍歷快就在于剛才我們的建樹過程已經將對象劃分到各個支點中去了,剩下的我們只要根據一個搜索區域或者以及一個精確度即可通過遞歸的方式遍歷與搜索區域相交的區間的節點即可。

比方說搜索區域只與第一區間相交,那么就意味之我們只需要遍歷第一個區間的節點即可,那樣我們就相當于剩下了其他3個區間對象的遍歷了,這就是4叉樹快的原因所在,而且他不跟對象數目直接相關,它只在乎建樹時的區間等級樹。

想我們做游戲場景一般都只會在5000*5000的范圍內,這樣的大小對于四叉樹來說只要6層左右就可以完成建樹過程了,但搜索的過程確實那么的快速、高效。

下邊是演示文件:

http://filer.blogbus.com/1587898/resource_158789812690578840.rar

四叉樹在游戲中要我們可以應用于:渲染面積,怪物的搜索ai,及數據搜索,條件剔除,深度排序等...

 

 

 

 

版權申明 ┊ 業務范圍 ┊ 加入我們  ┊ 聯系方式
翼虎動漫工作室承接各類Flash動畫制作 翼虎口號做客戶滿意的flash訂單。!
地址:上海市青浦區崧澤大道6066號19號樓二樓(整層) 全國免費咨詢熱線:400 804 9112
我們的業務還包括制作各式公交動畫廣告,地鐵動畫廣告,電視動畫廣告以及多媒體設計與制作。
友情鏈接: 北京三維動畫公司 二維動畫制作 Flash動畫制作 北京動畫制作公司 動畫制作公司 蘇ICP備19008057號
黑桃棋牌输钱经历