I actually opposed a master thesis on this last year. It was an
extreemely interesting presentation and he who did the work had actually
created a really nice algorithm that worked in areas with obstacles and
other moving objects in the area.
If I can recall it correctly his algorithm itterated all objects that
where meant to move and reserved their next space. Meaning after a space
had been reserved no other object could move to that space. After that
itteration was done all the objects moved to their next space.
I'm not sure how it handled the ordering but in the presentation we got
to see a graphical example of this algorithm and i worked beautifully.
For example if an object was blocking the only path to the goal of
another object this object would take a step out of the way to let the
object pass.
Thus even non moving characters had to reserve their space. I think I
still have a copy of the report if you would like to read it. Although
it was pretty heavy reading if I may say so myself but it was really cool.
Send me an email if you want a copy.
/Linus
On 03/28/2011 05:56 PM, Stéphane Magnenat wrote:
Hi Jannis,
You can think of the gradient as a pre-processing step for A*. Using
the gradient, and considering that there are no dynamic obstacle, the
pathfinding is optimal. When areas become crowded, the assumption of
no obstacle is not true as other globules cannot be considered as
transient obstacles and the whole pathfinding system collapses, hence
the jams.
It is not easy to solve this in general with a low-processing load.
That said, glob2 is so old that sometimes what was once intractable is
now possible, and adding to global gradients local gradients that are
recomputed on jams events could solve the problem. One could then
assign globule either to the global or to the jam gradients, in such a
way that the jam get solved. This is interesting.
There is a large and vivid community focused on the questions of
pathfinding in robotics. You might have a look on google scholar for
such papers (search for path planning).
Have a nice day,
Stéphane
_______________________________________________
glob2-devel mailing list
[email protected]
http://lists.nongnu.org/mailman/listinfo/glob2-devel
