In my A* code, the "open list" is a non-sorted 1D array. Its length is defined in the code, not in run-time, so I need to know what is the minimal array length L that is enough for any square-shaped map with length and width of W tiles (nodes). I don't need answers like "it's W*W/2, obviously". I would like to see a mathematical proof. I'll appreciate any help with this question...My algorithm is already optimized for best speed (I tried all the methods I found and the current one is clearly the fastest), but there's still this issue with the memory. Right now I'm using an array length of W*W/2, but 'm quite sure it's too much - a waste of memory. the problem is that I don't know how to find L using math.

It depends on how your nodes are connected. If every node is connected to every other node, then the maximum size of the open list will be (W * W - 1). If every node is only connected to two other nodes, then the maximum size of the open list will be 2.

Quote: Original post by SiCrane
If every node is only connected to two other nodes, then the maximum size of the open list will be 2.

Noooo......

The maximum length of the open list is the maximum length of a closed curve in your map (the curve is the "front" of the "wave"). I don't know what that length is. But obviously the number of nodes is an upper bound.

Quote: Original post by Emergent

Quote: Original post by SiCrane
If every node is only connected to two other nodes, then the maximum size of the open list will be 2.

Noooo......

The maximum length of the open list is the maximum length of a closed curve in your map (the curve is the "front" of the "wave").

In A*, every time you add nodes to the open list you remove one node from the open list first. In the situation that every node is connected to two other nodes, you start with one node. Remove it and add the nodes that are connected to it. This means there are two nodes in the open list. Now you remove another node and add nodes it's connected to to the open list. However, since one of those nodes must have already been processed, you end up removing one node and adding one node. That means there are still only two nodes in the open list. Repeat ad infinitum and you'll never have more than two nodes in the open list.

Quote: Original post by SiCrane

Quote: Original post by Emergent

Quote: Original post by SiCrane
If every node is only connected to two other nodes, then the maximum size of the open list will be 2.

Noooo......

The maximum length of the open list is the maximum length of a closed curve in your map (the curve is the "front" of the "wave").

In A*, every time you add nodes to the open list you remove one node from the open list first. In the situation that every node is connected to two other nodes, you start with one node. Remove it and add the nodes that are connected to it. This means there are two nodes in the open list. Now you remove another node and add nodes it's connected to to the open list. However, since one of those nodes must have already been processed, you end up removing one node and adding one node. That means there are still only two nodes in the open list. Repeat ad infinitum and you'll never have more than two nodes in the open list.

I don't think that's his situation though. He has a square map. Wouldn't he have to have to be at least 3 (more likely 4 or 8) links from each node? If you limited yourself to 2 links per node, you'd be representing a doubly-linked list.

The OP only said that his "open list is a non-sorted 1D array", but that his map was square-shaped.

In the case where you have each node with {north,south,east,west} connections, you will get between 0 and 3 nodes added depending on obstacles.

(edit: removed my speculative equation since it was obviously incorrect for either the 2-link case or the >2 link case)

[Edited by - Nypyren on January 10, 2009 3:15:49 PM]

Quote: Original post by SiCrane
In the situation that every node is connected to two other nodes[...] you'll never have more than two nodes in the open list.

Ah, I hadn't read carefully enough and missed the "connected to two other nodes" bit. It's a very special case though.

Quote: Original post by Nypyren
I don't think that's his situation though. He has a square map. Wouldn't he have to have to be at least 3 (more likely 4 or 8) links from each node? If you limited yourself to 2 links per node, you'd be representing a doubly-linked list.

Hence the "It depends on how your nodes are connected" at the beginning of my first post. Without knowing that, the two extremes would be 2 and W * W - 1.

Sorry, I forgot to mention a very important detail...the map allows diagonal movement, so from each node the path can go to up to 8 other nodes. My "open array" is a simple non-sorted 1D array. Each element of the array has x and y.

Well, I've got bad news for you. Worst case scenario in that case is actually bigger than W * W / 2. Take this 25 x 25 grid:

This has got 483 elements in the open list, which is just above three quarters the number of total nodes in the map (625). Of course, the chances of building such a messed up search is extremely low, but not impossible.

Then I'll probably change L to W*W . . . Unless someone shows me a calculation of the L that I'm looking for...