Complete.Org: Mailing Lists: Archives: freeciv-dev: September 2000:
[Freeciv-Dev] Re: client goto & patrol v2
Home

[Freeciv-Dev] Re: client goto & patrol v2

[Top] [All Lists]

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index] [Thread Index]
To: thue@xxxxxxx
Cc: freeciv-dev@xxxxxxxxxxx
Subject: [Freeciv-Dev] Re: client goto & patrol v2
From: Gaute B Strokkenes <gs234@xxxxxxxxx>
Date: 24 Sep 2000 02:33:07 +0200

Gaute B Strokkenes <gs234@xxxxxxxxx> writes:

> Thue <thue@xxxxxxx> writes:
> 
> What limitations?  Or, put another way, how severe are these
> limitations?
> 
> > Should I just ignore that problem and consider the network ideal?
> 
> I suppose it's unlikely to become a practical problem right now, but
> you'll have to deal with it sooner or later, if this multiple
> connection thingie catches on...
> 
> > Is it ideal in this respect?
> 
> Frog knows.  Maybe you could tag the packets with connection number.
> 
> > Any ideas as to how to get around the problem?
> 
> Well, any (that is, most ;-) tiles have got exactly eight neighbours.
> Thus, assuming that all goto routes are from adjacent tile to adjacent
> tile, you could pack each step into only 3 bits, which is a lot
> shorter than two shorts (32 bits?)

Looking at the latest version of your patch that I could find in the
archieves, this is actually sent as an array of struct map_position,
which means that you're sending 8 bytes per step.  Yikes.  I'd suggest
something like:

    int dx, dy, index;

    dx = newx - oldx + 1; /* 0, 1, 2 */
    dy = newy - oldy + 1; /* 0, 1, 2 */

    assert(-1 <= dx && dx <= 1); /* Don't leap. */
    assert(-1 <= dy && dy <= 1);
    assert(dx || dy); /* Don't stand still. */

    index = dy * 3 + dx - 1; /* 0 - 7 */

Note that you'll have to do something about x (and, in the future, y)
wrapping.  Then you could encode this with something along the lines
of:

    int byte1 = 0, byte2 = 0, byte3 = 0;

    #define PUT_INDEX(bitno, index) \
      { \
        if (index & 1) { \
          byte1 |= 1 << bitno; \
        } \
        if (index & 2) { \
          byte2 |= 1 << bitno; \
        } \
        if (index & 4) { \
          byte3 |= 1 << bitno; \
        } \
      }

    #define GET_INDEX(bitno, index) \
      { \
        index = 0; \
        if (byte1 & (1 << bitno)) { \
          index += 1; \
        } \
        if (byte2 & (1 << bitno)) { \
          index += 2; \
        } \
        if (byte3 & (1 << bitno)) { \
          index += 4; \
        } \
      }

    dx = ((index + 1) % 3) - 1;
    dy = ((index + 1) / 3) - 1;

I'm sure you get the idea.  It doesn't address the fundamental problem
of fixed limits, but it does give you a 64 to 3 compression rate[0],
which is pretty good.  That'll give you a lot more elbow-room before
you hit a the limit.  All this bit-fiddling probably takes a bit of
time, but then on the other hand you don't have to worry about
endianness or byte-swapping.

[0] 8 steps in 3 bytes versus 3/8 of a step in 3 bytes.

-- 
Big Gaute (not to be confused with LG)
Yow!  Now we can become alcoholics!



[Prev in Thread] Current Thread [Next in Thread]