Answered by:
A* path finding shortest distance comparison
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 = xgoalx 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
Answers

Hi,
You have probably seen it but this is a good explanation:
https://www.raywenderlich.com/4946/introductiontoapathfinding
Also see this recent post
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(xX)+Abs(yY)
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'. Edited by litdevModerator Sunday, March 13, 2016 3:40 PM
 Proposed as answer by a65001 Monday, March 14, 2016 1:43 AM
 Marked as answer by Ed Price  MSFTMicrosoft employee, Owner Saturday, March 26, 2016 6:40 AM

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.
 Edited by litdevModerator Sunday, March 13, 2016 6:58 PM
 Marked as answer by Ed Price  MSFTMicrosoft employee, Owner Saturday, March 26, 2016 6:40 AM
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(x2x1)*(x2x1)+(y2y1)*(y2y1)) , but I think you mean more than this?

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

Hi,
You have probably seen it but this is a good explanation:
https://www.raywenderlich.com/4946/introductiontoapathfinding
Also see this recent post
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(xX)+Abs(yY)
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'. Edited by litdevModerator Sunday, March 13, 2016 3:40 PM
 Proposed as answer by a65001 Monday, March 14, 2016 1:43 AM
 Marked as answer by Ed Price  MSFTMicrosoft employee, Owner Saturday, March 26, 2016 6:40 AM



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

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.
 Edited by litdevModerator Sunday, March 13, 2016 6:58 PM
 Marked as answer by Ed Price  MSFTMicrosoft employee, Owner Saturday, March 26, 2016 6:40 AM
