13
\$\begingroup\$

Im looking to improve my search algorithm in my battleship game. Code is not perfect but would appreciate any suggestions or recommendations.

Running the simulation using a 100x100 grid (10,000 possible locations) Im averaging ~30% accuracy.

Games played 500 Average = 0.31108

Im using a forward and backwards diagonal search approach. The search diagonal locations by moving forward and backwards by the using the maxShipSize that is still active. As a ship is sunk the maxShipSize changes.

If a ship is hit i check a cross pattern (left,up,right and down). When a ship is hit more then once a sequential pattern search occurs. enter image description here

enter image description here

[

battleship.py

# -*- coding: utf-8 -*-
from __future__ import division
import numpy
import operator
import commands
import random
import sys
import os
from time import sleep
from grid import grid 
from fleet import fleet 



#setupNavy
#Purpos: To place our ships on the grid
#Receives: setupSelection- either manual or random
#          gridClass
#          sortedShipList
#Return: 
def setupNavy(setupSelection,gridClass,sortedShipList):
    used="no"
    shipCoordList=[]
    for shipData in sortedShipList:
        shipName=shipData[0]
        shipSize=shipData[1]
        if setupSelection=="manual":
            header= "Ship placement: %s size is: %s\n"%(shipName,shipSize)
            sys.stdout.write(header)
        con="yes"
        while con=="yes": 
            if setupSelection=="manual":
                start=raw_input("Enter start point: ")
            else:
                randomX=random.randrange(0,gridClass.xGridSize)
                randomY=random.randrange(0,gridClass.yGridSize)
                xLetter=gridClass.alphDict[randomX]
                start="%s%d"%(xLetter,randomY)
            coordStatus=gridClass.checkDataPointValue(start)
            if coordStatus=="E":
                con="no"
                if setupSelection=="manual":
                    placement=raw_input("Place Vertical (V) or Horizontal (H): ")
                else:
                    placement=random.choice("VH")
                end=gridClass.determineEndPoint(start,shipSize,placement)
                if end=="F":
                    if setupSelection=="manual":
                        error= "Datapoint: %s will place %s off the grid \n"% (start,shipName)
                        sys.stdout.write(error)
                    used="yes"
                else:
                    shipCoordList=gridClass.determineFullLocation(start,end)
                    gridClass.shipLocationDict[shipName]=shipCoordList
                    for coord in shipCoordList:
                        coordList=coord.split(',')
                        dataPoint="%s%s"%(gridClass.alphDict[int(coordList[0])],coordList[1])
                        coordStatus=gridClass.checkDataPointValue(dataPoint)
                        if coordStatus=='T':
                             if setupSelection=="manual":
                                 error= "Datapoint: %s is already used \n"% dataPoint
                                 sys.stdout.write(error)
                             used="yes" 
                if used=="no":
                    gridClass.gridValuesUsed+=shipCoordList
            else: 
                if setupSelection=="manual":
                    error= "Datapoint: %s is already used \n"% dataPoint
                    sys.stdout.write(error)
                con="yes"
            if used=="yes":
                con="yes"
                used="no"

        os.system('clear; history -c')

        gridClass.shipPlacement(start,end,shipCoordList)
        gridDict=gridClass.populateGrid()
        if setupSelection=="manual":
            gridClass.displayGrid()

    sleep(0.25)
    os.system('clear; history -c')
    return 

def determineNextAttackInSeq (attackerGridClass):
    startLocation="";xHitList=[];yHitList=[]
    for hit in attackerGridClass.hitList:
        hitCoordList=hit.split(',')
        xHitList.append(hitCoordList[0])
        yHitList.append(hitCoordList[1])
    if len(set(xHitList))>1:
        nextY=yHitList[0]
        xHitList=sorted(xHitList)
        nextBegX=int(xHitList[0])-1
        nextEndX=int(xHitList[len(xHitList)-1])+1
        begCoord="%s,%s"%(nextBegX,nextY)
        lastCoord="%s,%s"%(nextEndX,nextY)
        if begCoord in attackerGridClass.attackList:
            startLocation=begCoord
        elif lastCoord in attackerGridClass.attackList:
            startLocation=lastCoord
    #Vertical order
    elif len(set(yHitList))>1:
        nextX=xHitList[0]
        yHitList=sorted(yHitList)
        nextBegY=int(yHitList[0])-1
        nextEndY=int(yHitList[len(yHitList)-1])+1
        begCoord="%s,%s"%(nextX,nextBegY)
        lastCoord="%s,%s"%(nextX,nextEndY)
        if begCoord in attackerGridClass.attackList:
            startLocation=begCoord
        elif lastCoord in attackerGridClass.attackList:
            startLocation=lastCoord
    return startLocation

def checkRoadBlocks(attackerGridClass,defenderFleetClass,startLocation):
    startList=startLocation.split(',')
    xValue=int(startList[0])
    yValue=int(startList[1])
    #Convert to alpha numeric for display purposes
    #ie. 2,13 is C13
    start="%s%s"%(attackerGridClass.alphDict[xValue],yValue)
    possVertLocList=[]
    possHorzLocList=[]
    maxGridSize=attackerGridClass.xGridSize
    minShipSize=defenderFleetClass.minShipSize
    possVertLocList.append(startLocation)
    possHorzLocList.append(startLocation)
    iteratorSeq=0
    startX=xValue
    startY=yValue
    while iteratorSeq < minShipSize:
        iteratorSeq=iteratorSeq+1
        #Veritcal locations
        possY=int(startY)+iteratorSeq
        if possY<maxGridSize and possY>=0:
            possVertLocBelow="%s,%s"%(startX,possY)
            possVertLocList.append(possVertLocBelow)
        possY=int(startY)-iteratorSeq
        if possY<maxGridSize and possY>=0:
            possVertLocAbove="%s,%s"%(startX,possY)
            possVertLocList.append(possVertLocAbove)
        #Horziontal locations
        possX=int(startX)+iteratorSeq
        if possX<maxGridSize and possX>=0:
            possHorzLocRight="%s,%s"%(possX,startY)
            possHorzLocList.append(possHorzLocRight)
        possX=int(startX)-iteratorSeq
        if possX<maxGridSize and possX>=0:
            possHorzLocLeft="%s,%s"%(possX,startY)
            possHorzLocList.append(possHorzLocLeft)
    for coord in attackerGridClass.missedList:
        if coord in possVertLocList:
            possVertLocList.remove(coord)
        elif coord in possHorzLocList:
            possHorzLocList.remove(coord)

    possVertLocList= sorted(possVertLocList)

    ySList=[]
    for coordS in possVertLocList:
        xySlist=coordS.split(',')
        ySList.append(xySlist[1])
    ySList.sort(key=int)
    numSeq=0
    prev=-1
    count=0
    ySeqList=[]
    for ySValue in ySList:
        ySValue=int(ySValue)
        if prev==ySValue:
            numSeq=numSeq+1
            prev=prev+1
        else:
            prev=int(ySValue)+1
            numSeq=1
        ySeqList.append(numSeq)

    possHorzLocList=sorted(possHorzLocList)
    xSList=[]
    for coordS in possHorzLocList:
        xySlist=coordS.split(',')
        xSList.append(xySlist[0])
    xSList.sort(key=int) 
    numSeq=0
    prev=-1
    count=0
    xSeqList=[]
    for xSValue in xSList:
        xSValue=int(xSValue)
        if prev==xSValue:
            numSeq=numSeq+1
            prev=prev+1
        else:
            prev=int(xSValue)+1
            numSeq=1
        xSeqList.append(numSeq)

    if minShipSize not in xSeqList and minShipSize not in ySeqList:
        attackerGridClass.blockedCoordList.append(startLocation)
    return attackerGridClass.blockedCoordList


def findAroundCoords(attackerGridClass,startLocation):
    startList=startLocation.split(',')
    xValue=int(startList[0])
    yValue=int(startList[1])
    left=xValue-1
    below=yValue-1
    right=xValue+1
    above=yValue+1

    if left>=0:
        leftValue="%s,%s"%(left,yValue)
        leftLetter="%s%s"%(attackerGridClass.alphDict[left],yValue)
        if leftValue not in attackerGridClass.attackList and leftValue not in attackerGridClass.hitList and leftValue not in attackerGridClass.missedList:
            attackerGridClass.attackList.append(leftValue)
    if below>=0:
        belowValue="%s,%s"%(xValue,below)
        belowLetter="%s%s"%(attackerGridClass.alphDict[xValue],below)
        if belowValue not in attackerGridClass.attackList and belowValue not in attackerGridClass.hitList and belowValue not in attackerGridClass.missedList:
           attackerGridClass.attackList.append(belowValue)
    if right<=(attackerGridClass.xGridSize-1):
        rightValue="%s,%s"%(right,yValue)
        rightLetter="%s%s"%(attackerGridClass.alphDict[right],yValue)
        if rightValue not in attackerGridClass.attackList and rightValue not in attackerGridClass.hitList and rightValue not in attackerGridClass.missedList:
           attackerGridClass.attackList.append(rightValue)
    if above<=(attackerGridClass.yGridSize-1) or above==attackerGridClass.yGridSize-1:
        aboveValue="%s,%s"%(xValue,above)
        aboveLetter="%s%s"%(attackerGridClass.alphDict[xValue],above)
        if aboveValue not in attackerGridClass.attackList and aboveValue not in attackerGridClass.hitList and aboveValue not in attackerGridClass.missedList:
           attackerGridClass.attackList.append(aboveValue)
    return  attackerGridClass.attackList

def checkShipStatus(attackerGridClass,defenderGridClass,defenderFleetClass):
    #Determine if the attacked ship is sunk.
    for ship, locationList in defenderGridClass.shipLocationDict.iteritems():
        hitsTaken=0
        shipSize=defenderFleetClass.shipFleetDict[ship]
        if defenderFleetClass.shipStatusDict[ship]=="active":
            for location in locationList:
                if location in attackerGridClass.attackedCoordList:
                    hitsTaken+=1
            if hitsTaken==shipSize:
                print "%s sunk a %s"%(whosTurn,ship)
                sleep(1.25)
                attackerGridClass.blockedCoordList=[]
                defenderFleetClass.shipStatusDict[ship]="sunk"
                defenderFleetClass.numberSunkShips+=1
                attackerGridClass.attackNumber=0
                defenderFleetClass.minShipSize=defenderFleetClass.determineMinShipSize()
                if len(attackerGridClass.hitList)>shipSize:
                    attackerGridClass.attackList=[]
                    tmpHitList=sorted(attackerGridClass.hitList)
                    firstCoord=tmpHitList[0]
                    findAroundCoords(attackerGridClass,firstCoord)
                    lastCoord=tmpHitList[len(tmpHitList)-1]
                    findAroundCoords(attackerGridClass,lastCoord)
                    attackerGridClass.hitList=[]

                else:
                    attackerGridClass.attackList=[]
                    attackerGridClass.hitList=[]
                #Empty attackList... Possiable problem!!!
                #print "*************************"
                #for extraCoord in attackerGridClass.attackList:
                #goodCoord=determineNextAttackInSeq(attackerGridClass)
                #print goodCoord
                #print attackerGridClass.attackList
    return




def attackShip(whosTurn,attackerGridClass,defenderGridClass,defenderFleetClass):
    newAttack="Y"    
    numShipsInFleet=len(defenderFleetClass.shipStatusDict)
    while newAttack=="Y":
        #Person vs computer. We prompt for location to attack
        if whosTurn=="player":
            attackCoords=raw_input("Input attack coordinates (ex B2): ")
            xLetter=attackCoords[:1]
            xValue=defenderGridClass.alphList.index(xLetter)
            yValue=int(attackCoords[1:])
            startLocation="%s,%s"%(xValue,yValue)
        else:
            #If we already have a planned attacked list then get the next one
            #The attackList is a educated guess where we should attack next
            #based on previous attacks. 
            print attackerGridClass.attackList
            if len(attackerGridClass.attackList)!=0:
                attackerGridClass.attackList=sorted(attackerGridClass.attackList)

                ################################################################
                # If we have a hit we want to check what the next sequitnal order would be 
                startLocation=determineNextAttackInSeq (attackerGridClass)

                if startLocation=="":
                    #Get first location in attack list
                    print "nexxxxt"
                    startLocation=attackerGridClass.attackList[0]
                    print startLocation
                ################################################################
                end=''
            else:
                searchListEmpty="T"
                while searchListEmpty=="T":
                    #If we dont have a searchList then lets build one.
                    #The searchList is some logical search. We built that in defineSearchList
                    if len(attackerGridClass.searchList)==0:
                       #Get the max size of active ships.
                       #The maxShipSize is used in our search algorithm
                       defenderFleetClass.maxShipSize=defenderFleetClass.determineMaxShipSize()
                       #defineSearchList is a digonal search 
                       attackerGridClass.searchList=attackerGridClass.defineSearchList(defenderFleetClass.maxShipSize,attackerGridClass.attackNumber)
                       attackerGridClass.attackNumber+=1
                       #Remove location if we have already missed/hit that spot
                       attackerGridClass.searchList=list(set(attackerGridClass.searchList) - set(attackerGridClass.missedList))
                       attackerGridClass.searchList=list(set(attackerGridClass.searchList) - set(attackerGridClass.hitList))

                       if len(attackerGridClass.searchList)>0:
                           startLocation=random.choice(attackerGridClass.searchList)
                       else:
                           startLocation=random.choice(attackerGridClass.validPoints)
                    else:
                       searchListEmpty="F"
                       startLocation=random.choice(attackerGridClass.searchList)
                #Randomly select a valid point from our searchList 
                #startLocation=random.choice(attackerGridClass.searchList)

        #######################################################################################################
        #We have our Attack location at this point. 
        startList=startLocation.split(',')
        xValue=int(startList[0])
        yValue=int(startList[1])
        #Convert to alpha numeric for display purposes
        #ie. 2,13 is C13
        start="%s%s"%(attackerGridClass.alphDict[xValue],yValue)
        ########################################################################################################
        #BREAKING
        attackerGridClass.blockedCoordList=checkRoadBlocks(attackerGridClass,defenderFleetClass,startLocation)
        ########################################################################################################

        #Cleanup some of our lists.
        #Remove our attack from our validPoint   
        #Remove our attack from our attacklist   
        if startLocation in attackerGridClass.attackList:
            attackerGridClass.attackList.remove(startLocation)
        #Remove our attack from our search list
        if startLocation in attackerGridClass.searchList:
              attackerGridClass.searchList.remove(startLocation)



        #if startLocation not in attackerGridClass.attackedCoordList and startLocation not in atta
        if startLocation in attackerGridClass.blockedCoordList:                                   
            pass                                                                                  
        elif startLocation not in attackerGridClass.attackedCoordList: 
            attackerGridClass.attackedCoordList.append(startLocation)
            newAttack="N"
            #if attack location is in the defenders values used then its a hit
            if startLocation in defenderGridClass.gridValuesUsed:
                print "Attacking at %s (%s)" %(start,startLocation)
                print "BOOM!! Direct Hit"
                print attackerGridClass.attackList
                sleep(1.25)
                os.system('clear; history -c')
                hit='\033[1;31m×\033[1;m'
                defenderHit='\033[1;31m×\033[1;m'

                #Displays when a enemys ship is hit.
                attackerGridClass.gridValuesAttacked[xValue][yValue]="[%s]"%hit
                #Displays when a ship is hit. shows an x in the place of the ship
                defenderGridClass.gridValues[xValue][yValue]="[%s]"%defenderHit

                #Add or attack locatio to our hit list
                attackerGridClass.hitList.append(startLocation)
                findAroundCoords(attackerGridClass,startLocation)
                if startLocation in attackerGridClass.validPoints:
                    attackerGridClass.validPoints.remove(startLocation)

                #############################################################################




                #############################################################################
                #Determine if the attacked ship is sunk.
                checkShipStatus(attackerGridClass,defenderGridClass,defenderFleetClass)

                #############################################################################
                attackerGridClass.blockedCoordList=[]

            else:
                print "Attacking at %s (%s)" %(start,startLocation)
                attackerGridClass.missedList.append(startLocation)
                attackerGridClass.attackedCoordList.append(startLocation)
                if startLocation in attackerGridClass.validPoints:
                    attackerGridClass.validPoints.remove(startLocation)
                newAttack="N"
                print "Missed....."

                sleep(1.25)
                os.system('clear; history -c')
                #attackResult="[M]"
                #miss='ø'
                miss='\033[1;30mø\033[1;m'
                attackResult="[%s]"%miss
                attackerGridClass.gridValuesAttacked[xValue][yValue]="[%s]"%miss
                attackerGridClass.blockedCoordList=[]

        else:
            hitOrMiss="Miss"
            if startLocation in attackerGridClass.hitList:
                hitOrMiss="HIT" 
            if whosTurn=="player":
                print "You already attacked %s%d which was a %s "%(xLetter,yValue,hitOrMiss)
            #Alert message... saying skipping cause road block in the way
    if defenderFleetClass.numberSunkShips==numShipsInFleet:
        gameOver(attackerGridClass.gridName)
        displayGameStats(xGrid)
        sys.exit()
        return
    return 

def determineMaxMoves(xGrid,yGrid,player):
    i=0;turnList=[]
    maxTurns=(xGrid*yGrid)*2
    while i < maxTurns:
        if i%2==0:
            turnList.append(player)
        else:
            turnList.append('Joshua')
        i+=1 
    return turnList

def gameOver(winner):
    if winner=="USA":
        print "\n******** %s WINS******** \n" %winner
        #print u'{:─^10}'.format(u'')

        print """
         ____________________________________________
        |* * * * * * * * * * |_______________________|
        |* * * * * * * * * * |_______________________|
        |* * * * * * * * * * |_______________________|
        |* * * * * * * * * * |_______________________|
        |* * * * * * * * * * |_______________________|
        |____________________________________________|
        |____________________________________________|
        |____________________________________________|
        |____________________________________________|
        |____________________________________________|
        """        
    else:
        print "Better luck next time..  %s WINS \n" %winner
        print "GAME OVER"

def displayGameStats(xsize):
    print "      Results  \n"

    print "%s BATTLEFIELD"% enemyGridClass.gridName
    enemyGridClass.populateGrid()
    enemyGridClass.displayGrid()
    print "\n"
    for shipName,shipStatus in enemyFleetClass.shipStatusDict.iteritems():
        print shipName,shipStatus
    print "\n"

    print "%s BATTLEFIELD"% myGridClass.gridName
    myGridClass.populateGrid()
    myGridClass.displayGrid()


    print "\n"
    for shipName,shipStatus in myFleetClass.shipStatusDict.iteritems():
        print shipName,shipStatus
    print "\n"
    possiableAttacks=xsize * xsize
    percentage=enemyGridClass.attackCounter/possiableAttacks
    print "Total Number of locations: %s"%possiableAttacks
    print "Number of attacks: %s"%enemyGridClass.attackCounter

    print "Percent of accuracy: %s"%percentage
    print "\n"

def displayMessage(msg):
    for letter in msg:
        sys.stdout.write(letter)
        sys.stdout.flush()
        sleep(.085)

######################################################################################
#Display welcome message... Start of game. Meaningless messages just for fun.
user=commands.getoutput("whoami")
msg= "Greetings %s  my name is Joshua.. Shall we play a game? " % user
#displayMessage(msg)
#playGame=raw_input("Y or N ")
playGame="Y"
if playGame.upper()=="Y":
    msg="Number of players 0 or 1:"
    #displayMessage(msg)

    #Determine number of players.
    #0 Computer vs Computer
    #1 Person vs Computer
    #numberOfPlayers=int(raw_input(" "))
    numberOfPlayers=0
    if numberOfPlayers==0:
        player="Professor Flakner"
    else:
        player=user
    msg="How about Global Thermonuclear War?......"
    #displayMessage(msg)
    #sleep(2.0)
    msg="My apologies.\nThat game has been removed from my system. Lets play BattleShip\n\n"    
    #displayMessage(msg)
    countryList=['China','Russia','SouthKorea','India','France','Mexico','Taiwan','Turkey','NorthKorea']
    if numberOfPlayers==1:
        msg="Which country would you like to play?\n"
        displayMessage(msg)
        for country in countryList:
            msg="%s \n"%country
            displayMessage(msg)
        enemy=raw_input(": ")
        msg="Very well.\n"
    msg="Please be patient as battle tatics and anaylsis are loaded\n"
    #displayMessage(msg)
    #for i in range(21): 
    #    sys.stdout.write('\r')
    #    sys.stdout.write("[%-20s] %d%%" % ('='*i, 5*i))
    #    sys.stdout.flush()
    #    sleep(0.25) 
    #print "\n\n"
else:
    msg="A Strange Game.\nThe only winning move is not to play..\nHow about a nice game of chess.."
    displayMessage(msg)
    sys.exit()


################################################################################################
## Define the size of the Grid

#gridSelection=raw_input("Would you like to define the size of of the grid ('Y' or 'N')? " )
gridSelection="N"
if gridSelection.upper()=="Y":
    inputValuesValid="False"
    while inputValuesValid=="False":
        gridSize=int(raw_input("Input size of X and Y axis (Min:6  Max:17576)? " ))
        if gridSize <6:
            print "Biggest ship is 6 units.. Will not fit on grid." 
        if gridSize >17576:
            print "Nah dude..Max x and y xis size is 26  " 
        #If the grid size is in range then lets proceed
        if gridSize >6  or gridSize <= 17576:
            inputValuesValid="True"
            xGrid=gridSize
            yGrid=gridSize
else:
    #Default Grid size
    xGrid=16
    yGrid=16

################################################################################################
#Built a list of "whos turn it is". 
#For example
#['Professor Flakner','Joshua', 'Professor Flakner', 'Joshua']
turnList=determineMaxMoves(xGrid,yGrid,player)
################################################################################################
#Initalize our grid

myGridClass=grid('USA',xGrid,yGrid)
if numberOfPlayers==0:
    enemyGridClass=grid(random.choice(countryList),xGrid,yGrid)
else:
    enemyGridClass=grid(enemy,xGrid,yGrid)

################################################################################################
#Initalize our fleet

myFleetClass=fleet()
myFleetClass.maxShipSize=myFleetClass.determineMaxShipSize()
myFleetClass.minShipSize=myFleetClass.determineMinShipSize()

enemyFleetClass=fleet()
enemyFleetClass.maxShipSize=enemyFleetClass.determineMaxShipSize()
enemyFleetClass.minShipSize=enemyFleetClass.determineMinShipSize()
################################################################################################

#Set up grid values
enemyGridValues=enemyGridClass.gridValues
enemyGridClass.searchList=enemyGridClass.defineSearchList(myFleetClass.maxShipSize,enemyGridClass.attackNumber)

myGridValues=myGridClass.gridValues
myGridClass.searchList=myGridClass.defineSearchList(enemyFleetClass.maxShipSize,myGridClass.attackNumber)
################################################################################################

#Sort our ships by size. 
sortedShipList=sorted(myFleetClass.shipFleetDict.iteritems(), key=operator.itemgetter(1),reverse=True)

################################################################################################
#Setup the layout of our ships.

#Populate Computer/Enemy grid.
#Randomly place our ships 
setupNavy('random',enemyGridClass,sortedShipList)
#setupNavy('manual',enemyGridClass,sortedShipList)
enemyGridClass.populateGrid()

#Prompt if we want to manually place our ships.
if numberOfPlayers==1:
    choiceForSetup=raw_input("Would you like to manually place your ships ('Y' or 'N')?" )
else:
    choiceForSetup="N"
#Manually setup our ships
if choiceForSetup.upper()=='Y':
    #Display an empty grid
    myGridClass.populateGrid()
    myGridClass.displayGrid()
    #Manually setup our ships
    setupNavy('manual',myGridClass,sortedShipList)
    myGridClass.populateGrid()
else: 
    #Randomly setup or ships.
    setup='Y'
    while setup=="Y":
        setupNavy('random',myGridClass,sortedShipList)
        #setupNavy('manual',myGridClass,sortedShipList)
        #Display our random fleet location
        myGridClass.populateGrid()
        myGridClass.displayGrid()
        #If person is playing computer, prompt if they like the fleet setup 
        if numberOfPlayers==1:
            con=raw_input("Are you satisfied with your location of your ships ('Y' or 'N')? ")
        else:
            con="Y"
        #Setup is good so we change our conditional statement
        if con.upper()=="Y":
            setup="N"
        else:
        #Setup is NOT goodd so lets reset our grid and randomly setup another fleet
            myGridClass.gridValuesUsed=[]
            myGridValues=myGridClass.resetGridValues()
################################################################################################
#All necessary setup requirements have been met so lets get this party started.
for whosTurn in turnList:
    print "\n%s turn"%whosTurn
    if whosTurn!="Joshua":
        #If person is playing computer then we send in a flag "player"
        #This allows us to pick a attack location rather then the computer
        if int(numberOfPlayers) ==1:
            whosTurn='player'
        attackShip(whosTurn,myGridClass,enemyGridClass,enemyFleetClass)
        myGridClass.attackCounter+=1
    else:
        attackShip(whosTurn,enemyGridClass,myGridClass,myFleetClass)
        enemyGridClass.attackCounter+=1

    print "\n    MY BATTLEFIELD"
    myGridClass.populateGrid()
    myGridClass.displayGrid()

    print "\n    MY ATTACKS"   
    myGridClass.populateEnemyGrid()
    myGridClass.displayEnemyGrid()

fleet.py

class fleet:
    def __init__(self):
        #List of current ships of the United States Navy
        #Ship name         |           Size
        #--------------------------------------
        #airCraftCarrier               6   
        #battleShip                    5   
        #submarine                     4   
        #cruiser                       3   
        #destroyer                     2   

        #self.shipFleetDict={'airCraftCarrier':6}



        self.shipFleetDict={'airCraftCarrier':5,
                            'battleship':4,
                            'submarine':3,
                            'cruiser':3,
                            'destroyer':2}

        self.shipStatusDict={'airCraftCarrier':'active',
                             'battleship':'active',
                             'submarine':'active',
                             'cruiser':'active',
                             'destroyer':'active'} 

        self.numberSunkShips=0
        self.maxShipSize=0
        self.minShipSize=0


    def determineMaxShipSize(self):
        maxShipSize=0
        for ship,state in self.shipStatusDict.iteritems():
            if state=='active':
                if self.shipFleetDict[ship]>maxShipSize:
                    maxShipSize=self.shipFleetDict[ship]
        return maxShipSize

    def determineMinShipSize(self):
        from time import sleep
        minShipSize=1000
        for ship,state in self.shipStatusDict.iteritems():
            if state=='active':
                if self.shipFleetDict[ship]<minShipSize:
                    minShipSize=self.shipFleetDict[ship]
        return minShipSize

grid.py

# -*- coding: utf-8 -*-
import sys
import re
from time import sleep

#Color codes
#http://www.siafoo.net/snippet/88

class grid:
    def __init__(self,name,xSize,ySize):
        self.gridName =name
        self.attackCounter=0
        self.digCount=0
        self.hitList=[]
        self.attackedCoordList=[]
        self.blockedCoordList=[]
        self.missedList=[]
        self.gridValuesUsed=[]
        self.attackList=[]
        self.displayGridDict={}
        self.displayEnemyGridDict={}
        self.shipLocationDict={}
        self.xGridSize=xSize
        self.yGridSize=ySize
        self.gridValues=[ [ '\033[1;44m[ ]\033[1;m' for i in range(self.yGridSize) ] for j in range(self.xGridSize) ]
        self.gridValuesAttacked=[ [ '\033[1;44m[ ]\033[1;m' for i in range(self.yGridSize) ] for j in range(self.xGridSize) ]
        self.validPoints=self.defineValidPoints()
        self.alphList=self.defineAlphList()
        self.alphDict=self.generateDict()
        self.searchList=[]
        self.maxCharLen=self.determineMaxChars()
        self.attackNumber=1

    def determineMaxChars(self):
        maxCharLen=len(self.alphList[self.xGridSize])
        return maxCharLen

    def defineAlphList(self):
        import itertools
        alphaString=''.join(map(chr, range(65,91)))
        alpha=26
        maxDict={}
        maxList=[]
        #FROM A to ZZZ
        chosen=100
        x=0
        y=0
        overloop=0
        while x < chosen:
            mod=x%alpha
            if x!=0 and mod==0:
                overloop+=1
                maxList+=[''.join(i) for i in itertools.product(alphaString,repeat=overloop)]
            x+=1
        return maxList

    def get_rows(self,grid):
        return [[cell for cell in row] for row in grid]

    def get_cols(self,grid):
        cols = [[] for col in grid[0]]
        for row in grid:
            for col_index, cell in enumerate(row):
                cols[col_index].append(cell)
        return cols

    def get_forward_diagonals(self,grid,maxShipSize):
        buff = ['X']*(len(grid[0])+1)
        buff_grid = []
        for row_index, row in enumerate(self.get_rows(grid)):
            buff_grid.append( buff[row_index:] + row + buff[:row_index+maxShipSize] )
        cols = self.get_cols(buff_grid)[2:-1]
        for col in cols:
            while 'X' in col:
                col.remove('X')
        return cols

    def get_cols_backward(self,grid):
        cols = [[] for col in grid[len(grid)-1]]
        for row in grid:
            for col_index, cell in enumerate(row):
                cols[col_index].append(cell)
        return cols

    def get_backward_diagonals(self,grid,maxShipSize):
        buff = ['X']*(len(grid[0])+1)
        buff_grid = []
        for row_index, row in enumerate(self.get_rows(grid)):
            buff_grid.append( buff[:row_index+1] + row + buff[row_index-maxShipSize:] )
        cols = self.get_cols_backward(buff_grid)[1:-2]
        for col in cols:
            while 'X' in col:
                col.remove('X')
        return cols


    def get_digonals_maxSize(self,allList,maxShipSize):
        iterator=0
        searchList=[]
        allList = [x for x in allList if x != []]
        middle=int(round(float(len(allList)/2)))
        while middle>0:
            searchList.append(allList[middle])
            middle-=maxShipSize
        middleHigh=int(round(float(len(allList)/2)))
        while middleHigh<len(allList)-1:
            searchList.append(allList[middleHigh])
            middleHigh+=maxShipSize
        searchList=sorted(searchList)
        #remove duplicate lists
        searchList=[searchList[i] for i in range(len(searchList)) if i == 0 or searchList[i] != searchList[i-1]]
        return searchList

    def get_digonals_maxSize_backward(self,allList,maxShipSize):
        searchList=[]
        allList = [x for x in allList if x != []]
        middle=int(round(float(len(allList)/2)))
        while middle>0:
            searchList.append(allList[middle])
            middle-=maxShipSize
        middleHigh=int(round(float(len(allList)/2)))
        while middleHigh<len(allList)-1:
            searchList.append(allList[middleHigh])
            middleHigh+=maxShipSize
        #searchList=sorted(searchList)
        #remove duplicate lists
        searchList=[searchList[i] for i in range(len(searchList)) if i == 0 or searchList[i] != searchList[i-1]]
        return searchList


    def defineCoords(self):
        maxGrid=self.yGridSize
        coordsList=[]
        grid=[ [ '[]' for i in range(maxGrid) ] for j in range(maxGrid) ]
        for i in range(maxGrid):
            searchList=[]
            for j in range(maxGrid):
                coords="%s,%s"%(i,j)
                searchList.append(coords)
            coordsList.append(searchList)
        return coordsList

    def defineSearchListForwardList(self,maxShipSize,attackNumber):
        coordsList=self.defineCoords()
        allList= self.get_forward_diagonals(coordsList,maxShipSize)
        searchList=self.get_digonals_maxSize(allList,maxShipSize)
        what="%s %s "% (attackNumber-1,len(searchList))
        if attackNumber-1<len(searchList):
            return searchList[attackNumber-1]
        else:
            return self.validPoints


    def defineSearchList(self,maxShipSize,attackNumber):
        coordsList=self.defineCoords()
        allListForward= self.get_forward_diagonals(coordsList,maxShipSize)
        searchListForward=self.get_digonals_maxSize(allListForward,maxShipSize)
        searchListForward=sorted(searchListForward, key=len,reverse=True)
        allListBackward= self.get_backward_diagonals(coordsList,maxShipSize)
        searchListBackward=self.get_digonals_maxSize_backward(allListBackward,maxShipSize)
        searchListBackward=sorted(searchListBackward, key=len,reverse=True)

        searchList=searchListForward+searchListBackward
        searchList=[searchList[i] for i in range(len(searchList)) if i == 0 or searchList[i] != searchList[i-1]]
        searchList=sorted(searchList, key=len,reverse=True)
        if self.digCount < len(searchList):
            searchListToReturn=searchList[self.digCount]
            self.digCount+=1
            return searchListToReturn
        else:
            return self.validPoints


    def defineValidPoints(self):
        validPoints=[]
        x=0
        while x < self.xGridSize: 
            y=0 
            while y < self.yGridSize:
                validPoints.append("%s,%s"%(x,y))
                y+=1
            x+=1
        return validPoints

    def generateDict(self):
        alphDict={}
        i=0
        for i in range(0, len(self.alphList)):
            #alphDict[(ord(self.alphList[i])%32)-1] = self.alphList[i]
            alphDict[i] = self.alphList[i]

        return alphDict

    def resetGridValues(self):
        #sam
        self.gridValues=[ [ '[ ]' for i in range(self.yGridSize) ] for j in range(self.xGridSize) ]
        return self.gridValues 

    def checkDataPointValue(self,dataPoint):
        m=re.search('([A-Z]*)([0-9]*)',dataPoint)
        xValue=m.group(1)
        yValue=m.group(2)

        xValue=self.alphList.index(xValue)
        coords="%s,%s"%(xValue,yValue)
        if coords in self.gridValuesUsed:
            return "T"
        else:
            return "E"

    def determineEndPoint(self,start,size,placement):
        startValues=re.search('([A-Z]*)([0-9]*)',start)
        x=startValues.group(1)
        y=startValues.group(2)
        if placement.upper()=='V':
            yEnd=(int(y)+size)-1
            if yEnd > self.yGridSize-1: return "F" 
            endPoint="%s%s"%(x,str(yEnd))
        else:
            xValueNumber=self.alphList.index(x)
            xEnd=xValueNumber+size-1
            if xEnd > self.xGridSize-1: return "F" 
            endPoint="%s%s"%(self.alphList[xEnd],y)
        return endPoint

    def determineFullLocation(self,start,end):
        startValues=re.search('([A-Z]*)([0-9]*)',start)
        xValueStart=startValues.group(1)
        yValueStart=int(startValues.group(2))

        endValues=re.search('([A-Z]*)([0-9]*)',end)
        xValueEnd=endValues.group(1)
        yValueEnd=int(endValues.group(2))

        shipCoordList=[]
        if xValueStart==xValueEnd: #placing vertical
            xValueNumber=self.alphList.index(xValueStart)
            i=yValueStart
            while i <= yValueEnd:
                shipCoordList.append('%s,%s'%(xValueNumber,i))
                i+=1
        else:
            xValueStart=self.alphList.index(xValueStart)
            xValueEnd=self.alphList.index(xValueEnd)
            i=xValueStart
            while i <= xValueEnd:
                shipCoordList.append('%s,%s'%(i,yValueStart))
                i+=1
        return shipCoordList

    def shipPlacement(self,start,end,shipCoordList):
        startValues=re.search('([A-Z]*)([0-9]*)',start)
        xValueStart=startValues.group(2)
        xValueEnd=startValues.group(1)
        block='■'
        if xValueStart==xValueEnd: #placing vertical
            for coord in shipCoordList:
                coordList=coord.split(',')
                xValue=int(coordList[0])
                yValue=int(coordList[1])
                displayVal="\033[1;44m[%s]\033[1;44m"%block
                self.gridValues[xValue][yValue]=displayVal
        else: #placing horizontal
            i=1
            size=len(shipCoordList)
            for coord in shipCoordList:
                coordList=coord.split(',')
                xValue=int(coordList[0])
                yValue=int(coordList[1])
                if i ==1:
                    displayVal="[%s "%block
                elif i==size:
            displayVal=" %s]"%block
                else:
                    displayVal=" %s "%block
                self.gridValues[xValue][yValue]=displayVal
                i+=1
        return 

    def populateGrid(self):
        y=0
        #gridDict={}
        numElements=len(self.gridValues)
        while y < self.yGridSize:
            values=[]
            x=0 
            while x < self.xGridSize:
                values.append(self.gridValues[x][y]) 
                x+=1
            if numElements>9:
                yDisplay="%02d" % (y,)
                self.displayGridDict[yDisplay]=values
            else:
                self.displayGridDict[y]=values
            values=[]
            y+=1
        return


    def displayGrid(self):
        row=0
        header=""
        numElements= len(self.displayGridDict)
        x=0
        while x<numElements:
            #Horzintal label
            header+="[%s]"%self.alphList[x]
            x+=1
        numElements=len(self.displayGridDict)
        for key in sorted(self.displayGridDict.iterkeys()):
            value=self.displayGridDict[key]
            if row==0:
                if numElements>9:
                    displayStr="  %s\n"%(header)
                else:
                    displayStr=" %s\n"%(header)
                sys.stdout.write(displayStr)
                displayStr=""
            #Vertical Label
            displayStr+="%s"%key

            for cell in value:
                displayStr+="%s"%cell
            displayStr+="\n"
            sys.stdout.write(displayStr)
            displayStr=""
            row+=1


    def populateEnemyGrid(self):
        y=0
        #gridDict={}
        numElements=len(self.gridValuesAttacked)
        while y < self.yGridSize:
            values=[]
            x=0 
            while x < self.xGridSize:
                values.append(self.gridValuesAttacked[x][y]) 
                x+=1
            if numElements>9:
                yDisplay="%02d" % (y,)
                self.displayEnemyGridDict[yDisplay]=values
            else:
                self.displayEnemyGridDict[y]=values
            values=[]
            y+=1
        return


    def displayEnemyGrid(self):
        row=0
        header=""
        numElements= len(self.displayEnemyGridDict)
        x=0
        while x<numElements:
            header+="[%s]"%self.alphList[x]
            x+=1
        numElements=len(self.displayEnemyGridDict)
        for key in sorted(self.displayEnemyGridDict.iterkeys()):
            value=self.displayEnemyGridDict[key]
            if row==0:
                if numElements>9:
                    displayStr="  %s\n"%(header)
                else:
                    displayStr=" %s\n"%(header)
                sys.stdout.write(displayStr)
                displayStr=""
            displayStr+="%s"%key

            for cell in value:
                displayStr+="%s"%cell
            displayStr+="\n"
            sys.stdout.write(displayStr)
            displayStr=""
            row+=1
\$\endgroup\$
  • 2
    \$\begingroup\$ I'm putting this as a comment since I'm not confident in it as an answer, but why are you starting with the largest size? If you start at the largest, you'll eventually need to backtrack and then do the smaller ones anyway. My guess is that the opposite is faster, but I'm ready to be proven totally wrong about it. \$\endgroup\$ – SuperBiasedMan Sep 7 '15 at 13:28
  • \$\begingroup\$ I used to confuse the computer by putting a battleship and a destroyer end-to-end. Often the computer would destroy the battleship and one cell of the destroyer and think it had hit my aircraft-carrier. You should always take one step further once you think you've destroyed a ship. \$\endgroup\$ – OldCurmudgeon Sep 7 '15 at 13:56
  • 1
    \$\begingroup\$ @SuperBiasedMan When placing ships, the largest has the least amount of possible places. Doing that first makes placement easier. \$\endgroup\$ – Mast Sep 7 '15 at 14:55
  • \$\begingroup\$ @Mast You're talking about placement but the OP is using it to try find ships to attack. \$\endgroup\$ – SuperBiasedMan Sep 7 '15 at 15:00
  • 1
    \$\begingroup\$ @SuperBiasedMan thank for your suggestion. I originally started off with that a approach (checkerboard attack) and the percent of accuracy was a lot lower. :) \$\endgroup\$ – Sam Sanchez Sep 7 '15 at 15:18
10
\$\begingroup\$

Some general style suggestions; incomplete due to lack of time, but they should give you some things to think about.

Upgrade to Python 3 if possible. You appear to only be using stdlib code, so this should be reasonable painless.

You have a lot of java-esque naming conventions. Python style (see especially PEP 8) prefers methods and variables to be named like_this rather than likeThis. Names of classes should be capitalised, so Grid instead of grid. You have some of your methods named according to this style already - you should generally try to pick one style and stick with it; preferably follow the conventions in PEP 8 unless there's a compelling reason not to.

You use strings as flags a lot - eg,

used="no"
con="yes"
while con=="yes": 

Python supports booleans, so you can do

used = False
con = True
while con:

Comments like this:

#setupNavy
#Purpos: To place our ships on the grid
#Receives: setupSelection- either manual or random
#          gridClass
#          sortedShipList
#Return: 

Should be docstrings - basically, make it an unassigned string literal, and put it directly inside the function definition.

The first argument to setup_navy is another string-as-flag. Use a bool instead, and all it automatic_placement. But even better, split this into two functions. The one that does it automatically could actually be a method of Grid called place_ships, and document it as placing them randomly. The one that places them manually does belong out in the main flow of your program, since it continually does IO. This will simplify your code greatly.

The second argument is called gridClass but actually expects a Grid instance. Just call it grid.

sortedShipList could just be called ships. If you want to document its structure (which isn't a bad idea), you can do better than giving it a clunky name that only documents some of it's structure - in your docstring, do this:

def place_ships(self, ships):
    '''
    Randomly place the given ships on the grid.

    `ships`: a sorted list of tuples (name, type)
    '''

Consider using a namedtuple for the ships, so then this loop:

for shipData in sortedShipList:
    shipName=shipData[0]
    shipSize=shipData[1]

can become just:

for ship in ships:

and you can immediately work with ship.name and ship.data.

shipCoordList=gridClass.determineFullLocation(start,end)
gridClass.shipLocationDict[shipName]=shipCoordList

It seems odd to ask gridClass to work something out for you, and then immediately assign exactly that result back to an attribute on gridClass. It would make more sense if you could come up with a flow that the grid can modify it's own attributes appropriately. I think it might make sense for grid to have a method to place a single ship at a particular start location, and going in a particular direction - perhaps raising an exception if it would go past the end (possibly taking a flag to say that that's ok sometimes). It looks like you already have a method called grid.shipPlacement - why aren't you using it here?

Your coordinates here are strings. Instead, leave them as (x, y) tuples so you don't have to keep parsing them every time you want to do stuff with them.

Drop the word "determine" from various method names. It's just noise. We know that a function either does something or calculates something - ie, functions usually (although there are occasionally good reasons to have exceptions) follow the principle of command-query separation. So if its name is a noun phrase, we already know that it must calculate whatever that phrase refers to. You might consider making some of them into propertys so that you can use them as attributes.

\$\endgroup\$
  • \$\begingroup\$ Thank you for the suggestions. I really like the boolen idea using named tuples. I will also use docstrings. Your suggestions will help clean up the code for easier readability. The function "checkDataPointValue" verifies that a ship can fit on the board. Adding proper docstrings with each function will help clarify stuff like this. :) I will also work on better naming conventions. I typically put the type of data structure in the variable name for quickly knowing what type it is. ie shipCoordList or shipLocationDict. Is that not a good idea? \$\endgroup\$ – Sam Sanchez Sep 7 '15 at 15:37
6
\$\begingroup\$

You don't need to have a large sprawling comment like this and then have a dictionary that mimics the table data anyway.

    #List of current ships of the United States Navy
    #Ship name         |           Size
    #--------------------------------------
    #airCraftCarrier               6   
    #battleShip                    5   
    #submarine                     4   
    #cruiser                       3   
    #destroyer                     2   

    #self.shipFleetDict={'airCraftCarrier':6}

    self.shipFleetDict={'airCraftCarrier':5,
                        'battleship':4,
                        'submarine':3,
                        'cruiser':3,
                        'destroyer':2}

If you rename shipFleetDict to ship_fleet_sizes then you make it obvious what the dictionary is for even without adding a comment. Also generally speaking using the datatype in the name is redundant since it's clear in the code anyway that you're defining a dictionary. It's extra bad though that you define the size of the ships differently in the comment and the dictionary itself. Comments should be accurate and up to date to avoid confusion.

In your next dictionary for ship status, I would again remove Dict from the name and switch to using True and False rather than 'active'. It's a faster check, and more Pythonic. It would allow you to do this:

if fleet.ship_status['airCraftCarrier']:

Also why not call your two ship size functions in init?

    self.max_ship = self.min_ship_size()
    self.min_ship = self.max_ship_size()

Speaking of those methods, you should be combining the if statements rather than doing 2 separate ones.

max = 0
for ship,active in self.shipStatusDict.iteritems():
    if (active and self.ship_fleet[ship] > max):

I recommend not mimicking the names of the class attributes, it's liable to cause confusion and look like you just forgot to include self. before it. max is clear enough to use on these few lines.

And you left in a useless import in determineMinShipSize. If you're no longer using this, clean it out.

from time import sleep
\$\endgroup\$
  • \$\begingroup\$ I really like your idea of using a true,false boolean instead of active or sunk. if fleet.ship_status['airCraftCarrier']: is really nice and a lot nicer then checking its value. \$\endgroup\$ – Sam Sanchez Sep 7 '15 at 15:40
  • \$\begingroup\$ @SamSanchez The reason is that it makes variable names extra long and harder to follow. Generally it should be obvious what type something is from how you use it. fleet.ship_size['cruiser'] is quite clear because you know that collection objects (lists, dictionaries etc.) are accessed with [] and dictionaries are the usual collection object that takes a key to access the values. If it was a more unusual data type that might be mistaken for another (like a Counter), then it could be worth including it in the name. \$\endgroup\$ – SuperBiasedMan Sep 7 '15 at 15:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.