Re: [glob2-devel] understanding pathfinding

[Linus Probert]

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