[Freeciv-Dev] (PR#8872) RFC: design for nations_used

["Jason Short" <jdorje@xxxxxxxxxxxxxxxxxxxxx>]

<URL: http://rt.freeciv.org/Ticket/Display.html?id=8872 >

 From PR#8743:

 > [per@xxxxxxxxxxx - Sat May 15 23:32:25 2004]:
 >
 > On Sat, 15 May 2004, Raimar Falke wrote:
 > > >PACKET_NATIONS_SELECTED_INFO=9;sc,lsend
 > > >  UINT8 num_nations_used;
 > > > -NATION nations_used[MAX_NUM_PLAYERS:num_nations_used];
 > > > +NATION nations_used[MAX_NUM_ITEMS:num_nations_used];
 > > >end
 > >
 > > This looks like a mistake.
 >
 > No. We don't send the number of start positions here, we send an array of
 > all _deactivated_ nations.
 >
 > Quite inefficient, true. A bitvector would be far more appropriate. But I
 > just extended the current code a bit, so...

I started updating this part of the patch, and ran into the same bit of 
code.

This code is really overly ugly IMO.  I'm not even sure that I 
understand it.  In srv_main there is a function:

/*************************************************************************
  mark_nation_as_used() - shuffles the appropriate arrays to indicate that
  the specified nation number has been allocated to some player and is
  therefore no longer available to any other player.  We do things this way
  so that the process of determining which nations are available to AI 
players
  is more efficient.
*************************************************************************/
static int mark_nation_as_used (int nation)
{
   if (num_nations_avail <= 0) {        /* no more unused nation */
     die("Argh! ran out of nations!");
   }

    nations_used[nations_avail[num_nations_avail-1]]=nations_used[nation];
    nations_avail[nations_used[nation]]=nations_avail[--num_nations_avail];
    nations_used[nation]=-1;

    return nation;
}

The "allocation to AI players is more effecient" text I think is a bad 
goal.  With n players and m nations, allocation with the current method 
is O(n) [O(1) per player].  You pick a random nation for the player and 
do a lookup into the list of available nations.  Whereas with a bitfield 
array it is an O(mn) operation [O(m) per player], since you have to loop 
over the nation list to see which are unavailable.  Seems to me this is 
hardly a concern.

So the above packet currently lists the used nations.  All others can be 
assumed to be available.  However with the scenario improvements change 
any number of nations can be marked as unavailable.  Per's original 
patch kept the other code as it is and just extends the list.  This is 
an arbitrarily long list containing the ID of each used nation.  For 
some scenarios this will be almost all nations.  Clearly it would be 
better to use a boolean array here.  It's not too hard to change the 
network packet but changing the data structures is harder.

However there's yet another problem.  To lengthen this array Per has to 
put a hard limit on the number of nations.  Currently there is no such 
limit; you can put as many nations as you want in the ruleset.  Per 
imposes a limit of MAX_NUM_ITEMS here.  Now, if we impose any limit we 
also have to add a check to the ruleset code to avoid loading more than 
this many nations.  We should also call it MAX_NUM_NATIONS not 
MAX_NUM_ITEMS.  Moreover I don't think MAX_NUM_ITEMS is a good limit.  I 
don't think we should impose a limit for a paltry thing like network 
packet convenience (especially after all the work elsewhere to avoid 
such a limit).  And if we do impose a limit it should be bigger than 200 
(which is not really that many, once it is easier to add nations and 
with our current classification of nations system).

So what I propose is this:

- The nations_avail code in the server is made into simply a 
bitfield/boolean array.  This is at the cost of a little bit of speed 
when choosing AI player nations.

- Instead of sending a packet containing the used status of all nations, 
just send a single packet telling that a nation is unused.  This means 
for scenarios a lot of (tiny) packets must be sent out at the beginning. 
  But when a nation is chosen the new packet that is sent out is very 
small.  In most cases the network bandwidth used should be the same. 
And it means there is no need for a hard limit on the number of nations.

I haven't yet looked at the client code but I imagine it will be easy to 
deal with.

jason