Implementing an open/closed list

[user_name_void]

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.

[MK27]

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.

[quzah]

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.

[user_name_void]

I'm using the A* algorithm.

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

[MK27]

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:

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.

[user_name_void]

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

[iMalc]

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.

[MK27]

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

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:

datatypeWhatever  my_normative_2Darray[10][10];

Please get back to us.

[user_name_void]

Okay okay, I've gotten to 2d arrays :shame:

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

[MK27]

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:

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:

node maze[10][10];

Then you only need to maintain an "open list" of pointers to select from -- you may not even need that.