[Freeciv-Dev] Re: code optimization ideas

[Jules Bean <jmlb2@xxxxxxxxxxxxxxxx>]

Tony Stuckey wrote:
>         One problem is that a lot of the code is just stupid.
>         It will go to 13,27 and look at all 8 surrounding tiles.  Then it
> will go to 13,28 and look at all 8 surrounding tiles, many of which were
> just looked at.  Sometimes this happens multiple times.  This definitely
> happens in the pathfinding stuff, where calls to "is_enemy_unit_tile" and
> similar stuff *have* to be done to check ZOC issues when trying to move
> around.
> 
>         It's not clear to me that caching this data provides a real win,
> though, without making the code massively more convoluted.  Some of it is
> already convoluted enough to be scary.
> 
>         The real-time nature of the game doesn't help.  If Freeciv were
> strictly turn-based as all other Civs were, most of these issues would only
> change when you successfully attacked and killed an enemy.  As it is, a lot
> of calculations must be performed for each unit, because the world might
> have changed unexpectedly around you.

Excuse my slight ignorance here, I haven't perused the code in detail.

If ZOC is the only issue, then we can solve that by storing a set of
arrays which store ZOC information for each player.  Conceptually this
is a rectangular array of booleans, map-sized, with 'true' or 'false'
indicating if each player has ZOC on that square.  With byte-long
booleans, this takes (# players) * (map size) bytes - or 20K per player,
at maximum map-size.  This can be reduced by a factor of eight by
packing bits, but 20K per player is not that much, I wouldn't think.

If it was straightforwardly the case that every square is in at most one
person's ZOC, we could do better, but I believe that's not the case.

Then, we can account for the 'realtime' nature of the game by updating
these arrays instantly every time a piece moves.

My gut feeling tells me that this would be a real speed gain, but I
haven't checked the code to see exactly where the bottlenecks are.

Jules


-- 
/----------------+-------------------------------+---------------------\
|  Jelibean aka  | jules@xxxxxxxxxxxxxxx         |  6 Evelyn Rd        |
|  Jules aka     |                               |  Richmond, Surrey   |
|  Julian Bean   | jmlb2@xxxxxxxxxxxxxxxx        |  TW9 2TF *UK*       |
+----------------+-------------------------------+---------------------+
|  War doesn't demonstrate who's right... just who's left.             |
|  When privacy is outlawed... only the outlaws have privacy.          |
\----------------------------------------------------------------------/