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