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 _______________________________________________ glob2-devel mailing list [email protected] http://lists.nongnu.org/mailman/listinfo/glob2-devel
