quote: Original post by Merrick
Just quickly, I''m going to take this opportunity to go slightly off-topic:

Why don''t you have your units head in a GENERAL direction towards their target, but only path to the places in their line of sight? It would seem more realistic, and not as heavy on the pathfinder.

This is really only more realistic if your units have no knowledge of the terrain. (ie, it is the first exploration) No intelligent entity is going to head north to get to where its going when it knows the only way through the mountains is to the east. Know what I mean?

So it would appear to me that your problem is not one of pathfinding, but rather one of replanning.

If you think of a path to walk as a set of movement commands - e.g., turn to heading theta and walk at a speed of V - then your units are executing plans that take them from a start state to a goal state. Pathfinding is just a very specialised form of planning that is implemented as search.

When your agents are executing their plan, the plan will be successful unless one or both of the following occurs: a) the outcome of a given action is not as predicted when creating the plan; and/or, b) the world has changed in such a way as to invalidate the plan.

In either of these cases, the plan is said to have broken. You will need to replan. This does not mean creating a whole new plan from the current state. Indeed, that sort of replanning is only necessary in the worst case scenario.

Before going down the ''new plan'' path, the better (and computationally cheaper alternative) is to try and repair the old plan. In other words, find the cheapest action sequence that gets from the broken state back in to a valid state of the plan. Obviously, you also want to choose a state that will not lead directly back to the same broken state. In terms of pathfinding, this might mean finding the shortest route around an obstacle to where the original ''path'' emerges on the other side.

The other alternative is to perform predictive replanning. This is quite tricky and requires a knowledge of the sorts of events that can take place in the world and their likelihood (probability). Whenever the agent obtains new information that the world is not as it was when it made its plan, it predicts the outcome of its current plan given this ''new world model''. It then alters its current plan (by either splicing in extra actions or finding a complete new plan where the former is not possible) before it arrives in the predicted broken state.

My suggestion for your problem is simply to repair your plan when it breaks. Here is one way to do it. Associated with the original plan is a section of the state space that the plan takes the agent through. The plan breaks when the path through this section of state space is ''blocked''. So, look ahead in the plan and compare it to the new state space (ie, the new world model) and find the first state that is not blocked. In terms of pathfinding, find the nearest point on the current path segment that is not blocked and then perform a search for a path from the current spot to that spot.

Computationally this will be far cheaper than performing a new search from your agents current state. Unfortunately, the downside is the the unit movement want ''look'' overly intelligent, in that it will insist on going to just the other side of the object before taking up its plan again. You can tweak this method a little by making your units cut corners where possible. This will tend to smooth out their path and make it look a little more intelligent.

I hope these thoughts have helped.

Good luck,

Timkin

quote: Original post by ragonastick
Repairing the path is something I hadn''t really considered, and doesn''t sound too difficult. Do you have any experience with this because I would like to know a few things, mainly about the end result.

Mmm, you could say that I have some experience with replanning. It''s the basis of my PhD research in which I developed some of the ideas I mentioned in my previous post. My domain was a lot tougher though - that of a fully autonomous robotic aircraft performing meteorologial reconnaisance.

quote: Original post by ragonastick
What I *think* will end up happening is that if you have a group of agents all moving from near point A to point B, then there will be a lot of repairing and shuffling at the start, and then they will assume a kind of single file line. If that is the case, I might just try and calculate one path and tell the other agents to follow the leader.

How you get units to move relative to each other depends on whether you intentionally group them or not. My suggestion here is - that given you expect lots of obstacles - implement a flocking behaviour to ''coordinate'' movement of several units at once. The general path they follow can be determined by your planning algorithm.

Now, let''s consider the problem of the ''destroyed wall''. First of all, you have an ''event'' occuring that changes the world. This can be used as a trigger for considering whether replanning is necessary or not. You have some things to think about if you choose to consider replanning after an event. What you do will depend on how the event affected the world. If the event altered the state space so as to block the path, then you will need to consider what I wrote in my previous post. If however the event ''opened up'' a region of the state space (as in your example) then you need to consider two actions: 1) Perform the whole pathfinding task again, or 2) ask whether the current path can be ''improved''. As you have already seen, the first option is computationally expensive when considered against the timeframe for replanning. The second option is far less so.

The path can be improved if any set of segments of the path can be replaced by a shorter (read cheaper cost) segment. If the path is defined by a set of waypoints (which can be set as the locales of the end of actions) then you can do the following. Starting at the current location (call it point S) and skipping the next waypoint in the plan sequence, check to see if there exists a path from S to each successive waypoint. If such a path exists to waypoint wi, that has lower cost (or shorter distance if cost is a linear function of distance travelled), then set the next waypoint to be wi and delete all intervening waypoints. Iterate this procedure over all waypoints, remembering that the set of waypoints needs to be updated as soon as a shorter segment is found.


Good luck,

Timkin

Here is a bit of a ''weirder'' insight into a possible solution:

-Unit plans out path. Along that path (each movement increment) this unit actually places an invisible ''waypoint'' object. If a waypoint already exists somewhere along his path; this unit just adds his name or id or whatever.

-As your unit moves along his path, when he begins to head towards the next waypoint, he requests control of it, if he succeeds in controlling it; he moves towards it. If not, he can either re-calculate his path; or attempt to find another path. When he is not able to gain control of the waypoint; that means another unit already has control of it. After he leaves the waypoint, he relinquishes his control, and removes his name from the list. If all names or ids are removed from the waypoint, it can be deleted.

So far; that basically solves the multiple units along a similar or interesecting paths. If you let the units just wait until they can gain control of a waypoint; they will end up either falling into a line (if they are on the same path); or they will display coordinating behavior.

-As far as the dynamic ''collisions''; when the collision occurs, simply find the nearest waypoint(s), and send a message to each unit listed on that waypoint; whereas at that time they re-calculate their path.

The one problem I foresee with this solution is if your waypoints are fairly distanced and not aligned on common boundaries(i.e. not grid-like). If this is the case; you still may end up with various units running into each other; or paths from one waypoint to another being blocked. If this is the case; a possible solution would be to lock a ''box'' of waypoints off each movement. For example; lock all waypoints within a radius of the target waypoint.

Kind of a weird solution; but I think it may work out for you.

-mihkael