## Civilization 4 (c) 2005 Firaxis Games
##
## name     : AStarTool.py
## author   : 12monkeys
## date     : 10.03.2006
## version  : 1.1
##
## Notes
##   - Must be initialized externally by calling init()
##
## Modified for The BUG Mod by EmperorFool


from CvPythonExtensions import *

import BugCore
PleOpt = BugCore.game.PLE

gc = CyGlobalContext()
        
#####################################################################
# Class : AStar
#####################################################################
# class provides functions to create a path from plot A to plot B for 
# a given unit. 
# Main function to be used from outsiede are : 
#   generatePath()  : creates a path and prepares the reults
#   getPath()       : retrurns the path if one has been found
#   generateArea()  : creates an area a unit can move to
#   getArea()       : returns the area if one has been created
# see the methods for further definitions
#####################################################################               
class AStar:
    
    def __init__(self):
        self.pOpenList              = AStarList()
        self.pCloseList             = AStarList()
        self.pTargetPlot            = None
        self.pFromPlot              = None
        self.pUnit                  = None
        self.fHeuristicMvmtFactor   = 0.0               # possible smallest cost value a move from plot to plot will take
        self.fHeuristicTieBreak     = float(1.0/1000.0)     # assuming the paths are shorter than 400 steps
        self.bResultValid           = false
        self.iLoopCount             = 0
        self.eDomain                = 0
        self.bIgnoreMovesLeft       = false
        self.MODE_AREA              = 'A'
        self.MODE_PATH              = 'P'
            
    # moves a plot from open list to close list
    def moveToClose(self, pPlot):
        pParent = self.pOpenList.getParent(pPlot)
        iGCost = self.pOpenList.getGCosts(pPlot)
        fHCost = self.pOpenList.getHCosts(pPlot)
        self.pCloseList.set(pPlot, pParent, iGCost, fHCost)
        self.pOpenList.delete(pPlot)
        
    # returns the minimum x-distance, considering the x-axis over-/underflow
    def getRealXDist(self, x1, x2):
        d1 = abs(x1-x2)
        d2 = abs(min(x1, x2)+CyMap().getGridWidth()-max(x1, x2))
        return min(d1, d2)
        
    # returns the minimum y-distance, considering the y-axis over-/underflow
    def getRealYDist(self, y1, y2):
        d1 = abs(y1-y2)
        d2 = abs(min(y1, y2)+CyMap().getGridHeight()-max(y1, y2))
        return min(d1, d2)
    
    # calculates the heuristic 
    def calcHeuristic(self, pPlot):
        if self.nMode == self.MODE_PATH:
            # using "diagonal distance" method
            H = self.fHeuristicMvmtFactor * max(self.getRealXDist(pPlot.getX(), self.pTargetPlot.getX()), self.getRealYDist(pPlot.getY(), self.pTargetPlot.getY()))
            # methods to calculate the tie-break value usding the vector cross-product (dot-product)
            dx1 = pPlot.getX() - self.pTargetPlot.getX()
            dy1 = pPlot.getY() - self.pTargetPlot.getY()
            dx2 = self.pFromPlot.getX() - pPlot.getX()
            dy2 = self.pFromPlot.getY() - pPlot.getY()
            cross = float(abs(dx1*dy2 - dx2*dy1))
            H += float(cross*0.001)
        elif self.nMode == self.MODE_AREA:
            # no heuristic if we want to find an area. THis ensures that the complete area is examined
            H = 0.0
        return H

    # calculates a factor for the heuristic for the heuristic
    def calculateHeuristicFactors(self):
        pUnitTypeInfo = gc.getUnitInfo(self.pUnit.getUnitType())
        self.eDomain = pUnitTypeInfo.getDomainType()
        if (self.eDomain == DomainTypes.DOMAIN_SEA):
            # all sea plots have movements costs of 60/plot
            self.fHeuristicMvmtFactor   = 60.0
        else:
            # min possible movement costs of 12/plot
            self.fHeuristicMvmtFactor   = 12.0 
            
    # checks in case of sea plots, if there is a landbridge between the two plots
    def fnCheckLandBridge(self, pPlot, x, y):
        pTestPlot = CyMap().plot(pPlot.getX()+x, pPlot.getY()+y)
        if not (pPlot.isCity() or pTestPlot.isCity()):
            pTestPlot = CyMap().plot(pPlot.getX()+x, pPlot.getY())
            if (pTestPlot.isCoastalLand()):
                pTestPlot = CyMap().plot(pPlot.getX(), pPlot.getY()+y)
                if (pTestPlot.isCoastalLand()):
                    return true
        return false
            
    # returns an adjacent plots reletaive to the coordinates of pPlot.
    # takes consideration of x and/or y overlows or underflows
    def getNewPlot(self, pPlot, dx, dy):
        x = pPlot.getX()+dx
        y = pPlot.getY()+dy
        # check x underflow
        if x < 0:
            x += CyMap().getGridWidth()
        # check x overflow
        elif x >= CyMap().getGridWidth():
            x -= CyMap().getGridWidth()
        # check y underflow
        if y < 0:
            y += CyMap().getGridHeight()
        # check y overflow
        elif y >= CyMap().getGridHeight():
            y -= CyMap().getGridHeight()
        return CyMap().plot(x, y)
        
    # core function of the A* algorithm
    # calculates the adjacents and puts them on the open list together wth the moving costs.
    # in case of area check, the heuristic is zero.
    def addAdjacents(self, pPlot):
        # loops for adjacent plots
        for dx in range(-1, 2):
            for dy in range(-1, 2):
                # ignore center plot
                if not (dx == 0 and dy == 0):
                    # create a plot objects
                    pNewPlot = self.getNewPlot(pPlot, dx, dy)
                    # check in case sof a sea unit, if there is a land bridge to cross
                    if (dx != 0) and (dy != 0) and (self.eDomain == DomainTypes.DOMAIN_SEA):
                        bCont = not self.fnCheckLandBridge(pPlot, dx, dy)
                    else: 
                        bCont = true
                    if bCont:
                        # check if the plot is passable
                        if self.pUnit.canMoveOrAttackInto(pNewPlot, true):
                            # check if the plot is already on the close list
                            if not self.pCloseList.exists(pNewPlot):
                                # calculate movement cost from root plot to new plot
                                if self.pCloseList.exists(pPlot):
                                    iParentGCosts = self.pCloseList.getGCosts(pPlot)
                                else:
                                    iParentGCosts = self.pOpenList.getGCosts(pPlot)
                                iGCosts = pPlot.movementCost(self.pUnit, pNewPlot)+iParentGCosts
                                if (self.bIgnoreMovesLeft) or (iGCosts <= self.iMovesLeft):
                                    # calculate heuristics cost new plot to targetplot
                                    fHCosts = self.calcHeuristic(pNewPlot)
                                    # calculate total costs new plot to targetplot
                                    fFCosts = float(iGCosts) + fHCosts
                                    # checks if the plot is on the open list already
                                    if self.pOpenList.exists(pNewPlot):
                                        # check if the already stored costs are less than the actual ones
                                        if iGCosts <= self.pOpenList.getGCosts(pNewPlot):
                                            self.pOpenList.set(pNewPlot, pPlot, iGCosts, fHCosts)
                                    else:
                                        # add it to the open list
                                        self.pOpenList.set(pNewPlot, pPlot, iGCosts, fHCosts)
                        else:
                            if self.nMode == self.MODE_AREA:
                                self.pCloseList.set(pNewPlot, pPlot, -1, 0)
        return 
    
    # 
    # returns the path data which has been generate by "generatePath()" method.
    # It only returns a result when there is a valid result stored. If there is 
    # no valid result, the function returns an empty list
    # Attention : The first element of the returned list, is the last plot of the path!!!
    # The Method should only be called, if the "generatePath()" method has been called before.
    #
    # Parameters:
    #   none
    # Returns: 
    #   list in the format [(xn,yn), .... , (x2,y2), (x1,y1), (x0,y0)]
    #   where 
    #       (xn,yn) : is the to-plot tuple and 
    #       (x0,y0) : is the from-plot tuple. x and y are ints.
    # 
    def getPath(self):
        lPath = []
        if self.bResultValid:
            pWorkPlot   = self.pTargetPlot
            pParentPlot = self.pTargetPlot
            while true:
                # adding target plot to the path
                lPath.append(self.pCloseList.getXY(pWorkPlot))
                # looking for the parent of the 
                pParentPlot = self.pCloseList.getParent(pWorkPlot)
                # make parent the work plot
                pWorkPlot = pParentPlot
                # check if we reached from plot
                if (pWorkPlot.getX() == self.pFromPlot.getX()) and (pWorkPlot.getY() == self.pFromPlot.getY()):
                    break
        return lPath            
            
    #
    # tries to find a path from plot A to B and returns the overall movement costs for 
    # the unit. If no path could be found -1 is returned.
    # To get the path itself, the method getPath() must be called afterwards.
    # 
    # Parameters:
    #   pUnit           : CyUnit 
    #   pFromPlot       : CyPlot
    #   pToPlot         : CyPlot
    #   bIgnoreMovesLeft: bool
    # Returns:
    #   int         (the costs to get from pFromPlot to pToPlot. -1 if no path could be found)
    #
    # The parameter "bIgnoreMovesLeft" can be used to reduce execution time. If the parameter is true, 
    # the algorithm stops a single path examiation if the remaining moves of a unit are not enough 
    # to reach the target plot. This significantly speeds up the algorithm in case you want to look for the 
    # the movable area. 
    # The parameter should be set to false in case you want to find a path from plot A to B without 
    # cost restrictions.
    # 
    def generatePath(self, pUnit, pFromPlot, pToPlot, bIgnoreMovesLeft):
    
        # clear the actual results
        self.bResultValid = false
        self.pOpenList.clear()
        self.pCloseList.clear()
        self.nMode = self.MODE_PATH
        
        # setting some variables
        self.pTargetPlot        = pToPlot
        self.pFromPlot          = pFromPlot
        self.pUnit              = pUnit
        pNewPlot                = pFromPlot
        pCurrentPlot            = pFromPlot
        bBreak                  = false
        self.iLoopCount         = 0
        self.iMovesLeft         = pUnit.movesLeft()
        self.bIgnoreMovesLeft   = bIgnoreMovesLeft

        # perfrom some checks ...
        if ((pFromPlot.getX() == pToPlot.getX()) and (pFromPlot.getY() == pToPlot.getY())):
            # From and To plot are equal -> break
            return -1
        if not (self.pUnit.canMoveOrAttackInto(pToPlot, true)):
            # To plot not passable -> break
            return -1       
        
        # calculates some values for the heuristic
        self.calculateHeuristicFactors()
        
        # put start plot on the open list
        self.pOpenList.set(pCurrentPlot, pCurrentPlot, 0, self.calcHeuristic(pNewPlot)) 

        # repeat until target plot is reached
        while (true):
            self.addAdjacents(pCurrentPlot)
            self.moveToClose(pCurrentPlot)  
            if (self.pCloseList.exists(self.pTargetPlot)):
                # path found
                break
            if (self.pOpenList.len() == 0):
                # no path found
                bBreak = true
                break
            # find the plot with the lowest costs on the open list
            pCurrentPlot = self.pOpenList.findMinFCost()
            self.iLoopCount += 1

        # return the G-Costs of the Target Plot
        if bBreak:
            # no path found
            iReturn = -1
            self.bResultValid = false
        else:
            iReturn = int(self.pCloseList.getGCosts(pCurrentPlot))
            self.bResultValid = true
            
        return iReturn

    #
    # returns the area which has been found by "generateArea()". If no valid result is stored, an
    # empty list is retured.
    # The method should only be called, if the "generateArea()" method has been called before.
    # 
    # Parameters:
    #   none
    # Returns:
    #   list on the format [((x0,y0),c0), ((x1,y1),c1), ... , ((xn,yn),cn)]
    #   where :
    #       (x,y) : is a tuple of ints describing the plots coordinates 
    #       c : the movements costs to get to the plot. -1 if the plot is impassable 
    # 
    def getArea(self):
        lArea = []
        if self.bResultValid:
            for i in range(self.pCloseList.len()):
                if i == 0:
                    lAPlot = self.pCloseList.getFirst()
                else:
                    lAPlot = self.pCloseList.getNext()
                iCosts = self.pCloseList.getGCosts(CyMap().plot(lAPlot[0], lAPlot[1]))
                lArea.append((lAPlot, iCosts))
        return lArea        

    #
    # creates an area a unit can move to within its remaining movement points. 
    # the function always returns 1, because even an empty list is a result.
    # to get the area itself, after the generateArea function, the method getArea() must be called
    #
    # Paramters : 
    #   pUnit       : CyUnit 
    #   pFromPlot   : CyPlot
    # Returns : 
    #   int         (constant 1)
    #
    def generateArea(self, pUnit, pFromPlot):
        
        # clear the actual results
        self.bResultValid = false
        self.pOpenList.clear()
        self.pCloseList.clear()
        self.nMode = self.MODE_AREA
        
        # setting some variables
        self.pTargetPlot        = None
        self.pFromPlot          = pFromPlot
        self.pUnit              = pUnit
        pNewPlot                = pFromPlot
        pCurrentPlot            = pFromPlot
        bBreak                  = false
        self.iLoopCount         = 0
        self.iMovesLeft         = pUnit.movesLeft()
        self.bIgnoreMovesLeft   = false

        
        # calculates some values for the heuristic
        self.calculateHeuristicFactors()
        
        # put start plot on the open list
        self.pOpenList.set(pCurrentPlot, pCurrentPlot, 0, self.calcHeuristic(pNewPlot)) 

        # repeat until target plot is reached
        while (true):
            self.addAdjacents(pCurrentPlot)
            self.moveToClose(pCurrentPlot)  
            if (self.pOpenList.len() == 0):
                # list is empty -> all plots are examined
                break
            # find the plot with the lowest costs on the open list
            pCurrentPlot = self.pOpenList.findMinFCost()
            self.iLoopCount += 1

        # return the G-Costs of the Target Plot
        iReturn = 1
        self.bResultValid = true
        
        return iReturn
        
        
#####################################################################
# Class : AStarMoveArea
#####################################################################
# class provides functions to create a list of plots a unit can move 
# within its left moves. It also provides some functions to display
# and clear the this area.
# Main function to be used from outsiede are : 
#   highlightMoveArea()     : calculates and highlights the area the can move to and computes the plot colors
#   dehighlightMoveArea()   : clears the display of that area
# see the methods for further definitions
# 
# the colors of the signle plots can be set in the __init__ section of the class
# COLOR_CLEAR can be used for no highlighting at all
#####################################################################       
class AStarMoveArea:

    def __init__(self):
        self.dPlotList                  = {}
        self.AS                         = AStar()
        self.pUnit                      = 0
        self.pFromPlot                  = 0
        self.PLE_HIGHLIGHT_PLOTS        = PlotLandscapeLayers.PLOT_LANDSCAPE_LAYER_REVEALED_PLOTS 
        self.lArea                      = []
        self.iActivePlayerTeam          = 0
        self.iActivePlayer              = 0
        
        # color values
        self.COL_NO                     = "COLOR_CLEAR"
        
    # converts a CyPlot into a tuple (x,y)
    def getPlotXY(self, pPlot):
        return (pPlot.getX(), pPlot.getY())
        
    # checks if there are any units on the plot and returns the corresponding color
    def checkUnit(self, pPlot):
        iNumUnits = pPlot.getNumUnits()
        bEnemy = false
        bNeutral = false
        bBarbarian = false
        for i in range(iNumUnits):
            pUnit = pPlot.getUnit(i)
            iTeam = pUnit.getTeam()
            if (iTeam == self.iActivePlayerTeam or pUnit.isCounterSpy()):
                continue
            iInvisibleType = pUnit.getInvisibleType()
            if (iInvisibleType != InvisibleTypes.NO_INVISIBLE):
                for j in range(self.pUnit.getNumSeeInvisibleTypes()):
                    if (iInvisibleType == self.pUnit.getSeeInvisibleType(j)):
                        break
                else:
                    continue
            if (gc.getTeam(iTeam).isBarbarian()):
                bBarbarian = true
            elif (gc.getTeam(iTeam).isAtWar(self.iActivePlayerTeam)):
                bEnemy = true
            else:
                bNeutral = true
        if bEnemy:
            return PleOpt.MH_Color_Enemy_Unit()
        elif bBarbarian:
            return PleOpt.MH_Color_Barbarian_Unit()
        elif bNeutral:
            return PleOpt.MH_Color_Neutral_Unit()
        return PleOpt.MH_Color_Passable_Terrain()

    # checks if there forwign territory on the plot and returns the corresponding color
    def checkTerritory(self, pPlot):
        iPlayer = pPlot.getRevealedOwner(self.iActivePlayerTeam, false)
        pPlayer = gc.getPlayer(iPlayer)
        iTeam = pPlot.getRevealedTeam(self.iActivePlayerTeam, false)
        pTeam = gc.getTeam(iTeam)
        if pPlot.isRevealedGoody(iTeam):
            if (pPlot.getImprovementType() == 3):#ImprovementTypes.IMPROVEMENT_GOODY_HUT):
                return PleOpt.MH_Color_Passable_Barbarian_Territory()
        elif (iPlayer == PlayerTypes.NO_PLAYER) or (iPlayer == self.iActivePlayer):
            return PleOpt.MH_Color_Passable_Terrain()
        elif pTeam.isAtWar(self.iActivePlayerTeam):
            return PleOpt.MH_Color_Passable_Enemy_Territory()
        else:
            return PleOpt.MH_Color_Passable_Neutral_Territory()         
    
    # checks if there are revelaed plots adjacent to the given plot
    def checkAdjacentRevealed(self, pPlot):
        for dx in range(-1, 2):
            for dy in range(-1, 2):
                if not (dx == 0 and dy == 0):
                    if CyMap().plot(pPlot.getX()+dx, pPlot.getY()+dy).isRevealed(self.iActivePlayerTeam, false):
                        return true
        return false
    
    # handles the color for a plot
    def setPlotColor(self, x, y, iCosts):
        pPlot = CyMap().plot(x, y)
        tPlot = (x, y)
        self.dPlotList[tPlot] = self.COL_NO
        # check impassable
        if iCosts == -1:
            if (pPlot.isWater() and (self.eDomain == DomainTypes.DOMAIN_SEA)) or ((not pPlot.isWater()) and (self.eDomain == DomainTypes.DOMAIN_LAND or self.eDomain == DomainTypes.DOMAIN_SCOUT)):
                self.dPlotList[tPlot] = PleOpt.MH_Color_Impassable_Terrain()
        # check if plot is reachable
        elif iCosts <= self.iMovesLeft:
            # check if the plot is reavealed
            if pPlot.isRevealed(self.iActivePlayerTeam, false):
                # check if a unit at that plot
                if pPlot.isUnit() and pPlot.isVisible(self.iActivePlayerTeam, false):
                    self.dPlotList[tPlot] = self.checkUnit(pPlot)
                # check if the plot is foreign territory
                elif pPlot.isVisible(self.iActivePlayerTeam, false):
                    self.dPlotList[tPlot] = self.checkTerritory(pPlot)
                # nothing special with that plot
                else:
                    self.dPlotList[tPlot] = PleOpt.MH_Color_Passable_Terrain()
            else:
                if self.checkAdjacentRevealed(pPlot):
                    self.dPlotList[tPlot] = PleOpt.MH_Color_Passable_Terrain()
                else:
                    self.dPlotList[tPlot] = self.COL_NO     
    
    #
    # highlights the area a unit can move to with its remaining movement points
    #
    # Parameters:
    #   pUnit : CyUnit
    # Returns:
    #   int     (constant 1)
    # 
    def highlightMoveArea(self, pUnit):
        # init some variables
        self.pUnit              = pUnit
        self.pFromPlot          = pUnit.plot()
        self.dPlotList          = {}
        self.iMovesLeft         = self.pUnit.movesLeft()
        pUnitTypeInfo           = gc.getUnitInfo(self.pUnit.getUnitType())
        self.eDomain            = pUnitTypeInfo.getDomainType()
        self.iActivePlayer      = CyGame().getActivePlayer()
        pActivePlayer           = gc.getPlayer(self.iActivePlayer)
        self.iActivePlayerTeam  = pActivePlayer.getTeam()
        
        # add from plot to OK list
        self.dPlotList[self.getPlotXY(self.pFromPlot)] = 0

        # creates the infromation of the moveable area
        self.AS.generateArea(self.pUnit, self.pFromPlot)
        self.lArea = self.AS.getArea()
        
        # analyze data and set plot colors
        for i in range(len(self.lArea)):
            tItem = self.lArea[i]
            self.setPlotColor(tItem[0][0], tItem[0][1], tItem[1])
                
        # highlight the area
        self.highlightMoves()
        return 1
    
    # displays the area on the screen
    def highlightMoves(self):
        for plot, color in self.dPlotList.items(): 
            if color != self.COL_NO:
                CyEngine().addColoredPlotAlt(plot[0], plot[1], PlotStyles.PLOT_STYLE_TARGET, self.PLE_HIGHLIGHT_PLOTS, color, .5)

    #
    # clears the disaply of the area 
    #
    # Parameters:
    #   none
    # Returns:
    #   int     (constant 1)
    # 
    def dehighlightMoveArea(self):
        CyEngine().clearColoredPlots(self.PLE_HIGHLIGHT_PLOTS)
        return 1
    

    
#####################################################################
# Class : AStarPlot
#####################################################################
# class which is used to handle a specific plot format
# the plot data is stored as tuple in the format (x, y)
# class provides several function to handle this format 
# Only for internal use. 
#####################################################################       
class AStarPlot:
    
    def __init__(self):
        self.lPlot = (-1, -1)
        self.IDX_X = 0
        self.IDX_Y = 1
        
    # clears plot data
    def clear(self):
        self.lPlot = (-1, -1)
        
    # x, y : ints
    def setXY(self, x, y):
        self.lPlot = (x, y)
        
    # pPlot: CyPlot
    def setXYplot(self, pPlot):
        self.lPlot = (pPlot.getX(), pPlot.getY())
        
    # return x: int
    def getX(self):
        return self.lPlot[self.IDX_X]

    # return y: int
    def getY(self):
        return self.lPlot[self.IDX_Y]

    # x, y : ints
    # return (x,y)
    def getXY(self):
        return (self.getX(), self.getY())
        
    # pCompPlot: AStarPlot()
    # returns true if plot coords are equal
    def compare(self, pCompPlot):
        if (self.getX() == pCompPlot.getX()) and (self.getY() == pCompPlot.getY()):
            return true
        else:
            return false

            
#####################################################################
# Class : AStarList
#####################################################################
# class wto handle the open and close list for the AStar algorithm
# for internal use only
#####################################################################       
class AStarList:
    
    def __init__(self):
        self.dList = {}
        self.IDX_PARENT = 0
        self.IDX_GCOSTS = 1
        self.IDX_HCOSTS = 2
        self.IDX_FCOSTS = 3
        self.IDX_X = 0
        self.IDX_Y = 1
        self.maxCost = 9999999.9

    # clears the list
    def clear(self):
        self.dList = {}

    # creates a AStarPlot 
    # x, y: int
    # return: AStarPlot
    def makeAPlotXY(self, x, y):
        pAPlot = AStarPlot()
        pAPlot.setXY(x, y)
        return pAPlot
        
    # creates a AStarPlot 
    # pPlot = CyPlot
    # return: AStarPlot
    def makeAPlot(self, pPlot):
        return self.makeAPlotXY(pPlot.getX(), pPlot.getY())
        
    # sets all plot data
    # pAParent: AStarPlot, others are floats
    # return: ((x,y), int, float, float)
    def setPlotData(self, pAParent, iGCosts, fHCosts, fFCosts):
        return (pAParent, iGCosts, fHCosts, fFCosts)

    # returns all plot data
    # pAPlot: AStarPlot
    # return: ((x,y), float, float, float)
    def getPlotData(self, pAPlot):
        return self.dList[pAPlot.getXY()]

        
    # adds the complete plot to the list
    # pThisPlot, pParentPlot : CyPlot
    # iGCosts, fHCosts : int, float
    # if plot already exists, it will be overwritten
    def set(self, pThisPlot, pParentPlot, iGCosts, fHCosts):
        pAThisPlot = self.makeAPlot(pThisPlot)
        pAParentPlot = self.makeAPlot(pParentPlot)
        self.dList[pAThisPlot.getXY()] = self.setPlotData(pAParentPlot, iGCosts, fHCosts, float(iGCosts)+float(fHCosts))
            
    # pPlot : CyPlot
    # deletes the plot from the list
    def delete(self, pPlot):
        pAPlot = self.makeAPlot(pPlot)
        if self.dList.has_key(pAPlot.getXY()):
            del self.dList[pAPlot.getXY()]
            return true
        else:
            return false
            
    # pPlot : CyPlot
    # returns the g-costs as float
    def getGCosts(self, pPlot):
        pAPlot = self.makeAPlot(pPlot)
        return float(self.dList[pAPlot.getXY()][self.IDX_GCOSTS])

    # pPlot : CyPlot
    # returns the h-costs as float
    def getHCosts(self, pPlot):
        pAPlot = self.makeAPlot(pPlot)
        return float(self.dList[pAPlot.getXY()][self.IDX_HCOSTS])

    # pPlot : CyPlot
    # returns the f-costs as float
    def getFCosts(self, pPlot):
        pAPlot = self.makeAPlot(pPlot)
        return float(self.dList[pAPlot.getXY()][self.IDX_FCOSTS])

    # pPlot : CyPlot
    # returns the parent plot of the passed plot as CyPlot
    def getParent(self, pPlot):
        pAPlot = self.makeAPlot(pPlot)
        pAPlotData = self.getPlotData(pAPlot)
        x = pAPlotData[self.IDX_PARENT].getX()
        y = pAPlotData[self.IDX_PARENT].getY()
        return CyMap().plot(x, y)
        
    # returns the coords of a plot  (x,y)
    # pPlot: CyPlot
    def getXY(self, pPlot):
        pAPlot = self.makeAPlot(pPlot)
        return pAPlot.getXY()
        
    # pPlot : CyPlot
    # returns true if the plot exists in the list
    def exists(self, pPlot):
        pAPlot = self.makeAPlot(pPlot)
        if self.dList.has_key(pAPlot.getXY()):
            return true
        return false

    # pPlot : CyPlot
    # returns AStarPlot if found, else ()
    def search(self, pPlot):
        pAPlot = self.makeTPlot(pPlot)
        if self.dList.has_key(pAPlot.getXY()):
            return self.dList[(pAPlot.getXY())]
        return ()

    # returns the number of items in the list
    def len(self):
        return len(self.dList)

    # looks for the element with the smallest f-costs and returns it as CyPlot
    def findMinFCost(self):
        fComp = self.maxCost
        for key, val in self.dList.items():
            lData = self.dList[key]
            if lData[self.IDX_FCOSTS] < fComp:
                fComp = lData[self.IDX_FCOSTS]
                retKey = key
        x = retKey[0]
        y = retKey[1]
        return CyMap().plot(x, y)
    
    # returns the first element in the dict as CyPlot and prepares to fetch the next
    def getFirst(self):
        self.lList = []
        self.iList = 0
        for key, val in self.dList.items():
            self.lList.append(key)
        return self.lList[0]
        
    # returns the next element in the dict as CyPlot. "getFirst" needs to be called before.
    def getNext(self):
        if self.iList < self.len():
            self.iList += 1
            return self.lList[self.iList]
        else:
            return ()
