Strangely I've never written a pathfinding routine!
But I'll give it a go anyway
Here's a simple map I drew to help visualise things...
We have a green start, red finish, white roads and black walls. We need to get our monster from green to red passing over only white squares. This map is stored in an array...
Dim map(16,16)
wall=1:road=2: `labels
map(1,1)= road
map...
We will also need to make a second array with the same dimensions to act as our monsters "brain", after all he needs to know where he's been...
Junctions are where the decisions are made, everywhere else we just have to remember which direction we're moving in.
The simplest way we can do this is to mark (in the monster brain) which squares we've traversed, when we come to a junction we take one of the routes and if that fails we come back to the junction and try a different route. If we increment the "footfall" value of a square each time we visit it then we can make a path by selecting the lowest value adjoining square, that way if even all routes from a junction fail we can retrace our steps all the way back down the road before the junction to find the next available route.
Ok, lets test this formula out with our maze.
We start on the green square and add one to its footfall value, we then look at the adjoining squares and see only one road so we take it. There's only one route up the winding path to the first T-junction, when we reach it we have to make a decision to go north or south, for arguments sake lets try going south first.
We follow to road round and up to the dead-end, since we're at a dead-end we mark the square again - as if the monster is stamping his feet in frustration
- we do this to make sure the algorithm doesn't decide to come back here. Now the lowest possible square is to the right, we take it and now because our dead-end is a 2 the path back to the junction is the lesser (being 1).
We eventually get back to the junction. Now we have a 1 to the west a 2 to the south and a 0 to the north, so we go north. If you repeat the process you'll see we eventually get to the finish.
[edit]
Extra Lesson: Recursive Functions
Path finding is the perfect situation to use a recursive function - if you haven't learned functions yet I'd steer clear as it can get a bit complicated and confusing.
A recursive function is one that calls itself; this seems a strange idea at first, surely this would be an endless loop of function calls? But no, we have a condition inside the function that determines whether the function recurs or not. But if the function is calling itself how can the outcome of the condition change? That's where the clever part comes in. On the second call we send different parameters to the function, and so we alter the outcome of conditions within the function. The simplest of examples produces a FOR-loop type effect...
fill_circle(320,240,32)
wait key
end
Function fill_circle(x,y,r)
if r>0
fill_circle(x,y,r-1)
endif
circle x,y,r
Endfunction
Hope it works, no testing!
The novel thing here is that the circles are only draw once the radius reaches 0 and can't get any smaller. When the function ends it can't just go back to the main program, it has to re-trace it's steps back through the previous calls of the function drawing the larger and larger circles it left behind as it goes.
Here's a program I made a while ago that uses recursion.
You can do some pretty cool things with recursion.
`*** The Towers of Hanoi Problem ***
`I will use a binary system to store rings on poles (1=small ring, 2=medium, 4=large)
DIM Pole(3)
source = 1 : `set start pole
`setup
hide mouse
sync on
DO
`set up new puzzle
repeat : destination= rnd(2)+1 : until destination <> source : `get end pole
repeat : temporary_store= rnd(2)+1 : until temporary_store <> source and temporary_store <> destination
Pole(source) = 7 : Pole(destination) = 0 : Pole(temporary_store) = 0 : `initiate poles
display() : `display the initial puzzle
print "New destination: " ; destination : sync : wait 1000 : `begin puzzle message
source = Transfer(3, source, destination, temporary_store) : `complete the puzzle and return new source
LOOP
`Transfer
FUNCTION Transfer(N, source, destination, temporary_store)
`Problem Fix Variables
S = source
D = destination
T = temporary_store
If N = 1
Move(S, D)
Else
Transfer(N-1, S, T, D)
Move(S, D)
Transfer(N-1, T, D, S)
Endif
ENDFUNCTION destination
`Move
FUNCTION Move(source, destination)
`which ring is to be moved?
Select Pole(source)
Case 1 : ring = 1 : Endcase
Case 2 : ring = 2 : Endcase
Case 3 : ring = 1 : Endcase
Case 4 : ring = 4 : Endcase
Case 5 : ring = 1 : Endcase
Case 6 : ring = 2 : Endcase
Case 7 : ring = 1 : Endcase
Endselect
`Take ring from source and add to destination
Pole(source) = Pole(source) - ring
Pole(destination) = Pole(destination) + ring
`Update display
Display()
ENDFUNCTION
`Display
FUNCTION Display()
cls
For x = 1 to 3
`draw poles
ink rgb(120,40,0),0
Line 100+(100*x), 100, 100+(100*x), 200
`disintegrate pole variables
ink rgb(255,200,0),0
pole = Pole(x) : `store current pole rings value
rings = 0
`big ring?
if pole - 4 >=0
inc rings
box 100+(100*x)-40, 183-((rings-1)*20), 100+(100*x)+40, 200-((rings-1)*20)
pole = pole - 4
endif
`medium ring?
if pole - 2 >=0
inc rings
box 100+(100*x)-30, 183-((rings-1)*20), 100+(100*x)+30, 200-((rings-1)*20)
pole = pole - 2
endif
`small ring?
if pole - 1 >=0
inc rings
box 100+(100*x)-20, 183-((rings-1)*20), 100+(100*x)+20, 200-((rings-1)*20)
pole = pole - 1
endif
Next x
sync
wait 1000
ENDFUNCTION
Goke of the day: [Q]What's a coders' favourite part of an orchestra?
[A]The strings.
