Solving mazes!!!

[Maeco]

I need help solving mazes...
i have a maze description in a file.
First row x x (dimensions)
second x x (where start)
third x x (where to arrive)
.... x x x x x
.... x x x x x
x x x x x
...ecc

where each x form the third row represents an integer from one to 15
es: 5=0101 (N-W-S-E walls)
1 means wall in that direction
0 means no wall in that.

Now i have read the matrix from the file and stored in an Array [j].
1)How design it in stdout
2)How have a binary description of integer
3)iterations to do for finding the path from starting point to end

thanks

 

[Michael Mair]

I need help solving mazes...
i have a maze description in a file.
First row x x (dimensions)
second x x (where start)
third x x (where to arrive)
... x x x x x
... x x x x x
x x x x x
..ecc

where each x form the third row represents an integer from one to 15
es: 5=0101 (N-W-S-E walls)
1 means wall in that direction
0 means no wall in that.

Now i have read the matrix from the file and stored in an Array [j].
1)How design it in stdout
2)How have a binary description of integer
3)iterations to do for finding the path from starting point to end

Please, learn to ask smart questions:
http://www.catb.org/~esr/faqs/smart-questions.html

0) Your description does not state the maze format clearly:
Are you considering everything from the point of view of
square fields, i.e.
6:

|
-
or from the possible intersections of walls:
5:

-+
|
Is the information redundant? I.e. if one entry demands
a wall in the east, does its eastern neighbour demand one
in the west?
1) Do you want to draw the maze?
2) Look at the physical representation of the integer
Maybe you are asking for hexadecimal representation in
the file or you really want to print binary
3) Try to find out what constitutes a valid path, then
either compute one or try exhaustive search.


Cheers
Michael

 

[slebetman]

I need help solving mazes...
i have a maze description in a file.
First row x x (dimensions)
second x x (where start)
third x x (where to arrive)
... x x x x x
... x x x x x
x x x x x
..ecc

where each x form the third row represents an integer from one to 15
es: 5=0101 (N-W-S-E walls)
1 means wall in that direction
0 means no wall in that.

Now i have read the matrix from the file and stored in an Array [j].
1)How design it in stdout
2)How have a binary description of integer
3)iterations to do for finding the path from starting point to end

thanks

The classical algorithm of solving mazes is keep looking left or keep
looking right.
The 'left' version of the algorithm:

if (can go left) then go left
elseif (can go forward) then go forward
elseif (can go right) then go right
else turn around and go back where you came form

or the 'right' version of the algorithm:

if (can go right) then go right
elseif (can go forward) then go forward
elseif (can go left) then go left
else turn around and go back where you came form

 

[Nick Keighley]

(e-mail address removed) wrote:

The classical algorithm of solving mazes is keep looking left or keep
looking right.
The 'left' version of the algorithm:

if (can go left) then go left
elseif (can go forward) then go forward
elseif (can go right) then go right
else turn around and go back where you came form

or the 'right' version of the algorithm:

if (can go right) then go right
elseif (can go forward) then go forward
elseif (can go left) then go left
else turn around and go back where you came form

_____
| |
| |_| |
|__ __|

 

[Nick Keighley]

I need help solving mazes...
i have a maze description in a file.
First row x x (dimensions)
second x x (where start)
third x x (where to arrive)
... x x x x x
... x x x x x
x x x x x
..ecc

where each x form the third row represents an integer from one to 15
es: 5=0101 (N-W-S-E walls)
1 means wall in that direction
0 means no wall in that.

I don't understand. Is each row 4 numbers "1234" or is it a binary
encoding and hence
a single number? In that case does an 'x' indicate a bit or a number?
Is the number hex
or decimal?

Could you simply give an example of a maze file?

Now i have read the matrix from the file and stored in an Array [j].
1)How design it in stdout

what? Do you mean print it?

2)How have a binary description of integer

I've no idea. Do you mean express an integer in binary?

3)iterations to do for finding the path from starting point to end

do you mean "how do I solve the maze?"?


--
Nick Keighley

The fscanf equivalent of fgets is so simple
that it can be used inline whenever needed:-
char s[NN + 1] = "", c;
int rc = fscanf(fp, "%NN[^\n]%1[\n]", s, &c);
if (rc == 1) fscanf("%*[^\n]%*c);
if (rc == 0) getc(fp);
Dan Pop (clc)

 

[Raymond Martineau]

(e-mail address removed) wrote:

The classical algorithm of solving mazes is keep looking left or keep
looking right.
The 'left' version of the algorithm:

if (can go left) then go left
elseif (can go forward) then go forward
elseif (can go right) then go right
else turn around and go back where you came form

[...]
_____
| |
| |_| |
|__ __|

A simple change counters this - it involves dropping breadcrumbs where the
algorithm treats advancing to such a cell to be "illegal" (even though it
is not.)

Besides, that's not a classical maze.

 

[slebetman]

(e-mail address removed) wrote:



_____
| |
| |_| |
|__ __|

Yeah, punch a hole *anywhere* in that maze and start anywhere and
either of the algorithms I described will find a way out. In fact the
algorithm solves any maze (provided there is a way out).

 

[Michael Mair]

Yeah, punch a hole *anywhere* in that maze and start anywhere and
either of the algorithms I described will find a way out. In fact the
algorithm solves any maze (provided there is a way out).

No. If you start in the centre square, you will _never_ find out,
regardless of the amount of holes.
Your algorithm works fine for 2D mazes if you start from the
border and are looking for a border exit, provided it is
there.
Without breadcrumbs or whatever Ariadne gifted you with, however,
you cannot safely cover every square in your maze, or find an
exit starting from somewhere inside.


Cheers
Michael

 

[Mabden]

No. If you start in the centre square, you will _never_ find out,
regardless of the amount of holes.
Your algorithm works fine for 2D mazes if you start from the
border and are looking for a border exit, provided it is
there.
Without breadcrumbs or whatever Ariadne gifted you with, however,
you cannot safely cover every square in your maze, or find an
exit starting from somewhere inside.

Also, there may be monsters, or hordes of Visigoths or Mabden there to
surprise you. I remember this one time my tribe and I were stalking a
"watcher"... I sent Bobo along in front - well, long story short, there
he was frozen and we stripped him naked and went North. It took him 4
hours to find him and he had to wear Johnson's pants.
No, wait that was a dream.

Are we still talking about C here...?

 

[zuran]

1)Matrix: 10 10 (dimensions)
6 6 (start point)
9 9( end point to reach)
14 9 9 4 x x x
x x x x.....
...
...

1)reading the maze from a file,i mean reading and storing the number in
a bidimens array of char

2)my question is not correct because an int,a char....have just a
binary rappresentation in memory.
But with the first element i.e. decimal :14= binary 1110(N-W-S-E). This
means that the first 1 on the left tell me that there is a wall in the
north,the second in the west,third in the south and there are no walls
in est.

3)you are in the right:i'm searching the algorithm tosolve this.

i was thinking to a list ,within pointers to next square and previos
square...but im not sure it is the best way..thanks

 

[Peter Harrison]

1)Matrix: 10 10 (dimensions)
6 6 (start point)
9 9( end point to reach)
14 9 9 4 x x x
x x x x.....
...
...

1)reading the maze from a file,i mean reading and storing the number in
a bidimens array of char

2)my question is not correct because an int,a char....have just a
binary rappresentation in memory.
But with the first element i.e. decimal :14= binary 1110(N-W-S-E). This
means that the first 1 on the left tell me that there is a wall in the
north,the second in the west,third in the south and there are no walls
in est.

3)you are in the right:i'm searching the algorithm tosolve this.

i was thinking to a list ,within pointers to next square and previos
square...but im not sure it is the best way..thanks

A good algorithm is described (however well) here

http://micromouse.cannock.ac.uk/maze/fastfloodsolver.htm

Just to keep us moderately on-topic I guess, my solvers are written in C

I have to say, the term "maze solving" just generated over 21,000 hits in
Google

Pete Harrison