Jump to content
  • Advertisement
Sign in to follow this  
Tom Backton

Size of "open array" in A*

This topic is 3538 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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.

Share this post


Link to post
Share on other sites
Advertisement
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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]

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!