Wondering if anyone can help!! =P Currently trying to implement A* using a non-uniform grid (ie the squares that make up the grid vary in size). The grid is made up of ''sectors'' which vary in size to each other(square or rectangular). Neighbouring sectors are connected by transitions between them, so these transitions can be narrow or very long. What''s the best way to calculate the costs (cost to and heuristic cost) from one sector to another? Using the center of sectors doesn''t work, since if you''re on the edge of a sector, it pulls you away from the destination, and you''ll possibly end up going a longer route. I hope I''m being clear! If not, I can send a diagram (can''t attach things to the post!) to you!!

Send a diagram to make absolutely sure we understand you. However...

If I understand you correctly, you should use the distance between the midpoints of the line segments that describe the connections between the cells. (if you imagine a door at each boundary, it would be the midpoint of the door)

I think MikeD used this approach and wrote about it in one of the Gems books.




My Website: ai-junkie.com My Book: AI Techniques for Game Programming

I''ve worked it out on paper, but found that if the transition between to cells is very long then the cost becomes very high using the midpoint.

For example, if there''s a transition running from north to south for about 10 meters, and the start pos is near the north-most end of it, and your destination vector is north of where you are (but oyu can''t go directly north, then that transition actually gives a greater heuristic cost as the midpoint is south of where the start position is.

I''ve thought about finding the closest point on the transition to the start position, but it ends up doing all kinds of nasty things to later heuristic calculations.

I''ll send a diagram to your email add with an example!

Thanks fup!!

Use Straight Line Distance (SLD) for your heuristic. Your actual path cost will depend on how you want your agents to move through the sectors. If the sectors are much larger than the agents then you might need to consider breaking them up into smaller segments - as in a navigation mesh - or using some other means of determinging waypoints for your search graph.

Timkin

If you wanted to be completely accurate, for a set of n transitions on a partly built graph you could calculate the point on transition n as being the point closest to the point on transition n - 1. The point on transition 1 (the first node expanded) would be the point closest to the start point. You could even offset the point on the line (presuming transitions were all lines) by the width of the agent, assuming that the agent would walk the most optimal route along the final path.
So, if you have the dining room connected to the kitchen connected to the front hall in your house and you're starting in the dining room and walking to the front hall. The point on the transition between the dining room and the kitchen would be the closest point on that transition from your start point in the dining room and the point used on the transition from the kitchen to the front hall would be the closest point on that transition to the transition point found between the dining room and the kitchen. So the transition points depend on the path found to date.

There are plenty of algorithms for finding the closest point on a line from a given point, with offset for radius. If you have trouble I could post some code here, if what I've said doesn't make sense I could even draw some diagrams .

As an addition, if you've calculated transition n + 1, the optimal point on the previous transition depends on this point as well. As you're walking from room A to room D through room B and C, the point on the transition from B to C that would be optimal is the one that comes closest to a line drawn between the transition from room A to room B and the transition from room C to room D. You could, in fact, recalculate every transition based on new knowledge of the route as each new node was expanded (this might cause a large or non-existent change in certain nodes along the path, depending on the entire route). This would, of course, be less optimal in CPU time but more optimal in heuristic calculation.

Mike

[edited by - MikeD on June 16, 2003 5:31:34 AM]

While I agree completely with Mike that what he proposed is a more optimal solution in terms of path length, it''s also more computationally expensive than general mesh methods. You could increase performance of his suggested method by utilising fixed transitions manually placed along the edges when you design your landscape. You can then either compute distances between transitions on the fly during run time (and hence evaluate path costs), or you can preprocess them offline and store the information for each sector in a look up table (matrix). The latter is a tradeoff of computation time during play for data load time (and memory requirement) at the start of the level.

Cheers,

Timkin

Thanks for all the help guys!

The transitions are actually overlapping into both sector, and are bounded by the edge cells that make up the sectors. I think I''ll try calculating the heuristic from the closest cell in the transition to the agent as Mike suggested!

Again, thanks!

I think the best plan is to be willing to experiment, as you obviously are, try a few ideas, play around with them and find the best cost/accuracy payoff. Timkin''s completely right when he says that my method is more expensive. It depends on the results you''re looking for, the size of the world and the number of path generations.

Mike

Love to experiment, but I''ve got to give a basic working demo next week Tuesday! (ARRGH!!) I''ve literally only been given a few weeks to totally re-do floorspace data and re-write the A* to work with it. I just looooove working to tight schedules... =P

Hmmm.... Just found the problem Mike talked about, about how once you expand a node (n) and then n+1, but find n+1 doesn''t work, and expand another n+1, then the point picked along transition n may not be the shortest route from n to the new n+1 anymore, and you''ll have to back propogate along all the previous nodes from n+1 to find the best places to cross the transitions.

Mike, I heard you have some good stuff on how to deal with this in one of your books. Is it easily available in bookstores, and if so, which shop would most likely have it in stock?

Cheers!

Dom