Commits

mastrojionis committed 129f69c

Path finding methods (needs cleaning and support for abitrary map sizes)

Comments (0)

Files changed (2)

 from pymongo.objectid import ObjectId
 import bson
 
+import astar
+
 from flask import Flask, request
 app = Flask(__name__)
 app.config.from_object('settings.Config')
         obj = []
     return repr(list(obj))
 
+def getlevel(cardid):
+    try:
+        objid = ObjectId(cardid)
+        obj = db.cards.find({'_id': ObjectId(cardid)})
+    except bson.errors.InvalidId:
+        return None
+    return obj[0]['level'][0]
+
+@app.route("/testPath")
+def testPath():
+    required = ['X', 'Y', 'targetX', 'targetY', 'level']
+    params = dict(request.args)
+    card = {}
+    for p in required:
+        if p not in params:
+            return "Missing param: %s" % p
+        card[p] = params.pop(p)
+    for extra in params.keys():
+        card[extra] = params.pop(extra)
+
+    x = int(card['X'][0])
+    y = int(card['Y'][0])
+    targetX = int(card['targetX'][0])
+    targetY = int(card['targetY'][0])
+    level = getlevel(card['level'][0])
+    exec('level = ' + level)
+    if level == None:
+        pathAvailable = 'No such map'
+    else:
+        pathAvailable = astar.astar(x,y,targetX,targetY,level)
+    return repr(pathAvailable)
+
+
 if __name__ == "__main__":
     app.run(host=app.config['APP_HOST'], port=app.config['APP_PORT'])
 c = [1, 1, 1, 1, 1, 1, 1, 0]   #unblocked.  When accessing a cell, type y-
 d = [0, 0, 1, 1, 1, 1, 1, 0]   #coordinate first, then the x-coordinate.  like:
 e = [0, 0, 0, 0, 0, 0, 0, 0]   #"map[4][0]" to access the top left cell in a.
-map = [e,                   #list 0
-       d,                   #list 1
-       c,                   #list 2
-       b,                   #list 3
-       a]                   #list 4
 
-openlist = []                           #open list is empty
-closedlist = []                         #closed list is empty
-targetX = 6                             #goal cell X coordinate
-targetY = 1                             #goal cell Y coordinate
-startX = 0                              #start X coordiante
-startY = 3                              #start Y coordinate
-numpasses = 0           #Used to count how many times the while-loop looped.
+level=[a,b,c,d,e]
 
-#These are the heuristic constants.  If Dg > Dh, more cells are analyzed and a
-#more ideal path is found.  If Dh >= Dg, less cells are analyzed and a path is
-#found quicker.
-Dg = 1
-Dh = 1
-
-maxValX = 7                             #x value of a cell cannot be greater
-maxValY = 4                             #y value of a cell cannot be greater
-
-#--------------------------------------------------------------------
-#This part of the code creates a 2-dimensional array for storing parent cells.
-#For example: Pcell[2][3] = [2, 2].  It has the same dimensions and size as the
-#above map, so no "cell is out of range" errors can occur.  It works the same as
-#the map above; y value first and x second.  Example: Pcell[y][x] = [NewX, NewY]
-
-ap = [0, 0, 0, 0, 0, 0, 0, 0]
-bp = [0, 0, 0, 0, 0, 0, 0, 0]
-cp = [0, 0, 0, 0, 0, 0, 0, 0]
-dp = [0, 0, 0, 0, 0, 0, 0, 0]
-ep = [0, 0, 0, 0, 0, 0, 0, 0]
-Pcell = [ep, dp, cp, bp, ap]
+STARTX = 0
+STARTY = 0
+TARGETX = 0
+TARGETY = 0
+Dg = 0
+Dh = 0
 
 #--------------------------------------------------------------------
 #this part of the code establishes the telnet connection to the RCC and is
 #independent and unrelated to the A* algorithm or finding a path (it is only
 #used to physically move the robot after the path is found).
 
-import telnetlib
-import time
-import string
+##import telnetlib
+##import time
+##import string
 
 ##HOST = "localhost"
 ##
 #These are the mathamatical heuristics, used to calculate the so-called G,
 #H and F scores of a cell.
 
+
+
 def G(a):
-    answerG = Dg * (abs(a[0] - startX) + abs(a[1] - startY))
+    answerG = Dg * (abs(a[0] - STARTX) + abs(a[1] - STARTY))
     return answerG
 
 def H(a):
-    Hscore = Dh * (abs(a[0] - targetX) + abs(a[1] - targetY))
+    Hscore = Dh * (abs(a[0] - TARGETX) + abs(a[1] - TARGETY))
     return Hscore
 
 def F(a):
 #----------------------------------------------------------------------
 #This part of the code is the actual A* algorithm.
 
-curCellX = startX                             #start cell is the current cell
-curCellY = startY
+def astar(startX, startY,targetX, targetY,level=None):
+    if level != None:
+        a=level[0]
+        b=level[1]
+        c=level[2]
+        d=level[3]
+        e=level[4]
 
-closedlist.append([startX, startY])           #add start cell to closed list
+    STARTX = startX
+    STARTY = startY
+    TARGETX = targetX
+    TARGETY = targetY    
 
-rest = 0                              #start search.  I set up a dummy variable,
-while not rest:                       #so it would loop.
+    map = [e,                   #list 0
+           d,                   #list 1
+           c,                   #list 2
+           b,                   #list 3
+           a]                   #list 4
 
-      numpasses = numpasses + 1       #Counts how many times it has looped.
+    openlist = []                           #open list is empty
+    closedlist = []                         #closed list is empty
+    ##targetX = 6                             #goal cell X coordinate
+    ##targetY = 1                             #goal cell Y coordinate
+    ##startX = 0                              #start X coordiante
+    ##startY = 3                              #start Y coordinate
+    numpasses = 0           #Used to count how many times the while-loop looped.
 
-      NcellX = curCellX
-      NcellY = curCellY + 1
-      ScellX = curCellX
-      ScellY = curCellY - 1
-      EcellX = curCellX + 1
-      EcellY = curCellY
-      WcellX = curCellX -1
-      WcellY = curCellY
+    #These are the heuristic constants.  If Dg > Dh, more cells are analyzed and a
+    #more ideal path is found.  If Dh >= Dg, less cells are analyzed and a path is
+    #found quicker.
+    Dg = 1
+    Dh = 1
 
-      #check if north cell is in range, that is, not under 0 or over max value
-      if NcellX >= 0 and NcellY >= 0 and NcellX <= maxValX and NcellY <= maxValY:
-         #check if it's on the closed list or blocked.  Its blocked if the cell
-         #NcellX and NcellY represent is = 0, open is = 1    
-         if map[NcellY][NcellX] != 0 and closedlist.count([NcellX, NcellY]) == 0:
-             #if it's not on the openlist, add it and set parent.
-             if openlist.count([NcellX, NcellY]) == 0:
-                 openlist.append([NcellX, NcellY])
-                 Pcell[NcellY][NcellX] = [curCellX, curCellY]
-             else:
-                 #check if path from current cell has a lower G value
-                 if G([curCellX, curCellY]) + Dg < G([NcellX, NcellY]):
-                     #if it is, set parent to current cell and recalculate G&F scores
-                     #for this cell
+    maxValX = 7                             #x value of a cell cannot be greater
+    maxValY = 4                             #y value of a cell cannot be greater
+
+    #--------------------------------------------------------------------
+    #This part of the code creates a 2-dimensional array for storing parent cells.
+    #For example: Pcell[2][3] = [2, 2].  It has the same dimensions and size as the
+    #above map, so no "cell is out of range" errors can occur.  It works the same as
+    #the map above; y value first and x second.  Example: Pcell[y][x] = [NewX, NewY]
+
+    ap = [0, 0, 0, 0, 0, 0, 0, 0]
+    bp = [0, 0, 0, 0, 0, 0, 0, 0]
+    cp = [0, 0, 0, 0, 0, 0, 0, 0]
+    dp = [0, 0, 0, 0, 0, 0, 0, 0]
+    ep = [0, 0, 0, 0, 0, 0, 0, 0]
+    Pcell = [ep, dp, cp, bp, ap]
+      
+    
+    curCellX = startX                             #start cell is the current cell
+    curCellY = startY
+    numpasses = 0
+
+    closedlist.append([startX, startY])           #add start cell to closed list
+
+    rest = 0                              #start search.  I set up a dummy variable,
+    while not rest:                       #so it would loop.
+
+          numpasses = numpasses + 1       #Counts how many times it has looped.
+
+          NcellX = curCellX
+          NcellY = curCellY + 1
+          ScellX = curCellX
+          ScellY = curCellY - 1
+          EcellX = curCellX + 1
+          EcellY = curCellY
+          WcellX = curCellX -1
+          WcellY = curCellY
+
+          #check if north cell is in range, that is, not under 0 or over max value
+          if NcellX >= 0 and NcellY >= 0 and NcellX <= maxValX and NcellY <= maxValY:
+             #check if it's on the closed list or blocked.  Its blocked if the cell
+             #NcellX and NcellY represent is = 0, open is = 1    
+             if map[NcellY][NcellX] != 0 and closedlist.count([NcellX, NcellY]) == 0:
+                 #if it's not on the openlist, add it and set parent.
+                 if openlist.count([NcellX, NcellY]) == 0:
+                     openlist.append([NcellX, NcellY])
                      Pcell[NcellY][NcellX] = [curCellX, curCellY]
-                     G([NcellX, NcellY]) == G([curCellX, curCellY]) + Dg
-                     F([NcellX, NcellY]) == G([NcellX, NcellY]) + H([NcellX, NcellY])
+                 else:
+                     #check if path from current cell has a lower G value
+                     if G([curCellX, curCellY]) + Dg < G([NcellX, NcellY]):
+                         #if it is, set parent to current cell and recalculate G&F scores
+                         #for this cell
+                         Pcell[NcellY][NcellX] = [curCellX, curCellY]
+                         G([NcellX, NcellY]) == G([curCellX, curCellY]) + Dg
+                         F([NcellX, NcellY]) == G([NcellX, NcellY]) + H([NcellX, NcellY])
 
-      #repeat above, only for south, east and west cells.
-      if ScellX >= 0 and ScellY >= 0 and ScellX <= maxValX and ScellY <= maxValY:
-         if map[ScellY][ScellX] != 0 and closedlist.count([ScellX, ScellY]) == 0:
-              if openlist.count([ScellX, ScellY]) == 0:
-                  openlist.append([ScellX, ScellY])
-                  Pcell[ScellY][ScellX] = [curCellX, curCellY]
-              else:
-                  if G([curCellX, curCellY]) + Dg < G([ScellX, ScellY]):
+          #repeat above, only for south, east and west cells.
+          if ScellX >= 0 and ScellY >= 0 and ScellX <= maxValX and ScellY <= maxValY:
+             if map[ScellY][ScellX] != 0 and closedlist.count([ScellX, ScellY]) == 0:
+                  if openlist.count([ScellX, ScellY]) == 0:
+                      openlist.append([ScellX, ScellY])
                       Pcell[ScellY][ScellX] = [curCellX, curCellY]
-                      G([ScellX, ScellY]) == G([curCellX, curCellY]) + Dg
-                      F([ScellX, ScellY]) == G([ScellX, ScellY]) + H([ScellX, ScellY])
+                  else:
+                      if G([curCellX, curCellY]) + Dg < G([ScellX, ScellY]):
+                          Pcell[ScellY][ScellX] = [curCellX, curCellY]
+                          G([ScellX, ScellY]) == G([curCellX, curCellY]) + Dg
+                          F([ScellX, ScellY]) == G([ScellX, ScellY]) + H([ScellX, ScellY])
 
-      if EcellX >= 0 and EcellY >= 0 and EcellX <= maxValX and EcellY <= maxValY:
-         if map[EcellY][EcellX] != 0 and closedlist.count([EcellX, EcellY]) == 0:
-              if openlist.count([EcellX, EcellY]) == 0:
-                  openlist.append([EcellX, EcellY])
-                  Pcell[EcellY][EcellX] = [curCellX, curCellY]
-              else:
-                  if G([curCellX, curCellY]) + Dg < G([EcellX, EcellY]):
+          if EcellX >= 0 and EcellY >= 0 and EcellX <= maxValX and EcellY <= maxValY:
+             if map[EcellY][EcellX] != 0 and closedlist.count([EcellX, EcellY]) == 0:
+                  if openlist.count([EcellX, EcellY]) == 0:
+                      openlist.append([EcellX, EcellY])
                       Pcell[EcellY][EcellX] = [curCellX, curCellY]
-                      G([EcellX, EcellY]) == G([curCellX, curCellY]) + Dg
-                      F([EcellX, EcellY]) == G([EcellX, EcellY]) + H([EcellX, EcellY])
+                  else:
+                      if G([curCellX, curCellY]) + Dg < G([EcellX, EcellY]):
+                          Pcell[EcellY][EcellX] = [curCellX, curCellY]
+                          G([EcellX, EcellY]) == G([curCellX, curCellY]) + Dg
+                          F([EcellX, EcellY]) == G([EcellX, EcellY]) + H([EcellX, EcellY])
 
-      if WcellX >= 0 and WcellY >= 0 and WcellX <= maxValX and WcellY <= maxValY:
-         if map[WcellY][WcellX] != 0 and closedlist.count([WcellX, WcellY]) == 0:
-              if openlist.count([WcellX, WcellY]) == 0:
-                  openlist.append([WcellX, WcellY])
-                  Pcell[WcellY][WcellX] = [curCellX, curCellY]
-              else:
-                  if G([curCellX, curCellY]) + Dg < G([WcellX, WcellY]):
+          if WcellX >= 0 and WcellY >= 0 and WcellX <= maxValX and WcellY <= maxValY:
+             if map[WcellY][WcellX] != 0 and closedlist.count([WcellX, WcellY]) == 0:
+                  if openlist.count([WcellX, WcellY]) == 0:
+                      openlist.append([WcellX, WcellY])
                       Pcell[WcellY][WcellX] = [curCellX, curCellY]
-                      G([WcellX, WcellY]) == G([curCellX, curCellY]) + Dg
-                      F([WcellX, WcellY]) == G([WcellX, WcellY]) + H([WcellX, WcellY])
+                  else:
+                      if G([curCellX, curCellY]) + Dg < G([WcellX, WcellY]):
+                          Pcell[WcellY][WcellX] = [curCellX, curCellY]
+                          G([WcellX, WcellY]) == G([curCellX, curCellY]) + Dg
+                          F([WcellX, WcellY]) == G([WcellX, WcellY]) + H([WcellX, WcellY])
 
-      if len(openlist) == 0:                         #if openlist is empty, exit
-          NoSolutionFound()                          #loop; there is no solution.
-          break
+          if len(openlist) == 0:                         #if openlist is empty, exit
+              return False
+              NoSolutionFound()                          #loop; there is no solution.
+              break
 
-      #now we find the cell on the openlist with the lowest F score and set it
-      #as the current cell.
-      smallest = F(openlist[0])         #Assume the first member is the smallest.
-      for r in openlist:
-          if F(r) <= smallest:          #If an item on the list is smaller than
-              smallest = F(r)           #the first item, set it as the new smallest
-              NewX = r[0]
-              NewY = r[1]           #Keep looping until a smaller value is found
+          #now we find the cell on the openlist with the lowest F score and set it
+          #as the current cell.
+          smallest = F(openlist[0])         #Assume the first member is the smallest.
+          for r in openlist:
+              if F(r) <= smallest:          #If an item on the list is smaller than
+                  smallest = F(r)           #the first item, set it as the new smallest
+                  NewX = r[0]
+                  NewY = r[1]           #Keep looping until a smaller value is found
 
-      #add the cell you just selected to the closed list and remove it from the
-      #open list.        
-      closedlist.append([NewX, NewY])
-      openlist.remove([NewX, NewY])
+          #add the cell you just selected to the closed list and remove it from the
+          #open list.        
+          closedlist.append([NewX, NewY])
+          openlist.remove([NewX, NewY])
 
-      #Find out if the cell you put in the closed list is the target cell
-      #else, mark the current cell, so when you print "map", you can see it
-      #was analyzed (analyzed cells are marked with the number 3)
-      if NewX == targetX and NewY == targetY:
-          ShowPath()
-          break
+          #Find out if the cell you put in the closed list is the target cell
+          #else, mark the current cell, so when you print "map", you can see it
+          #was analyzed (analyzed cells are marked with the number 3)
+          if NewX == targetX and NewY == targetY:
+              return True #ShowPath()
+              break
 
-      if NewX > -1 and NewY > -1 and NewX < maxValX and NewY < maxValY:
-          map[NewY][NewX] = 3
+          if NewX > -1 and NewY > -1 and NewX < maxValX and NewY < maxValY:
+              map[NewY][NewX] = 3
 
-      curCellX = NewX
-      curCellY = NewY
+          curCellX = NewX
+          curCellY = NewY
+
+