The data structures are not going to matter a great deal -- how are you going to get the maze into the program? (Do you have to parse a file, read a list of vertices, ???) How are you going to solve the maze? Those are the only questions that matter, and you appear to have not started on them.
Oh yeah good point. I think i will be able to read the maze from a text file as it is. Afterwards it has to be converted to adjacency matrix notation. How to do that?Originally Posted by tabstop
You do that as you read it in. How you do it depends on how the maze is represented in the file.
say this is the maze in the text file
S - Start F- FinishCode:Soxxxxooooooxxxx oooooooooooxoxxo xooooooxxxxoooox xoxxxoxoooooooox xxxoooxoooxxxxox ooooxxxxoooxooox oxoooxoooooxooox oxoooxooooxooooo oxoooxxxxoxoxooo oxoooxooooxxxxxo xxxxoxxxxoxooxoo oooooxoooooooxoo oxooooooxxxxxxoo oxxxxooooxxooooo ooxoooooxoxoxxxx oooooxxxooxooooF
Now once i read it and put it into a 2D array i get is the same thing
This will not be a adjacency matrix
How can i resolve this issue.
To build an adjacency matrix you have to
- figure out how many squares there are in the maze
- make a 2D matrix that is that many on each side
- Using the text, decide which squares are connected
- Put a 1 in the appropriate places in the adjacency matrix
- Make a note of starting node and finishing node
- Use whatever algorithm you feel appropriate to solve the maze
- Print the solution, making conversions from internal representation to user representation
How do i represent walls?
You don't. An adjacency matrix only stores the places you can move to. (EDIT: To be more clear, a 0 in the adjacency matrix means you can't get from point A to point B, for whatever reason, whether it's a wall, or because the two squares aren't next to each other.)
Last edited by tabstop; 04-28-2010 at 08:46 PM.
okay then the no of movable nodes = total no of nodes - no of walls
am i correct?
