Is there a heuristic for the maximum expected size of the priority queue in A*? Thanks, Ralph

What does your graph look like? On an arbitrary graph, the maximum expected size is the size of the graph.

It depends on the problem you're trying to solve.

Obviously it will be dependent on the cost surface properties the node density. Off the top of my head I do not know of an exact metric for computing the expectation, although I vaguely recall having read something on this topic some time ago, so you might be able to find some information. I've got a good book on search methods at home... I'll flip through it tonight. We do know that this number will be bounded above by the number of nodes expanded in a greedy search (heuristic cost of zero) and my intuition tells me that it will be bounded below by the number of nodes currently in the closed list, since A* guarantees to expand fewer nodes than any other algorithm (given that an optimal solution exists).

Cheers,

Timkin

Quote: Original post by Vorpy
It depends on the problem you're trying to solve.

It's for a wargame, Operational Art of war III, currently a 300x300 grid. It's possible to have 'Islands' where there is no connectivity, but generally the terrain is passable. I'm capping the AI's search path at 200.

Quote: Original post by Ralph Trickey

Quote: Original post by Vorpy
It depends on the problem you're trying to solve.

It's for a wargame, Operational Art of war III, currently a 300x300 grid.

Squares or hexes? If squares, can you move diagonally? ie. Is there a branching factor of 4, 6, or 8 at each step?

Does the previous path to a given place affect the future path? In other words, if on my way from A to B via C, and I find 2 routes to B, one taking less time than the other, can I safely discard the previous route to B?

Quote: It's possible to have 'Islands' where there is no connectivity, but generally the terrain is passable.

If you precompute the islands, then you can very quickly reject impossible paths. This means you can think more about the average case rather than the worse case. Even if the islands change, it's probably quick to recalculate them.

I don't think you need a heuristic here. I think you need to test. Run a few thousand random paths across a map, and plot a graph of open list size vs. path length. For simple maps, the open list size is proportional to the branching factor of each node, and for complex maps, it'll be proportional to the branching factor of each potential route, but you'll get a far better understanding of where your game lies between those extremes by testing than by analysis.

think about this:

What if there is no path? Dont you want it to try all possible routs before giving up? If so, you need to store all nodes.

300 * 300 * 10 = 900kb, which is a small amount of memory when you get pathfinding in return...

Quote: Original post by Kylotan
Squares or hexes? If squares, can you move diagonally? ie. Is there a branching factor of 4, 6, or 8 at each step?

Does the previous path to a given place affect the future path? In other words, if on my way from A to B via C, and I find 2 routes to B, one taking less time than the other, can I safely discard the previous route to B?

It's hexes. I can discard one of the paths, the path cost currently relies only on the previous and next hexes. I'm ignoring the harder problem of the fact that you can switch modes from 'foot' to train or sea or helicopter or plane sometimes. If you have some advice on articles that talk about that problem, I'd be interested, it seems a lot harder. This is a turn-based game, and you can only switch transportation modes at the beginning or end of a turn, depending on the mode you're switching to. For now, the pathfinding is used a turn at a time, so I don't see if there's an optimal path if it requires more than one turn to utilize it. Since these are not random maps, it works in most cases.

Quote:

Quote: It's possible to have 'Islands' where there is no connectivity, but generally the terrain is passable.

If you precompute the islands, then you can very quickly reject impossible paths. This means you can think more about the average case rather than the worse case. Even if the islands change, it's probably quick to recalculate them.

Agreed, it's on 'the list' of things to do.

Quote:

I don't think you need a heuristic here. I think you need to test. Run a few thousand random paths across a map, and plot a graph of open list size vs. path length. For simple maps, the open list size is proportional to the branching factor of each node, and for complex maps, it'll be proportional to the branching factor of each potential route, but you'll get a far better understanding of where your game lies between those extremes by testing than by analysis.

I can do that, I was hoping for some more robust way to do it, though. I want the queue size to be as small as possible to allow for fast operation, but I don't want to overflow it.

Has anyone done anything like start with a smaller 'average' queue size and resize it if it gets too big? I suppose that's a reasonable alternative.

Thanks,
Ralph Trickey
TOAW III Programmer

Quote: Original post by uncutno
think about this:

What if there is no path? Dont you want it to try all possible routs before giving up? If so, you need to store all nodes.

300 * 300 * 10 = 900kb, which is a small amount of memory when you get pathfinding in return...

uncutno,
Sorry, I keep forgetting that there are many ways to implement A*. I'm using 6 arrays. The open bit array, the closed bit array, one for g(path distance so far), one for the parent pointers and one for the distance between any point and the destination (probably not necessary, but it may speed things up. Thinking about it, that probably hurts, I only need the value in that one place.) And one single dimensioned array for the priority queue of open items. I want that queue to be as small as possible since it uses memmove to add items to it, and is called frequently, but I don't want to run out of space.

Path length is never going to be beyond about 200. Since it's less than the full size of the map, I think that the area that the path could potentially cover is something like drawing a line between the two points, and a line perpindicular to the middle of that line that's as far out as the 200-distance/2. That is, if the're 100 units apart, the line could deviate by a max of 50 distance from that line, but I can't make that leap to how many that means are possible in the open list.

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

I'm trying to not use memory allocation if at all possible, since this code is called many, many times.

Thanks,
Ralph Trickey
TOAW III Programmer

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.

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.

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.