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