Now I had done for my PathFinding ( with smoothing ) But if the distance was too long, it got much more cost in Pathfinding. I tried to do this in Mid-Point ( which can divid the path be several segment ), but I have no idea how to avoid the unit to search back to his original location? any best way to solve this problem ? Thanks , and sorry for my poor English...

quote:Original post by Jonoson
Now I had done for my PathFinding ( with smoothing )
But if the distance was too long, it got much more cost in Pathfinding. I tried to do this in Mid-Point ( which can divid the path be several segment ), but I have no idea how to avoid the unit to search back to his original location? any best way to solve this problem ?

Thanks , and sorry for my poor English...

I''m not sure I understand what you are wanting to do, so I''ll guess and offer a suggestion that
might work with regards to that guess.

I think you have found a path, but for some reason the distance is too long, and now you want
a shorter version of that path, that ends at (or near) the mid-point of that path.

If this is what you want to do, then the following may help you. If this is not what you want
to do, then perhaps you will have to explain your problem again.

When you first find your path (the one that becomes too long) then save the steps along the
path (along with their distances) into an array or list. When you discover the original path
is too long, and then want the mid-point version, then use the total distance to calculate what
the mid-point distance would be, and iterate through the array or the list, to reach that step
that just exceeds the mid-point distance.

Good luck,

Eric

Like Eric I am not sure of the exact nature of the question however I suspect he has interpreted correctly. I would like to respond with another suggestion though that will avoid needless planning.

In order to do planning we need a starting state (start), an end state (goal), a set of possible actions, a metric (measure) for finding distance between states and a cost/utility function of the metric. We have all that we need to determine if the path length is going to be too long (computationally expensive to compute). We might do this if we wish to spend only a given amount of computational effort on path segments which might occur if we are splitting pathfinding over several frame updates of our game.

If you are concerned that the path length between two states is too long then you can test this before planning by computing the cost of travelling on a straight line from the start to the goal. In general, this straight line will not be a spatial one, but in pathfinding it will be. This cost will be the actual cost or an underestimate of the actual cost to go from the start to the goal. If this cost is greater than some threshold you set then you can set a sub-goal (a midpoint) and recompute your cost to this point. When the cost estimate is under your threshold, perform the planning operation. To that midpoint.

To choose the subgoal (midpoint) you must consider that before planning, we do not know the optimal path from the start to the goal, so it will be by pure luck that we happen to choose a sub-goal (midpoint) that lies on the optimal path if we do it randomly or choose the point that lies half way between the start and end on the straight line between them.

One way to deal with this problem is the following...

Consider a perpendicular bisector of the start and goal. That is, if you take a straight line (chord) between these two points, a perpendicular bisector is a line that intersects the chord at the midpoint of the chord and is perpendicular to it.

Now consider a set of points evenly distributed on this bisector. For each point compute the cost of a straight line from the start to that point. Take the average of all such costs. This is an estimate of the average cost of travelling from the start point to the bisector. Use this as your cost estimate of travelling from the start point to the midpoint. If it is higher than the threshold repeat the process.

When it comes time to plan, you need to select a point on the perpendicular bisector that lies on or close to the optimal path from start to goal. We know that this optimal path must pass through the bisector. Again though, choosing the appropriate point to set as the sub-goal is not strictly possible without further information. However, choosing any point on the bisector that has path cost (from start to that point) that is less than the average cost to get to the bisector, is a good policy to follow. Choosing the minimum cost point does not ensure that you will find the optimum path from start to goal, but only the optimum path from start to goal that passes through the various sub-goals.

Here is some pseudo-code for the above algorithm... (you could probably implement this recursively but I haven''t bothered to work out the procedure for it yet)

(note: SL_Cost(A,B) is the straight line cost between points A and B)


// description: This function returns a point B close enough to A
// so as to ensure that the cost of travelling from A to B is
// less than a given threshold cost

function getSubGoal(A,B)
{
subgoal <-- B
averageCost <-- SL_Cost(A,B)
while averageCost > threshold
| find perpendicular bisector of (A,subgoal)
| point[] <-- uniformly distributed points on bisector
| for each point
| | compute SL_Cost(A,point)
| | add cost to sum
| | if cost < lowest cost remember point
| ---
| averageCost <-- sum / number of points
| subgoal <-- point with lowest cost
---
return subgoal
}


Hope this helps... if it wasn''t what you were looking for, sorry to take up your bandwidth!

Tim

Actually, I think what he means is that if the distance between the start and the end of the path is too long, then it takes too long to actually calculate the path, so he wants to calculate only half of the path, and then start travelling along that while he is calculating the rest (so it doesn''t take too long before the unit starts moving)

The best way to do this (this is how I would do it, at least) is to divide your map up into chunks (depending on how fast your path-finding is, you may make fairly big chunks or fairly small ones)

Anyway, in each of these chunks, you store "connectivity" information, ie, which chunks they connect to, and at what points they connect.

Then, the first thing you do when finding a path is to look at these chunks for an "overall" path, that is, you say "I''ll go to chunk A first, then C, then D - which is where I want to end up".

Then, you have the problem broken up in such a way that you have three separate paths to find. That is, the path from the start to the A/C chunk boundary, then from the A/C boundary to the C/D boundary and finally from the C/D boundary to the end point. Since you can then restrict your path to be within those chunks only, just calculate the start -> A/C boundary first, then start following that path. While that''s happening, calculate the A/C -> C/D path. When you hit the A/C boundary, you''ve got the next part of the path all ready to go. While you''re on that path, calculate the C/D -> endpoint path.

I hope you can follow my description...

Anyway, this won''t always find the best path, but it''ll find a more "direct" one, which may seem more natural anyway.

War Worlds - A 3D Real-Time Strategy game in development.

Hi, it''s me . First , I''m sorry for my fuzzy question that made you guys confused. Dean Harding means right that it takes too long cost, so I tried to divide onto several sub-path in mid-point.

One friend had suggested that way which Dean Harding said above to slove this problem. But what about the worst case if the obstacles surround the unit that made the unit have to go backward before he walk forward the the goal ? ( Uh, actually I''m poor in English ) ... For example which following :

. means Grid
* means obstacle
X means the Unit
G means the Goal

.............
............. section A
...*.....*...
===*=====*=== The bourdary of section ( chrunk ) A and B
...*..X..*...
...*.....*...
...*.....*... section B
...*.....*...
===*=====*=== The bourdary of section ( chrunk ) B and C
...*******...
............. section C
......G......
.............

That''s my question. IF every grid means more than 1 thousand tiles ( shown with . in the mini-map ) , in other words, if it''s impossible to tried every tiled in the area which the obstacles surround, then basicly follow the algorithm, it would go to the bourdary of section B and C first, in next search, it would get block and calculate the new mid-point in the bourdary of section A and B.

so what about then ? follow the algorithm, it could just walk repeatly between the two bourdary again and again. Make larger section (chrunk )? ... Maybe there are more obstacle surrounded.

I hope you guys can understand what I''m asking...uh, I got to study English more hardly...
Besides, thanks a lot.

Ouch!!! I forgot that I can''t paint in this forum because of the font....
you guys may copy the map and paste into Note.

quote:Original post by Jonoson
But what about the worst case if the obstacles surround the unit that made the unit have to go backward before he walk forward the the goal ?

Any general planning algorithm - and in particular pathfinding - should contain a cost function that, given a segment of path, returns the cost to travel that path segment. Hence, if you''re unit is surrounded on three of four sides, then the path cost of exiting the area via one of those directions is infinite, while the path cost for the fourth side is a finite number. Since the aim of the pathfinding search is to find a path of minimal cost, then your search algorithm should easily determine what to do in this case.

BTW: The algorithm I gave above is similar to a dynamic version of the grid/mesh method that Dean talked about. The standard mesh approach is to treat the region you are trying to find a path in as a graph structure and use Dijkstra''s algorithm to find the shortest path between any two nodes.

Of course, now that you have cleared up the confusion I had regarding your question, might I suggest you investigate dynamic planning methods. Essentially the problem you are trying to solve has been solved in the domain of mobile (ground based) robots. In particular, check out the work done at the University of Michigan''s AI laboratory or simply do a web search on replanning/dynamic planning.

Good luck,

Tim