中文字幕二区_国产精品免费在线观看_黄色网站观看_人人草人人澡_日本真实娇小xxxx

地形數(shù)據(jù)不屬于A*尋路的范圍，這里定義一個(gè) IMapTileModel 接口，由其它（模型）類來(lái)實(shí)現(xiàn)地圖通路的判斷。其它比如尋路超時(shí)的判斷這里也不介紹，具體參考 AStar類及其測(cè)試代碼。這里只介紹三部分主要內(nèi)容：

* 數(shù)據(jù)存儲(chǔ)
    * 尋路過(guò)程
    * 列表排序

數(shù)據(jù)存儲(chǔ)
首先看看三個(gè)關(guān)鍵變量：

private var m_openList : Array; //開(kāi)放列表，存放節(jié)點(diǎn)ID
private var m_openCount : int; //當(dāng)前開(kāi)放列表中節(jié)點(diǎn)數(shù)量
private var m_openId : int; //節(jié)點(diǎn)加入開(kāi)放列表時(shí)分配的唯一ID(從0開(kāi)始)

開(kāi)放列表 m_openList 是個(gè)二叉堆（一維數(shù)組），F(xiàn)值最小的節(jié)點(diǎn)始終排在最前。為加快排序，開(kāi)放列表中只存放節(jié)點(diǎn)ID ，其它數(shù)據(jù)放在各自的一維數(shù)組中：

private var m_xList : Array; //節(jié)點(diǎn)x坐標(biāo)
private var m_yList : Array; //節(jié)點(diǎn)y坐標(biāo)
private var m_pathScoreList : Array; //節(jié)點(diǎn)路徑評(píng)分F值
private var m_movementCostList : Array; //(從起點(diǎn)移動(dòng)到)節(jié)點(diǎn)的移動(dòng)耗費(fèi)G值
private var m_fatherList : Array; //節(jié)點(diǎn)的父節(jié)點(diǎn)(ID)

這些數(shù)據(jù)列表都以節(jié)點(diǎn)ID為索引順序存儲(chǔ)。看看代碼如何工作：

//每次取出開(kāi)放列表最前面的ID
currId = this.m_openList[0];
//讀取當(dāng)前節(jié)點(diǎn)坐標(biāo)
currNoteX = this.m_xList[currId];
currNoteY = this.m_yList[currId];

還有一個(gè)很關(guān)鍵的變量：private var m_noteMap : Array;
//節(jié)點(diǎn)(數(shù)組)地圖,根據(jù)節(jié)點(diǎn)坐標(biāo)記錄節(jié)點(diǎn)開(kāi)啟關(guān)閉狀態(tài)和ID

使用 m_noteMap 可以方便的存取任何位置節(jié)點(diǎn)的開(kāi)啟關(guān)閉狀態(tài)，并可取其ID進(jìn)而存取其它數(shù)據(jù)。m_noteMap 是個(gè)三維數(shù)組，第一維y坐標(biāo)（第幾行），第二維x坐標(biāo)（第幾列），第三維節(jié)點(diǎn)狀態(tài)和ID。判斷點(diǎn)(p_x, p_y)是否在開(kāi)啟列表中：

return this.m_noteMap[p_y][p_x][NOTE_OPEN];

尋路過(guò)程
AStar類 尋路的方法是 find() :

/**
* 開(kāi)始尋路
* @param p_startX        起點(diǎn)X坐標(biāo)
* @param p_startY        起點(diǎn)Y坐標(biāo)
* @param p_endX        終點(diǎn)X坐標(biāo)
* @param p_endY        終點(diǎn)Y坐標(biāo)
* @return                 找到的路徑(二維數(shù)組 : [p_startX, p_startY], ... , [p_endX, p_endY])
*/      
public function find(p_startX : int, p_startY : int, p_endX : int, p_endY : int) : Array{/* 尋路 */}

注意這里返回?cái)?shù)據(jù)的形式：從起點(diǎn)到終點(diǎn)的節(jié)點(diǎn)數(shù)組，其中每個(gè)節(jié)點(diǎn)為一維數(shù)組[x, y]的形式。為了加快速度，類里沒(méi)有使用Object或是Point，節(jié)點(diǎn)坐標(biāo)全部以數(shù)組形式存儲(chǔ)。如節(jié)點(diǎn)note的x坐標(biāo)為note[0],y坐標(biāo)為note[1]。

下面開(kāi)始尋路，第一步將起點(diǎn)添加到開(kāi)啟列表：

this.openNote(p_startX, p_startY, 0, 0, 0);

openNote() 方法將節(jié)點(diǎn)加入開(kāi)放列表的同時(shí)分配一個(gè)唯一的ID、按此ID存儲(chǔ)數(shù)據(jù)、對(duì)開(kāi)啟列表排序。接下來(lái)是尋路過(guò)程：

while (this.m_openCount > 0)
{
    //每次取出開(kāi)放列表最前面的ID
    currId = this.m_openList[0];
    //將編碼為此ID的元素列入關(guān)閉列表
    this.closeNote(currId);
    //如果終點(diǎn)被放入關(guān)閉列表尋路結(jié)束，返回路徑
    if (currNoteX == p_endX && currNoteY == p_endY)
        return this.getPath(p_startX, p_startY, currId);
    //...每輪尋路過(guò)程
}
//開(kāi)放列表已空，找不到路徑
return null;

每輪的尋路：

//獲取周圍節(jié)點(diǎn)，排除不可通過(guò)和已在關(guān)閉列表中的
aroundNotes = this.getArounds(currNoteX, currNoteY);
//對(duì)于周圍每個(gè)節(jié)點(diǎn)
for each (var note : Array in aroundNotes)
{
    //計(jì)算F和G值
    cost = this.m_movementCostList[currId] + (note[0] == currNoteX || note[1] == currNoteY) ? COST_STRAIGHT : COST_DIAGONAL;
    score = cost + (Math.abs(p_endX - note[0]) + Math.abs(p_endY - note[1])) * COST_STRAIGHT;
    if (this.isOpen(note[0], note[1])) //如果節(jié)點(diǎn)已在開(kāi)啟列表中
    {
        //測(cè)試節(jié)點(diǎn)的ID
    checkingId = this.m_noteMap[note[1]][note[0]][NOTE_ID];
    //如果新的G值比節(jié)點(diǎn)原來(lái)的G值小,修改F,G值，換父節(jié)點(diǎn)
    if(cost < this.m_movementCostList[checkingId])
    {
        this.m_movementCostList[checkingId] = cost;
        this.m_pathScoreList[checkingId] = score;
        this.m_fatherList[checkingId] = currId;
        //對(duì)開(kāi)啟列表重新排序
        this.aheadNote(this.getIndex(checkingId));
    }
    } else //如果節(jié)點(diǎn)不在開(kāi)放列表中
    {
    //將節(jié)點(diǎn)放入開(kāi)放列表
    this.openNote(note[0], note[1], score, cost, currId);
    }
}

從終點(diǎn)開(kāi)始依次沿父節(jié)點(diǎn)回到到起點(diǎn)，返回找到的路徑：

/**
* 獲取路徑
* @param p_startX    起始點(diǎn)X坐標(biāo)
* @param p_startY    起始點(diǎn)Y坐標(biāo)
* @param p_id        終點(diǎn)的ID
* @return             路徑坐標(biāo)數(shù)組
*/      
private function getPath(p_startX : int, p_startY : int, p_id: int) : Array
{
    var arr : Array = [];
    var noteX : int = this.m_xList[p_id];
    var noteY : int = this.m_yList[p_id];
    while (noteX != p_startX || noteY != p_startY)
    {
    arr.unshift([noteX, noteY]);
    p_id = this.m_fatherList[p_id];
    noteX = this.m_xList[p_id];
    noteY = this.m_yList[p_id];
    }
    arr.unshift([p_startX, p_startY]);
    this.destroyLists();
    return arr;
}

列表排序
這部分看代碼和注釋就可以了，不多說(shuō)：

/** 將(新加入開(kāi)放別表或修改了路徑評(píng)分的)節(jié)點(diǎn)向前移動(dòng) */
private function aheadNote(p_index : int) : void
{
    var father : int;
    var change : int;
    //如果節(jié)點(diǎn)不在列表最前
    while(p_index > 1)
    {
    //父節(jié)點(diǎn)的位置
    father = Math.floor(p_index ／ 2);
    //如果該節(jié)點(diǎn)的F值小于父節(jié)點(diǎn)的F值則和父節(jié)點(diǎn)交換
    if (this.getScore(p_index) < this.getScore(father))
    {
        change = this.m_openList[p_index - 1];
        this.m_openList[p_index - 1] = this.m_openList[father - 1];
        this.m_openList[father - 1] = change;
        p_index = father;
    } else
    {
        break;
    }
    }
}
/** 將(取出開(kāi)啟列表中路徑評(píng)分最低的節(jié)點(diǎn)后從隊(duì)尾移到最前的)節(jié)點(diǎn)向后移動(dòng) */
private function backNote() : void
{
    //尾部的節(jié)點(diǎn)被移到最前面
    var checkIndex : int = 1;
    var tmp : int;
    var change : int;
    while(true)
    {
    tmp = checkIndex;
    //如果有子節(jié)點(diǎn)
    if (2 * tmp <= this.m_openCount)
    {
        //如果子節(jié)點(diǎn)的F值更小
        if(this.getScore(checkIndex) > this.getScore(2 * tmp))
        {
        //記節(jié)點(diǎn)的新位置為子節(jié)點(diǎn)位置
        checkIndex = 2 * tmp;
        }
        //如果有兩個(gè)子節(jié)點(diǎn)
        if (2 * tmp + 1 <= this.m_openCount)
        {
        //如果第二個(gè)子節(jié)點(diǎn)F值更小
        if(this.getScore(checkIndex) > this.getScore(2 * tmp + 1))
        {
            //更新節(jié)點(diǎn)新位置為第二個(gè)子節(jié)點(diǎn)位置
            checkIndex = 2 * tmp + 1;
        }
        }
    }
    //如果節(jié)點(diǎn)位置沒(méi)有更新結(jié)束排序
    if (tmp == checkIndex)
    {
        break;
    }
    //反之和新位置交換，繼續(xù)和新位置的子節(jié)點(diǎn)比較F值
    else
    {
        change = this.m_openList[tmp - 1];
        this.m_openList[tmp - 1] = this.m_openList[checkIndex - 1];
        this.m_openList[checkIndex - 1] = change;
    }
    }
}

其中 getScore() 方法：

/**
* 獲取某節(jié)點(diǎn)的路徑評(píng)分F值
* @param p_index    節(jié)點(diǎn)在開(kāi)啟列表中的索引(從1開(kāi)始)
*/      
private function getScore(p_index : int) : int
{
    //開(kāi)啟列表索引從1開(kāi)始，ID從0開(kāi)始，數(shù)組索引從0開(kāi)始
    return this.m_pathScoreList[this.m_openList[p_index - 1]];
}

經(jīng)典論壇討論:
http://bbs.blueidea.com/thread-2738527-1-1.html

本文鏈接：http://www.95time.cn/tech/multimedia/2007/4665.asp　

出處：藍(lán)色理想
責(zé)任編輯：elesa

上一頁(yè) 如虎添翼 - 使用二叉堆優(yōu)化 下一頁(yè)

◎進(jìn)入論壇Flash專欄版塊參加討論