forest-net
an overlay networks for large-scale virtual worlds
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator
Avatar-save.cpp
1 
10 #include "stdinc.h"
11 #include "Forest.h"
12 #include "Avatar.h"
13 #include <string>
14 #include <algorithm>
15 
16 using namespace forest;
17 
40 int main(int argc, char *argv[]) {
41  ipa_t myIpAdr, cliMgrIpAdr;
42  comt_t firstComt, lastComt;
43  uint32_t finTime;
44  if (argc != 9 ||
45  (myIpAdr = Np4d::ipAddress(argv[1])) == 0 ||
46  (cliMgrIpAdr = Np4d::ipAddress(argv[2])) == 0 ||
47  sscanf(argv[4],"%d", &firstComt) != 1 ||
48  sscanf(argv[5],"%d", &lastComt) != 1 ||
49  sscanf(argv[8],"%d", &finTime) != 1)
50  fatal("usage: Avatar myIpAdr cliMgrIpAdr walls "
51  "firstComt lastComt uname pword finTime");
52  Avatar avatar(myIpAdr,firstComt,lastComt);
53  string uname = string(argv[6]);
54  string pword = string(argv[7]);
55  char* wallsFile = argv[3];
56  if (!avatar.init(cliMgrIpAdr,uname,pword,wallsFile))
57  fatal("Avatar:: initialization failure");
58  avatar.run(1000000*finTime);
59 }
60 
61 namespace forest {
62 
69 Avatar::Avatar(ipa_t mipa, comt_t fc, comt_t lc)
70  : myIp(mipa), firstComt(fc), lastComt(lc) {
71  int nPkts = 10000;
72  ps = new PacketStore(nPkts+1, nPkts+1);
73  mySubs = new set<int>();
74  nearAvatars = new HashSet(MAXNEAR);
75  visibleAvatars = new HashSet(MAXNEAR);
76  myVisSet = new set<int>;
77 
78  numNear = numVisible = 0;
79  seqNum = 0;
80  switchState = IDLE;
81 }
82 
83 Avatar::~Avatar() {
84  delete mySubs; delete nearAvatars; delete ps; delete [] walls;
85  delete myVisSet;
86  if (sock >= 0) close(sock);
87  if (listenSock >= 0) close(listenSock);
88 }
89 
93 bool Avatar::init(ipa_t cmIpAdr, string& uname, string& pword,
94  char *wallsFile) {
95  Misc::getTime(); // starts clock running
96 
97  // open and configure forest socket
98  sock = Np4d::datagramSocket();
99  if (sock<0 || !Np4d::bind4d(sock,myIp,0) || !Np4d::nonblock(sock)) {
100  cerr << "Avatar::init: could not open/configure forest "
101  "socket\n";
102  return false;
103  }
104 
105  // open and configure listen socket
106  listenSock = Np4d::streamSocket();
107  if (listenSock < 0 || !Np4d::bind4d(listenSock,myIp,0) ||
108  !Np4d::listen4d(listenSock) || !Np4d::nonblock(listenSock)) {
109  cerr << "Avatar::init: could not open/configure external "
110  "socket\n";
111  return false;
112  }
113  connSock = -1; // connection socket for listenSock
114  // -1 means not connected
115  string s;
116  cout << "listen socket: " << Np4d::ip2string(myIp,s)
117  << "/" << Np4d::getSockPort(listenSock) << endl;
118  cout.flush();
119 
120  // login and setup walls
121  if (!login(cmIpAdr, uname, pword)) return false;
122  if (!setupWalls(wallsFile)) return false;
123  // initialize avatar to a random position
124  srand(myAdr);
125  while (true) {
126  x = randint(0,GRID*worldSize-1);
127  y = randint(0,GRID*worldSize-1);
128  if (!(walls[groupNum(x,y)-1]&4)) break;
129  }
130  direction = (double) randint(0,359);
131  deltaDir = 0;
132  speed = MEDIUM;
133 
134  return true;
135 }
136 
143 bool Avatar::login(ipa_t cmIpAdr, string uname, string pword) {
144  // open socket to client manager
145 cerr << "logging in\n";
146  int loginSock = Np4d::streamSocket();
147  if (loginSock < 0 ||
148  !Np4d::bind4d(loginSock, myIp, 0) ||
149  !Np4d::connect4d(loginSock,cmIpAdr,Forest::CM_PORT)) {
150  cerr << "Avatar::login: cannot open/configure socket to "
151  "ClientMgr\n";
152  return false;
153  }
154  // start login dialog
155  string s = "Forest-login-v1\nlogin: " + uname +
156  "\npassword: " + pword + "\nover\n";
157 cerr << "login string " << s << endl;
158  Np4d::sendString(loginSock,s);
159  NetBuffer buf(loginSock,1024);
160  string s0, s1, s2;
161  if (!buf.readLine(s0) || s0 != "success" ||
162  !buf.readLine(s1) || s1 != "over") {
163  return false;
164  }
165 
166  // proceed to new session dialog
167  s = "newSession\nover\n";
168  Np4d::sendString(loginSock,s);
169 
170  // process reply - expecting my forest address
171  if (!buf.readAlphas(s0) || s0 != "yourAddress" || !buf.verify(':') ||
172  !buf.readForestAddress(s1) || !buf.nextLine())
173  return false;
174  myAdr = Forest::forestAdr(s1.c_str());
175 
176  // continuing - expecting info for my forest access router
177  int port;
178  if (!buf.readAlphas(s0) || s0 != "yourRouter" || !buf.verify(':') ||
179  !buf.verify('(') || !buf.readIpAddress(s1) || !buf.verify(',') ||
180  !buf.readInt(port) || !buf.verify(',') ||
181  !buf.readForestAddress(s2) || !buf.verify(')') || !buf.nextLine())
182  return false;
183  rtrIp = Np4d::getIpAdr(s1.c_str());
184  rtrPort = (ipp_t) port;
185  rtrAdr = Forest::forestAdr(s2.c_str());
186 
187  // continuing - expecting address of comtree controller
188  if (!buf.readAlphas(s0) || s0 != "comtCtlAddress" || !buf.verify(':') ||
189  !buf.readForestAddress(s1) || !buf.nextLine())
190  return false;
191  ccAdr = Forest::forestAdr(s1.c_str());
192 
193  // continuing - expecting connection nonce
194  if (!buf.readAlphas(s0) || s0 != "connectNonce" || !buf.verify(':') ||
195  !buf.readInt(nonce) || !buf.nextLine())
196  return false;
197  if (!buf.readLine(s0) || (s0 != "over" && s0 != "overAndOut"))
198  return false;
199 
200  close(loginSock);
201 
202  cout << "avatar address=" << Forest::fAdr2string(myAdr,s) << endl;
203  cout << "router info= (" << Np4d::ip2string(rtrIp,s) << ",";
204  cout << rtrPort << "," << Forest::fAdr2string(rtrAdr,s) << ")\n";
205  cout << "comtCtl address=" << Forest::fAdr2string(ccAdr,s) << "\n";
206  cout << "nonce=" << nonce << endl;
207  return true;
208 }
209 
215 bool Avatar::setupWalls(const char *wallsFile) {
216  ifstream ifs(wallsFile);
217  if (ifs.fail()) {
218  cerr << "setupWalls: cannot open walls file\n";
219  return false;
220  }
221  int y = 0; walls = NULL;
222  bool horizRow = true;
223  while(ifs.good()) {
224  string line;
225  getline(ifs,line);
226  if (walls == NULL) {
227  worldSize = line.size()/2;
228  y = worldSize-1;
229  try {
230  walls = new char[worldSize*worldSize];
231  } catch(exception& e) {
232  cerr << "setupWalls: could not allocate space "
233  "for walls array (worldSize="
234  << worldSize << ")\n" << endl;
235  perror("");
236  exit(1);
237  }
238  } else if ((int) line.size()/2 != worldSize) {
239  cerr << "setupWalls: format error, all lines must have "
240  "same length\n";
241  return false;
242  }
243  for(int xx = 0; xx < 2*worldSize; xx++) {
244  int pos = y * worldSize + xx/2;
245  if (horizRow) {
246  if (!(xx&1)) continue;
247  if (line[xx] == '-') walls[pos] |= 2;
248  continue;
249  }
250  if (xx&1) {
251  if (line[xx] == 'x') walls[pos] |= 4;
252  } else if (line[xx] == '|') walls[pos] |= 1;
253  }
254  horizRow = !horizRow;
255  if (horizRow) y--;
256  if (y < 0) break;
257  }
258  return true;
259 }
260 
266 void Avatar::computeVisSet(int g1, set<int>& vSet) {
267  int x1 = (g1-1)%worldSize; int y1 = (g1-1)/worldSize;
268  vSet.clear();
269  vSet.insert(g1);
270 
271  bool *visVec = new bool[worldSize];
272  bool *prevVisVec = new bool[worldSize];
273 
274  // start with upper right quadrant
275  prevVisVec[0] = true;
276  int dlimit = min(worldSize,MAX_VIS);
277  for (int d = 1; d <= dlimit; d++) {
278  bool done = true;
279  for (int x2 = x1; x2 <= min(x1+d,worldSize-1); x2++) {
280  int y2 = d + y1 - (x2 - x1);
281  if (y2 >= worldSize) continue;
282  int dx = x2-x1;
283  visVec[dx] = false;
284  if ((x1==x2 && !prevVisVec[dx]) ||
285  (x1!=x2 && y1==y2 && !prevVisVec[dx-1]) ||
286  (x1!=x2 && y1!=y2 && !prevVisVec[dx-1] &&
287  !prevVisVec[dx])) {
288  continue;
289  }
290  int g2 = 1 + x2 + y2*worldSize;
291 
292  if (isVis(g1,g2)) {
293  visVec[dx] = true;
294  vSet.insert(g2);
295  done = false;
296  }
297  }
298  if (done) break;
299  for (int x2 = x1; x2 <= min(x1+d,worldSize-1); x2++) {
300  prevVisVec[x2-x1] = visVec[x2-x1];
301  }
302  }
303  // now process upper left quadrant
304  prevVisVec[0] = true;
305  for (int d = 1; d <= dlimit; d++) {
306  bool done = true;
307  for (int x2 = x1; x2 >= max(x1-d,0); x2--) {
308  int dx = x1-x2;
309  int y2 = d + y1 - dx;
310  if (y2 >= worldSize) continue;
311  visVec[dx] = false;
312  if ((x1==x2 && !prevVisVec[dx]) ||
313  (x1!=x2 && y1==y2 && !prevVisVec[dx-1]) ||
314  (x1!=x2 && y1!=y2 && !prevVisVec[dx-1] &&
315  !prevVisVec[dx])) {
316  continue;
317  }
318  int g2 = 1 + x2 + y2*worldSize;
319  if (isVis(g1,g2)) {
320  visVec[dx] = true;
321  vSet.insert(g2);
322  done = false;
323  }
324  }
325  if (done) break;
326  for (int x2 = x1; x2 >= max(x1-d,0); x2--) {
327  int dx = x1-x2;
328  prevVisVec[dx] = visVec[dx];
329  }
330  }
331  // now process lower left quadrant
332  prevVisVec[0] = true;
333  for (int d = 1; d <= dlimit; d++) {
334  bool done = true;
335  for (int x2 = x1; x2 >= max(x1-d,0); x2--) {
336  int dx = x1-x2;
337  int y2 = (y1 - d) + dx;
338  if (y2 < 0) continue;
339  visVec[dx] = false;
340  if ((x1==x2 && !prevVisVec[dx]) ||
341  (x1!=x2 && y1==y2 && !prevVisVec[dx-1]) ||
342  (x1!=x2 && y1!=y2 && !prevVisVec[dx-1] &&
343  !prevVisVec[dx])) {
344  continue;
345  }
346  int g2 = 1 + x2 + y2*worldSize;
347  if (isVis(g1,g2)) {
348  visVec[dx] = true;
349  vSet.insert(g2);
350  done = false;
351  }
352  }
353  if (done) break;
354  for (int x2 = x1; x2 >= max(x1-d,0); x2--) {
355  int dx = x1-x2;
356  prevVisVec[dx] = visVec[dx];
357  }
358  }
359  // finally, process lower right quadrant
360  prevVisVec[0] = true;
361  for (int d = 1; d <= dlimit; d++) {
362  bool done = true;
363  for (int x2 = x1; x2 <= min(x1+d,worldSize-1); x2++) {
364  int dx = x2-x1;
365  int y2 = (y1 - d) + dx;
366  if (y2 < 0) continue;
367  visVec[dx] = false;
368  if ((x1==x2 && !prevVisVec[dx]) ||
369  (x1!=x2 && y1==y2 && !prevVisVec[dx-1]) ||
370  (x1!=x2 && y1!=y2 && !prevVisVec[dx-1] &&
371  !prevVisVec[dx])) {
372  continue;
373  }
374  int g2 = 1 + x2 + y2*worldSize;
375  if (isVis(g1,g2)) {
376  visVec[dx] = true;
377  vSet.insert(g2);
378  done = false;
379  }
380  }
381  if (done) break;
382  for (int x2 = x1; x2 <= min(x1+d,worldSize-1); x2++) {
383  int dx = x2-x1;
384  prevVisVec[dx] = visVec[dx];
385  }
386  }
387  delete [] visVec; delete [] prevVisVec;
388 }
389 
400 void Avatar::run(uint32_t finishTime) {
401  connect(); // send initial connect packet
402  uint32_t now; // free-running us clock
403  uint32_t nextTime; // time of next operational cycle
404  uint32_t lastComtSwitch; // last time a comt switched
405 
406  now = nextTime = Misc::getTime();
407  uint32_t comtSwitchTime = now+1;
408  comt = 0;
409 
410  bool waiting4switch = false;
411  while (finishTime == 0 || now <= finishTime) {
412  //reset hashtables and report
413  numNear = nearAvatars->size(); nearAvatars->clear();
414  numVisible = visibleAvatars->size(); visibleAvatars->clear();
415 
416  // check for a command from driver and process it
417  // if not yet connected, check4command attempts an accept
418  comt_t newComt = check4command();
419  if (newComt != 0 && newComt != comt) {
420  startComtSwitch(newComt,now);
421  waiting4switch = true;
422  }
423 
424  now = Misc::getTime();
425  pktx px;
426  while ((px = receive()) != 0) {
427  Packet& p = ps->getPacket(px);
428  Forest::ptyp_t ptyp = p.type;
429  if (waiting4switch) {
430  // pass client signalling packets to
431  // completeComtSwitch and discard all others
432  if (ptyp == Forest::CLIENT_SIG) {
433  waiting4switch =
434  !completeComtSwitch(px,now);
435  }
436  ps->free(px); continue;
437  }
438  if (ptyp != Forest::CLIENT_DATA) { // ignore other packets
439  ps->free(px); continue;
440  }
441  // process status reports from other avatars
442  // and forward to driver for this avatar
443  updateNearby(px);
444  if (connSock >= 0) {
445  uint64_t key = p.srcAdr;
446  key = (key << 32) | p.srcAdr;
447  bool isVis = visibleAvatars-> member(key);
448  forwardReport(now, (isVis ? 2 : 3), px);
449  }
450  ps->free(px);
451  }
452  // check for timeout
453  waiting4switch = !completeComtSwitch(0,now);
454 
455  if (!waiting4switch) {
456  updateStatus(now); // update Avatar status
457  sendStatus(now); // send status on comtree
458  updateSubs(); // update subscriptions
459  if (connSock >= 0) {
460  // send "my" status to driver
461  forwardReport(now, 1);
462 
463  } else if (comt == 0 ||
464  now-comtSwitchTime < ((unsigned) 1)<<31) {
465  // switch comtrees if not connected to driver
466  lastComtSwitch = now;
467  comt_t newComt = randint(firstComt, lastComt);
468  if (comt != newComt) {
469  startComtSwitch(newComt,now);
470  waiting4switch = true;
471  }
472  comtSwitchTime = now + randint(10,30)*1000000;
473  }
474  }
475 
476  // update time and wait for next cycle
477  nextTime += 1000*UPDATE_PERIOD;
478  now = Misc::getTime();
479  useconds_t delay = nextTime - now;
480  if (delay < ((uint32_t) 1) << 31) usleep(delay);
481  else nextTime = now + 1000*UPDATE_PERIOD;
482  }
483  disconnect(); // send final disconnect packet
484 }
485 
492 void Avatar::startComtSwitch(comt_t newComt, uint32_t now) {
493  nextComt = newComt;
494  if (comt != 0) {
495  unsubscribeAll();
496  send2comtCtl(CtlPkt::CLIENT_LEAVE_COMTREE);
497  switchState = LEAVING;
498  switchTimer = now; switchCnt = 1;
499  } else {
500  comt = nextComt;
501  send2comtCtl(CtlPkt::CLIENT_JOIN_COMTREE);
502  switchState = JOINING;
503  switchTimer = now; switchCnt = 1;
504  }
505 }
506 
519 bool Avatar::completeComtSwitch(pktx px, uint32_t now) {
520  if (switchState == IDLE) return true;
521  if (px == 0 && now - switchTimer < SWITCH_TIMEOUT)
522  return false; // nothing to do in this case
523  switch (switchState) {
524  case LEAVING: {
525  if (px== 0) {
526  if (switchCnt > 3) { // give up
527  cerr << "completeSwitch: failed while "
528  "attempting to leave " << comt
529  << " (timeout)" << endl;
530  comt = 0; switchState = IDLE; return true;
531  }
532  // try again
533  send2comtCtl(CtlPkt::CLIENT_LEAVE_COMTREE,RETRY);
534  switchTimer = now; switchCnt++;
535  return false;
536  }
537  Packet& p = ps->getPacket(px);
538  CtlPkt cp(p.payload(),p.length - Forest::OVERHEAD);
539  cp.unpack();
540  if (cp.type == CtlPkt::CLIENT_LEAVE_COMTREE) {
541  if (cp.mode == CtlPkt::POS_REPLY) {
542  comt = nextComt;
543  send2comtCtl(CtlPkt::CLIENT_JOIN_COMTREE);
544  switchState = JOINING;
545  switchTimer = now; switchCnt = 1;
546  return false;
547  } else if (cp.mode == CtlPkt::NEG_REPLY) { // give up
548  cerr << "completeSwitch: failed while "
549  "attempting to leave " << comt
550  << " (request rejected)" << endl;
551  comt = 0; switchState = IDLE; return true;
552  }
553  }
554  return false; // ignore anything else
555  }
556  case JOINING: {
557  if (px == 0) {
558  if (switchCnt > 3) { // give up
559  cerr << "completeSwitch: failed while "
560  "attempting to join " << comt
561  << " (timeout)" << endl;
562  comt = 0; switchState = IDLE; return true;
563  }
564  // try again
565  send2comtCtl(CtlPkt::CLIENT_JOIN_COMTREE,RETRY);
566  switchTimer = now; switchCnt++;
567  return false;
568  }
569  Packet& p = ps->getPacket(px);
570  CtlPkt cp(p.payload(),p.length - Forest::OVERHEAD);
571  cp.unpack();
572  if (cp.type == CtlPkt::CLIENT_JOIN_COMTREE) {
573  if (cp.mode == CtlPkt::POS_REPLY) {
574  subscribeAll();
575  switchState = IDLE; return true;
576  } else if (cp.mode == CtlPkt::NEG_REPLY) { // give up
577  cerr << "completeSwitch: failed while "
578  "attempting to join " << comt
579  << " (request rejected)" << endl;
580  comt = 0; switchState = IDLE; return true;
581  }
582  }
583  return false; // ignore anything else
584  }
585  default: break;
586  }
587  return false;
588 }
589 
594 void Avatar::sendStatus(int now) {
595  if (comt == 0) return;
596  pktx px = ps->alloc();
597  Packet& p = ps->getPacket(px);
598  p.length = 4*(5+8); p.type = Forest::CLIENT_DATA; p.flags = 0;
599  p.comtree = comt; p.srcAdr = myAdr; p.dstAdr = -groupNum(x,y);
600 
601  uint32_t *pp = p.payload();
602  pp[0] = htonl(STATUS_REPORT);
603  pp[1] = htonl(now);
604  pp[2] = htonl(x);
605  pp[3] = htonl(y);
606  pp[4] = htonl((uint32_t) direction);
607  pp[5] = htonl((uint32_t) speed);
608  pp[6] = htonl(numVisible);
609  pp[7] = htonl(numNear);
610  send(px);
611 }
612 
621 void Avatar::forwardReport(uint32_t now, int avType, pktx px) {
622  if (comt == 0) return;
623  uint32_t buf[10];
624  buf[0] = htonl((uint32_t) now);
625  buf[8] = htonl((uint32_t) comt);
626  buf[9] = htonl(avType);
627  if (avType == 1) { // send report for this avatar
628  buf[1] = htonl((uint32_t) myAdr);
629  buf[2] = htonl((uint32_t) x);
630  buf[3] = htonl((uint32_t) y);
631  buf[4] = htonl((uint32_t) direction);
632  buf[5] = htonl((uint32_t) speed);
633  buf[6] = htonl((uint32_t) numVisible);
634  buf[7] = htonl((uint32_t) numNear);
635  } else if (px != 0) {
636  Packet& p = ps->getPacket(px);
637  uint32_t *pp = p.payload();
638  if (p.comtree != comt) return;
639 
640  buf[1] = htonl(p.srcAdr);
641  buf[2] = pp[2];
642  buf[3] = pp[3];
643  buf[4] = pp[4];
644  buf[5] = pp[5];
645  buf[6] = pp[6];
646  buf[7] = pp[7];
647  } else {
648  return;
649  }
650  int nbytes = NUM_ITEMS*sizeof(uint32_t);
651  char *bp= (char *) buf;
652  while (nbytes > 0) {
653  int n = write(connSock, (void *) bp, nbytes);
654  if (n < 0) fatal("Avatar::forwardReport: failure in write");
655  bp += n; nbytes -= n;
656  }
657 }
658 
663 void Avatar::send2comtCtl(CtlPkt::CpType joinLeave, bool retry) {
664  pktx px = ps->alloc();
665  if (px == 0)
666  fatal("Avatar::send2comtCtl: no packets left to allocate");
667  Packet& p = ps->getPacket(px);
668  if (!retry) seqNum++;
669  CtlPkt cp(joinLeave,CtlPkt::REQUEST,seqNum,p.payload());
670  cp.comtree = comt;
671  cp.ip1 = myIp;
672  cp.port1 = Np4d::getSockPort(sock);
673  int len = cp.pack();
674  if (len == 0)
675  fatal("Avatar::send2comtCtl: control packet packing error");
676  p.length = Forest::OVERHEAD + len;
677  p.type = Forest::CLIENT_SIG; p.flags = 0;
678  p.comtree = Forest::CLIENT_SIG_COMT;
679  p.srcAdr = myAdr; p.dstAdr = ccAdr;
680  p.pack();
681  send(px);
682 }
683 
703 comt_t Avatar::check4command() {
704  if (connSock < 0) {
705  connSock = Np4d::accept4d(listenSock);
706  if (connSock < 0) return 0;
707  if (!Np4d::nonblock(connSock))
708  fatal("can't make connection socket nonblocking");
709  bool status; int ndVal = 1;
710  status = setsockopt(listenSock,IPPROTO_TCP,TCP_NODELAY,
711  (void *) &ndVal,sizeof(int));
712  if (status != 0) {
713  cerr << "setsockopt for no-delay failed\n";
714  perror("");
715  exit(1);
716  }
717  }
718  char buf[5];
719  int nbytes = read(connSock, buf, 5);
720  if (nbytes < 0) {
721  if (errno == EAGAIN) return 0;
722  fatal("Avatar::check4command: error in read call");
723  } else if (nbytes == 0) { // remote display closed connection
724  close(connSock); connSock = -1;
725  unsubscribeAll();
726  return 0;
727  } else if (nbytes < 5) {
728  fatal("Avatar::check4command: incomplete command");
729  }
730  char cmd = buf[0];
731  uint32_t param = ntohl(*((int*) &buf[1]));
732  switch (cmd) {
733  case 'j': direction -= 10;
734  if (direction < 0) direction += 360;
735  break;
736  case 'l': direction += 10;
737  if (direction > 360) direction -= 360;
738  break;
739  case 'i': if (speed == STOPPED) speed = SLOW;
740  else if (speed == SLOW) speed = MEDIUM;
741  else if (speed == MEDIUM) speed = FAST;
742  break;
743  case 'k': if (speed == FAST) speed = MEDIUM;
744  else if (speed == MEDIUM) speed = SLOW;
745  else if (speed == SLOW) speed = SLOW;
746  break;
747  case 'c': return param;
748  }
749  return 0;
750 }
751 
755 bool Avatar::connect() {
756  pktx px = ps->alloc();
757  Packet& p = ps->getPacket(px);
758 
759  p.payload()[0] = htonl((uint32_t) (nonce >> 32));
760  p.payload()[1] = htonl((uint32_t) (nonce & 0xffffffff));
761  p.length = Forest::OVERHEAD + 8; p.type = Forest::CONNECT; p.flags = 0;
762  p.comtree = Forest::CONNECT_COMT;
763  p.srcAdr = myAdr; p.dstAdr = rtrAdr;
764 
765  int resendTime = Misc::getTime();
766  int resendCount = 1;
767  while (true) {
768  int now = Misc::getTime();
769  if (now > resendTime) {
770  if (resendCount > 3) { ps->free(px); return false; }
771  send(px);
772  resendTime += 1000000;
773  resendCount++;
774  }
775  int rx = receive();
776  if (rx == 0) { usleep(100000); continue; }
777  Packet& reply = ps->getPacket(rx);
778  bool status = (reply.type == Forest::CONNECT &&
779  reply.flags == Forest::ACK_FLAG);
780  ps->free(px); ps->free(rx);
781  return status;
782  }
783 }
784 
787 bool Avatar::disconnect() {
788  pktx px = ps->alloc();
789  Packet& p = ps->getPacket(px);
790 
791  p.payload()[0] = htonl((uint32_t) (nonce >> 32));
792  p.payload()[1] = htonl((uint32_t) (nonce & 0xffffffff));
793  p.length = Forest::OVERHEAD + 8; p.type = Forest::DISCONNECT;
794  p.flags = 0; p.comtree = Forest::CONNECT_COMT;
795  p.srcAdr = myAdr; p.dstAdr = rtrAdr;
796 
797  int resendTime = Misc::getTime();
798  int resendCount = 1;
799  while (true) {
800  int now = Misc::getTime();
801  if (now > resendTime) {
802  if (resendCount > 3) { ps->free(px); return false; }
803  send(px);
804  resendTime += 1000000;
805  resendCount++;
806  }
807  int rx = receive();
808  if (rx == 0) { usleep(100000); continue; }
809  Packet& reply = ps->getPacket(rx);
810  bool status = (reply.type == Forest::DISCONNECT &&
811  reply.flags == Forest::ACK_FLAG);
812  ps->free(px); ps->free(rx);
813  return status;
814  }
815 }
816 
819 void Avatar::send(pktx px) {
820  Packet& p = ps->getPacket(px);
821  p.pack();
822 //string s;
823 //cerr << "sending to (" << Np4d::ip2string(rtrIp,s) << "," << rtrPort << ")\n";
824 //cerr << p.toString(s);
825  int rv = Np4d::sendto4d(sock,(void *) p.buffer, p.length,
826  rtrIp, rtrPort);
827  if (rv == -1) fatal("Avatar::send: failure in sendto");
828  ps->free(px);
829 }
830 
833 int Avatar::receive() {
834  pktx px = ps->alloc();
835  if (px == 0) return 0;
836  Packet& p = ps->getPacket(px);
837 
838  ipa_t remoteIp; ipp_t remotePort;
839  int nbytes = Np4d::recvfrom4d(sock, p.buffer, 1500,
840  remoteIp, remotePort);
841  if (nbytes < 0) {
842  if (errno == EWOULDBLOCK) {
843  ps->free(px); return 0;
844  }
845  fatal("Avatar::receive: error in recvfrom call");
846  }
847  p.unpack();
848 //string s;
849 //cerr << "received from (" << Np4d::ip2string(remoteIp,s) << "," << remotePort << ")\n";
850 //cerr << p.toString(s);
851  if ((p.type == Forest::CLIENT_SIG &&
852  p.comtree != Forest::CLIENT_SIG_COMT) &&
853  p.comtree != comt) {
854  ps->free(px);
855  return 0;
856  }
857  p.bufferLen = nbytes;
858  p.tunIp = remoteIp;
859  p.tunPort = remotePort;
860 
861  return px;
862 }
863 
869 void Avatar::updateStatus(uint32_t now) {
870  const double PI = 3.141519625;
871 
872  int prevRegion = groupNum(x,y)-1;
873 
874  if (connSock >= 0) { // if there's a driver, stop on collision
875  double dist = speed;
876  double dirRad = direction * (2*PI/360);
877  int x1 = x + (int) (dist * sin(dirRad));
878  int y1 = y + (int) (dist * cos(dirRad));
879  int postRegion = groupNum(x1,y1)-1;
880  if (x1 <= 0 || x1 >= GRID*worldSize-1 ||
881  y1 <= 0 || y1 >= GRID*worldSize-1 ||
882  (prevRegion != postRegion &&
883  (walls[postRegion]&4 ||
884  separated(prevRegion,postRegion)))) {
885  speed = STOPPED;
886  } else {
887  x = x1; y = y1;
888  if (postRegion != prevRegion) updateVisSet();
889  }
890  return;
891  }
892 
893  // remainder for case of no driver
894  bool atLeft = (prevRegion%worldSize == 0);
895  bool atRight = (prevRegion%worldSize == worldSize-1);
896  bool atBot = (prevRegion/worldSize == 0);
897  bool atTop = (prevRegion/worldSize == worldSize-1);
898  int xd = x%GRID; int yd = y%GRID;
899  if (xd < .25*GRID && (atLeft || walls[prevRegion]&1 ||
900  walls[prevRegion-1]&4)) {
901  // near left edge of prevRegion
902  if (direction >= 270 || direction < 20) direction += 20;
903  if (160 < direction && direction < 270) direction -= 20;
904  speed = SLOW; deltaDir = 0;
905  } else if (xd > .75*GRID && (atRight || walls[prevRegion+1]&1 ||
906  walls[prevRegion+1]&4)) {
907  // near right edge of prevRegion
908  if (340 < direction || direction <= 90) direction -= 20;
909  if (90 < direction && direction < 200) direction += 20;
910  speed = SLOW; deltaDir = 0;
911  } else if (yd < .25*GRID && (atBot || walls[prevRegion-worldSize]&2 ||
912  walls[prevRegion-worldSize]&4)) {
913  // near bottom of prevRegion
914  if (70 < direction && direction <= 180) direction -= 20;
915  if (180 < direction && direction < 290) direction += 20;
916  speed = SLOW; deltaDir = 0;
917  } else if (yd > .75*GRID && (atTop || walls[prevRegion]&2 ||
918  walls[prevRegion+worldSize]&4)) {
919  // near top of prevRegion
920  if (0 <= direction && direction < 110) direction += 20;
921  if (250 < direction && direction <= 359) direction -= 20;
922  speed = SLOW; deltaDir = 0;
923  } else {
924  // no walls to avoid, so just make random
925  // changes to direction and speed
926  direction += deltaDir;
927  double r;
928  if ((r = randfrac()) < 0.1) {
929  if (r < .05) deltaDir -= 0.2 * randfrac();
930  else deltaDir += 0.2 * randfrac();
931  deltaDir = min(1.0,deltaDir);
932  deltaDir = max(-1.0,deltaDir);
933  }
934  // update speed
935  if ((r = randfrac()) <= 0.1) {
936  if (speed == SLOW || speed == FAST) speed = MEDIUM;
937  else if (r < 0.05) speed = SLOW;
938  else speed = FAST;
939  }
940  }
941  // update position using adjusted direction and speed
942  if (direction < 0) direction += 360;
943  if (direction >= 360) direction -= 360;
944  double dist = speed;
945  double dirRad = direction * (2*PI/360);
946  x += (int) (dist * sin(dirRad));
947  y += (int) (dist * cos(dirRad));
948  int postRegion = groupNum(x,y)-1;
949  if (postRegion != prevRegion) updateVisSet();
950 }
951 
957 bool Avatar::separated(int c0, int c1) {
958  if (c0 > c1) { int temp = c1; c1 = c0; c0 = temp; }
959  if (c0/worldSize == c1/worldSize) // same row
960  return walls[c1]&1;
961  else if (c0%worldSize == c1%worldSize) // same column
962  return walls[c0]&2;
963  else if (c0%worldSize > c1%worldSize) { // se/nw diagonal
964  if ((walls[c0]&3) == 3 ||
965  (walls[c0]&1 && walls[c1+1]&1) ||
966  (walls[c0]&2 && walls[c0-1]&2) ||
967  (walls[c1+1]&1 && walls[c0-1]&2))
968  return true;
969  else
970  return false;
971  } else { // sw/ne diagonal
972  if ((walls[c0]&2 && walls[c0+1]&1) ||
973  (walls[c0+1]&1 && walls[c1]&1) ||
974  (walls[c0]&2 && walls[c0+1]&2) ||
975  (walls[c0+1]&2 && walls[c1]&1))
976  return true;
977  else
978  return false;
979  }
980 }
981 
987 int Avatar::groupNum(int x1, int y1) {
988  return 1 + (x1/GRID) + (y1/GRID)*worldSize;
989 }
990 
996 bool Avatar::isVis(int g1, int g2) {
997  int sq1 = g1-1; int sq2 = g2-1;
998 
999  int x1 = sq1%worldSize; int y1 = sq1/worldSize;
1000  int x2 = sq2%worldSize; int y2 = sq2/worldSize;
1001 
1002  if (x1 > x2) { // swap so x1 <= x2
1003  int x = x1; x1 = x2; x2 = x;
1004  int y = y1; y1 = y2; y2 = y;
1005  }
1006 
1007  if (x1 == x2) {
1008  int lo = min(y1, y2); int hi = max(y1, y2);
1009  for (int y = lo; y < hi; y++) {
1010  if (walls[x1 + y*worldSize] & 2) return false;
1011  }
1012  return true;
1013  } else if (y1 == y2) {
1014  for (int x = x1+1; x <= x2; x++) {
1015  if (walls[x + y1*worldSize] & 1) return false;
1016  }
1017  return true;
1018  }
1019 
1020  const double eps = .001;
1021  double sq1xs[] = {x1+eps, x1+(1.0-eps),x1+eps,x1+(1.0-eps)};
1022  double sq1ys[] = {y1+(1.0-eps),y1+(1.0-eps),y1+eps,y1+eps };
1023  double sq2xs[] = {x2+eps, x2+(1.0-eps),x2+eps,x2+(1.0-eps)};
1024  double sq2ys[] = {y2+(1.0-eps),y2+(1.0-eps),y2+eps,y2+eps };
1025 
1026  int miny = min(y1,y2); int maxy = max(y1,y2);
1027  double slope = (y2-y1)/((double) x2-x1);
1028 
1029  for (int i = 0; i < 4; i++) {
1030  for (int j = 0; j < 4; j++) {
1031  bool canSee = true;
1032  double ax = sq1xs[i]; double ay = sq1ys[i];
1033  double bx = sq2xs[j]; double by = sq2ys[j];
1034  // line segment ab connects a corner of sq1 to a corner of sq2
1035  for (int x = x1; x <= x2 && canSee; x++) {
1036  int lo = miny; int hi = maxy;
1037  if (y2 > y1) {
1038  lo = (x==x1 ? y1 : (int) ((x-(x1+1))*slope + y1));
1039  hi = ((x+1)-x1)*slope + (y1+1);
1040  lo = max(lo,y1); hi = min(hi,y2);
1041  } else { // y2 < y1
1042  lo = ((x+1)-x1)*slope + y1;
1043  hi = (x==x1 ? y1-1 : (int) ((x-(x1+1))*slope + (y1+1)));
1044  lo = max(lo,y2); hi = min(hi,y1);
1045  }
1046  for (int y = lo; y <= hi; y++) {
1047  double cx = (double) x;
1048  double cy = (double) (y+1);
1049  // (cx,cy) is top left corner of square (x,y)
1050  int k = x+y*worldSize; // k=square index
1051  if (walls[k] & 1) {
1052  // square k has a left side wall
1053  // check if ab intersects it
1054  double dx = cx; double dy = cy-1;
1055  if (linesIntersect(ax,ay,bx,by,cx,cy,dx,dy)) {
1056  canSee = false; break;
1057  }
1058  }
1059  if (walls[k] & 2) {
1060  // square k has a top wall
1061  // check if ab intersects it
1062  double dx = cx+1; double dy = cy;
1063  if (linesIntersect(ax,ay,bx,by,cx,cy,dx,dy)) {
1064  canSee = false; break;
1065  }
1066  }
1067  } }
1068  if (canSee) return true;
1069  } }
1070  return false;
1071 }
1072 
1073 bool Avatar::linesIntersect(double ax, double ay, double bx, double by,
1074  double cx ,double cy, double dx, double dy) {
1075  double epsilon = .001; // two lines are considered vertical if
1076  // x values differ by less than epsilon
1077  // first handle special case of two vertical lines
1078  if (abs(ax-bx) < epsilon && abs(cx-dx) < epsilon) {
1079  return abs(ax-cx) < epsilon && max(ay,by) >= min(cy,dy)
1080  && min(ay,by) <= max(cy,dy);
1081  }
1082  // now handle cases of one vertical line
1083  if (abs(ax-bx) < epsilon) {
1084  double s2 = (dy-cy)/(dx-cx); // slope of second line
1085  double i2 = cy - s2*cx; // y-intercept of second line
1086  double y = s2*ax + i2; // lines intersect at (ax,y)
1087  return (y >= min(ay,by) && y <= max(ay,by) &&
1088  y >= min(cy,dy) && y <= max(cy,dy));
1089  }
1090  if (abs(cx-dx) < epsilon) {
1091  double s1 = (by-ay)/(bx-ax); // slope of first line
1092  double i1 = ay - s1*ax; // y-intercept of first line
1093  double y = s1*cx + i1; // lines intersect at (cx,y)
1094  return (y >= min(ay,by) && y <= max(ay,by) &&
1095  y >= min(cy,dy) && y <= max(cy,dy));
1096  }
1097  double s1 = (by-ay)/(bx-ax); // slope of first line
1098  double i1 = ay - s1*ax; // y-intercept of first line
1099  double s2 = (dy-cy)/(dx-cx); // slope of second line
1100  double i2 = cy - s2*cx; // y-intercept of second line
1101 
1102  // handle special case of lines with equal slope
1103  // treat the slopes as equal if both slopes have very small
1104  // magnitude, or if their relative difference is small
1105  if (abs(s1)+abs(s2) <= epsilon ||
1106  abs(s1-s2)/(abs(s1)+abs(s2)) < epsilon) {
1107  return (abs(i1-i2) < epsilon &&
1108  min(ax,bx) <= max(cx,dx) && max(ax,bx) >= min(cx,dx));
1109  }
1110  // now, to the common case
1111  double x = (i2-i1)/(s1-s2); // x value where the lines interesect
1112 
1113  return (x >= min(ax,bx) && x <= max(ax,bx) &&
1114  x >= min(cx,dx) && x <= max(cx,dx));
1115 }
1116 
1117 void Avatar::subscribe(list<int>& glist) {
1118  if (comt == 0 || glist.size() == 0) return;
1119  pktx px = ps->alloc();
1120  Packet& p = ps->getPacket(px);
1121  uint32_t *pp = p.payload();
1122 
1123  int nsub = 0;
1124  list<int>::iterator gp;
1125  for (gp = glist.begin(); gp != glist.end(); gp++) {
1126  int g = *gp; nsub++;
1127  if (nsub > 350) {
1128  pp[0] = htonl(nsub-1); pp[nsub] = 0;
1129  p.length = Forest::OVERHEAD + 4*(2+nsub);
1130  p.type = Forest::SUB_UNSUB; p.flags = 0;
1131  p.comtree = comt;
1132  p.srcAdr = myAdr; p.dstAdr = rtrAdr;
1133  send(px);
1134  nsub = 1;
1135  }
1136  pp[nsub] = htonl(-g);
1137  }
1138  pp[0] = htonl(nsub); pp[nsub+1] = 0;
1139  p.length = Forest::OVERHEAD + 4*(2+nsub);
1140  p.type = Forest::SUB_UNSUB; p.flags = 0;
1141  p.comtree = comt;
1142  p.srcAdr = myAdr; p.dstAdr = rtrAdr;
1143  send(px);
1144  ps->free(px);
1145 }
1146 
1150 void Avatar::unsubscribe(list<int>& glist) {
1151  if (comt == 0 || glist.size() == 0) return;
1152  pktx px = ps->alloc();
1153  Packet& p = ps->getPacket(px);
1154  uint32_t *pp = p.payload();
1155 
1156  int nunsub = 0;
1157  list<int>::iterator gp;
1158  for (gp = glist.begin(); gp != glist.end(); gp++) {
1159  int g = *gp; nunsub++;
1160  if (nunsub > 350) {
1161  pp[0] = 0; pp[1] = htonl(nunsub-1);
1162  p.length = Forest::OVERHEAD + 4*(2+nunsub);
1163  p.type = Forest::SUB_UNSUB; p.flags = 0;
1164  p.comtree = comt;
1165  p.srcAdr = myAdr; p.dstAdr = rtrAdr;
1166  send(px);
1167  nunsub = 1;
1168  }
1169  pp[nunsub+1] = htonl(-g);
1170  }
1171  pp[0] = 0; pp[1] = htonl(nunsub);
1172  p.length = Forest::OVERHEAD + 4*(2+nunsub);
1173  p.type = Forest::SUB_UNSUB; p.flags = 0; p.comtree = comt;
1174  p.srcAdr = myAdr; p.dstAdr = rtrAdr;
1175  send(px);
1176  ps->free(px);
1177 }
1178 
1182 void Avatar::subscribeAll() {
1183  list<int> glist;
1184  set<int>::iterator gp;
1185  for (gp = myVisSet->begin(); gp != myVisSet->end(); gp++) {
1186  if (mySubs->find(*gp) == mySubs->end()) {
1187  mySubs->insert(*gp); glist.push_back(*gp);
1188  }
1189  }
1190  subscribe(glist);
1191 }
1192 
1195 void Avatar::unsubscribeAll() {
1196  list<int> glist;
1197  set<int>::iterator gp;
1198  for (gp = mySubs->begin(); gp != mySubs->end(); gp++)
1199  glist.push_back(*gp);
1200  unsubscribe(glist);
1201  mySubs->clear();
1202 }
1203 
1209 void Avatar::updateSubs() {
1210  // identify subscriptions for squares that are not currently visible
1211  list<int> glist;
1212  set<int>::iterator gp;
1213  for (gp = mySubs->begin(); gp != mySubs->end(); gp++) {
1214  int g = *gp;
1215  if (myVisSet->find(g) == myVisSet->end())
1216  glist.push_back(g);
1217  }
1218  // remove them from subscription set and unsubscribe
1219  list<int>::iterator p;
1220  for (p = glist.begin(); p != glist.end(); p++)
1221  mySubs->erase(*p);
1222  unsubscribe(glist);
1223 
1224  // identify squares that are now visible
1225  // add their multicast groups to subscription set and subscribe
1226  glist.clear();
1227  set<int>::iterator vp;
1228  for (vp = myVisSet->begin(); vp != myVisSet->end(); vp++) {
1229  int g = *vp;
1230  if (mySubs->find(g) == mySubs->end()) {
1231  mySubs->insert(g);
1232  glist.push_back(g);
1233  }
1234  }
1235  subscribe(glist);
1236 }
1237 
1247 void Avatar::updateNearby(pktx px) {
1248  Packet& p = ps->getPacket(px);
1249  p.unpack();
1250  uint32_t *pp = p.payload();
1251  if (ntohl(pp[0]) != (int) STATUS_REPORT) return;
1252 
1253  // add the Avatar that sent this status report to the nearAvatars set
1254  uint64_t avId = p.srcAdr; avId = (avId << 32) | p.srcAdr;
1255  if (nearAvatars->size() < MAXNEAR)
1256  nearAvatars->insert(avId);
1257 
1258  // determine if we can see the Avatar that sent this report
1259  int x1 = ntohl(pp[2]); int y1 = ntohl(pp[3]);
1260  int g1 = groupNum(x1,y1);
1261  if (myVisSet->find(g1) == myVisSet->end()) {
1262  visibleAvatars->remove(avId);
1263  return;
1264  }
1265 
1266  // still possible that (x,y) can see (x1,y1)
1267  // check for walls that intersect the connecting line
1268  // it sufficies to check walls that belong to the squares
1269  // that are visible from (x,y)
1270  bool canSee = true;
1271  set<int>::iterator vp;
1272  int minx = min(x,x1)/GRID; int maxx = max(x,x1)/GRID;
1273  int miny = min(y,y1)/GRID; int maxy = max(y,y1)/GRID;
1274  for (vp = myVisSet->begin(); vp != myVisSet->end(); vp++) {
1275  int i = (*vp)-1; // i is index of a visible square
1276  int xi = i%worldSize; int yi = i/worldSize;
1277  if (xi < minx || xi > maxx || yi < miny || yi > maxy)
1278  continue;
1279  xi *= GRID; yi *= GRID;
1280  int ax = xi; int ay = yi + GRID;
1281  if (walls[i] & 2) { // i has top wall
1282  if(linesIntersect(x,y,x1,y1,ax,ay,ax+GRID,ay)) {
1283  canSee = false; break;
1284  }
1285  }
1286  if (walls[i] & 1) { // i has left wall
1287  if(linesIntersect(x,y,x1,y1,ax,ay,ax,ay-GRID)) {
1288  canSee = false; break;
1289  }
1290  }
1291  }
1292  if (canSee && visibleAvatars->size() < MAXNEAR)
1293  visibleAvatars->insert(avId);
1294 }
1295 
1296 /* incremental computation of visibility sets
1297  *
1298  * Setup a cache of visibility sets
1299  * When this avatar moves between squares, update pointer myVisSet to
1300  * point to the visibility set for the current square.
1301  * If the visibility set for the current square is not in the cache,
1302  * add it to the cache, possibly evicting the least-recently used
1303  * thing in the cache.
1304  * The current visSet goes to the front of the lruList for the cache
1305  *
1306  * Where does this happen? In updateStatus, I detect if I am in a new square
1307  * or not, so this is the place to update myVisSet.
1308  *
1309  * Do I need a cache? Given current speeds it takes 16, 40 or 100 time
1310  * steps to cross a square, so 50 on average. I can do visibility calculation
1311  * in <1ms so can have 50 avatars doing an update concurrently before
1312  * that swamps the machine and so this allows maybe 2500 avatars on
1313  * a machine. Other things will limit it well before this.
1314  *
1315  * So, perhaps it's best to start just doing visibility calculation
1316  * online and defer the cache option. Can always add it later should
1317  * it be necessary. With this approach, the only big data structure is
1318  * walls array and it's a byte per region, so a million regions is fine.
1319  *
1320  * Add a maximum visibility distance as well. In practice, 50 squares
1321  * should be ample. Might get by with 10-20, depending on how we scale
1322  * things in the world.
1323  *
1324  */
1325 
1326 void Avatar::updateVisSet() {
1327  computeVisSet(groupNum(x,y),*myVisSet);
1328 }
1329 
1330 } // ends namespace
1331