# 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 = 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

• Hi,

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

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
• 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

### 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
• 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:

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
• 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
• 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
• 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