none
A* path finding shortest distance comparison RRS feed

  • Question

  • i am wondering how to compare each square to the other squares and the computer chooses which is the shortest distance. but i dont know how to do that. hopefully this would make sense to some of you.

    gw = 500
    gh = 500
    GraphicsWindow.Height = gh
    GraphicsWindow.Width = gw
    goalx = 0 
    goaly = 0
    
    botx = Math.GetRandomNumber(50)*10
    boty = Math.GetRandomNumber(50)*10
    
    For x = 0 to 500 step 10
    For y = 0 To 500 Step 10
    distancex = x-goalx
    distancey = y - goaly
    distance = distancex+distancey
    
    node[x][y] = distance
    i = i + 1 
    GraphicsWindow.DrawLine(x, y, x+1, y)
    remainder = Math.Remainder(i, 10)
    
    EndFor
    endfor
    TextWindow.WriteLine("Drawing finsihed")
    GraphicsWindow.DrawRectangle(goalx, goaly, 10, 10)
    GraphicsWindow.DrawRectangle(botx, boty, 10, 10)
    space = 1
    checkspaces()
    
    For i = 1 To 4 Step 1
      openlist[i] = possiblespace[i] 'adds the spaces to open list where the robot can move
    endfor
    
    
    
    
    
    
    
    Sub checkspaces
      GraphicsWindow.PenColor="Blue" ' if blue it is checked
      left = botx -10
      If left < 0 Then
      left = botx +10
      EndIf
    possiblespace[space]["distance"] = node[left][boty]
    possiblespace[space]["x"] = left
    possiblespace[space]["y"] = boty
    TextWindow.WriteLine("distance for possiblespace left" + space + "is "+ possiblespace[space]["distance"])
    GraphicsWindow.DrawRectangle(possiblespace[space]["x"],possiblespace[space]["y"], 10, 10) 
    space = 2
    
    right = botx+10
    If right > gw Then
      right = botx -10
      EndIf
    possiblespace[space]["distance"] = node[right][boty]
    possiblespace[space]["x"] = right
    possiblespace[space]["y"] = boty
    TextWindow.WriteLine("distance for possiblespace right" + space + "is "+ possiblespace[space]["distance"])
    GraphicsWindow.DrawRectangle(possiblespace[space]["x"],possiblespace[space]["y"], 10, 10)
    space = 3
    up = boty+10
    If up > gh Then
      up = boty -10
      EndIf
    possiblespace[space]["distance"] = node[botx][up]
    possiblespace[space]["x"] = botx
    possiblespace[space]["y"] = up
    TextWindow.WriteLine("distance for possiblespace up " + space + "is "+ possiblespace[space]["distance"])
    GraphicsWindow.DrawRectangle(possiblespace[space]["x"],possiblespace[space]["y"], 10, 10)
    space = 4
    down = boty - 10
    If down < 0 Then
      down = boty +10
      EndIf
    possiblespace[space]["distance"] = node[botx][down]
    possiblespace[space]["x"] = botx
    possiblespace[space]["y"] = down
    TextWindow.WriteLine("distance for possiblespace down" + space + "is "+ possiblespace[space]["distance"])
    GraphicsWindow.DrawRectangle(possiblespace[space]["x"],possiblespace[space]["y"], 10, 10)
    endsub

     
    Saturday, March 12, 2016 9:35 PM

Answers

  • Hi,

    You have probably seen it but this is a good explanation:

    https://www.raywenderlich.com/4946/introduction-to-a-pathfinding

    Also see this recent post

    https://social.msdn.microsoft.com/Forums/en-US/85175715-5bbb-4405-b8b6-7eb2ab8724ee/path-finding-help?forum=smallbasic

    And a version of a65001's code that I modified to find the shortest path throught the maze collecting all the yellow pills, import LNN766.

    Back to A*, assume we are square (x,y) and the target is (X,Y), first calculate h:

    Perhaps the easiest would be h = Abs(x-X)+Abs(y-Y)

    Note x,y and X,Y are the integer square positions not pixel coordinates.

    g starts at 0

    then consider all neighbour valid squares (excluding any we have already passed through), their g value will be current g+1, their h will be calulated as above.  f is the g+h.  Move to the square with the lowest f and repeat.

    Also note that the A* algorithm may get stuck in 'dead ends'.
    Sunday, March 13, 2016 3:08 PM
    Moderator
  • g is a += : yes every step increases g

    h is an estimate of how far to go (not accounting for obstacles), so if we have to move away from the target because of an obstacle the A* algorithm may fail.

    So in a strainght line every step g+=1 and h-=1 so f is constant for each step.

    lnn766 uses a different algorithm, more powerful, more complex to code, but may be potentially slower.



    Sunday, March 13, 2016 6:57 PM
    Moderator

All replies

  • Can you give some more details on what you are trying to finally achieve, maybe a quick sketch.

    One answer could be the shortest distance between 2 points (x1,y1) and (x2,y2) is by Pythagoras: sqrt(x2-x1)*(x2-x1)+(y2-y1)*(y2-y1)) , but I think you mean more than this?

    Sunday, March 13, 2016 11:12 AM
    Moderator
  • Sure. i know how to get f = g+h in the a* algorithm, i was able to do it in java, but for smallbasic how can i sort the square/space to get the smallest cost/distance. I would think you will have to compare each space to each other. BUt i dont really know how i would do this. would it be a if statement nested into 2 for loops the first being what u want to compare and the second what you are comparing it to? HTH.

    Matthew

    Sunday, March 13, 2016 2:39 PM
  • Hi,

    You have probably seen it but this is a good explanation:

    https://www.raywenderlich.com/4946/introduction-to-a-pathfinding

    Also see this recent post

    https://social.msdn.microsoft.com/Forums/en-US/85175715-5bbb-4405-b8b6-7eb2ab8724ee/path-finding-help?forum=smallbasic

    And a version of a65001's code that I modified to find the shortest path throught the maze collecting all the yellow pills, import LNN766.

    Back to A*, assume we are square (x,y) and the target is (X,Y), first calculate h:

    Perhaps the easiest would be h = Abs(x-X)+Abs(y-Y)

    Note x,y and X,Y are the integer square positions not pixel coordinates.

    g starts at 0

    then consider all neighbour valid squares (excluding any we have already passed through), their g value will be current g+1, their h will be calulated as above.  f is the g+h.  Move to the square with the lowest f and repeat.

    Also note that the A* algorithm may get stuck in 'dead ends'.
    Sunday, March 13, 2016 3:08 PM
    Moderator
  • Yes, i do know that it may get stuck in a dead end and will just follow the next path.  i will go and import those programs and check the website out. Thank you.

    Matthew

    Sunday, March 13, 2016 6:28 PM
  • The only bit that isn't clearly described is how to calculate h, I thought h = Abs(x-X)+Abs(y-Y) - the combined x and y steps between squares.

    If you have questions or problems with the code then just ask.

    Sunday, March 13, 2016 6:33 PM
    Moderator
  • I believe that g is the cost of moving to the square. it adds up over time. moving to the next square is 1, then the next is cost 2 from the start. h is the distance to the goal from the chosen square. So lets say you have a line, simple line, no y, just x. the lets say from start to end is 5 moves apart. g will get bigger and h will get smaller as its getting closer to the goal and f is the total cost of the entire move.. what your thinking of is g. and g is a +=, not just an =. but you could do = if you keep checking back to the original square. hopefully that wasnt too confusing, hehe. I imported the lnn766 and i now understand how to get the smallest distance. thank you.

    Matthew

    Sunday, March 13, 2016 6:45 PM
  • g is a += : yes every step increases g

    h is an estimate of how far to go (not accounting for obstacles), so if we have to move away from the target because of an obstacle the A* algorithm may fail.

    So in a strainght line every step g+=1 and h-=1 so f is constant for each step.

    lnn766 uses a different algorithm, more powerful, more complex to code, but may be potentially slower.



    Sunday, March 13, 2016 6:57 PM
    Moderator
  • Good way of implementing the Send Turtle Thing by the way. I should probably publish the game concept sometime. 

    Also Matthew good luck on the path finding with the A* algorithim

    Sunday, March 13, 2016 8:23 PM