I use linked lists (not pointers but with indexes), and since all nodes could be in any list, all nodes got a link (to another node or to NULL)... this way, no data is allocated or released, all i need is a List-Head[x,y] and then node[x,y] points to node[i,k] or null... this way, all nodes can be in one list, and no data is realocated anytime (not even in worst case)... makes the List code a little more complicated, since i have to make sure that all lists are correct and in order, but when this List-wrapper is done, its lightning fast!

Quote: Original post by Kylotan
Note that if you use a bit array for the open list, be aware of the situation where you may find 2 different routes to a position and the route you find second beats the route you found first. Some algorithms don't take this into account properly. You may well have this covered already; it's hard to work out exactly what is what when you have both a bit array and a priority queue. No doubt part of that is for optimisation.

I should be OK. I'm recalculating the path cost when looking at whether I'm looking too far, so I'm covered. It's a bit more expensive, but I didn't really want another array<g>. Basically, each element of the array uses a backpointer to the previous element.

Quote:

Quote: I'm also not having any luck with visualizing out what the worst case map for A* would look like.

A* beats breadth first search purely by using the heuristic that directs it towards the goal, cutting down on the number of branches you need to follow. The worst case therefore is one where the heuristic is useless or misleading, and all branches have to be followed no matter what. Given the restriction that your nodes are spatially oriented in Euclidean space, a simple worst-case example is where almost the entire search space is blocked from the destination, and the heuristic gives you the 'wrong' direction for most of the search, like so:

S for start, E for end.+-------------+|             || ----------+ ||           | ||          S|E||           | || ----------+ ||             |+-------------+

You will probably flood-fill the entire map in this case.

Sorry, I can visualize that case, and I've run into it. I meant that I can't visualize what map would give the most items in the open list at a given time. It almost feels like it

Thanks for the detailed explanation.

Quote: Original post by Kylotan
The simplest way to get round your memory issues is to use std::vectors or a container that acts similarly. They resize as you add to them, and keep their size when you remove from them. The end result is that you do a bit of memory allocation early on, and only ever allocate more when you find yourself needing more space than you have used before.

I've used the STL before, but currently the only memory allocation is done by the sound and graphics subsystems, I'm hoping to keep it that way. I agree that using the STL would make my life easier, but I'm old-fashioned. This way I KNOW what the performance is going to be. It also leaves me open to port to XNA, or a PDA or a console or whatever later on. First I've got the 'minor' task of creating clean objects, and separating out the display and control code from the main processing<g>. It's only 4.22 Meg of well-written C code, that shouldn't take me long, right?

Ralph Trickey
TOAW III Programmer

Quote: Original post by Ralph Trickey

Quote: Original post by Kylotan
The simplest way to get round your memory issues is to use std::vectors or a container that acts similarly. They resize as you add to them, and keep their size when you remove from them. The end result is that you do a bit of memory allocation early on, and only ever allocate more when you find yourself needing more space than you have used before.

I've used the STL before, but currently the only memory allocation is done by the sound and graphics subsystems, I'm hoping to keep it that way. I agree that using the STL would make my life easier, but I'm old-fashioned. This way I KNOW what the performance is going to be. It also leaves me open to port to XNA, or a PDA or a console or whatever later on. First I've got the 'minor' task of creating clean objects, and separating out the display and control code from the main processing<g>. It's only 4.22 Meg of well-written C code, that shouldn't take me long, right?

Ralph Trickey
TOAW III Programmer

The other issue is that keeping the path with the unit wouldn't work, only one unit is moving at a time, and the path cost depends on unit stacking, and some other factors. I'm avoiding recalculating the complete patch by saving the queue between calls if it's identical, but doing more isn't practical for me. Given that, I don't know that I want to clutter things up with memory allocation.

Quote: Original post by Ralph Trickey
I meant that I can't visualize what map would give the most items in the open list at a given time.

As I said in my earlier post... any map in which the heuristic used is zero will result in the maximum open list size. Essentially, this means any map where the heuristic does not sufficiently differentiate between any two leaf nodes of the search that have the same (or similar) traversal cost from the root node to the leaf node. In this situation, both nodes will be expanded, even though only one of them could possibly lie on the optimal path. (In other words, it has nothing to do with the map and everything to do with your choice of heuristic).

It is possible to determine the maximum size of the open list for a given map, if you know the cost function. A* guarantees to expand every node in a given cost contour before expanding any node in the next highest cost contour. So, for a given starting state on a discrete grid you could determine the discrete cost contours. Once you find the contour with the goal in it, you know you'll have to open every node in every lower cost contour before you open that one (and find it is the goal). You can run this offline for every possible start-goal pair (or a reasonable sample... I'd use a Monte Carlo sampling approach) to produce a mapping from expected path cost to number of nodes (for a fully connected map with uniform transition cost and no islands (disconnected sub-regions) this would be a constant for a given path length). Then, for any online search, compute the heuristic for the start-goal pair given and use this as a lookup into the table to get an estimate of the number of nodes you'll search through. Allocate this much space and start searching (you'll probably want to ensure that your table slightly over-estimates the expected number of nodes to be opened, or stores a worst case number).

Cheers,

Timkin

Quote: Original post by Timkin

Quote: Original post by Ralph Trickey
I meant that I can't visualize what map would give the most items in the open list at a given time.

As I said in my earlier post... any map in which the heuristic used is zero will result in the maximum open list size. Essentially, this means any map where the heuristic does not sufficiently differentiate between any two leaf nodes of the search that have the same (or similar) traversal cost from the root node to the leaf node. In this situation, both nodes will be expanded, even though only one of them could possibly lie on the optimal path. (In other words, it has nothing to do with the map and everything to do with your choice of heuristic).

Cheers,

Timkin

Thanks, I'd missed that in your earlier post.