Implementing an open/closed list

This is a discussion on Implementing an open/closed list within the C Programming forums, part of the General Programming Boards category; Hi, I'm not sure what data structure I should use, but here is my situation. I'm implementing a path finding ...

  1. #1
    Registered User
    Join Date
    Nov 2009
    Posts
    37

    Implementing an open/closed list

    Hi,

    I'm not sure what data structure I should use, but here is my situation. I'm implementing a path finding algorithm on a 2d grid map (saved as a 2d array). When I expand from one node to another, I have to save the nodes expanded to, but not yet explored (for their cost function). I therefore need a data structure which is cable of saving such nodes (open list), and when the node has been explored and deemed costly, to discard of it (to a closed list).

    From my limited understanding of how linked lists work, I am thinking that it may be an acceptable choice. What are my other options? I would very much appreciate some pseudo code to help aid my understanding.

    Thank you.

  2. #2
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    The only significant difference between a linked list and an array is that inserting and re-arranging the list is much more efficient. If you just need to keep an unsorted stack of node references, just use an array.

    From the sound of things, you want to move a node from list to another, so probably a linked list is the way to go, unless you are comfortable using an array with recyclable slots in it.
    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

  3. #3
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Quote Originally Posted by MK27 View Post
    The only significant difference between a linked list and an array is that inserting and re-arranging the list is much more efficient.
    I'd say it's pretty significant that array elements are next to each other in memory, where as linked list nodes are likely not.

    When you say "expand to", what sort of path finding are you using? You might just want an array that is x*y nodes (the same size as your maze), because it's easy use. I don't know that I'd bother with a linked list unless it's a massive array (in which case, I still don't know that I'd bother with a linked list--and I like linked lists), I'd just allocate x*y dynamically. I can't really see using a linked list here.


    Quzah.
    Hope is the first step on the road to disappointment.

  4. #4
    Registered User
    Join Date
    Nov 2009
    Posts
    37
    I'm using the A* algorithm.

    Would the array implementation be used as some sort of queue, like discussed here?
    Queue - Array Implementation - Types

  5. #5
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by user_name_void View Post
    Would the array implementation be used as some sort of queue, like discussed here?
    Queue - Array Implementation - Types
    Less "CS", more C From a C perspective, a "queue" is unlikely to be an array, it is more likely to resemble a linked list, since shifting an entire array around is inefficient.

    What is an array, using the C programming language?

    It could be this:
    Code:
    typedef struct {
         [whatever you want]
    } node;
    node array[10];
    You can only put 10 nodes in there tho. That's fine, if the number of nodes in your list is always going to be less than ten. If the number of nodes is indeterminate, then
    that is a complication.

    From the sounds of what you are doing, it is hard to tell whether the number of nodes in the open list is determinate. I've never done path finding, but I would guess that using this system you are working backward from the goal, or in stages, so the number of open nodes is going to be much less than the total. Is there an obvious limit?

    The closed list could grow until it includes all the nodes, if there is no path.

    I would think seriously about quzah's suggestion...that is, that you maintain a parallel matrix. Then you can just set elements open or closed.

    Of course, a boolean member in the node struct would accomplish the same thing, but maybe that is not your assignment.
    Last edited by MK27; 12-12-2009 at 05:43 PM.
    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. #6
    Registered User
    Join Date
    Nov 2009
    Posts
    37
    I'm working from the source to the goal. So from the initial node, there is only one node to consider, then if possible we expand up, down, left, and right with respect to the initial node. The cost of moving from the initial node to each of the expanded nodes is calculated, and also the cost of moving from the expanded nodes to the goal is also calculated. The node with the lowest cost is then taken and we continue to expand in the same matter as we did from the initial node until the goal is met. So we will have to keep some nodes in the list even though they have a higher cost because the path could be blocked for the node with the lowest cost, in which case we have to use the node with the second lowest cost and so on. So it seems like all nodes have to be kept in the list because we have to work backwards. Unless moving from the closed list to open list is efficient. But I am still somewhat clueless as to how to get this list into code.

    For node array[10], we can only put a 1d number, but what about a 2d co-ordinate, how do we get that in there? I guess it must be obvious by this post and my other threads that I'm learning C in order to finish this task

  7. #7
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,288
    You typically have to search for whether a node belongs to the open list or closed list during the algorithm running. If this search is O(n) because you're using a linked-list, then the overall search speed could suffer, particularly for larger data sets.
    You also need to extract the item from the open set that is the most promising. If you use a linked-list then you'll probably be keeping the items ordered in order of how promising they are, but then that comes at the cost of insertion & removal.

    In summary. you can do this with a linked-list, but using another data structure such as a binary-tree, heap, hash table, or other such structure that allows you to represent a logical set, is going to give you better performance.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  8. #8
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by user_name_void View Post
    For node array[10], we can only put a 1d number, but what about a 2d co-ordinate, how do we get that in there? I guess it must be obvious by this post and my other threads that I'm learning C in order to finish this task


    Quote Originally Posted by user_name_void View Post
    I'm not sure what data structure I should use, but here is my situation. I'm implementing a path finding algorithm on a 2d grid map (saved as a 2d array).
    Okay, when this makes some kind of sense to you:
    Code:
    datatypeWhatever  my_normative_2Darray[10][10];
    Please get back to us.
    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. #9
    Registered User
    Join Date
    Nov 2009
    Posts
    37
    Okay okay, I've gotten to 2d arrays :shame:

    This is Open/Closed list (set) I am referring to:
    Implementation notes

  10. #10
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Okay, that is a bit different that what I was thinking earlier -- that the CLOSED list would be nodes that should not be used, whereas now I take it the closed list is just ones already in the path.

    The idea is fine, just it seems to me that it would be easiest to implement using something in your node struct:
    Code:
    typedef struct {
          int open;      /* this could be -1 for unlisted, 0 for closed, 1 for open */
          int fvalue;
    } node;
    You do not need coordinates in the struct since you will be using a 2D array:
    Code:
    node maze[10][10];
    Then you only need to maintain an "open list" of pointers to select from -- you may not even need that.
    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

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. One more linked list implementation
    By BlackOps in forum C Programming
    Replies: 17
    Last Post: 07-16-2009, 09:34 PM
  2. Anyone good with linked list.....I am not....
    By chadsxe in forum C++ Programming
    Replies: 11
    Last Post: 11-10-2005, 01:48 PM
  3. Linked List
    By jpipitone in forum C Programming
    Replies: 4
    Last Post: 03-30-2003, 08:27 PM
  4. Linked list with two class types within template.
    By SilasP in forum C++ Programming
    Replies: 3
    Last Post: 02-09-2002, 05:13 AM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM

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