Thread: Represent Maze

  1. #16
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by iamnew View Post
    oo no i don't understand whats going on . Iam confused with maze representation. can you guys please explain in the most simplest way. Iam kind of a NOOB.
    Alright, first off, is this for a homework assignment? That's okay, we can still help you, but it makes a big difference with regard to what you are trying to accomplish. I think both those definitions make sense, would serve a purpose, and you could write a program to derive such a thing from a graph which describes a maze.

    If it's not homework, explain why you are doing this. Also: do you understand how to implement a graph in a computer program?
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  2. #17
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    An adjacency list is just a list of all the adjacent squares. So the list for the maze you posted might start ((A0,A1), (A2,A3), (A4,A5), (A1,B1), (A2,B2), (A4,B4), (A5,B5), (A6,B6), (A7,B7), (B0,B1), (B1,B2), ......) Or you can sort by vertex and keep a list, for every square, which other squares are adjacent. So the list for A0 would be (A1); for A1 it would be (A0, B1); for A2 it would be (A3, B2); etc.

  3. #18
    Registered User
    Join Date
    Apr 2010
    Posts
    50
    Isn't the adjacency list representation the best way of solving the maze problem. Since it requires substantially lesser amount of nodes.

  4. #19
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Quote Originally Posted by iamnew View Post
    Isn't the adjacency list representation the best way of solving the maze problem. Since it requires substantially lesser amount of nodes.
    Compared to what? You probably wouldn't be storing actual whatever-you're-using-for-your-squares in your lists, but pointers.

    In any event, you need to work out what your algorithm is for getting through the maze; that will probably suggest a data structure for storing your maze.

  5. #20
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    If you want to use this to solve the maze, I would think the second kind (a list for each node) would be more useful. Like tabstop says, you need some idea of how you are going to solve the maze.

    But if that is your goal (to solve the maze), an adjacency list is probably not necessary at all since that information is encapsulated in a graph structure anyway.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  6. #21
    Registered User
    Join Date
    Apr 2010
    Posts
    50
    Oh well i have to use a graph representation anyway. Now in the adjacency representation a node is the point at which a decision has to be taken in the maze. So since in the entire maze has only a few decision points only a few nodes are needed.

  7. #22
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    You're going to have 48 nodes no matter what, since that's how many squares there are.

  8. #23
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by iamnew View Post
    Oh well i have to use a graph representation anyway. Now in the adjacency representation a node is the point at which a decision has to be taken in the maze. So since in the entire maze has only a few decision points only a few nodes are needed.
    Sure, but a graph node (for a 2D maze) looks (something) like this:
    Code:
    struct node {
        int ID;  // not necessary
        struct node *north;
        struct node *south;
        struct node *east;
        struct node *west;
    }
    It already contains a list of adjacent nodes.

    Also, you need all the nodes, not just the decision points, or the "decision points" will have no relation.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  9. #24
    Registered User
    Join Date
    Apr 2010
    Posts
    50
    Quote Originally Posted by MK27 View Post
    Sure, but a graph node (for a 2D maze) looks (something) like this:
    Code:
    struct node {
        int ID;  // not necessary
        struct node *north;
        struct node *south;
        struct node *east;
        struct node *west;
    }
    It already contains a list of adjacent nodes.

    Also, you need all the nodes, not just the decision points, or the "decision points" will have no relation.
    Why there will be no relation. The decision points will be connected with an edge and the edge will have a weight equal to the no of squares in between.

  10. #25
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    Quote Originally Posted by iamnew View Post
    Why there will be no relation. The decision points will be connected with an edge and the edge will have a weight equal to the no of squares in between.
    How do you know what the "right" decision points are until you solve the maze? If you're going by the unsolved version, every square is then a "decision point".

  11. #26
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    >>The decision points will be connected with an edge and the edge will have a weight equal to the no of squares in between.
    Good point. I guess you could describe a maze that way too. It still renders the "adjacency list" question superfluous. I also don't see the point in weighting the edge, unless you are looking for the shortest route.

    Actually using a weighted edge introduces a form of complication such that I don't think this will be an improvement over graphing all the nodes UNLESS you are thinking of a maze with many long straight corridors. Even then, I don't think it is necessarily better. Maybe.
    Last edited by MK27; 04-28-2010 at 09:04 AM.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  12. #27
    Registered User
    Join Date
    Apr 2010
    Posts
    50
    okay the other way that iam thinking of is using a boolean 2D array. Is this a good method over adjacency matrix? Can i do graph traversals using a boolean 2D array?

  13. #28
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,336
    A boolean 2D array is an adjacency matrix.

  14. #29
    Registered User
    Join Date
    Apr 2010
    Posts
    50
    I feel like using a adjacency list and taking nodes as the decision point is not very good because we have to compute the edge value. I like if all the computing is done by the PC.

  15. #30
    Registered User
    Join Date
    Apr 2010
    Posts
    50
    SO with which representation should go forward? IS it the matrix or list? Iam exhausted now. I feel like giving up.

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, 12:15 PM
  2. Q: Recursion to find all paths of a maze
    By reti in forum C Programming
    Replies: 7
    Last Post: 11-26-2002, 09: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, 01: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, 03:27 AM