[Freeciv-Dev] Re: goto algoritm

[Falk Hueffner <falk.hueffner@xxxxxxxxxxxxxxxxxxxxxxxx>]

Thue Janus Kristensen <thue@xxxxxxx> writes:

> On Thu, 08 Jun 2000, Falk Hueffner wrote:
> > Thue Janus Kristensen <thue@xxxxxxx> writes:
> > 
> > > Btw, if anyone wants to really improve the goto algoritm and warmap
> > > generation for land units (x1.5 to x2 maybe) they should look replace the
> > > queue with a priority queue.
> > 
> > I am really considering doing this. It would probably even speed up
> > gotos to allow realtime sketching of the way taken on the map like in
> > civctp, sometimes a nice feature.
> > 
> > If only we were using C++... I'm not exactly eager to write a priority
> > queue myself...
> > 
> > BTW which would be the functions to replace? do_unit_goto and
> > find_the_shortest_path?
> > 
> >     Falk
> 
> find_the_shortest_path() and really_generate_warmap()

Uh, that's what I meant :)

> As to realtime sketching the current algoritm is fine for that
> already, but it would require the code to be moved to /common (not a
> bad thing) and for changes in how the goto work, ie optionally
> saving a goto instead of recalculation each turn (not a bad thing
> either).

I think this would be bad. For example, if I build an additional road
that a unit with a goto could use, it should.

For client realtime sketching, really_generate_warmap would be more
useful, I think, to save time when the mouse is moved to another
square. So two variants would be needed, one that finds any best path,
and one that finds them all for the AI to evaluate. The latter would
be a lot slower, because if it takes n moves to the goal, we must
investigate *all* squares up to distance n, because they might be
connected to the goal by railroad (*mutters something about how
railoads destroy all the nice and nifty algoritms*).

>   Also, we would need to save the whole path of the goto in > the
>   server and savegame (not too hard).

> Are you sure there isn't a GPL'ed priority queue available
> somewhere? But maybe we would wan't to make our own anyway.

There surely is, but likely with type abstraction, which is extremely
clumsy in C (see genlists) and not needed in our case. It's also not
very hard to code, I've some code for a heap lying around. One
question is whether to use dynamic reallocation, but it seems just
statically allocating the space worked fine and didn't matter too
much. I am also not sure it is actually faster for the "find all
paths" variant, since you need to swap around some additional data for
each queue element.

                Falk