I am a beginning programmer, and very new to artificial intelligence. I have stumbled on a problem I cannot seem to solve in a C++ book I bought (Dietel & Dietel How to Program C++, Third edition). It involves writing a maze-solving and maze-writing algorithm, where the array is a 12 by 12 char array with #''s being the walls of the maze and .''s being the walkable paths. After a dozen or so unsuccessful attempts, I turn to the GameDev.net forum posters for assistance. For solving it, it recommends the "Right-Hand Rule," where you keep your right hand on the wall and follow it to the exit. Not the fastest or most effecient route, but it''ll get you there. Any advice or (preferably) code samples would be VASTLY appreciated. No rush, as this is not an assignment of any sort, I''m just quite interested in seeing how it is accomplished. Thanks in advance! Krunk

The right hand rule goes along the lines of ''if there is a wall to your right move forward. If there is no wall turn right until there is''

You will need you position {x,y} and the direction (vector) you are travelling. your vector will be FORWARD{1,0}, DOWN{0,-1}, RIGHT(-1,0} or UP(0,1}.

so if you are travelling left you need to check for a wall along the vector UP.

I wont give you the whole solution because:
a) thinking through the solution will lead to insight.
b) I am listening to Red Hot Chili Peppers (Give It Away) at volume 12
c) I am very possibly drunk
d) it is 1:39AM

P.S. seriously though, if you still have problems email me. This is a very good programming excercise.

D.V.

The right hand rule goes along the lines of ''if there is a wall to your right move forward. If there is no wall turn right until there is''

You will need you position {x,y} and the direction (vector) you are travelling. your vector will be FORWARD{1,0}, DOWN{0,-1}, RIGHT(-1,0} or UP(0,1}.

so if you are travelling left you need to check for a wall along the vector UP.

I wont give you the whole solution because:
a) thinking through the solution will lead to insight.
b) I am listening to Red Hot Chili Peppers (Give It Away) at volume 12
c) I am very possibly drunk
d) it is 1:39AM

P.S. seriously though, if you still have problems email me. This is a very good programming excercise.

D.V.

Tried that, but I end up running into walls at the end of hallways such as this:
#######
.....X#
#######

X is where I get stuck. Thanks for the help so far though!

Oh, and 1:40 is early. I''m writing at 4:17 and I''m still gonna be up for a few hours. Gonna try the algorithm one more time tonight. I figure I use your system, but when theres a wall on the right it checks for a wall ahead too, in which case it turns left until theres nothing ahead of it. Hopefully that works.

Krunk

Update - its 5:25 AM and I just finished coding my latest attempt. This one gets stuck right at the opening and I have no idea why. You can see my code at
http://members.aol.com/antsage/maze.txt
Its not the most efficient thing in the world, but I cannot see why its not doin it. Any advice would be much appreciated.

Krunk

Stop everything!

I have already cerated a game where the computer can create random mazes 100 x 100 squares big. It can solve them, too. The user can create their own mazes, and there are several different games I've made out of it. It is 100% reliable and is garanteed to create mazes with only one route between two points on the map. If you want to know more, just post. (It is written in Delphi, though)

~ There's no substitute for failure ~

Edited by - MarkyD on August 18, 2001 5:44:58 AM

Basically, for every square you''re on, you look at the squares around you:

1 passable square: You''re in a dead end: turn 180 and continue.
2 passable squares: Follow the one that you didn''t just come from (ie. don''t go backwards if you don''t need to). This equates to ''following the passage''.
3 or more passable squares: You''re at a junction: choose the one most to your right.

Note that this doesn''t work if you have circular areas in a map, such as:

#########......#..####..#......######### 

Because the algorithm just goes round and round.

Thanks for the help so far, but I was also curious as to what the failure(s) in my code is/are. And MarkyD, I''m more interested in coding this myself or at least examining the C++ code so that I can understand the problem.

Krunk

Righto

regarding your cde that worked until you got stuck in a dead end eg
#######
.....X#
#######

the solution is to turn back on your self and reapply the right hand rule

###########
#.........3
#.#########
#.#########
#........2#
#.#########
#.#
#.#
#1#

so if you started at position 1 and applied the right hand rule you''d get to position 2. Now, if you turn back on yourself and carry on applying the right hand rule, you will get to position 3

oh yeah, if you use the right hand rule, never turn left as this will stop the algorithm from working.

===========================
The price of intelligence is stupidity