Represent Maze

This is a discussion on Represent Maze within the C++ Programming forums, part of the General Programming Boards category; The data structures are not going to matter a great deal -- how are you going to get the maze ...

  1. #31
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    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.

  2. #32
    Registered User
    Join Date
    Apr 2010
    Posts
    50
    Quote Originally Posted by tabstop View Post
    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?

  3. #33
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Quote Originally Posted by iamnew View Post
    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?
    You do that as you read it in. How you do it depends on how the maze is represented in the file.

  4. #34
    Registered User
    Join Date
    Apr 2010
    Posts
    50
    say this is the maze in the text file
    Code:
    Soxxxxooooooxxxx
    oooooooooooxoxxo
    xooooooxxxxoooox
    xoxxxoxoooooooox
    xxxoooxoooxxxxox
    ooooxxxxoooxooox
    oxoooxoooooxooox
    oxoooxooooxooooo
    oxoooxxxxoxoxooo
    oxoooxooooxxxxxo
    xxxxoxxxxoxooxoo
    oooooxoooooooxoo
    oxooooooxxxxxxoo
    oxxxxooooxxooooo
    ooxoooooxoxoxxxx
    oooooxxxooxooooF
    S - Start F- Finish

    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.

  5. #35
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    To build an adjacency matrix you have to
    1. figure out how many squares there are in the maze
    2. make a 2D matrix that is that many on each side
    3. Using the text, decide which squares are connected
    4. Put a 1 in the appropriate places in the adjacency matrix
    5. Make a note of starting node and finishing node
    6. Use whatever algorithm you feel appropriate to solve the maze
    7. Print the solution, making conversions from internal representation to user representation

  6. #36
    Registered User
    Join Date
    Apr 2010
    Posts
    50
    How do i represent walls?

  7. #37
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Quote Originally Posted by iamnew View Post
    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.

  8. #38
    Registered User
    Join Date
    Apr 2010
    Posts
    50
    okay then the no of movable nodes = total no of nodes - no of walls

    am i correct?

Page 3 of 3 FirstFirst 123
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Solving A Maze Using C Language!!!!
    By jonnybgood in forum C Programming
    Replies: 6
    Last Post: 11-08-2005, 11:15 AM
  2. Q: Recursion to find all paths of a maze
    By reti in forum C Programming
    Replies: 7
    Last Post: 11-26-2002, 08:28 AM
  3. My Maze Game --- A Few Questions
    By TechWins in forum Game Programming
    Replies: 18
    Last Post: 04-24-2002, 11:00 PM
  4. Algorithm to walk through a maze.
    By Nutshell in forum C Programming
    Replies: 30
    Last Post: 01-21-2002, 12:54 AM
  5. Maze game, complete with maze editor and an example maze!
    By Brian in forum A Brief History of Cprogramming.com
    Replies: 2
    Last Post: 01-20-2002, 02:27 AM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21