This is a simple maze solver program. It it based on mazes from the Micromouse competition. As the mouse does not know the maze beforehand it has to find its way by trial and error. It marks all junctions with an X and puts each one it passes on a stack. When it goes into a dead end the last few junctions are deleted from the stack and it tries another direction from the junction where it entered the deadend. This gives a reasonably fast route but I don't think it is optimal as there may be several routes from start to finish and the one it finds first may not be the fastest. Also it can get surplus loops in its final route which are easy to remove but I didn't implement this as it would have meant more work and testing.
I expanded this program in stages. I started by just drawing the maze on the screen, then got it so the user could move the mouse around using direction keys. Pascal has a turtle graphics thing which was designed to control robots with pens, so I used this. You just set the angle and forward distance. Then I got the mouse to go from junction to junction picking the next path at random. It never once managed to reach the centre of the maze with this method. What actually happened was it sort of got a way then kept getting 'dragged' back to the start like the force of gravity, actually it was the force of probabilities evening out. As you can imagine, say 20 junctions with 2 or 3 routes = 2 to the power 20. Less than a 1 in a million chance. So I then got it to cancel routes it had tried out and it worked, then added a routine to optimise the route.
Programmed using Borland Pascal with Libraries. Download FREE from the Internet. You might also want Object Orientated Pascal for more complicated Programmes. The mouse can always find it's way to the centre of the Maze, by searching and blocking dead-ends. With Random selection it never gets more than half way to the centre due to a 'Probability Well'. Also it has to know that's where it wants to go in the first place.
program mouse;
uses graph3, crt, maze;
type JUNCTION_RECORD = RECORD
x: INTEGER;
y: INTEGER;
back: INTEGER;
end; { Record }
var name: STRING;
any_maze, new_maze: MAZE_ARRAY;
choice, key: CHAR;
loop, loop2, x_pos, y_pos, x_wall, y_wall, stack, direction, null: INTEGER;
is_junction: ARRAY [1..16,1..16] OF BOOLEAN;
junction: ARRAY [0..100] OF JUNCTION_RECORD;
path: ARRAY [1..50] OF INTEGER;
procedure move (turtle_direction: INTEGER);
begin
setheading(turtle_direction*90); forwd (10);
case turtle_direction of
0: y_pos := y_pos - 1;
1: x_pos := x_pos + 1;
2: y_pos := y_pos + 1;
3: x_pos := x_pos - 1;
end; { Case }
x_wall := x_pos * 2; y_wall := y_pos * 2;
end; {move}
procedure move_and_log (turtle_direction: INTEGER);
begin
move (turtle_direction);
if is_junction [x_pos,y_pos] then
begin
junction[stack].x := x_pos; junction[stack].y := y_pos;
junction[stack].back := (turtle_direction+2) MOD 4;
stack:=stack+1;
end;
end; {move_and_log}
procedure goto_next_junction (junction_heading: INTEGER);
var opersite, heading: INTEGER;
begin
if is_junction [x_pos,y_pos] AND
NOT ((junction[stack-1].x = x_pos) AND (junction[stack-1].y = y_pos)) then
begin
opersite := (junction_heading+2) MOD 4;
move_and_log (junction_heading);
end;
while NOT is_junction [x_pos,y_pos] do
begin
if (new_maze [y_wall-1][x_wall ] <> '-') AND (opersite <> 0) then
heading:=0;
if (new_maze [y_wall ][x_wall+1] <> 'Ý') AND (opersite <> 1) then
heading:=1;
if (new_maze [y_wall+1][x_wall ] <> '-') AND (opersite <> 2) then
heading:=2;
if (new_maze [y_wall ][x_wall-1] <> 'Ý') AND (opersite <> 3) then
heading:=3;
opersite := (heading+2) MOD 4;
move_and_log (heading);
end;
end; { goto_next_junction }
function goto_and_log (junction_heading: INTEGER):INTEGER;
var opersite, heading: INTEGER;
begin
heading:=junction_heading;
opersite := (heading+2) MOD 4;
move (heading);
while NOT is_junction [x_pos,y_pos] do
begin
if (new_maze [y_wall-1][x_wall ] <> '-') AND (opersite <> 0) then
heading:=0;
if (new_maze [y_wall ][x_wall+1] <> 'Ý') AND (opersite <> 1) then
heading:=1;
if (new_maze [y_wall+1][x_wall ] <> '-') AND (opersite <> 2) then
heading:=2;
if (new_maze [y_wall ][x_wall-1] <> 'Ý') AND (opersite <> 3) then
heading:=3;
opersite := (heading+2) MOD 4;
move (heading);
end;
goto_and_log:=(heading+2) MOD 4;
end; {goto_and_log}
procedure go_back;
var exit: INTEGER;
begin
if (wall_count (x_pos, y_pos, new_maze) = 3) then
begin
if (new_maze [y_wall-1][x_wall ] <> '-') then exit:=0;
if (new_maze [y_wall ][x_wall+1] <> 'Ý') then exit:=1;
if (new_maze [y_wall+1][x_wall ] <> '-') then exit:=2;
if (new_maze [y_wall ][x_wall-1] <> 'Ý') then exit:=3;
goto_next_junction (exit);
stack:=stack-1;
end
else if is_junction[x_pos,y_pos] then
begin
stack:=stack-1;
goto_next_junction (junction[stack].back);
end;
end; {go_back}
procedure block_and_move (turtle_direction: INTEGER);
begin
case turtle_direction of
0: new_maze [y_wall-1][x_wall ] := 'B';
1: new_maze [y_wall ][x_wall+1] := 'B';
2: new_maze [y_wall+1][x_wall ] := 'B';
3: new_maze [y_wall ][x_wall-1] := 'B';
end;
move_and_log (turtle_direction);
end; {block_and_move}
begin {main}
repeat
clrscr;
writeln ('(C)hicago');
writeln ('(J)apan');
writeln ('(L)ondon');
writeln ('(Q)uit');
repeat
choice:=readkey;
choice:=upcase(choice);
if choice = 'C' then init_chicago_maze (name, any_maze);
if choice = 'J' then init_japan_maze (name, any_maze);
if choice = 'L' then init_london_maze (name, any_maze);
until (choice='C') OR (choice='J') OR (choice='L') OR (choice='Q');
if choice <> 'Q' then
begin
for loop:=1 to 50 do path[loop]:=0;
for loop:=0 to 100 do
begin
junction[loop].x:=0;
junction[loop].y:=0;
junction[loop].back:=0;
end;
stack:=1;
new_maze := any_maze;
new_maze[33][2]:='-'; { Block start }
write_text (name);
draw_maze (new_maze, GREEN);
for x_pos := 1 to 16 do
for y_pos := 1 to 16 do
if wall_count (x_pos, y_pos, new_maze) < 2 then
begin
draw ((x_pos*10)+12,(y_pos*10)+14,(x_pos*10)+20,(y_pos*10)+22,RED);
draw ((x_pos*10)+20,(y_pos*10)+14,(x_pos*10)+12,(y_pos*10)+22,RED);
is_junction [x_pos,y_pos] := TRUE;
end else
is_junction [x_pos,y_pos] := FALSE;
penup; setposition (-133, -80);
pendown; showturtle;
x_pos := 1; y_pos := 16;
x_wall := x_pos * 2; y_wall := y_pos * 2;
for loop := 1 to 20000 do
begin
randomize; direction := random(4); delay (10);
if (roadblock_count (x_pos, y_pos, new_maze) = 3) AND
is_junction [x_pos,y_pos] then
begin
if (new_maze [y_wall-1][x_wall ] = ' ') then direction:=0;
if (new_maze [y_wall ][x_wall+1] = ' ') then direction:=1;
if (new_maze [y_wall+1][x_wall ] = ' ') then direction:=2;
if (new_maze [y_wall ][x_wall-1] = ' ') then direction:=3;
block_and_move (direction);
end
else
begin
if (direction = 0) AND (new_maze [y_wall-1][x_wall] = ' ') then
block_and_move (0);
if (direction = 1) AND (new_maze [y_wall][x_wall+1] = ' ') then
block_and_move (1);
if (direction = 2) AND (new_maze [y_wall+1][x_wall] = ' ') then
block_and_move (2);
if (direction = 3) AND (new_maze [y_wall][x_wall-1] = ' ') then
block_and_move (3);
end;
{ Check if centre reached }
if ((x_pos = 8) AND (y_pos = 8)) OR ((x_pos = 8) AND (y_pos = 9))
OR ((x_pos = 9) AND (y_pos = 8)) OR ((x_pos = 9) AND (y_pos = 9)) then
begin
key := readkey;
loop:=20000;
end
else if (roadblock_count (x_pos, y_pos, new_maze) = 4) then go_back;
end;
penup;
setheading(270); forwd(63);
pendown;
x_pos:=junction[stack-1].x; y_pos:=junction[stack-1].y;
x_wall:=x_pos*2; y_wall:=y_pos*2;
loop2:=1;
stack:=stack-1;
for loop:=stack downto 2 do
begin
if NOT ((junction[loop].y = junction[loop-1].y) AND
(junction[loop].x = junction[loop-1].x)) then
begin
path[loop2]:=goto_and_log(junction[loop].back);
loop2:=loop2+1;
end;
end;
write_text (name);
draw_maze (new_maze, GREEN);
penup;
setheading(270); forwd(133);
setheading(180); forwd(80);
pendown;
x_pos := 1; y_pos := 16;
x_wall:=x_pos*2; y_wall:=y_pos*2;
for loop:=loop2 downto 1 do
null:=goto_and_log(path[loop]);
key:=readkey;
end; {if}
until choice = 'Q';
clrscr;
textmode(BW80);
end. { mouse }