Re: [glob2-devel] further direction for mars and months to come

[Marcos Dumay de Medeiros]

Em Ter 04 Mar 2008, Kai Antweiler escreveu:
> >  Ok, I've been mainly silent because I'm currently lacking time to work on 
> > it.
> >  I want to try a new pathfiding algorithm on the game.
> 
> Go ahead. It's fun!
> I joined that way too 2 years ago.

Thanks for the support.

> You can try, but A* is O(g*n^2) where "g" is the number of globs and n
> is the number of fields.
> Gradient is O(b*n) where "b" is the number of buildings and it is
> expected that "b" is a lot smaller than "g".
> I don't believe that you can write an algorithm that way that would be
> fast enough (especially for the 512x512 maps),
> but if you succeed, we probably could improve the gameplay.

Yeah, I am also afraid that is not possible. But that won't stop me from trying 
:)

I'm planning to reuse already calculated paths, and A* is only proportional to 
(g*n^2)
at the worst case, where there is no path available. I'm planning to detect 
that case most of
the times at the heuristic. So I still have some hope that it will be fast 
enough.

@Arsenault,
Gradient is not perfect. It may be the best we can do with the time constraint, 
but is not perfect.

[]'s
Marcos