fork download
copy 
  1. #!/usr/bin/env python
  2. import sys
  3. from collections import deque #high performance queue "deck"
  4.  
  5. class Node(object):
  6.         def __init__(self,x,y,history):
  7.                 self.locationx = x
  8.                 self.locationy = y
  9.                 self.data = None
  10.                 self.history = history #previous node to go backwards
  11.  
  12. def printNodePathTrace(inNode,width,height,mapTerrain,frontier):
  13.     #travel backward through node history until history == None is reached
  14.     #print off map of path
  15.     mapPath = mapTerrain
  16.     for i in range(width): #fill map with blanks
  17.         for j in range(height):
  18.             mapPath[i][j] = '-'
  19.  
  20.     #print frontier list
  21.     print "length of frontier"
  22.     print len(frontier)
  23.     for item in frontier:
  24.  
  25.         #print item.locationy
  26.         #print item.locationx
  27.         mapPath[item.locationy][item.locationx] = '*'
  28.  
  29.     #print path found
  30.     done = 0
  31.     count = 0
  32.     currentNode = inNode
  33.     while(done == 0 and count < 50):
  34.         mapPath[currentNode.locationy][currentNode.locationx] = '#'
  35.         if currentNode.history == None:
  36.             done = 1
  37.         currentNode = currentNode.history
  38.         count += 1
  39.     printMap(mapPath)
  40.  
  41. def printMap(mapTerrain): #horizontal right positive x, verticle down positive y
  42.         for i in mapTerrain:
  43.             for j in i:
  44.                 sys.stdout.write(j)
  45.             sys.stdout.write('\n')
  46.  
  47. def printMapStartAndGoal(mapTerrain,startX,startY,goalX,goalY):
  48.     #Y is row, X is column. Y is vertical, X is horizontal
  49.     temp1 = mapTerrain[startY][startX]
  50.     temp2 = mapTerrain[goalY][goalX]
  51.     mapTerrain[startY][startX] = 'S'
  52.     mapTerrain[goalY][goalX] = 'G'
  53.     printMap(mapTerrain)
  54.     mapTerrain[startY][startX] = temp1
  55.     mapTerrain[goalY][goalX] = temp2
  56.  
  57. def main():
  58.     #Input map
  59.     #Your program should be able to read a map file in the following format.
  60.     #Width Height
  61.     #StartX StartY
  62.     #GoalX GoalY
  63.     #map
  64.     searchMode = "BFS" #options are BFS, LC, ID, A*1, A*2
  65.  
  66.     logfile = open("smallmap2.txt", "r")
  67.     [width,height] = map(int,logfile.readline().split())
  68.     [startX,startY] = map(int,logfile.readline().split())
  69.     [goalX,goalY] = map(int,logfile.readline().split())
  70.  
  71.     mapTerrainInput = logfile.read()
  72.     mapTerrain = map(list,mapTerrainInput.splitlines())
  73.     #map the list function to mapTerrainInput split into lines without '\n'
  74.  
  75.     printMapStartAndGoal(mapTerrain,startX,startY,goalX,goalY)
  76.  
  77.     print mapTerrain
  78.     printMap(mapTerrain)
  79.  
  80.     closedList = [] #contains list of nodes visited already
  81.     frontier = deque([])
  82.     startNode = Node(startX,startY,None)
  83.  
  84.     #check if node is a goal node
  85.     #add node to closed list
  86.     #add expansions to frontier list (not ones on closed list)
  87.     #Repeat with next node in Frontier
  88.  
  89.     goalFound = 0 ### there's an error with this line's indentation???
  90.     iterationCount = 0
  91.     currentNode = startNode
  92.     while goalFound == 0 and iterationCount < 500: #stop when goal is found
  93.             if (currentNode.locationx == goalX and currentNode.locationy == goalY):
  94.                     goalFound = 1
  95.                     break
  96.  
  97.             closedList.append(currentNode)
  98.             #expand node - currently not checking the closed list
  99.             if (currentNode.locationy > 0): #can expand up
  100.                 frontier.append(Node(currentNode.locationx,currentNode.locationy - 1,currentNode))
  101.             if (currentNode.locationy < height - 1): #can expand down
  102.                 frontier.append(Node(currentNode.locationx,currentNode.locationy + 1,currentNode))
  103.             if (currentNode.locationx > 0): #can expand left
  104.                 frontier.append(Node(currentNode.locationx - 1,currentNode.locationy,currentNode))
  105.             if (currentNode.locationx < width -1): #can expand right
  106.                 frontier.append(Node(currentNode.locationx + 1,currentNode.locationy,currentNode))
  107.             #done expanding
  108.  
  109.             currentNode = frontier.popleft()
  110.             iterationCount += 1
  111.  
  112.  
  113.     print currentNode.history
  114.     print currentNode.locationx
  115.     print currentNode.locationy
  116.  
  117.     printNodePathTrace(currentNode,width,height,mapTerrain,closedList)
  118.  
  119.  
  120. if __name__ == '__main__':
  121.     main()
Runtime error #stdin #stdout 0.03s 6712KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/USAvc
language:
Python (cpython 2.7.16)
created:
12 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!