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

[Kai Antweiler]

>  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.


>  I'm planning to implement an A* search, instead of
>  gradient hill clibing. That algorithm needs an heuristic map, that looks the 
> same
>  of a gradient (just a bit simper to calculate)

The gradient is very simple. We just tried to improve the calculation
speed by exploiting some geometry and
by guessing how the gradient develops most of the time.


>  The bad news is that A* is slower (altough the heuristic map being easier to 
> calculate
>  than the current gradient gives some hope that it won't be too slow).

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.
-- 
Kai Antweiler