sys/src/games/packet.c

   1 #include <u.h>
   2 #include <libc.h>
   3 #include <thread.h>
   4 #include <draw.h>
   5 #include <mouse.h>
   6
   7 #define minx -1.0
   8 #define maxx 1.0
   9 #define miny -1.0
  10 #define maxy 1.0
  11
  12 double speedOff = 0.001;
  13 double decay = 0.99;
  14 double speedBonus = 0.001;
  15 int regenRate = 5;
  16 double thickFactor = 0.01;
  17 double dispThresh = 0.001;
  18 #define ncolours 200
  19 int nnode = 40;
  20
  21 typedef struct Pos Pos;
  22 typedef struct List List;
  23 typedef struct Node Node;
  24 typedef struct Pack Pack;
  25
  26 struct Pos
  27 {
  28         double x, y;
  29 };
  30
  31 struct List
  32 {
  33         void *next, *prev;
  34 };
  35
  36 struct Node
  37 {
  38         Pos;
  39         int die, ref, targref;
  40 };
  41
  42 struct Pack
  43 {
  44         List;
  45         Pos;
  46         int targ, p, q;
  47         double λ, v;
  48         Image *c;
  49 };
  50
  51 Node *nodes;
  52 Pack plist;
  53 Mousectl *mctl;
  54 double *dist, *path, *speed, *speedn;
  55 int *nextn;
  56 Image *col[ncolours];
  57 Image *grey;
  58
  59 void *
  60 emallocz(int size)
  61 {
  62         void *v;
  63
  64         v = mallocz(size, 1);
  65         if(v == nil)
  66                 sysfatal("malloc: %r");
  67         setmalloctag(v, getcallerpc(&size));
  68         return v;
  69 }
  70
  71 Point
  72 convert(Pos* p)
  73 {
  74         return (Point){
  75                 screen->r.min.x + (screen->r.max.x - screen->r.min.x) *
  76                 ((p->x - minx) / (maxx - minx)),
  77                 screen->r.min.y + (screen->r.max.y - screen->r.min.y) *
  78                 ((p->y - minx) / (maxx - minx))};
  79 }
  80
  81 Pos
  82 deconvert(Point p)
  83 {
  84         return (Pos){
  85                 minx + (maxx - minx) *
  86                 ((double)(p.x - screen->r.min.x) / (screen->r.max.x - screen->r.min.x)),
  87                 miny + (maxy - miny) *
  88                 ((double)(p.y - screen->r.min.y) / (screen->r.max.y - screen->r.min.y))};
  89 }
  90
  91 void
  92 rect(Pos *p, int size, Image *col)
  93 {
  94         Point poi;
  95         Rectangle r;
  96
  97         poi = convert(p);
  98         r = insetrect(Rpt(poi, poi), -size);
  99         draw(screen, r, col, nil, ZP);
 100 }
 101
 102 List *
 103 add(List *head, List *obj)
 104 {
 105         obj->prev = head->prev;
 106         obj->next = head;
 107         ((List*)head->prev)->next = obj;
 108         head->prev = obj;
 109         return obj;
 110 }
 111
 112 List *
 113 unlink(List *obj)
 114 {
 115         ((List*)obj->prev)->next = obj->next;
 116         ((List*)obj->next)->prev = obj->prev;
 117         return obj;
 118 }
 119
 120 void
 121 calcdist(void)
 122 {
 123         int i, j;
 124         double dx, dy;
 125
 126         dist = realloc(dist, sizeof(*dist) * nnode * nnode);
 127         path = realloc(path, sizeof(*path) * nnode * nnode);
 128         nextn = realloc(nextn, sizeof(*nextn) * nnode * nnode);
 129         for(i = 0; i < nnode; i++)
 130                 for(j = 0; j < nnode; j++){
 131                         if(nodes[j].die == 2){
 132                                 dist[i * nnode + j] = Inf(1);
 133                                 continue;
 134                         }
 135                         dx = nodes[i].x - nodes[j].x;
 136                         dy = nodes[i].y - nodes[j].y;
 137                         dist[i * nnode + j] = sqrt(dx * dx + dy * dy);
 138                 }
 139 }
 140
 141 u32int
 142 randomcol(void)
 143 {
 144         int c[3] = {0, 255, 0};
 145         int *j, t;
 146
 147         c[2] = rand() % 256;
 148         j = c + rand() % 3;
 149         t = c[2];
 150         c[2] = *j;
 151         *j = t;
 152         if(rand()%2){
 153                 t = c[1];
 154                 c[1] = c[0];
 155                 c[0] = t;
 156         }
 157         return (c[0] << 24) | (c[1] << 16) | (c[2] << 8) | 0xFF;
 158 }
 159
 160 void
 161 createstuff(void)
 162 {
 163         int i;
 164         plist.next = &plist;
 165         plist.prev = &plist;
 166
 167         for(i = 0; i < ncolours; i++)
 168                 col[i] = allocimage(display, Rect(0, 0, 1, 1), screen->chan, 1, randomcol());
 169         grey = allocimage(display, Rect(0, 0, 1, 1), screen->chan, 1, 0x888888FF);
 170
 171         nodes = emallocz(sizeof(*nodes) * nnode);
 172         for(i = 0; i < nnode; i++){
 173                 nodes[i].x = frand() * (maxx - minx) + minx;
 174                 nodes[i].y = frand() * (maxy - miny) + miny;
 175         }
 176         calcdist();
 177         speed = emallocz(sizeof(*speed) * nnode * nnode);
 178         speedn = emallocz(sizeof(*speedn) * nnode * nnode);
 179 }
 180
 181 void
 182 resizespeed(int diff)
 183 {
 184         int nnode1, i, j;
 185
 186         nnode1 = nnode - diff;
 187         speedn = realloc(speedn, sizeof(*speedn) * nnode * nnode);
 188         for(i = 0; i < nnode; i++)
 189                 for(j = 0; j < nnode; j++)
 190                         if(i < nnode1 && j < nnode1)
 191                                 speedn[i * nnode + j] = speed[i * nnode1 + j];
 192                         else
 193                                 speedn[i * nnode + j] = 0;
 194         speed = realloc(speed, sizeof(*speedn) * nnode * nnode);
 195         memcpy(speed, speedn, sizeof(*speedn) * nnode * nnode);
 196 }
 197
 198 void
 199 createpacket(void)
 200 {
 201         Pack *p;
 202
 203         p = emallocz(sizeof(*p));
 204         do{
 205                 p->q = rand() % nnode;
 206                 p->targ = rand() % nnode;
 207         }while(p->q == p->targ || nodes[p->q].die || nodes[p->targ].die);
 208         nodes[p->q].ref++;
 209         nodes[p->targ].targref++;
 210         p->p = -1;
 211         p->Pos = nodes[p->q].Pos;
 212         p->c = col[rand() % ncolours];
 213         add(&plist, p);
 214 }
 215
 216 int
 217 getpath(int i, int j)
 218 {
 219         int k;
 220
 221         i *= nnode;
 222         while((k = nextn[i + j]) != j)
 223                 j = k;
 224         return j;
 225 }
 226
 227 void
 228 floyd(void)
 229 {
 230         int i, j, k;
 231         double a, *b;
 232
 233         for(i = 0; i < nnode; i++)
 234                 for(j = 0; j < nnode; j++){
 235                         path[i * nnode + j] = dist[i * nnode + j] / (speedOff + speed[i * nnode + j]);
 236                         nextn[i * nnode + j] = j;
 237                 }
 238         for(k = 0; k < nnode; k++)
 239                 for(i = 0; i < nnode; i++)
 240                         for(j = 0; j < nnode; j++){
 241                                 a = path[i * nnode + k] + path[k * nnode + j];
 242                                 b = path + i * nnode + j;
 243                                 if(a < *b){
 244                                         *b = a;
 245                                         nextn[i * nnode + j] = k;
 246                                 }
 247                         }
 248 }
 249
 250 void
 251 createnode(Pos p)
 252 {
 253         int i, j;
 254
 255         j = nnode;
 256         for(i = 0; i < nnode; i++){
 257                 if(nodes[i].Pos.x == p.x && nodes[i].Pos.y == p.y)
 258                         return;
 259                 if(nodes[i].die == 3 && j == nnode)
 260                         j = i;
 261         }
 262         if(j == nnode){
 263                 nodes = realloc(nodes, sizeof(*nodes) * ++nnode);
 264                 resizespeed(1);
 265         }
 266         nodes[j].Pos = p;
 267         nodes[j].die = 0;
 268         nodes[j].ref = 0;
 269         nodes[j].targref = 0;
 270         calcdist();
 271         floyd();
 272 }
 273
 274 Pack *
 275 advancepacket(Pack *p)
 276 {
 277         Pack *n;
 278         Node *np, *nq;
 279
 280         if(p->p == -1){
 281                 p->p = p->q;
 282                 p->q = getpath(p->q, p->targ);
 283                 nodes[p->q].ref++;
 284                 p->λ = 0;
 285                 p->v = (speedOff + speed[p->p * nnode + p->q]) / dist[p->p * nnode + p->q];
 286         }else{
 287                 p->λ += p->v;
 288                 if(p->λ >= 1){
 289                         speedn[p->p * nnode + p->q] += speedBonus;
 290                         speedn[p->q * nnode + p->p] += speedBonus;
 291                         nodes[p->p].ref--;
 292                         p->p = -1;
 293                         if(p->q == p->targ){
 294                                 n = p->next;
 295                                 nodes[p->q].ref--;
 296                                 nodes[p->q].targref--;
 297                                 free(unlink(p));
 298                                 return n;
 299                         }
 300                         p->Pos = nodes[p->q].Pos;
 301                         return p->next;
 302                 }
 303         }
 304         np = nodes + p->p;
 305         nq = nodes + p->q;
 306         p->x = np->x * (1 - p->λ) + nq->x * p->λ;
 307         p->y = np->y * (1 - p->λ) + nq->y * p->λ;
 308         return p->next;
 309 }
 310
 311 long sync;
 312
 313 void
 314 timing()
 315 {
 316         for(;;){
 317                 semrelease(&sync, 1);
 318                 sleep(25);
 319         }
 320 }
 321
 322 void
 323 simstep(void)
 324 {
 325         static int regen;
 326         Pack *p;
 327         int i, j;
 328
 329         for(p = plist.next; p != &plist; )
 330                 p = advancepacket(p);
 331         for(i = 0; i < nnode; i++){
 332                 if(nodes[i].die == 1 && nodes[i].targref == 0){
 333                         nodes[i].die++;
 334                         calcdist();
 335                 }
 336                 if(nodes[i].die == 2 && nodes[i].ref == 0){
 337                         nodes[i].die++;
 338                         for(j = 0; j < nnode; j++)
 339                                 speedn[i * nnode + j] = speedn[i + j * nnode] = 0;
 340                 }
 341         }
 342         for(i = 0; i < nnode * nnode; i++)
 343                 speed[i] = speedn[i] *= decay;
 344         floyd();
 345         if(regen-- == 0){
 346                 regen = rand() % regenRate;
 347                 createpacket();
 348                 createpacket();
 349         }
 350 }
 351
 352 void
 353 domouse(void)
 354 {
 355         static Mouse m;
 356         int lastbut;
 357         double dx, dy, d;
 358         int i;
 359         Point poi;
 360
 361         if(nbrecv(mctl->resizec, &i) == 1)
 362                 if(getwindow(display, Refnone) < 0)
 363                         sysfatal("getwindow: %r");
 364         lastbut = m.buttons;
 365         nbrecv(mctl->c, &m);
 366         if(lastbut & 4 && !(m.buttons & 4))
 367                 for(i = 0; i < nnode; i++){
 368                         poi = convert(&nodes[i]);
 369                         dx = poi.x - m.xy.x;
 370                         dy = poi.y - m.xy.y;
 371                         d = sqrt(dx * dx + dy * dy);
 372                         if(d < 5){
 373                                 nodes[i].die = 1;
 374                                 break;
 375                         }
 376                 }
 377         if(lastbut & 1 && !(m.buttons & 1))
 378                 createnode(deconvert(m.xy));
 379 }
 380
 381 void
 382 usage(void)
 383 {
 384         fprint(2, "USAGE: %s options\n", argv0);
 385         fprint(2, " -n number of nodes [40]\n");
 386         fprint(2, " -o speed of unused connections [0.001]\n");
 387         fprint(2, " -d decay rate [0.99]\n");
 388         fprint(2, " -b speed bonus per packet [0.001]\n");
 389         fprint(2, " -r packet generation period [5]\n");
 390         fprint(2, " -t line thickness factor [0.01]\n");
 391         fprint(2, " -T display threshold [0.001]\n");
 392         exits("usage");
 393 }
 394
 395 void
 396 threadmain(int argc, char **argv)
 397 {
 398         Node *n;
 399         Pack *p;
 400         int i, j;
 401
 402         ARGBEGIN{
 403         case 'n': nnode = atoi(EARGF(usage())); break;
 404         case 'o': speedOff = atof(EARGF(usage())); break;
 405         case 'd': decay = atof(EARGF(usage())); break;
 406         case 'b': speedBonus = atof(EARGF(usage())); break;
 407         case 'r': regenRate = atoi(EARGF(usage())); break;
 408         case 't': thickFactor = atof(EARGF(usage())); break;
 409         case 'T': dispThresh = atof(EARGF(usage())); break;
 410         default: usage();
 411         }ARGEND;
 412
 413         initdraw(nil, nil, nil);
 414         mctl = initmouse(nil, screen);
 415         srand(time(0));
 416         createstuff();
 417         floyd();
 418         proccreate(timing, nil, mainstacksize);
 419         for(;;){
 420                 domouse();
 421                 draw(screen, screen->r, display->white, nil, ZP);
 422                 for(i = 0; i < nnode; i++)
 423                         for(j = 0; j < i; j++)
 424                                 if(speed[i * nnode + j] >= dispThresh)
 425                                         line(screen, convert(nodes + i), convert(nodes + j), 0, 0, speed[i * nnode + j] / thickFactor, display->black, ZP);
 426                 for(n = nodes; n < nodes + nnode; n++)
 427                         if(!n->die || n->ref)
 428                                 rect(n, 3, n->die ? grey : display->black);
 429                 for(p = plist.next; p != &plist; p = p->next)
 430                         rect(p, 2, p->c);
 431                 flushimage(display, 1);
 432                 simstep();
 433                 semacquire(&sync, 1);
 434         }
 435 }