支持8方向的AStar寻路AS3算法


package hongwei.game.arithmetics
{
    import hongwei.game.map.IMapData;
    
    public final class AStar
    {
        private const COST_STRAIGHT:int = 5;
        private const COST_DIAGONAL:int = 7;
        
        private const NOTE_ID:int = 0;
        private const NOTE_OPEN:int = 1;
        private const NOTE_CLOSED:int = 2;
        
        private var oId:int;
        private var oCount:int;
        
        private var xList:Array;
        private var yList:Array;
        private var oList:Array;
        private var fList:Array;
        private var psList:Array;
        private var mcList:Array;
        private var noteMap:Array;
        
        public function AStar(mapData:IMapData)
        {
            _mapData = mapData;
        }
        
        private var _maxTry:int = 500;
        public function get maxTry():int
        {
            return _maxTry;
        }
        public function set maxTry(value:int):void
        {
            _maxTry = value;
        }
        
        private var _mapData:IMapData;
        public function get mapData():IMapData
        {
            return _mapData;
        }
        public function set mapData(value:IMapData):void
        {
            _mapData = value;
        }
        
        public function find(startX:int, startY:int, endX:int, endY:int):Array
        {
            initLists();
            oId = -1;
            oCount = 0;
            
            openNote(startX, startY, 0, 0, 0);
            
            var currentTry:int = 0;
            var currentId:int;
            var currentNoteX:int;
            var currentNoteY:int;
            var aroundNotes:Array;
            
            var checkingId:int;
            
            var cost:int;
            var score:int;
            
            while (0 < oCount)
            {
                if (++currentTry > _maxTry)
                {
                    destroyLists();
                    return null;
                }
                
                currentId = oList[0];
                currentNoteX = xList[currentId];
                currentNoteY = yList[currentId];
                
                closeNote(currentId);
                
                if (currentNoteX == endX && currentNoteY == endY)
                    return getPath(startX, startY, currentId);
                
                aroundNotes = getArounds(currentNoteX, currentNoteY);
                
                for each (var note:Array in aroundNotes)
                {
                    cost = mcList[currentId]
                        + (note[0] == currentNoteX || note[1] == currentNoteY ? COST_STRAIGHT : COST_DIAGONAL)
                        * _mapData.getCost(currentNoteX, currentNoteY, note[0], note[1]);
                    score = cost + (Math.abs(endX - note[0]) + Math.abs(endY - note[1])) * COST_STRAIGHT;
                    
                    if (isOpen(note[0], note[1]))
                    {
                        checkingId = noteMap[note[1]][note[0]][NOTE_ID];
                        
                        if (cost < mcList[checkingId])
                        {
                            fList[checkingId] = currentId;
                            psList[checkingId] = score;
                            mcList[checkingId] = cost;
                            
                            aheadNote(getIndex(checkingId));
                        }
                    }
                    else
                        openNote(note[0], note[1], score, cost, currentId);
                }
            }
            
            destroyLists();
            
            return null;
        }
        
        private function openNote(x:int, y:int, score:int, cost:int, fatherId:int):void
        {
            oId++;
            oCount++;
            
            if (null == noteMap[y])
                noteMap[y] = [];
            
            noteMap[y][x] = [];
            noteMap[y][x][NOTE_ID] = oId;
            noteMap[y][x][NOTE_OPEN] = true;
            
            xList.push(x);
            yList.push(y);
            oList.push(oId);
            fList.push(fatherId);
            psList.push(score);
            mcList.push(cost);
            
            aheadNote(oCount);
        }
        
        private function closeNote(id:int):void
        {
            oCount--;
            
            var noteX:int = xList[id];
            var noteY:int = yList[id];
            
            noteMap[noteY][noteX][NOTE_OPEN] = false;
            noteMap[noteY][noteX][NOTE_CLOSED] = true;
            
            if (0 >= oCount)
            {
                oCount = 0;
                oList = [];
                return;
            }
            
            oList[0] = oList.pop();
            backNote();
        }
        
        private function aheadNote(index:int):void
        {
            var fIndex:int;
            var change:int;
            
            while (index > 1)
            {
                fIndex = Math.floor(index / 2);
                
                if (getScore(index) < getScore(fIndex))
                {
                    change = oList[index - 1];
                    oList[index - 1] = oList[fIndex - 1];
                    oList[fIndex - 1] = change;
                    index = fIndex;
                }
                else
                    break;
            }
        }
        
        private function backNote():void
        {
            var cIndex:int = 1;
            var tIndex:int;
            var change:int;
            
            while (true)
            {
                tIndex = cIndex;
                
                if (2 * tIndex <= oCount)
                {
                    if (getScore(cIndex) > getScore(2 * tIndex))
                        cIndex = 2 * tIndex;
                    if (2 * tIndex + 1 <= oCount &&
                        getScore(cIndex) > getScore(2 * tIndex + 1))
                        cIndex = 2 * tIndex + 1;
                }
                
                if (tIndex == cIndex)
                    break;
                else
                {
                    change = oList[tIndex - 1];
                    oList[tIndex - 1] = oList[cIndex - 1];
                    oList[cIndex - 1] = change;
                }
            }
        }
        
        private function getArounds(x:int, y:int):Array
        {
            var r:Array = [];
            var checkX:int;
            var checkY:int;
            var canDiagonal:Boolean;
            
            checkX = x + 1;
            checkY = y;
            var canRight:Boolean = _mapData.isBlock(x, y, checkX, checkY);
            if (canRight && !isClosed(checkX, checkY))
                r.push([checkX, checkY]);
            
            checkX = x;
            checkY = y + 1;
            var canDown:Boolean = _mapData.isBlock(x, y, checkX, checkY);
            if (canDown && !isClosed(checkX, checkY))
                r.push([checkX, checkY]);
            
            checkX = x - 1;
            checkY = y;
            var canLeft:Boolean = _mapData.isBlock(x, y, checkX, checkY);
            if (canLeft && !isClosed(checkX, checkY))
                r.push([checkX, checkY]);
            
            checkX = x;
            checkY = y - 1;
            var canUp:Boolean = _mapData.isBlock(x, y, checkX, checkY);
            if (canUp && !isClosed(checkX, checkY))
                r.push([checkX, checkY]);
            
            checkX = x + 1;
            checkY = y + 1;
            canDiagonal = _mapData.isBlock(x, y, checkX, checkY);
            if (canDiagonal && canRight && canDown && !isClosed(checkX, checkY))
                r.push([checkX, checkY]);
            
            checkX = x - 1;
            checkY = y + 1;
            canDiagonal = _mapData.isBlock(x, y, checkX, checkY);
            if (canDiagonal && canLeft && canDown && !isClosed(checkX, checkY))
                r.push([checkX, checkY]);
            
            checkX = x - 1;
            checkY = y - 1;
            canDiagonal = _mapData.isBlock(x, y, checkX, checkY);
            if (canDiagonal && canLeft && canUp && !isClosed(checkX, checkY))
                r.push([checkX, checkY]);
            
            checkX = x + 1;
            checkY = y - 1;
            canDiagonal = _mapData.isBlock(x, y, checkX, checkY);
            if (canDiagonal && canRight && canUp && !isClosed(checkX, checkY))
                r.push([checkX, checkY]);
            
            return r;
        }
        
        private function getIndex(id:int):int
        {
            var r:int = 1;
            
            for each (var tId:int in oList)
            {
                if (id == tId)
                    return r;
                
                r++;
            }
            
            return -1;
        }
        
        private function getPath(startX:int, startY:int, endId:int):Array
        {
            var r:Array = [];
            var noteX:int = xList[endId];
            var noteY:int = yList[endId];
            
            while (noteX != startX || noteY != startY)
            {
                r.unshift([noteX, noteY]);
                endId = fList[endId];
                noteX = xList[endId];
                noteY = yList[endId];
            }
            
            r.unshift([startX, startY]);
            destroyLists();
            
            return r;
        }
        
        private function getScore(index:int):int
        {
            return psList[oList[index - 1]];
        }
        
        private function isOpen(x:int, y:int):Boolean
        {
            if (null == noteMap[y]) return false;
            if (null == noteMap[y][x]) return false;
            return noteMap[y][x][NOTE_OPEN];
        }
        
        private function isClosed(x:int, y:int):Boolean
        {
            if (null == noteMap[y]) return false;
            if (null == noteMap[y][x]) return false;
            return noteMap[y][x][NOTE_CLOSED];
        }
        
        private function initLists():void
        {
            xList = [];
            yList = [];
            oList = [];
            fList = [];
            psList = [];
            mcList = [];
            noteMap = [];
        }
        
        private function destroyLists():void
        {
            xList = null;
            yList = null;
            oList = null;
            fList = null;
            psList = null;
            mcList = null;
            noteMap = null;
        }
    }
}

package hongwei.game.map
{
    public interface IMapData
    {
        function getCost(startX:int, startY:int, endX:int, endY:int):int;
        function isBlock(startX:int, startY:int, endX:int, endY:int):Boolean;
    }
}