I''m not clear on this, are your paths simply aesthetically unpleasing, or are you getting legitimately bad paths?

While this reference doesn't implement A* (but rather a 3D version of the Distance Transform algorithm), it does cover path planning in a binary space partition of the state space (in this case using an oct-tree)... so you might get some pointers out of it.

Williams, M and Jones, D. I.
"A Rapid Method for Planning Path in Three Dimensions for a Small Aerial Robot"
Robotica, 19 2001, pp125-135


As for your specific problem with costs, I suspect that the problem you are finding is caused by your discretisation of the state space into large boxes. If you use finer resolution, do you get the same sub-optimal paths (you should, but they should be less sub-optimal the finer the resolution).

If this is not the cause, then what are you using for a heuristic function?

Cheers,

Timkin

[edited by - Timkin on April 20, 2004 10:26:03 PM]

Ok, I can think of two changes you can make.

One, instead of considering new nodes for the A* at the center of the squares consider new nodes at the center of the borders of each square. If we take and number your diagram:

     -----------     |2        |     |         |------         ||1  .|         ||    |         |----------------|3   |4 . |5   ||    |    |    |---------------- 

Assuming you''re pathing from the dot in 1 to the dot in 4, you are currently taking the dot in 1 and comparing it to the center of 2 and the center of 3. So it jumps to 3 before 2. However, if you consider the distance from the dot to the midpoint of the 1-2 border and the 1-3 border, then the 1-2 border will win out and the algorithm will push through 2 first.

The other solution is examine the use of your heuristic: A* only works properly if the heuristic used is either exact or underestimating. If you use an overestimating herustic A* may not work properly. And using a herusitic that goes through the center of 2 when moving from 1 to 4 would be overestimating. So instead, consider only the horizontal or veritcal distance to the border to the next square. This allows you to continue using the quadtree nodes as nodes in A* instead of the midpoint of the borders in your search.

Actually the optimal way to deal with your problem is a slight extension of SiCrane''s suggstion. Optimally, you want to compute the path from one square to another based on the point of intersection between the two squares that minimises the path length from the entry point of the given node to the exit of the next node. However, given that these points are also interpolations, you need to solve a set of simultaneous linear equations (constraints) along the length of the path, with the start and end points being the constraints that close the system.

The sub-optimal approximation to this is as SiCrane described: simply use the midpoint of the edge as the interpolated point.

There''s a fair bit of literature on this sort of problem out their, particularly in robotics and deterministic path planning.

Cheers,

Timkin

I ran into this exact issues with a nav mesh implementation. The cost was based on the center of the poly, which easily overestimated.

I ended up converting it to use, the cost to enter the poly:

     -----------     |         |     |         |------         ||   1|         ||    |         |--------X-------|    Y  0 |    ||    |    |    |----------------

In this case, I use the cost from 0 to X and 0 to Y as the cost for entering. This still isn't perfect, as it overestimated because X isn't colinear with 0 and 1, but it does solve some of the significantly worse cases.

This is really the same solution SiCrane proposed. Just had to mention it again as it worked well for me.

A few thoughts:

1) Do a check for a straight line before you search. If an unobstructed line exists, you can go stright there.

2) Do a post search optimization pass to 'slide' waypoints along the borders of meshes. For instance, a waypoint at X would be slid to the left to be colinear with 0 and 1.

Edit: Attempted to clean up ascii art.

[edited by - BrianL on April 21, 2004 11:04:09 AM]

You can use an additional data param to get a better estimate of travel cost by taking into account the entering and exting nodes. Using a edge quadrant param which classifies an edge from A-H ( see image )

      A      B    ------------  H |     |    | C    |     |    |    |----------|   G |     |    | D    |     |    |    ------------      F     E

As you can see there are 8 possible edge classes. This can be represented within 3 bits. A small precalcuated table (64 entires) can capture all combinations of enter/exit nodes. By combing the enter and exit bits into a single param and indexing that into the precaulcated travel cost modifer table, it should give you a better estimation. Also a node can't have multiple edge classes, so just choose the lower cost edge.

So the travese estimate = estimiate_table[combine_param]*node_length;

This should produce the best performance, as the precalcuated table will fit in the cache and all the edge classes also be predetermined.

Good Luck!

-ddn[/source]

[edited by - ddn3 on April 21, 2004 7:11:15 PM]

[edited by - ddn3 on April 21, 2004 7:11:32 PM]

Taking your initial idea of using the centres, you can then optimise the route by checking to see if, for every node n, there is an unblocked route between it and node n+2, if there is, you can delete node n+1 and join up n and n+2. You can repeat it over and over until no further optimisations can be made.