B+ Pathfinder

[bplus]

This uses no awareness of where B is until it hits it! Therefore you could find all the B's you want on a map, not just one.

And yet, can you find a path that takes less squares?

Sure this thing zigs when no zig or zag is needed but the square counts are the same.

 

Code: QB64: [Select]

1. _TITLE "PathFinder 1a, press spacebar to continue whenever it stops, press esc to quit"
2. 'QB64 X 64 version 1.2 20180228/86  from git b301f92
3. 'started 2018-08-11 when Colbalt asked about A* pathfinder
4. ' He has now 2018-08-12 posted a QB64 version that is nice!
5.  
6. ' 2018-08-11 started PathFinder 1
7. ' 2018-08-12 almost working but buggy backtract to point A after point B is found.
8. ' 2018-08-13 PathFinder 1a.bas I think I have a fix for buggy path BackTrack but major surgery so this new version
9. ' 8:38 PM 28 times in a row it worked, now diddle the size of array and loose the board text view
10. ' 9:09 PM I have run 2 dozen tests more at least and zero bugs! on smaller and more squares.
11. ' 9:25 PM Still no failures! Ready to show the world.
12.  
13.  
14. DEFINT A-Z
15. CONST ww = 800
16. CONST wh = 600
17. CONST sq = 10
18. CONST maxx = 80
19. CONST maxy = 60
20.  
21. SCREEN _NEWIMAGE(ww, wh, 32)
22. _SCREENMOVE (1280 - ww) / 2 + 30, (760 - wh) / 2
23. RANDOMIZE TIMER
24.  
25. TYPE xytype
26.     x AS INTEGER
27.     y AS INTEGER
28. END TYPE
29. DIM SHARED ax, ay, bx, by
30. DIM SHARED board(1 TO maxx, 1 TO maxy) AS STRING * 6
31. DO
32.     FOR y = 1 TO maxy
33.         FOR x = 1 TO maxx
34.             board(x, y) = " "
35.         NEXT
36.     NEXT
37.     'with these obstacles there is no guarantee a path will exist
38.     FOR i = 1 TO maxx * maxy * .8
39.         ox = rand(1, maxx): oy = rand(1, maxy)
40.         WHILE (ox = ax AND oy = ay) OR (ox = bx AND ox = by)
41.             ox = rand(1, maxx): oy = rand(1, maxy)
42.         WEND
43.         board(ox, oy) = "O"
44.     NEXT
45.     ax = rand(1, maxx): ay = rand(1, maxy)
46.     bx = rand(1, maxx): by = rand(1, maxy)
47.     WHILE ax = bx AND ay = by
48.         bx = rand(1, maxx): by = rand(1, maxy)
49.     WEND
50.     board(ax, ay) = "A"
51.     board(bx, by) = "B"
52.     displayB
53.     WHILE NOT _KEYDOWN(32): _LIMIT 100: WEND
54.     WHILE _KEYDOWN(32): _LIMIT 100: WEND
55.     parentF = 1: tick = 0: parentx = 0
56.     WHILE parentF = 1 AND parentx = 0
57.         parentF = 0: tick = tick + 1: changes$ = ""
58.         'IF tick > maxx * maxy THEN EXIT WHILE   'this was crude infinite loop stopper
59.         ystart = max(ay - tick, 1): ystop = min(ay + tick, maxy)
60.         FOR y = ystart TO ystop
61.             xstart = max(ax - tick, 1): xstop = min(ax + tick, maxx)
62.             'PRINT ystart, ystop, xstart, xstop
63.             'END
64.             FOR x = xstart TO xstop
65.                 'check out the neighbors
66.                 IF x - 1 >= 1 THEN xxstart = x - 1 ELSE xxstart = x
67.                 IF x + 1 <= maxx THEN xxstop = x + 1 ELSE xxstop = x
68.                 IF y - 1 >= 1 THEN yystart = y - 1 ELSE yystart = y
69.                 IF y + 1 <= maxy THEN yystop = y + 1 ELSE yystop = y
70.                 IF RTRIM$(board(x, y)) = "" THEN
71.                     cf = 0
72.                     FOR yy = yystart TO yystop
73.                         FOR xx = xxstart TO xxstop
74.                             IF xx <> x OR yy <> y THEN
75.                                 IF RTRIM$(board(xx, yy)) = "A" OR INSTR(RTRIM$(board(xx, yy)), ",") > 0 THEN 'found a parent to assign to cell
76.  
77.                                     '          This had ne stuck for awhile!
78.                                     'LOGIC BUG   board(x, y) = LTRIM$(STR$(xx)) + "," + LTRIM$(STR$(yy))
79.                                     'can't change board until all are checked!!!!   so save up changes
80.                                     changes$ = changes$ + LTRIM$(STR$(x)) + "," + LTRIM$(STR$(y)) + "{" + LTRIM$(STR$(xx)) + "," + LTRIM$(STR$(yy)) + "}"
81.                                     rec (x - 1) * sq + 3, (y - 1) * sq + 3, x * sq - 3, y * sq - 3, 555
82.                                     parentF = 1 'so will continue looping
83.                                     cf = 1: EXIT FOR
84.                                 END IF
85.                             END IF
86.                         NEXT
87.                         IF cf THEN EXIT FOR
88.                     NEXT
89.                 ELSEIF RTRIM$(board(x, y)) = "A" OR INSTR(board(x, y), ",") > 0 THEN 'see if B is a neighbor
90.                     FOR yy = yystart TO yystop
91.                         FOR xx = xxstart TO xxstop
92.                             IF xx <> x OR yy <> y THEN
93.                                 IF RTRIM$(board(xx, yy)) = "B" THEN 'B conects to x, y
94.                                     parentx = x: parenty = y 'from this we should be able to backtrack to A
95.                                     GOTO jump1
96.                                 END IF
97.                             END IF
98.                         NEXT
99.                     NEXT
100.                 END IF
101.             NEXT
102.         NEXT
103.         jump1:
104.         'update board with cells assigned parents
105.         WHILE changes$ <> ""
106.             new$ = leftOf$(changes$, "}")
107.             changes$ = rightOf$(changes$, "}")
108.             newxy$ = leftOf$(new$, "{")
109.             newParent$ = rightOf$(new$, "{")
110.             u = VAL(leftOf$(newxy$, ",")): v = VAL(rightOf$(newxy$, ","))
111.             board(u, v) = leftOf$(newParent$, ",") + "," + rightOf$(newParent$, ",")
112.         WEND
113.  
114.         '_DISPLAY
115.         _LIMIT 10
116.     WEND
117.     'displayB
118.     'either parentF = 0, no parents found for all the cells in tick or parentbx was found and we have a path to backtrack to A
119.     BackTrack$ = ""
120.     IF parentx THEN 'backtrack to A   note: B could be right next to A!!!
121.         'IF parentx <> ax AND parenty <> ay THEN
122.         frec (parentx - 1) * sq + 3, (parenty - 1) * sq + 3, sq - 6, sq - 6, 990
123.         'END IF
124.  
125.         'this had me stuck for the longest time! parentx was the fix! (along with removal of blunders)
126.         WHILE parentx 'trace the path back
127.             ps$ = board(parentx, parenty)
128.             parentx = VAL(leftOf$(ps$, ","))
129.             parenty = VAL(rightOf$(ps$, ","))
130.  
131.             'IF parentx <> ax AND parenty <> ay THEN
132.             frec (parentx - 1) * sq + 3, (parenty - 1) * sq + 3, sq - 6, sq - 6, 990
133.             'END IF
134.             'IF parentx <> ax AND parenty <> ay THEN EXIT WHILE
135.             '_DISPLAY
136.             _LIMIT 10
137.         WEND
138.         WHILE NOT _KEYDOWN(32)
139.             IF _KEYDOWN(27) THEN END
140.             _LIMIT 100
141.         WEND
142.         WHILE _KEYDOWN(32): _LIMIT 100: WEND
143.     ELSE
144.         rgb 999
145.         LOCATE 15, 10: PRINT "Did not connect to B"
146.         _DELAY 3
147.     END IF
148.  
149.     'for this to be of any use, I need to format the print to exact same size, well thats easy
150.     '
151.     '                      this is why board is string * 6 type
152.     '                          maxx = 16 maxy = 12  or less
153.     'rgb 999
154.     'CLS
155.     'FOR y = 1 TO maxy
156.     '    FOR x = 1 TO maxx
157.     '        PRINT board(x, y);
158.     '    NEXT
159.     '    PRINT: PRINT
160.     'NEXT
161.     'WHILE NOT _KEYDOWN(32)
162.     '    IF _KEYDOWN(27) THEN END
163.     '    _LIMIT 100
164.     'WEND
165.     'WHILE _KEYDOWN(32): _LIMIT 100: WEND
166. LOOP UNTIL _KEYDOWN(27)
167. SUB displayB
168.     FOR y = 1 TO maxy
169.         FOR x = 1 TO maxx
170.             SELECT CASE RTRIM$(board(x, y))
171.                 CASE IS = "": k = 0
172.                 CASE IS = "A": k = 9
173.                 CASE IS = "B": k = 999
174.                 CASE IS = "O": k = 50
175.                     'CASE ELSE: k = 30
176.             END SELECT
177.             frec (x - 1) * sq, (y - 1) * sq, sq, sq, k
178.         NEXT
179.     NEXT
180. END SUB
181. SUB rec (x1, y1, x2, y2, rgbN)
182.     rgb rgbN
183.     LINE (x1, y1)-(x2, y2), , B
184. END SUB
185. SUB frec (x1, y1, w, h, rgbN)
186.     rgb rgbN
187.     LINE (x1, y1)-STEP(w, h), , BF
188. END SUB
189. SUB rgb (n) ' New (even less typing!) New Color System 1000 colors with up to 3 digits
190.     s3$ = RIGHT$("000" + LTRIM$(STR$(n)), 3)
191.     r = VAL(MID$(s3$, 1, 1)): IF r THEN r = 28 * r + 3
192.     g = VAL(MID$(s3$, 2, 1)): IF g THEN g = 28 * g + 3
193.     b = VAL(MID$(s3$, 3, 1)): IF b THEN b = 28 * b + 3
194.     COLOR _RGB32(r, g, b)
195. END SUB
196. FUNCTION rand% (lo%, hi%)
197.     rand% = INT(RND * (hi% - lo% + 1)) + lo%
198. END FUNCTION
199. FUNCTION min (n1, n2)
200.     IF n1 > n2 THEN min = n2 ELSE min = n1
201. END FUNCTION
202. FUNCTION max (n1, n2)
203.     IF n1 < n2 THEN max = n2 ELSE max = n1
204. END FUNCTION
205. FUNCTION leftOf$ (source$, of$)
206.     posOf = INSTR(source$, of$)
207.     IF posOf > 0 THEN leftOf$ = MID$(source$, 1, posOf - 1)
208. END FUNCTION
209. FUNCTION rightOf$ (source$, of$)
210.     posOf = INSTR(source$, of$)
211.     IF posOf > 0 THEN rightOf$ = MID$(source$, posOf + LEN(of$))
212. END FUNCTION
213.  

[FellippeHeitor]

Very much amusing to watch, Mark.

[bplus]

Must be the zig zags! :)

[bplus]

I have noticed, when it does not find connection to B, I want more time to see for myself:

Mod for that (fits just before the end of the main loop):

Code: QB64: [Select]

1.     ELSE
2.         rgb 999
3.         LOCATE 15, 10: PRINT "Did not connect to B"
4.         WHILE NOT _KEYDOWN(32)
5.             IF _KEYDOWN(27) THEN END
6.             _LIMIT 100
7.         WEND
8.         WHILE _KEYDOWN(32): _LIMIT 100: WEND  '<<< BTW using spacebar several times in a row to restart the code, needs to be cleared from buffer
9.  
10.     END IF
11.  

The trick to this backtracking idea was learned from coding many versions of the Snake Game.

[johnno56]

Completely off topic.... I like your colour scheme... Care to share the settings?

J

[FellippeHeitor]

I believe that's preset scheme Camouflage, though I could be wrong.

[johnno56]

Yep. Looks like Camouflage to me too... Thanks for that...

J

[bplus]

Confirmed, Camouflage, I think I remember someone recommending it, Fellippe?

Holy Son of the Universal Machine! This Pathfinder technique can be generalized to every point on the map with the same one time calculation from a given point A!

stay tuned...

[Ashish]

Nice work bplus!
This can be useful for me.

[bplus]

Hi Ashish,

Actually, I could use some examples of maps to work out more practical uses.

[bplus]

B+ Pathfinder 2, shows that once the map has been setup, you can find a path from any part of the map. To me, this is more powerful than what an A star Pathfinder can do.

Code: QB64: [Select]

1. _TITLE "PathFinder 2, prepping maze as you read this."
2. 'QB64 X 64 version 1.2 20180228/86  from git b301f92
3. 'started 2018-08-11 when Colbalt asked about A* pathfinder
4. ' He has now 2018-08-12 posted a QB64 version that is nice!
5.  
6. ' 2018-08-11 started PathFinder 1
7. ' 2018-08-12 almost working but buggy backtract to point A after point B is found.
8. ' 2018-08-13 PathFinder 1a.bas I think I have a fix for buggy path BackTrack but major surgery so this new version
9. ' 2018-08-14 Pathfinder 2:  2 parts
10. ' Part 1: creates a map, a random Home point and backtracts all the points available to move over.
11. ' Part 2: allows clicking variaous points of map to see if path is found.
12.  
13. DEFINT A-Z
14. CONST ww = 800
15. CONST wh = 600
16. CONST sq = 10
17. CONST mapw = 80
18. CONST maph = 60
19.  
20. SCREEN _NEWIMAGE(ww, wh, 32)
21. _SCREENMOVE (1280 - ww) / 2 + 30, (760 - wh) / 2
22. RANDOMIZE TIMER
23.  
24. DIM SHARED ax, ay, bx, by
25. DIM SHARED board(1 TO mapw, 1 TO maph) AS STRING * 6
26. DO
27.  
28.     'this part sets up a sample map and get's the Backtracking build into map
29.  
30.     FOR y = 1 TO maph
31.         FOR x = 1 TO mapw
32.             board(x, y) = " "
33.         NEXT
34.     NEXT
35.     'with these obstacles there is no guarantee a path will exist
36.     FOR i = 1 TO mapw * maph * .7
37.         ox = rand(1, mapw): oy = rand(1, maph)
38.         board(ox, oy) = "O"
39.     NEXT
40.     ax = rand(1, mapw): ay = rand(1, maph)
41.     board(ax, ay) = "A"
42.     parentF = 1: tick = 0: parentx = 0
43.     WHILE parentF = 1 AND parentx = 0
44.         parentF = 0: tick = tick + 1: changes$ = ""
45.         ystart = max(ay - tick, 1): ystop = min(ay + tick, maph)
46.         FOR y = ystart TO ystop
47.             xstart = max(ax - tick, 1): xstop = min(ax + tick, mapw)
48.             FOR x = xstart TO xstop
49.                 'check out the neighbors
50.                 IF x - 1 >= 1 THEN xxstart = x - 1 ELSE xxstart = x
51.                 IF x + 1 <= mapw THEN xxstop = x + 1 ELSE xxstop = x
52.                 IF y - 1 >= 1 THEN yystart = y - 1 ELSE yystart = y
53.                 IF y + 1 <= maph THEN yystop = y + 1 ELSE yystop = y
54.                 IF RTRIM$(board(x, y)) = "" THEN
55.                     cf = 0
56.                     FOR yy = yystart TO yystop
57.                         FOR xx = xxstart TO xxstop
58.                             IF xx <> x OR yy <> y THEN
59.                                 IF RTRIM$(board(xx, yy)) = "A" OR INSTR(RTRIM$(board(xx, yy)), ",") > 0 THEN 'found a parent to assign to cell
60.                                     changes$ = changes$ + LTRIM$(STR$(x)) + "," + LTRIM$(STR$(y)) + "{" + LTRIM$(STR$(xx)) + "," + LTRIM$(STR$(yy)) + "}"
61.                                     parentF = 1 'so will continue looping
62.                                     cf = 1: EXIT FOR
63.                                 END IF
64.                             END IF
65.                         NEXT
66.                         IF cf THEN EXIT FOR
67.                     NEXT
68.                 END IF
69.             NEXT
70.         NEXT
71.         'update board with cells assigned parents
72.         WHILE changes$ <> ""
73.             new$ = leftOf$(changes$, "}")
74.             changes$ = rightOf$(changes$, "}")
75.             newxy$ = leftOf$(new$, "{")
76.             newParent$ = rightOf$(new$, "{")
77.             u = VAL(leftOf$(newxy$, ",")): v = VAL(rightOf$(newxy$, ","))
78.             board(u, v) = leftOf$(newParent$, ",") + "," + rightOf$(newParent$, ",")
79.         WEND
80.         _LIMIT 300
81.     WEND
82.  
83.  
84.     'this parts displays the ability to find a path to blue square anywhere in the maze
85.  
86.     _TITLE "Click maze to find a path to blue square (if any), c = clear, n = new map, esc = quit"
87.     displayB
88.     DO
89.         'CLS
90.         'displayB
91.         WHILE _MOUSEINPUT: WEND
92.         IF _MOUSEBUTTON(1) THEN
93.             mx = _MOUSEX - .5 * sq: my = _MOUSEY - .5 * sq
94.             bx = mx / sq + 1: by = my / sq + 1
95.             IF bx >= 1 AND bx <= mapw AND by >= 1 AND by <= maph THEN
96.                 frec (bx - 1) * sq + 2, (by - 1) * sq + 2, sq - 4, sq - 4, 990
97.                 ps$ = board(bx, by)
98.                 parentx = VAL(leftOf$(ps$, ","))
99.                 parenty = VAL(rightOf$(ps$, ","))
100.                 IF parentx THEN 'backtrack to A   note: B could be right next to A!!!
101.                     frec (parentx - 1) * sq + 3, (parenty - 1) * sq + 3, sq - 6, sq - 6, 999
102.                     WHILE parentx 'trace the path back
103.                         ps$ = board(parentx, parenty)
104.                         parentx = VAL(leftOf$(ps$, ","))
105.                         parenty = VAL(rightOf$(ps$, ","))
106.                         frec (parentx - 1) * sq + 3, (parenty - 1) * sq + 3, sq - 6, sq - 6, 999
107.                         _LIMIT 10
108.                         _DISPLAY
109.                     WEND
110.                 ELSE
111.                     rgb 999
112.                     LOCATE 15, 10: PRINT "Did not connect to B"
113.                     _DISPLAY
114.                     _DELAY 3
115.                     displayB
116.                 END IF
117.             END IF
118.         END IF
119.         IF _KEYDOWN(27) THEN END
120.         IF _KEYDOWN(ASC("n")) THEN EXIT DO
121.         IF _KEYDOWN(ASC("c")) THEN displayB
122.         _DISPLAY
123.         _LIMIT 100
124.     LOOP
125. LOOP UNTIL _KEYDOWN(27)
126.  
127. SUB displayB
128.     FOR y = 1 TO maph
129.         FOR x = 1 TO mapw
130.             SELECT CASE RTRIM$(board(x, y))
131.                 CASE "A": k = 9
132.                 CASE "B": k = 905
133.                 CASE "O": k = 50
134.                 CASE ELSE: k = 0
135.             END SELECT
136.             frec (x - 1) * sq, (y - 1) * sq, sq, sq, k
137.         NEXT
138.     NEXT
139. END SUB
140. SUB rec (x1, y1, x2, y2, rgbN)
141.     rgb rgbN
142.     LINE (x1, y1)-(x2, y2), , B
143. END SUB
144. SUB frec (x1, y1, w, h, rgbN)
145.     rgb rgbN
146.     LINE (x1, y1)-STEP(w, h), , BF
147. END SUB
148. SUB rgb (n) ' New (even less typing!) New Color System 1000 colors with up to 3 digits
149.     s3$ = RIGHT$("000" + LTRIM$(STR$(n)), 3)
150.     r = VAL(MID$(s3$, 1, 1)): IF r THEN r = 28 * r + 3
151.     g = VAL(MID$(s3$, 2, 1)): IF g THEN g = 28 * g + 3
152.     b = VAL(MID$(s3$, 3, 1)): IF b THEN b = 28 * b + 3
153.     COLOR _RGB32(r, g, b)
154. END SUB
155. FUNCTION rand% (lo%, hi%)
156.     rand% = INT(RND * (hi% - lo% + 1)) + lo%
157. END FUNCTION
158. FUNCTION min (n1, n2)
159.     IF n1 > n2 THEN min = n2 ELSE min = n1
160. END FUNCTION
161. FUNCTION max (n1, n2)
162.     IF n1 < n2 THEN max = n2 ELSE max = n1
163. END FUNCTION
164. FUNCTION leftOf$ (source$, of$)
165.     posOf = INSTR(source$, of$)
166.     IF posOf > 0 THEN leftOf$ = MID$(source$, 1, posOf - 1)
167. END FUNCTION
168. FUNCTION rightOf$ (source$, of$)
169.     posOf = INSTR(source$, of$)
170.     IF posOf > 0 THEN rightOf$ = MID$(source$, posOf + LEN(of$))
171. END FUNCTION
172.  

 

 
Blue square is Point A the start point. Yellow squares are different destinations from A.

[johnno56]

... Riddle me this one, Batman...

J

[bplus]

There you have clicked the hedge, the black is the free space on which paths are stepped through.

Also I was not satisfied when I clicked a spot that it was clicking the right square, so I adjusted the mouseX, mouseY by .5*sq = half the square size. For me it was better, for your pointer maybe worse,

Here is the line to diddle:
mx = _MOUSEX - .5 * sq: my = _MOUSEY - .5 * sq

maybe just leave it to mouse x, y no adjustments? Maybe adjust a whole square?

But you should be definitely attempting to click a black square. And some places will not connect to A the blue rectangle because the hedge completely surrounds the spot clicked.

[bplus]

Now the next logical step is to write a function that returns the actual path to take from A to B, step by step.

I am inclined to make this function a string. Can functions return arrays?

I think I have always used a sub for array building.

Better would be to have real map problems to work on now that I have proof of concept.

[SMcNeill]

Now the next logical step is to write a function that returns the actual path to take from A to B, step by step.

I am inclined to make this function a string. Can functions return arrays?

I think I have always used a sub for array building.

Better would be to have real map problems to work on now that I have proof of concept.

I tend to do something like this with an array of steps needed to move from point A to point B.

Code: QB64: [Select]

1. CONST StepByStep = -1 '-1 for TRUE, 0 for FALSE
2.  
3.  
4.  
5. SCREEN _NEWIMAGE(800, 600, 32)
6. _SCREENMOVE _MIDDLE
7. DIM SHARED Map(0 TO 26, 0 TO 26) AS INTEGER
8. RANDOMIZE TIMER
9.  
10. TYPE Coordinate
11.     x AS INTEGER
12.     y AS INTEGER
13. END TYPE
14.  
15. DIM SHARED HeroPosition AS Coordinate
16. DIM SHARED TargetPosition AS Coordinate
17.  
18. f = _LOADFONT(".\cyberbit.ttf", 8, "monospace")
19.  
20. DO
21.     'Clear Variables for a second run
22.     _FONT 16
23.     FOR x = 0 TO 26
24.         FOR y = 0 TO 26
25.             Map(x, y) = -1
26.     NEXT y, x
27.     HeroPosition.x = 0
28.     HeroPosition.y = 0
29.     TargetPosition.x = 0
30.     TargetPosition.y = 0
31.  
32.     FOR i = 0 TO 26 'Create Border
33.         Map(i, 0) = -2: Map(i, 26) = -2 'Filled
34.         Map(0, i) = -2: Map(26, i) = -2 'Filled
35.     NEXT
36.  
37.     FOR i = 1 TO 200 'Create Obsticals
38.         x = INT(RND * 26) + 1
39.         y = INT(RND * 26) + 1
40.         Map(x, y) = -2 'Filled
41.     NEXT
42.  
43.     'Place Hero
44.  
45.  
46.     DrawMap
47.     LOCATE 20, 70: PRINT "Use Mouse to place Hero"
48.     DO
49.         _LIMIT 30
50.         WHILE _MOUSEINPUT: WEND
51.         XPos = (_MOUSEX - 20) \ 20
52.         YPos = (_MOUSEY - 20) \ 20
53.         IF XPos > 0 AND XPos < 26 AND YPos > 0 AND YPos < 26 THEN
54.             IF _MOUSEBUTTON(1) AND (Map(XPos, YPos) <> -2) THEN
55.                 HeroPosition.x = XPos
56.                 HeroPosition.y = YPos
57.                 EXIT DO
58.             ELSEIF _MOUSEBUTTON(2) THEN GOTO redo
59.             END IF
60.         END IF
61.     LOOP
62.     DrawMap
63.  
64.     LOCATE 20, 70: PRINT "Use Mouse to place Target"
65.     DO
66.         _LIMIT 30
67.         WHILE _MOUSEINPUT: WEND
68.         XPos = (_MOUSEX - 20) \ 20
69.         YPos = (_MOUSEY - 20) \ 20
70.         IF XPos > 0 AND XPos < 26 AND YPos > 0 AND YPos < 26 THEN
71.             IF _MOUSEBUTTON(1) AND (Map(XPos, YPos) <> -2) AND XPos <> HeroPosition.x AND YPos <> HeroPosition.y THEN
72.                 TargetPosition.x = XPos
73.                 TargetPosition.y = YPos
74.                 EXIT DO
75.             END IF
76.         END IF
77.     LOOP
78.     _FONT f
79.  
80.     CalculateTravel
81.     DrawMap
82.  
83.     DO
84.         _LIMIT 30
85.         i$ = INKEY$
86.         IF i$ = CHR$(27) THEN SYSTEM
87.     LOOP UNTIL i$ <> ""
88.  
89.  
90.     redo:
91. LOOP
92.  
93.  
94.  
95.  
96.  
97.  
98. SUB DrawMap
99.     CLS
100.     IF HeroPosition.x <> 0 AND HeroPosition.y <> 0 THEN LINE (20 * HeroPosition.x + 20, 20 * HeroPosition.y + 20)-STEP(20, 20), &HFFFF0000, BF
101.     IF TargetPosition.x <> 0 AND TargetPosition.y <> 0 THEN LINE (20 * TargetPosition.x + 20, 20 * TargetPosition.y + 20)-STEP(20, 20), &HFFFFFF00, BF
102.     FOR x = 0 TO 26
103.         FOR y = 0 TO 26
104.             IF Map(x, y) = -2 THEN
105.                 LINE (20 * x + 20, 20 * y + 20)-STEP(20, 20), -1, BF
106.             ELSE
107.                 LINE (20 * x + 20, 20 * y + 20)-STEP(20, 20), -1, B
108.                 IF Map(x, y) > 0 THEN _PRINTSTRING (20 * x + 21, 20 * y + 21), _TRIM$(STR$(Map(x, y)))
109.             END IF
110.     NEXT y, x
111. END SUB
112.  
113. SUB CalculateTravel
114.     'Start at  TargetDestination
115.     Map(TargetPosition.x, TargetPosition.y) = 0
116.     FOR i = 0 TO 26
117.         mapchanged = 0
118.         FOR x = 1 TO 25
119.             FOR y = 1 TO 25
120.                 IF Map(x, y) = i THEN
121.                     IF Map(x - 1, y - 1) = -1 THEN Map(x - 1, y - 1) = i + 1: mapchanged = -1
122.                     IF Map(x, y - 1) = -1 THEN Map(x, y - 1) = i + 1: mapchanged = -1
123.                     IF Map(x + 1, y - 1) = -1 THEN Map(x + 1, y - 1) = i + 1: mapchanged = -1
124.                     IF Map(x - 1, y) = -1 THEN Map(x - 1, y) = i + 1: mapchanged = -1
125.                     IF Map(x + 1, y) = -1 THEN Map(x + 1, y) = i + 1: mapchanged = -1
126.                     IF Map(x - 1, y + 1) = -1 THEN Map(x - 1, y + 1) = i + 1: mapchanged = -1
127.                     IF Map(x, y + 1) = -1 THEN Map(x, y + 1) = i + 1: mapchanged = -1
128.                     IF Map(x + 1, y + 1) = -1 THEN Map(x + 1, y + 1) = i + 1: mapchanged = -1
129.                 END IF
130.                 IF Map(HeroPosition.x, HeroPosition.y) <> -1 THEN EXIT SUB
131.             NEXT
132.         NEXT
133.         IF StepByStep THEN
134.             DrawMap
135.             _DELAY 1 'A second delay so the user can watch us find the path
136.         END IF
137.         IF mapchanged = 0 THEN EXIT SUB
138.     NEXT
139. END SUB
140.  

Place Hero with mouse, then target with mouse, then watch as it tries to build you a path from one point to the other.  Hit ESC after that to quit, or any other key to go again on a second map.

Not only does this give you a path to the "hero", but it also tells you how many steps would be required to reach ANY point available on the map.

EDIT:  Minor modification where I changed total map size just so it could display fully on machines running a smaller resolution than mine is.

Also note:  To get back from the Target to the Hero (as if the target was a monster chasing the hero), simply count down from the largest number at the hero to the adjacent square with the next smaller number.    To path find from the hero to the target, we'd just swap their search order and then trace back from highest square to lowest, same as before.  (Basically, just swap the values for the two targets...)