1 // Hyperbolic Rogue -- cells
2 // Copyright (C) 2011-2019 Zeno Rogue, see 'hyper.cpp' for details
3
4 /** \file cell.cpp
5 * \brief General cells and maps
6 *
7 * Start with locations.cpp
8 */
9
10 #include "hyper.h"
11 namespace hr {
12
13 #if HDR
14 extern int default_levs();
15
16 struct hrmap {
getOriginhr::hrmap17 virtual heptagon *getOrigin() { return NULL; }
gamestarthr::hrmap18 virtual cell *gamestart() { return getOrigin()->c7; }
~hrmaphr::hrmap19 virtual ~hrmap() { }
20 virtual vector<cell*>& allcells();
verifyhr::hrmap21 virtual void verify() { }
on_dim_changehr::hrmap22 virtual void on_dim_change() { }
23 virtual bool link_alt(heptagon *h, heptagon *alt, hstate firststate, int dir);
24 virtual void extend_altmap(heptagon *h, int levs = default_levs(), bool link_cdata = true);
may_create_stephr::hrmap25 heptagon *may_create_step(heptagon *h, int direction) {
26 if(h->move(direction)) return h->move(direction);
27 return create_step(h, direction);
28 }
29 virtual heptagon *create_step(heptagon *h, int direction);
30 private:
31 virtual transmatrix relative_matrixh(heptagon *h2, heptagon *h1, const hyperpoint& hint);
32 virtual transmatrix relative_matrixc(cell *c2, cell *c1, const hyperpoint& hint);
33 public:
relative_matrixhr::hrmap34 transmatrix relative_matrix(heptagon *h2, heptagon *h1, const hyperpoint& hint) { return relative_matrixh(h2, h1, hint); }
relative_matrixhr::hrmap35 transmatrix relative_matrix(cell *h2, cell *h1, const hyperpoint& hint) { return relative_matrixc(h2, h1, hint); }
36
adjhr::hrmap37 virtual transmatrix adj(cell *c, int i) { return adj(c->master, i); }
38 virtual transmatrix adj(heptagon *h, int i);
iadjhr::hrmap39 transmatrix iadj(cell *c, int i) { cell *c1 = c->cmove(i); return adj(c1, c->c.spin(i)); }
iadjhr::hrmap40 transmatrix iadj(heptagon *h, int d) {
41 heptagon *h1 = h->cmove(d); return adj(h1, h->c.spin(d));
42 }
43 virtual void draw_all();
44 virtual void draw_at(cell *at, const shiftmatrix& where);
45
46 virtual void virtualRebase(heptagon*& base, transmatrix& at);
47
48 static constexpr ld SPIN_NOT_AVAILABLE = 1e5;
spin_anglehr::hrmap49 virtual ld spin_angle(cell *c, int d) { return SPIN_NOT_AVAILABLE; }
50
51 virtual transmatrix spin_to(cell *c, int d, ld bonus=0);
52 virtual transmatrix spin_from(cell *c, int d, ld bonus=0);
53
spacedisthr::hrmap54 virtual double spacedist(cell *c, int i) { return hdist0(tC0(adj(c, i))); }
55
strict_tree_ruleshr::hrmap56 virtual bool strict_tree_rules() { return false; }
57
58 virtual void find_cell_connection(cell *c, int d);
shvidhr::hrmap59 virtual int shvid(cell *c) { return 0; }
full_shvidhr::hrmap60 virtual int full_shvid(cell *c) { return shvid(c); }
get_cornerhr::hrmap61 virtual hyperpoint get_corner(cell *c, int cid, ld cf=3) { return C0; }
master_relativehr::hrmap62 virtual transmatrix master_relative(cell *c, bool get_inverse = false) { return Id; }
63 virtual int wall_offset(cell *c);
64
65 virtual transmatrix ray_iadj(cell *c, int i);
66
67 virtual subcellshape& get_cellshape(cell *c);
68
69 /** \brief in 3D honeycombs, returns a cellwalker res at cw->move(j) such that the face pointed at by cw and res share an edge */
70 virtual cellwalker strafe(cellwalker cw, int j);
71
72 /** \brief in 3D honeycombs, returns a vector<bool> v, where v[j] iff faces i and j are adjacent */
dirdisthr::hrmap73 const vector<char>& dirdist(cellwalker cw) { return get_cellshape(cw.at).dirdist[cw.spin]; }
74
75 /** \brief the sequence of heptagon movement direction to get from c->master to c->move(i)->master; implemented only for reg3 */
76 virtual const vector<int>& get_move_seq(cell *c, int i);
77 };
78
79 /** hrmaps which are based on regular non-Euclidean 2D tilings, possibly quotient
80 * Operators can be applied to these maps.
81 * Liskov substitution warning: maps which produce both tiling like above and 3D tilings
82 * (e.g. Euclidean and Crystal) also inherit from hrmap_standard
83 **/
84 struct hrmap_standard : hrmap {
85 void draw_at(cell *at, const shiftmatrix& where) override;
86 transmatrix relative_matrixh(heptagon *h2, heptagon *h1, const hyperpoint& hint) override;
87 transmatrix relative_matrixc(cell *c2, cell *c1, const hyperpoint& hint) override;
88 heptagon *create_step(heptagon *h, int direction) override;
89 transmatrix adj(cell *c, int d) override;
90 transmatrix adj(heptagon *h, int d) override;
91 ld spin_angle(cell *c, int d) override;
92 double spacedist(cell *c, int i) override;
93 void find_cell_connection(cell *c, int d) override;
94 virtual int shvid(cell *c) override;
95 virtual hyperpoint get_corner(cell *c, int cid, ld cf) override;
96 virtual transmatrix master_relative(cell *c, bool get_inverse) override;
97 virtual bool link_alt(heptagon *h, heptagon *alt, hstate firststate, int dir) override;
98 };
99
100 void clearfrom(heptagon*);
101 void verifycells(heptagon*);
102
103 struct hrmap_hyperbolic : hrmap_standard {
104 heptagon *origin;
105 hrmap_hyperbolic();
106 hrmap_hyperbolic(heptagon *origin);
getOriginhr::hrmap_hyperbolic107 heptagon *getOrigin() override { return origin; }
~hrmap_hyperbolichr::hrmap_hyperbolic108 ~hrmap_hyperbolic() {
109 // verifycells(origin);
110 // printf("Deleting hyperbolic map: %p\n", hr::voidp(this));
111 clearfrom(origin);
112 }
verifyhr::hrmap_hyperbolic113 void verify() override { verifycells(origin); }
114 void virtualRebase(heptagon*& base, transmatrix& at) override;
115 };
116 #endif
117
create_step(heptagon * h,int direction)118 heptagon *hrmap::create_step(heptagon *h, int direction) {
119 throw hr_exception("create_step called unexpectedly");
120 return NULL;
121 }
122
relative_matrixh(heptagon * h2,heptagon * h1,const hyperpoint & hint)123 transmatrix hrmap::relative_matrixh(heptagon *h2, heptagon *h1, const hyperpoint& hint) {
124 println(hlog, "relative_matrixh called unexpectedly\n");
125 return Id;
126 }
127
relative_matrixc(cell * c2,cell * c1,const hyperpoint & hint)128 transmatrix hrmap::relative_matrixc(cell *c2, cell *c1, const hyperpoint& hint) {
129 return relative_matrixh(c2->master, c1->master, hint);
130 }
131
link_alt(heptagon * h,heptagon * alt,hstate firststate,int dir)132 bool hrmap::link_alt(heptagon *h, heptagon *alt, hstate firststate, int dir) {
133 return true;
134 }
135
link_alt(heptagon * h,heptagon * alt,hstate firststate,int dir)136 bool hrmap_standard::link_alt(heptagon *h, heptagon *alt, hstate firststate, int dir) {
137 altmap::relspin(alt) = 3;
138 return true;
139 }
140
virtualRebase(heptagon * & base,transmatrix & at)141 void hrmap::virtualRebase(heptagon*& base, transmatrix& at) {
142 printf("virtualRebase called unexpectedly\n");
143 return;
144 }
145
ray_iadj(cell * c,int i)146 transmatrix hrmap::ray_iadj(cell *c, int i) {
147 if(WDIM == 2) {
148 return to_other_side(get_corner(c, i), get_corner(c, (i+1)));
149 }
150 return currentmap->iadj(c, i);
151 }
152
get_cellshape(cell * c)153 subcellshape& hrmap::get_cellshape(cell *c) {
154 if(cgi.heptshape) return *cgi.heptshape;
155 throw hr_exception("get_cellshape called unexpectedly");
156 }
157
strafe(cellwalker cw,int j)158 cellwalker hrmap::strafe(cellwalker cw, int j) {
159 throw hr_exception("strafe called unexpectedly");
160 }
161
get_move_seq(cell * c,int i)162 const vector<int>& hrmap::get_move_seq(cell *c, int i) {
163 throw hr_exception("get_move_seq not implemented for this map class");
164 }
165
spin_to(cell * c,int d,ld bonus)166 transmatrix hrmap::spin_to(cell *c, int d, ld bonus) {
167 ld sa = spin_angle(c, d);
168 if(sa != SPIN_NOT_AVAILABLE) { return spin(bonus + sa); }
169 transmatrix T = rspintox(tC0(adj(c, d)));
170 if(WDIM == 3) return T * cspin(2, 0, bonus);
171 return T * spin(bonus);
172 }
173
spin_from(cell * c,int d,ld bonus)174 transmatrix hrmap::spin_from(cell *c, int d, ld bonus) {
175 ld sa = spin_angle(c, d);
176 if(sa != SPIN_NOT_AVAILABLE) { return spin(bonus - sa); }
177 transmatrix T = spintox(tC0(adj(c, d)));
178 if(WDIM == 3) return T * cspin(2, 0, bonus);
179 return T * spin(bonus);
180 }
181
adj(heptagon * h,int i)182 transmatrix hrmap::adj(heptagon *h, int i) { return relative_matrix(h->cmove(i), h, C0); }
183
allcells()184 vector<cell*>& hrmap::allcells() {
185 static vector<cell*> default_allcells;
186 if(bounded && !(cgflags & qHUGE_BOUNDED) && !(hybri && hybrid::csteps == 0)) {
187 celllister cl(gamestart(), 1000000, 1000000, NULL);
188 default_allcells = cl.lst;
189 return default_allcells;
190 }
191 if(isize(dcal) <= 1) {
192 extern cellwalker cwt;
193 celllister cl(cwt.at, 1, 1000, NULL);
194 default_allcells = cl.lst;
195 return default_allcells;
196 }
197 return dcal;
198 }
199
dirdiff(int dd,int t)200 EX int dirdiff(int dd, int t) {
201 dd %= t;
202 if(dd<0) dd += t;
203 if(t-dd < dd) dd = t-dd;
204 return dd;
205 }
206
207 EX int cellcount = 0;
208
destroy_cell(cell * c)209 EX void destroy_cell(cell *c) {
210 tailored_delete(c);
211 cellcount--;
212 }
213
newCell(int type,heptagon * master)214 EX cell *newCell(int type, heptagon *master) {
215 cell *c = tailored_alloc<cell> (type);
216 c->type = type;
217 c->master = master;
218 initcell(c);
219 hybrid::will_link(c);
220 cellcount++;
221 return c;
222 }
223
224 // -- hrmap ---
225
226 EX hrmap *currentmap;
227 EX vector<hrmap*> allmaps;
228
newAltMap(heptagon * o)229 EX hrmap *newAltMap(heptagon *o) {
230 #if MAXMDIM >= 4
231 if(reg3::in_rule())
232 return reg3::new_alt_map(o);
233 #endif
234 if(currentmap->strict_tree_rules())
235 return rulegen::new_hrmap_rulegen_alt(o);
236 return new hrmap_hyperbolic(o);
237 }
238 // --- hyperbolic geometry ---
239
hyperbolic_origin()240 EX heptagon* hyperbolic_origin() {
241 int odegree = geometry == gBinaryTiling ? 6 : S7;
242 heptagon *origin = init_heptagon(odegree);
243 heptagon& h = *origin;
244 h.s = hsOrigin;
245 h.emeraldval = a46 ? 0 : 98;
246 h.zebraval = 40;
247 #if CAP_IRR
248 if(IRREGULAR) irr::link_start(origin);
249 else
250 #endif
251 h.c7 = newCell(odegree, origin);
252 return origin;
253 }
254
hrmap_hyperbolic(heptagon * o)255 hrmap_hyperbolic::hrmap_hyperbolic(heptagon *o) { origin = o; }
256
hrmap_hyperbolic()257 hrmap_hyperbolic::hrmap_hyperbolic() { origin = hyperbolic_origin(); }
258
find_cell_connection(cell * c,int d)259 void hrmap::find_cell_connection(cell *c, int d) {
260 heptagon *h2 = createStep(c->master, d);
261 c->c.connect(d, h2->c7,c->master->c.spin(d), c->master->c.mirror(d));
262 hybrid::link();
263 }
264
find_cell_connection(cell * c,int d)265 void hrmap_standard::find_cell_connection(cell *c, int d) {
266 #if CAP_IRR
267 if(IRREGULAR) {
268 irr::link_cell(c, d);
269 }
270 #endif
271 #if CAP_GP
272 else if(GOLDBERG) {
273 gp::extend_map(c, d);
274 if(!c->move(d)) {
275 printf("extend failed to create for %p/%d\n", hr::voidp(c), d);
276 exit(1);
277 }
278 hybrid::link();
279 }
280 #endif
281 else if(PURE) {
282 hrmap::find_cell_connection(c, d);
283 }
284 else if(c == c->master->c7) {
285
286 cell *n = newCell(S6, c->master);
287
288 heptspin hs(c->master, d, false);
289
290 int alt3 = c->type/2;
291 int alt4 = alt3+1;
292
293 for(int u=0; u<S6; u+=2) {
294 if(hs.mirrored && (S7%2 == 0)) hs++;
295 hs.at->c7->c.connect(hs.spin, n, u, hs.mirrored);
296 if(hs.mirrored && (S7%2 == 0)) hs--;
297 hs = hs + alt3 + wstep - alt4;
298 }
299 hybrid::link();
300 extern void verifycell(cell *c);
301 verifycell(n);
302 }
303
304 else {
305 cellwalker cw(c, d, false);
306 cellwalker cw2 = cw - 1 + wstep - 1 + wstep - 1;
307 c->c.connect(d, cw2);
308 hybrid::link();
309 }
310 }
311
312 /** very similar to createMove in heptagon.cpp */
createMov(cell * c,int d)313 EX cell *createMov(cell *c, int d) {
314 if(d<0 || d>= c->type)
315 throw hr_exception("ERROR createmov\n");
316 if(c->move(d)) return c->move(d);
317 currentmap->find_cell_connection(c, d);
318 return c->move(d);
319 }
320
eumerge(cell * c1,int s1,cell * c2,int s2,bool mirror)321 EX void eumerge(cell* c1, int s1, cell *c2, int s2, bool mirror) {
322 if(!c2) return;
323 c1->move(s1) = c2; c1->c.setspin(s1, s2, mirror);
324 c2->move(s2) = c1; c2->c.setspin(s2, s1, mirror);
325 }
326
327 // map<pair<eucoord, eucoord>, cell*> euclidean;
328
329 EX hookset<hrmap*()> hooks_newmap;
330
331 /** create a map in the current geometry */
initcells()332 EX void initcells() {
333 DEBB(DF_INIT, ("initcells"));
334
335 hrmap* res = callhandlers((hrmap*)nullptr, hooks_newmap);
336 if(res) currentmap = res;
337 #if CAP_SOLV
338 else if(asonov::in()) currentmap = asonov::new_map();
339 #endif
340 else if(nonisotropic || hybri) currentmap = nisot::new_map();
341 else if(INVERSE) currentmap = gp::new_inverse();
342 else if(fake::in()) currentmap = fake::new_map();
343 #if CAP_CRYSTAL
344 else if(cryst) currentmap = crystal::new_map();
345 #endif
346 else if(arb::in() && rulegen::known()) currentmap = rulegen::new_hrmap_rulegen();
347 else if(arb::in()) currentmap = arb::new_map();
348 #if CAP_ARCM
349 else if(arcm::in()) currentmap = arcm::new_map();
350 #endif
351 else if(euc::in()) currentmap = euc::new_map();
352 #if CAP_BT
353 else if(kite::in()) currentmap = kite::new_map();
354 #endif
355 #if MAXMDIM >= 4
356 else if(WDIM == 3 && !bt::in()) currentmap = reg3::new_map();
357 #endif
358 else if(sphere) currentmap = new_spherical_map();
359 else if(quotient) currentmap = quotientspace::new_map();
360 #if CAP_BT
361 else if(bt::in()) currentmap = bt::new_map();
362 #endif
363 else if(S3 >= OINF) currentmap = inforder::new_map();
364 else currentmap = new hrmap_hyperbolic;
365
366 allmaps.push_back(currentmap);
367
368 #if CAP_FIELD
369 windmap::create();
370 #endif
371
372 // origin->emeraldval =
373 }
374
clearcell(cell * c)375 EX void clearcell(cell *c) {
376 if(!c) return;
377 DEBB(DF_MEMORY, (format("c%d %p\n", c->type, hr::voidp(c))));
378 for(int t=0; t<c->type; t++) if(c->move(t)) {
379 DEBB(DF_MEMORY, (format("mov %p [%p] S%d\n", hr::voidp(c->move(t)), hr::voidp(c->move(t)->move(c->c.spin(t))), c->c.spin(t))));
380 if(c->move(t)->move(c->c.spin(t)) != NULL &&
381 c->move(t)->move(c->c.spin(t)) != c) {
382 DEBB(DF_MEMORY | DF_ERROR, (format("cell error: type = %d %d -> %d\n", c->type, t, c->c.spin(t))));
383 exit(1);
384 }
385 c->move(t)->move(c->c.spin(t)) = NULL;
386 }
387 DEBB(DF_MEMORY, (format("DEL %p\n", hr::voidp(c))));
388 destroy_cell(c);
389 gp::delete_mapped(c);
390 }
391
392 EX heptagon deletion_marker;
393
subcell(cell * c,const T & t)394 template<class T> void subcell(cell *c, const T& t) {
395 if(GOLDBERG) {
396 forCellEx(c2, c) if(c2->move(0) == c && c2 != c2->master->c7) {
397 subcell(c2, t);
398 }
399 }
400 else if(BITRUNCATED && !arcm::in() && !bt::in())
401 forCellEx(c2, c) t(c2);
402 t(c);
403 }
404
clearHexes(heptagon * at)405 EX void clearHexes(heptagon *at) {
406 if(at->c7 && at->cdata) {
407 delete at->cdata;
408 at->cdata = NULL;
409 }
410 if(0);
411 #if CAP_IRR
412 else if(IRREGULAR) irr::clear_links(at);
413 #endif
414 else if(at->c7) subcell(at->c7, clearcell);
415 }
416
unlink_cdata(heptagon * h)417 void unlink_cdata(heptagon *h) {
418 if(h->alt && h->c7) {
419 if(h->alt->cdata == (cdata*) h)
420 h->alt->cdata = NULL;
421 }
422 }
423
clear_heptagon(heptagon * at)424 EX void clear_heptagon(heptagon *at) {
425 clearHexes(at);
426 tailored_delete(at);
427 }
428
clearfrom(heptagon * at)429 EX void clearfrom(heptagon *at) {
430 if(!at) return;
431 queue<heptagon*> q;
432 unlink_cdata(at);
433 q.push(at);
434 at->alt = &deletion_marker;
435 //int maxq = 0;
436 while(!q.empty()) {
437 at = q.front();
438 // if(q.size() > maxq) maxq = q.size();
439 q.pop();
440 DEBB(DF_MEMORY, ("from %p", at));
441 if(!at->c7) {
442 heptagon *h = dynamic_cast<heptagon*> ((cdata_or_heptagon*) at->cdata);
443 if(h) {
444 if(h->alt != at) { DEBB(DF_MEMORY | DF_ERROR, ("alt error :: h->alt = ", h->alt, " expected ", at)); }
445 cell *c = h->c7;
446 subcell(c, destroycellcontents);
447 h->alt = NULL;
448 at->cdata = NULL;
449 }
450 }
451 int edges = at->degree();
452 if(bt::in() && WDIM == 2) edges = at->c7->type;
453 for(int i=0; i<edges; i++) if(at->move(i) && at->move(i) != at) {
454 if(at->move(i)->alt != &deletion_marker)
455 q.push(at->move(i));
456 unlink_cdata(at->move(i));
457 at->move(i)->alt = &deletion_marker;
458 DEBB(DF_MEMORY, ("!mov ", at->move(i), " [", at->move(i)->move(at->c.spin(i)), "]"));
459 if(at->move(i)->move(at->c.spin(i)) != NULL &&
460 at->move(i)->move(at->c.spin(i)) != at) {
461 DEBB(DF_MEMORY | DF_ERROR, ("hept error"));
462 exit(1);
463 }
464 at->move(i)->move(at->c.spin(i)) = NULL;
465 at->move(i) = NULL;
466 }
467 clearHexes(at);
468 tailored_delete(at);
469 }
470 //printf("maxq = %d\n", maxq);
471 }
472
verifycell(cell * c)473 EX void verifycell(cell *c) {
474 int t = c->type;
475 for(int i=0; i<t; i++) {
476 cell *c2 = c->move(i);
477 if(c2) {
478 if(BITRUNCATED && c == c->master->c7) verifycell(c2);
479 if(c2->move(c->c.spin(i)) && c2->move(c->c.spin(i)) != c) {
480 printf("cell error %p:%d [%d] %p:%d [%d]\n", hr::voidp(c), i, c->type, hr::voidp(c2), c->c.spin(i), c2->type);
481 exit(1);
482 }
483 }
484 }
485 }
486
verifycells(heptagon * at)487 EX void verifycells(heptagon *at) {
488 if(GOLDBERG || IRREGULAR || arcm::in()) return;
489 for(int i=0; i<at->type; i++) if(at->move(i) && at->move(i)->move(at->c.spin(i)) && at->move(i)->move(at->c.spin(i)) != at) {
490 printf("hexmix error %p [%d s=%d] %p %p\n", hr::voidp(at), i, at->c.spin(i), hr::voidp(at->move(i)), hr::voidp(at->move(i)->move(at->c.spin(i))));
491 }
492 if(!sphere && !quotient)
493 for(int i=0; i<S7; i++) if(at->move(i) && at->c.spin(i) == 0 && at->s != hsOrigin)
494 verifycells(at->move(i));
495 verifycell(at->c7);
496 }
497
compdist(int dx[])498 EX int compdist(int dx[]) {
499 int mi = dx[0];
500 for(int u=0; u<S3; u++) mi = min(mi, dx[u]);
501 for(int u=0; u<S3; u++)
502 if(dx[u] > mi+2)
503 return -1; // { printf("cycle error!\n"); exit(1); }
504 for(int u=0; u<S3; u++)
505 if(dx[u] == mi+2)
506 return mi+1;
507 int cnt = 0;
508 for(int u=0; u<S3; u++)
509 if(dx[u] == mi) cnt++;
510 if(cnt < 2)
511 return mi+1;
512 return mi;
513 }
514
celldist(cell * c)515 EX int celldist(cell *c) {
516 if(experimental) return 0;
517 if(hybri)
518 return hybrid::celldistance(c, currentmap->gamestart());
519 if(nil && !quotient) return DISTANCE_UNKNOWN;
520 if(euc::in()) return celldistance(currentmap->gamestart(), c);
521 if(sphere || bt::in() || WDIM == 3 || cryst || sn::in() || kite::in() || bounded) return celldistance(currentmap->gamestart(), c);
522 #if CAP_IRR
523 if(IRREGULAR) return irr::celldist(c, false);
524 #endif
525 if(arcm::in() || ctof(c) || arb::in()) return c->master->distance;
526 #if CAP_GP
527 if(INVERSE) {
528 cell *c1 = gp::get_mapped(c);
529 return UIU(gp::compute_dist(c1, celldist)) / 2;
530 /* TODO */
531 }
532 if(GOLDBERG) return gp::compute_dist(c, celldist);
533 #endif
534 int dx[MAX_S3];
535 for(int u=0; u<S3; u++)
536 dx[u] = createMov(c, u+u)->master->distance;
537 return compdist(dx);
538 }
539
540 #if HDR
541 static const int ALTDIST_BOUNDARY = 99999;
542 static const int ALTDIST_UNKNOWN = 99998;
543 static const int ALTDIST_ERROR = 90000;
544 #endif
545
celldistAlt(cell * c)546 EX int celldistAlt(cell *c) {
547 if(experimental) return 0;
548 if(hybri) {
549 if(in_s2xe()) return hybrid::get_where(c).second;
550 auto w = hybrid::get_where(c);
551 int d = c->master->alt && c->master->alt->alt ? hybrid::altmap_heights[c->master->alt->alt] : 0;
552 d = sl2 ? 0 : abs(w.second - d);
553 PIU ( d += celldistAlt(w.first) );
554 return d;
555 }
556 #if CAP_BT
557 if(bt::in() || sn::in()) return c->master->distance + (specialland == laCamelot && !ls::single() ? 30 : 0);
558 #endif
559 if(nil) return c->master->zebraval + abs(c->master->emeraldval) + (specialland == laCamelot && !ls::single() ? 30 : 0);;
560 #if CAP_CRYSTAL
561 if(cryst)
562 return crystal::dist_alt(c);
563 #endif
564 if(sphere || quotient) {
565 return celldist(c) - 3;
566 }
567 #if MAXMDIM >= 4
568 if(euc::in()) return euc::dist_alt(c);
569 if(hyperbolic && WDIM == 3 && !reg3::in_rule())
570 return reg3::altdist(c->master);
571 #endif
572 if(!c->master->alt) return 0;
573 #if CAP_IRR
574 if(IRREGULAR) return irr::celldist(c, true);
575 #endif
576 if(ctof(c)) return c->master->alt->distance;
577 if(reg3::in()) return c->master->alt->distance;
578 #if CAP_GP
579 if(GOLDBERG) return gp::compute_dist(c, celldistAlt);
580 if(INVERSE) {
581 cell *c1 = gp::get_mapped(c);
582 return UIU(gp::compute_dist(c1, celldistAlt)) / 2;
583 /* TODO */
584 }
585 #endif
586 int dx[MAX_S3]; dx[0] = 0;
587 for(int u=0; u<S3; u++) if(createMov(c, u+u)->master->alt == NULL)
588 return ALTDIST_UNKNOWN;
589 for(int u=0; u<S3; u++)
590 dx[u] = createMov(c, u+u)->master->alt->distance;
591 // return compdist(dx); -> not OK because of boundary conditions
592 int mi = dx[0];
593 for(int i=1; i<S3; i++) mi = min(mi, dx[i]);
594 for(int i=0; i<S3; i++) if(dx[i] > mi+2)
595 return ALTDIST_BOUNDARY; // { printf("cycle error!\n"); exit(1); }
596 for(int i=0; i<S3; i++) if(dx[i] == mi+2)
597 return mi+1;
598 return mi;
599 }
600
601 /** direction upwards in the tree */
updir(heptagon * h)602 EX int updir(heptagon *h) {
603 #if CAP_BT
604 if(bt::in()) return bt::updir();
605 #endif
606 #if MAXMDIM >= 4
607 if(WDIM == 3 && reg3::in_rule()) {
608 for(int i=0; i<S7; i++) if(h->move(i) && h->move(i)->distance < h->distance)
609 return i;
610 return -1;
611 }
612 #endif
613 if(h->s == hsOrigin) return -1;
614 return 0;
615 }
616
617 /** direction upwards in the alt-tree */
updir_alt(heptagon * h)618 EX int updir_alt(heptagon *h) {
619 if(euclid || !h->alt) return -1;
620 #if MAXMDIM >= 4
621 if(WDIM == 3 && reg3::in_rule()) {
622 for(int i=0; i<S7; i++) if(h->move(i) && h->move(i)->alt && h->move(i)->alt->distance < h->alt->distance)
623 return i;
624 return -1;
625 }
626 #endif
627 return gmod(updir(h->alt) + altmap::relspin(h->alt), h->type);
628 }
629
630
631 #if HDR
632 static const int RPV_MODULO = 5;
633 static const int RPV_RAND = 0;
634 static const int RPV_ZEBRA = 1;
635 static const int RPV_EMERALD = 2;
636 static const int RPV_PALACE = 3;
637 static const int RPV_CYCLE = 4;
638 #endif
639
640 // x mod 5 = pattern type
641 // x mod (powers of 2) = pattern type specific
642 // (x/5) mod 15 = picture for drawing floors
643 // x mod 7 = chance of pattern-specific pic
644 // whole = randomization
645
randpattern(cell * c,int rval)646 EX bool randpattern(cell *c, int rval) {
647 int i, sw=0;
648 switch(rval%5) {
649 case 0:
650 if(rval&1) {
651 return hrandpos() < rval;
652 }
653 else {
654 int cd = getCdata(c, 0);
655 return !((cd/(((rval/2)&15)+1))&1);
656 }
657 case 1:
658 i = zebra40(c);
659 if(i&1) { if(rval&4) sw^=1; i &= ~1; }
660 if(i&2) { if(rval&8) sw^=1; i &= ~2; }
661 i >>= 2;
662 i--; i /= 3;
663 if(rval & (16<<i)) sw^=1;
664 return sw;
665 case 2:
666 i = emeraldval(c);
667 if(i&1) { if(rval&4) sw^=1; i &= ~1; }
668 if(i&2) { if(rval&8) sw^=1; i &= ~2; }
669 i >>= 2; i--;
670 if(rval & (16<<i)) sw^=1;
671 return sw;
672 case 3:
673 if(polara50(c)) { if(rval&4) sw^=1; }
674 if(polarb50(c)) { if(rval&8) sw^=1; }
675 i = fiftyval049(c); i += 6; i /= 7;
676 if(rval & (16<<i)) sw^=1;
677 return sw;
678 case 4:
679 i = (rval&3);
680 if(i == 1 && (celldist(c)&1)) sw ^= 1;
681 if(i == 2 && (celldist(c)&2)) sw ^= 1;
682 if(i == 3 && ((celldist(c)/3)&1)) sw ^= 1;
683 if(rval & (4<<towerval(c, celldist))) sw ^= 1;
684 return sw;
685 }
686 return 0;
687 }
688
describeRPM(eLand l)689 EX string describeRPM(eLand l) {
690 int rval = randompattern[l];
691 switch(rval%5) {
692 case 0:
693 if(rval&1)
694 return "R:"+its(rval/(HRANDMAX/100))+"%";
695 else
696 return "Landscape/"+its(((rval/2)&15)+1);
697 case 1:
698 return "Z/"+its((rval>>2)&3)+"/"+its((rval>>4)&15);
699 case 2:
700 return "E/"+its((rval>>2)&3)+"/"+its((rval>>4)&2047);
701 case 3:
702 return "P/"+its((rval>>2)&3)+"/"+its((rval>>4)&255);
703 case 4:
704 return "C/"+its(rval&3)+"/"+its((rval>>2)&65535);
705 }
706 return "?";
707 }
708
randpatternCode(cell * c,int rval)709 EX int randpatternCode(cell *c, int rval) {
710 switch(rval % RPV_MODULO) {
711 case 1:
712 return zebra40(c);
713 case 2:
714 return emeraldval(c);
715 case 3:
716 return fiftyval049(c) + (polara50(c)?50:0) + (polarb50(c)?1000:0);
717 case 4:
718 return towerval(c, celldist) * 6 + celldist(c) % 6;
719 }
720 return 0;
721 }
722
723 #if HDR
724 #define RANDITER 31
725 #endif
726
727 char rpm_memoize[3][256][RANDITER+1];
728
clearMemoRPM()729 EX void clearMemoRPM() {
730 for(int a=0; a<3; a++) for(int b=0; b<256; b++) for(int i=0; i<RANDITER+1; i++)
731 rpm_memoize[a][b][i] = 2;
732 }
733
randpatternMajority(cell * c,int ival,int iterations)734 EX bool randpatternMajority(cell *c, int ival, int iterations) {
735 int rval = 0;
736 if(ival == 0) rval = randompattern[laCaves];
737 if(ival == 1) rval = randompattern[laLivefjord];
738 if(ival == 2) rval = randompattern[laEmerald];
739 if(rval%RPV_MODULO == RPV_RAND) return randpattern(c, rval);
740 int code = randpatternCode(c, rval);
741 char& memo(rpm_memoize[ival][code][iterations]);
742 if(memo < 2) return memo;
743 int z = 0;
744 if(iterations) for(int i=0; i<c->type; i++) {
745 if(randpatternMajority(createMov(c,i), ival, iterations-1))
746 z++;
747 else
748 z--;
749 }
750 if(z!=0) memo = (z>0);
751 else memo = randpattern(c, rval);
752 // printf("%p] rval = %X code = %d iterations = %d result = %d\n", c, rval, code, iterations, memo);
753 return memo;
754 }
755
756 #define RVAL_MASK 0x10000000
757 #define DATA_MASK 0x20000000
758
759 cdata orig_cdata;
760
geometry_supports_cdata()761 EX bool geometry_supports_cdata() {
762 if(hybri) return PIU(geometry_supports_cdata());
763 return among(geometry, gEuclid, gEuclidSquare, gNormal, gOctagon, g45, g46, g47, gBinaryTiling) || (arcm::in() && !sphere) || currentmap->strict_tree_rules();
764 }
765
affect(cdata & d,short rv,signed char signum)766 void affect(cdata& d, short rv, signed char signum) {
767 if(rv&1) d.val[0]+=signum; else d.val[0]-=signum;
768 if(rv&2) d.val[1]+=signum; else d.val[1]-=signum;
769 if(rv&4) d.val[2]+=signum; else d.val[2]-=signum;
770 if(rv&8) d.val[3]+=signum; else d.val[3]-=signum;
771 int id = (rv>>4) & 63;
772 if(id < 32)
773 d.bits ^= (1 << id);
774 }
775
setHeptagonRval(heptagon * h)776 void setHeptagonRval(heptagon *h) {
777 if(!(h->rval0 || h->rval1)) {
778 h->rval0 = hrand(0x10000);
779 h->rval1 = hrand(0x10000);
780 }
781 }
782
dmeq(int a,int b)783 EX bool dmeq(int a, int b) { return (a&3) == (b&3); }
784
785 /* kept for compatibility: Racing etc. */
getHeptagonCdata_legacy(heptagon * h)786 cdata *getHeptagonCdata_legacy(heptagon *h) {
787 if(h->cdata) return h->cdata;
788
789 if(sphere || quotient) h = currentmap->gamestart()->master;
790
791 if(h == currentmap->getOrigin()) {
792 h->cdata = new cdata(orig_cdata);
793 for(int& v: h->cdata->val) v = 0;
794 h->cdata->bits = reptilecheat ? (1 << 21) - 1 : 0;
795 if(yendor::on && specialland == laVariant) h->cdata->bits |= (1 << 8) | (1 << 9) | (1 << 12);
796 return h->cdata;
797 }
798
799 cdata mydata = *getHeptagonCdata_legacy(h->move(0));
800
801 for(int di=3; di<5; di++) {
802 heptspin hs(h, di, false);
803 int signum = +1;
804 while(true) {
805 heptspin hstab[15];
806 hstab[7] = hs;
807
808 for(int i=8; i<12; i++) {
809 hstab[i] = hstab[i-1];
810 hstab[i] += ((i&1) ? 4 : 3);
811 hstab[i] += wstep;
812 hstab[i] += ((i&1) ? 3 : 4);
813 }
814
815 for(int i=6; i>=3; i--) {
816 hstab[i] = hstab[i+1];
817 hstab[i] += ((i&1) ? 3 : 4);
818 hstab[i] += wstep;
819 hstab[i] += ((i&1) ? 4 : 3);
820 }
821
822 if(hstab[3].at->distance < hstab[7].at->distance) {
823 hs = hstab[3]; continue;
824 }
825
826 if(hstab[11].at->distance < hstab[7].at->distance) {
827 hs = hstab[11]; continue;
828 }
829
830 int jj = 7;
831 for(int k=3; k<12; k++) if(hstab[k].at->distance < hstab[jj].at->distance) jj = k;
832
833 int ties = 0, tiespos = 0;
834 for(int k=3; k<12; k++) if(hstab[k].at->distance == hstab[jj].at->distance)
835 ties++, tiespos += (k-jj);
836
837 // printf("ties=%d tiespos=%d jj=%d\n", ties, tiespos, jj);
838 if(ties == 2) jj += tiespos/2;
839
840 if(jj&1) signum = -1;
841 hs = hstab[jj];
842
843 break;
844 }
845 hs = hs + 3 + wstep;
846 setHeptagonRval(hs.at);
847
848 affect(mydata, hs.spin ? hs.at->rval0 : hs.at->rval1, signum);
849 }
850
851 return h->cdata = new cdata(mydata);
852 }
853
854
getHeptagonCdata(heptagon * h)855 cdata *getHeptagonCdata(heptagon *h) {
856 if(hybri) return PIU ( getHeptagonCdata(h) );
857 if(geometry == gNormal && BITRUNCATED) return getHeptagonCdata_legacy(h);
858 if(h->cdata) return h->cdata;
859
860 if(sphere || quotient) h = currentmap->gamestart()->master;
861
862 bool starting = h->s == hsOrigin;
863 #if CAP_BT
864 if(bt::in()) {
865 if(bt::mapside(h) == 0) starting = true;
866 for(int i=0; i<h->type; i++) if(bt::mapside(h->cmove(i)) == 0) starting = true;
867 }
868 #endif
869
870 if(currentmap->strict_tree_rules()) starting = h->distance <= 0;
871
872 if(starting) {
873 h->cdata = new cdata(orig_cdata);
874 for(int& v: h->cdata->val) v = 0;
875 h->cdata->bits = reptilecheat ? (1 << 21) - 1 : 0;
876 if(yendor::on && specialland == laVariant) h->cdata->bits |= (1 << 8) | (1 << 9) | (1 << 12);
877 return h->cdata;
878 }
879
880 int dir = updir(h);
881
882 cdata mydata = *getHeptagonCdata(h->cmove(dir));
883
884 if(S3 >= OINF) {
885 setHeptagonRval(h);
886 affect(mydata, h->rval0, 1);
887 }
888 else if(currentmap->strict_tree_rules()) {
889 for(eLand ws: {NOWALLSEP, NOWALLSEP_SWAP}) {
890 lalign(0, h->c7);
891 int dir = 1;
892 cellwalker hs(h->c7, dir, false);
893 eLand dummy = laNone;
894 vector<cell*> lpath, rpath;
895 while(true) {
896 int d = hs.at->master->distance;
897 general_barrier_advance(hs, dir, dummy, dummy, ws, false);
898 lpath.push_back(hs.at);
899 if(hs.at->master->distance > d) break;
900 }
901 dir = -dir;
902 while(true) {
903 int d = hs.at->master->distance;
904 general_barrier_advance(hs, dir, dummy, dummy, ws, false);
905 rpath.push_back(hs.at);
906 if(hs.at->master->distance > d) break;
907 }
908 setHeptagonRval(hs.at->master);
909 affect(mydata, ws == NOWALLSEP_SWAP ? hs.at->master->rval1 : hs.at->master->rval0, 1);
910 }
911 }
912 else if(S3 == 4) {
913 heptspin hs(h, 0);
914 while(dmeq((hs+1).cpeek()->dm4, (hs.at->dm4 - 1))) hs = hs + 1 + wstep + 1;
915 while(dmeq((hs-1).cpeek()->dm4, (hs.at->dm4 - 1))) hs = hs - 1 + wstep - 1;
916 setHeptagonRval(hs.at);
917 affect(mydata, hs.at->rval0, 1);
918 }
919 else for(int di: {0,1}) {
920 heptspin hs(h, dir, false);
921 hs -= di;
922 while(true) {
923 heptspin hs2 = hs + wstep + 1 + wstep - 1;
924 if(dmeq(hs2.at->dm4, hs.at->dm4 + 1)) break;
925 hs = hs2;
926 }
927 while(true) {
928 heptspin hs2 = hs + 1 + wstep - 1 + wstep;
929 if(dmeq(hs2.at->dm4, hs.at->dm4 + 1)) break;
930 hs = hs2;
931 }
932 setHeptagonRval(hs.at);
933 affect(mydata, hs.spin == dir ? hs.at->rval0 : hs.at->rval1, 1);
934 }
935
936 return h->cdata = new cdata(mydata);
937 }
938
getEuclidCdata(gp::loc h)939 cdata *getEuclidCdata(gp::loc h) {
940
941 int x = h.first, y = h.second;
942
943 #if CAP_ARCM
944 auto& data = arcm::in() ? arcm::get_cdata() : euc::get_cdata();
945 #else
946 auto& data = euc::get_cdata();
947 #endif
948
949 // hrmap_euclidean* euc = dynamic_cast<hrmap_euclidean*> (currentmap);
950 if(data.count(h)) return &(data[h]);
951
952 if(x == 0 && y == 0) {
953 cdata xx;
954 for(int i=0; i<4; i++) xx.val[i] = 0;
955 xx.bits = 0;
956 return &(data[h] = xx);
957 }
958 int ord = 1, bid = 0;
959 while(!((x|y)&ord)) ord <<= 1, bid++;
960
961 for(int k=0; k<3; k++) {
962 int x1 = x + (k<2 ? ord : 0);
963 int y1 = y - (k>0 ? ord : 0);
964 if((x1&ord) || (y1&ord)) continue;
965 int x2 = x - (k<2 ? ord : 0);
966 int y2 = y + (k>0 ? ord : 0);
967
968 cdata *d1 = getEuclidCdata({x1,y1});
969 cdata *d2 = getEuclidCdata({x2,y2});
970 cdata xx;
971 double disp = pow(2, bid/2.) * 6;
972
973 for(int i=0; i<4; i++) {
974 double dv = (d1->val[i] + d2->val[i])/2 + (hrand(1000) - hrand(1000))/1000. * disp;
975 xx.val[i] = floor(dv);
976 if(hrand(1000) / 1000. < dv - floor(dv)) xx.val[i]++;
977 }
978 xx.bits = 0;
979
980 for(int b=0; b<32; b++) {
981 bool gbit = ((hrand(2)?d1:d2)->bits >> b) & 1;
982 int flipchance = (1<<bid);
983 if(flipchance > 512) flipchance = 512;
984 if(hrand(1024) < flipchance) gbit = !gbit;
985 if(gbit) xx.bits |= (1<<b);
986 }
987
988 return &(data[h] = xx);
989 }
990
991 // impossible!
992 return NULL;
993 }
994
ld_to_int(ld x)995 int ld_to_int(ld x) {
996 return int(x + 1000000.5) - 1000000;
997 }
998
999 #if CAP_ARCM
pseudocoords(cell * c)1000 EX gp::loc pseudocoords(cell *c) {
1001 transmatrix T = arcm::archimedean_gmatrix[c->master].second;
1002 return {ld_to_int(T[0][LDIM]), ld_to_int((spin(60*degree) * T)[0][LDIM])};
1003 }
1004
arcmCdata(cell * c)1005 EX cdata *arcmCdata(cell *c) {
1006 auto &agm = arcm::archimedean_gmatrix;
1007 if(!agm.count(c->master) || !agm[c->master].first) {
1008 forCellEx(c1, c) if(agm.count(c->master) && agm[c->master].first) return arcmCdata(c1);
1009 static cdata dummy;
1010 return &dummy;
1011 }
1012 heptagon *h2 = agm[c->master].first;
1013 dynamicval<eGeometry> g(geometry, gNormal);
1014 dynamicval<hrmap*> cm(currentmap, arcm::current_altmap);
1015 return getHeptagonCdata(h2);
1016 }
1017 #endif
1018
getCdata(cell * c,int j)1019 EX int getCdata(cell *c, int j) {
1020 if(fake::in()) return FPIU(getCdata(c, j));
1021 if(experimental) return 0;
1022 if(hybri) { c = hybrid::get_where(c).first; return PIU(getBits(c)); }
1023 else if(INVERSE) {
1024 cell *c1 = gp::get_mapped(c);
1025 return UIU(getCdata(c1, j));
1026 }
1027 else if(euc::in()) return getEuclidCdata(euc2_coordinates(c))->val[j];
1028 #if CAP_ARCM
1029 else if(arcm::in() && euclid)
1030 return getEuclidCdata(pseudocoords(c))->val[j];
1031 else if(arcm::in() && (hyperbolic || sl2))
1032 return arcmCdata(c)->val[j]*3;
1033 #endif
1034 else if(!geometry_supports_cdata()) return 0;
1035 else if(ctof(c)) return getHeptagonCdata(c->master)->val[j]*3;
1036 else {
1037 int jj = 0;
1038 auto ar = gp::get_masters(c);
1039 for(int k=0; k<3; k++)
1040 jj += getHeptagonCdata(ar[k])->val[j];
1041 return jj;
1042 }
1043 }
1044
getBits(cell * c)1045 EX int getBits(cell *c) {
1046 if(fake::in()) return FPIU(getBits(c));
1047 if(experimental) return 0;
1048 if(hybri) { c = hybrid::get_where(c).first; return PIU(getBits(c)); }
1049 else if(INVERSE) {
1050 cell *c1 = gp::get_mapped(c);
1051 return UIU(getBits(c1));
1052 }
1053 else if(euc::in()) return getEuclidCdata(euc2_coordinates(c))->bits;
1054 #if CAP_ARCM
1055 else if(arcm::in() && euclid)
1056 return getEuclidCdata(pseudocoords(c))->bits;
1057 else if(arcm::in() && (hyperbolic || sl2))
1058 return arcmCdata(c)->bits;
1059 #endif
1060 else if(!geometry_supports_cdata()) return 0;
1061 else if(c == c->master->c7) return getHeptagonCdata(c->master)->bits;
1062 else {
1063 auto ar = gp::get_masters(c);
1064 int b0 = getHeptagonCdata(ar[0])->bits;
1065 int b1 = getHeptagonCdata(ar[1])->bits;
1066 int b2 = getHeptagonCdata(ar[2])->bits;
1067 return (b0 & b1) | (b1 & b2) | (b2 & b0);
1068 }
1069 }
1070
heptatdir(cell * c,int d)1071 EX cell *heptatdir(cell *c, int d) {
1072 if(d&1) {
1073 cell *c2 = createMov(c, d);
1074 int s = c->c.spin(d);
1075 s += 3; s %= 6;
1076 return createMov(c2, s);
1077 }
1078 else return createMov(c, d);
1079 }
1080
heptdistance(heptagon * h1,heptagon * h2)1081 EX int heptdistance(heptagon *h1, heptagon *h2) {
1082 // very rough distance
1083 int d = 0;
1084 #if CAP_CRYSTAL
1085 if(cryst) return crystal::space_distance(h1->c7, h2->c7);
1086 #endif
1087 #if CAP_SOLV
1088 if(sn::in()) return sn::approx_distance(h1, h2);
1089 #endif
1090 while(true) {
1091 if(h1 == h2) return d;
1092 for(int i=0; i<S7; i++) if(h1->move(i) == h2) return d + 1;
1093 int d1 = h1->distance, d2 = h2->distance;
1094 if(d1 >= d2) d++, h1 = createStep(h1, bt::updir());
1095 if(d2 > d1) d++, h2 = createStep(h2, bt::updir());
1096 }
1097 }
1098
heptdistance(cell * c1,cell * c2)1099 EX int heptdistance(cell *c1, cell *c2) {
1100 #if CAP_CRYSTAL
1101 if(cryst) return crystal::space_distance(c1, c2);
1102 #endif
1103 if(!hyperbolic || quotient || WDIM == 3) return celldistance(c1, c2);
1104 else return heptdistance(c1->master, c2->master);
1105 }
1106
1107 map<pair<cell*, cell*>, int> saved_distances;
1108
1109 EX set<cell*> keep_distances_from;
1110
1111 set<cell*> dists_computed;
1112
1113 int perma_distances;
1114
compute_saved_distances(cell * c1,int max_range,int climit)1115 EX void compute_saved_distances(cell *c1, int max_range, int climit) {
1116
1117 celllister cl(c1, max_range, climit, NULL);
1118
1119 for(int i=0; i<isize(cl.lst); i++)
1120 saved_distances[make_pair(c1, cl.lst[i])] = cl.dists[i];
1121 }
1122
permanent_long_distances(cell * c1)1123 EX void permanent_long_distances(cell *c1) {
1124 keep_distances_from.insert(c1);
1125 if(racing::on)
1126 compute_saved_distances(c1, 300, 1000000);
1127 else
1128 compute_saved_distances(c1, 120, 200000);
1129 }
1130
erase_saved_distances()1131 EX void erase_saved_distances() {
1132 saved_distances.clear(); dists_computed.clear();
1133
1134 for(auto c: keep_distances_from) compute_saved_distances(c, 120, 200000);
1135 perma_distances = isize(saved_distances);
1136 }
1137
max_saved_distance(cell * c)1138 EX int max_saved_distance(cell *c) {
1139 int maxsd = 0;
1140 for(auto& p: saved_distances) if(p.first.first == c) maxsd = max(maxsd, p.second);
1141 return maxsd;
1142 }
1143
random_in_distance(cell * c,int d)1144 EX cell *random_in_distance(cell *c, int d) {
1145 vector<cell*> choices;
1146 for(auto& p: saved_distances) if(p.first.first == c && p.second == d) choices.push_back(p.first.second);
1147 println(hlog, "choices = ", isize(choices));
1148 if(choices.empty()) return NULL;
1149 return choices[hrand(isize(choices))];
1150 }
1151
bounded_celldistance(cell * c1,cell * c2)1152 EX int bounded_celldistance(cell *c1, cell *c2) {
1153 int limit = 14400;
1154 #if CAP_SOLV
1155 if(geometry == gArnoldCat) {
1156 c2 = asonov::get_at(asonov::get_coord(c2->master) - asonov::get_coord(c1->master))->c7;
1157 c1 = currentmap->gamestart();
1158 limit = 100000000;
1159 }
1160 #endif
1161
1162 if(saved_distances.count(make_pair(c1,c2)))
1163 return saved_distances[make_pair(c1,c2)];
1164
1165 celllister cl(c1, 100, limit, NULL);
1166 for(int i=0; i<isize(cl.lst); i++)
1167 saved_distances[make_pair(c1, cl.lst[i])] = cl.dists[i];
1168
1169 if(saved_distances.count(make_pair(c1,c2)))
1170 return saved_distances[make_pair(c1,c2)];
1171
1172 return DISTANCE_UNKNOWN;
1173 }
1174
clueless_celldistance(cell * c1,cell * c2)1175 EX int clueless_celldistance(cell *c1, cell *c2) {
1176 if(saved_distances.count(make_pair(c1,c2)))
1177 return saved_distances[make_pair(c1,c2)];
1178
1179 if(dists_computed.count(c1)) return DISTANCE_UNKNOWN;
1180
1181 if(isize(saved_distances) > perma_distances + 1000000) erase_saved_distances();
1182 compute_saved_distances(c1, 64, 1000);
1183
1184 dists_computed.insert(c1);
1185
1186 if(saved_distances.count(make_pair(c1,c2)))
1187 return saved_distances[make_pair(c1,c2)];
1188
1189 return DISTANCE_UNKNOWN;
1190 }
1191
celldistance(cell * c1,cell * c2)1192 EX int celldistance(cell *c1, cell *c2) {
1193
1194 if(fake::in()) return FPIU(celldistance(c1, c2));
1195
1196 if(hybri) return hybrid::celldistance(c1, c2);
1197
1198 #if CAP_FIELD
1199 if(geometry == gFieldQuotient && (PURE || BITRUNCATED)) {
1200 int d = fieldpattern::field_celldistance(c1, c2);
1201 if(d != DISTANCE_UNKNOWN) return d;
1202 }
1203 #endif
1204
1205 if(bounded) return bounded_celldistance(c1, c2);
1206
1207 #if CAP_CRYSTAL
1208 if(cryst) return crystal::precise_distance(c1, c2);
1209 #endif
1210
1211 if(euc::in() && WDIM == 2) {
1212 return euc::cyldist(euc2_coordinates(c1), euc2_coordinates(c2));
1213 }
1214
1215 if(arcm::in() || quotient || sn::in() || (kite::in() && euclid) || experimental || sl2 || nil || arb::in())
1216 return clueless_celldistance(c1, c2);
1217
1218 if(S3 >= OINF) return inforder::celldistance(c1, c2);
1219
1220 #if CAP_BT && MAXMDIM >= 4
1221 if(bt::in() && WDIM == 3)
1222 return bt::celldistance3(c1, c2);
1223 #endif
1224
1225 #if MAXMDIM >= 4
1226 if(euc::in())
1227 return euc::celldistance(c1, c2);
1228
1229 if(hyperbolic && WDIM == 3) return reg3::celldistance(c1, c2);
1230 #endif
1231
1232 if(INVERSE) {
1233 c1 = gp::get_mapped(c1);
1234 c2 = gp::get_mapped(c2);
1235 return UIU(celldistance(c1, c2)) / 2;
1236 /* TODO */
1237 }
1238
1239 return hyperbolic_celldistance(c1, c2);
1240 }
1241
build_shortest_path(cell * c1,cell * c2)1242 EX vector<cell*> build_shortest_path(cell *c1, cell *c2) {
1243 #if CAP_CRYSTAL
1244 if(cryst) return crystal::build_shortest_path(c1, c2);
1245 #endif
1246 vector<cell*> p;
1247 if(euclid) {
1248 p.push_back(c1);
1249 hyperpoint h = tC0(calc_relative_matrix(c2, c1, C0));
1250 cell *x = c1;
1251 transmatrix T1 = rspintox(h);
1252 int d = celldistance(c1, c2);
1253 int steps = d * 10;
1254 ld step = hdist0(h) / steps;
1255 for(int i=0; i< steps; i++) {
1256 T1 = T1 * xpush(step);
1257 virtualRebase(x, T1);
1258 println(hlog, "x = ", x, "p length = ", isize(p), " dist = ", hdist0(tC0(T1)), " dist from end = ", hdist(tC0(T1), tC0(calc_relative_matrix(c2, x, C0))));
1259 while(x != p.back()) {
1260 forCellCM(c, p.back())
1261 if(celldistance(x, c) < celldistance(x, p.back())) {
1262 p.push_back(c);
1263 break;
1264 }
1265 }
1266 }
1267 if(isize(p) != d + 1)
1268 println(hlog, "warning: path size ", isize(p), " should be ", d+1);
1269 }
1270 else if(c2 == currentmap->gamestart()) {
1271 while(c1 != c2) {
1272 p.push_back(c1);
1273 forCellCM(c, c1) if(celldist(c) < celldist(c1)) { c1 = c; goto next1; }
1274 throw hr_shortest_path_exception();
1275 next1: ;
1276 }
1277 p.push_back(c1);
1278 }
1279 else if(c1 == currentmap->gamestart()) {
1280 p = build_shortest_path(c2, c1);
1281 reverse(p.begin(), p.end());
1282 }
1283 else {
1284 while(c1 != c2) {
1285 p.push_back(c1);
1286 forCellCM(c, c1) if(celldistance(c, c2) < celldistance(c1, c2)) { c1 = c; goto next; }
1287 throw hr_shortest_path_exception();
1288 next: ;
1289 }
1290 p.push_back(c1);
1291 }
1292 return p;
1293 }
1294
clearCellMemory()1295 EX void clearCellMemory() {
1296 for(int i=0; i<isize(allmaps); i++)
1297 if(allmaps[i])
1298 delete allmaps[i];
1299 allmaps.clear();
1300 currentmap = nullptr;
1301 last_cleared = NULL;
1302 saved_distances.clear();
1303 dists_computed.clear();
1304 keep_distances_from.clear(); perma_distances = 0;
1305 pd_from = NULL;
1306 gp::gp_adj.clear();
1307 }
1308
1309 auto cellhooks = addHook(hooks_clearmemory, 500, clearCellMemory);
1310
isNeighbor(cell * c1,cell * c2)1311 EX bool isNeighbor(cell *c1, cell *c2) {
1312 for(int i=0; i<c1->type; i++) if(c1->move(i) == c2) return true;
1313 return false;
1314 }
1315
isNeighborCM(cell * c1,cell * c2)1316 EX bool isNeighborCM(cell *c1, cell *c2) {
1317 for(int i=0; i<c1->type; i++) if(createMov(c1, i) == c2) return true;
1318 return false;
1319 }
1320
neighborId(cell * ofWhat,cell * whichOne)1321 EX int neighborId(cell *ofWhat, cell *whichOne) {
1322 for(int i=0; i<ofWhat->type; i++) if(ofWhat->move(i) == whichOne) return i;
1323 return -1;
1324 }
1325
1326 EX int mine_adjacency_rule = 0;
1327
1328 EX map<cell*, vector<cell*>> adj_memo;
1329
geometry_has_alt_mine_rule()1330 EX bool geometry_has_alt_mine_rule() {
1331 if(S3 >= OINF) return false;
1332 if(WDIM == 2) return valence() > 3;
1333 if(WDIM == 3) return !among(geometry, gHoroHex, gCell5, gBitrunc3, gCell8, gECell8, gCell120, gECell120);
1334 return true;
1335 }
1336
adj_minefield_cells(cell * c)1337 EX vector<cell*> adj_minefield_cells(cell *c) {
1338 vector<cell*> res;
1339 if(mine_adjacency_rule == 0 || !geometry_has_alt_mine_rule())
1340 forCellCM(c2, c) res.push_back(c2);
1341 else if(WDIM == 2) {
1342 cellwalker cw(c, 0);
1343 cw += wstep;
1344 cw++;
1345 cellwalker cw1 = cw;
1346 do {
1347 res.push_back(cw.at);
1348 cw += wstep;
1349 cw++;
1350 if(cw.cpeek() == c) cw++;
1351 }
1352 while(cw != cw1);
1353 }
1354 else if(adj_memo.count(c)) return adj_memo[c];
1355 else {
1356 auto& ss = currentmap->get_cellshape(c);
1357 const vector<hyperpoint>& vertices = ss.vertices_only_local;
1358 manual_celllister cl;
1359 cl.add(c);
1360 vector<transmatrix> M = {Id};
1361 for(int i=0; i<isize(cl.lst); i++) {
1362 cell *c1 = cl.lst[i];
1363 bool shares = false;
1364 transmatrix T = M[i];
1365 if(c != c1) {
1366 auto& ss1 = currentmap->get_cellshape(c1);
1367 auto& vertices1 = ss1.vertices_only_local;
1368 for(hyperpoint h: vertices) for(hyperpoint h2: vertices1)
1369 if(hdist(h, T * h2) < 1e-6) shares = true;
1370 if(shares) res.push_back(c1);
1371 }
1372 if(shares || c == c1) forCellIdEx(c2, i, c1) {
1373 if(cl.listed(c2)) continue;
1374 cl.add(c2);
1375 M.push_back(T * currentmap->adj(c1, i));
1376 }
1377 }
1378 // println(hlog, "adjacent to ", c, " = ", isize(res), " of ", isize(M));
1379 adj_memo[c] = res;
1380 }
1381 return res;
1382 }
1383
reverse_directions(cell * c,int dir)1384 EX vector<int> reverse_directions(cell *c, int dir) {
1385 if(PURE && !(kite::in() && WDIM == 2)) return reverse_directions(c->master, dir);
1386 int d = c->degree();
1387 if(d & 1)
1388 return { gmod(dir + c->type/2, c->type), gmod(dir + (c->type+1)/2, c->type) };
1389 else
1390 return { gmod(dir + c->type/2, c->type) };
1391 }
1392
reverse_directions(heptagon * c,int dir)1393 EX vector<int> reverse_directions(heptagon *c, int dir) {
1394 int d = c->degree();
1395 switch(geometry) {
1396 case gBinary3:
1397 if(dir < 4) return {8};
1398 else if(dir >= 8) return {0, 1, 2, 3};
1399 else return {dir ^ 1};
1400
1401 case gHoroTris:
1402 if(dir < 4) return {7};
1403 else if(dir == 4) return {5, 6};
1404 else if(dir == 5) return {6, 4};
1405 else if(dir == 6) return {4, 5};
1406 else return {0, 1, 2, 3};
1407
1408 case gHoroRec:
1409 if(dir < 2) return {6};
1410 else if(dir == 6) return {0, 1};
1411 else return {dir^1};
1412
1413 case gKiteDart3: {
1414 if(dir < 4) return {dir ^ 2};
1415 if(dir >= 6) return {4, 5};
1416 vector<int> res;
1417 for(int i=6; i<c->type; i++) res.push_back(i);
1418 return res;
1419 }
1420
1421 case gHoroHex: {
1422 if(dir < 6) return {12, 13};
1423 if(dir >= 12) return {0, 1, 2, 3, 4, 5};
1424 const int dt[] = {0,0,0,0,0,0,10,11,9,8,6,7,0,0};
1425 return {dt[dir]};
1426 }
1427
1428 default:
1429 if(d & 1)
1430 return { gmod(dir + c->type/2, c->type), gmod(dir + (c->type+1)/2, c->type) };
1431 else
1432 return { gmod(dir + c->type/2, c->type) };
1433 }
1434 }
1435
standard_tiling()1436 EX bool standard_tiling() {
1437 return !arcm::in() && !kite::in() && !bt::in() && !arb::in() && !nonisotropic && !hybri;
1438 }
1439
valence()1440 EX int valence() {
1441 if(BITRUNCATED || IRREGULAR) return 3;
1442 if(INVERSE) return WARPED ? 4 : max(S3, S7);
1443 #if CAP_ARCM
1444 if(arcm::in()) return arcm::valence();
1445 #endif
1446 if(arb::in()) return arb::current.min_valence;
1447 return S3;
1448 }
1449
1450 /** portalspaces are not defined outside of a boundary */
is_boundary(cell * c)1451 EX bool is_boundary(cell *c) {
1452 if(c == &out_of_bounds) return true;
1453 return (cgflags & qPORTALSPACE) && isWall(c->wall);
1454 }
1455
1456 /** compute the distlimit for a tessellation automatically */
auto_compute_range(cell * c)1457 EX int auto_compute_range(cell *c) {
1458 if(sphere) {
1459 cgi.base_distlimit = SEE_ALL;
1460 return SEE_ALL;
1461 }
1462 cgi.base_distlimit = 0;
1463 const int expected_count = 400;
1464 celllister cl(c, 1000, expected_count, NULL);
1465 int z = isize(cl.dists);
1466 int d = cl.dists.back();
1467 while(cl.dists[z-1] == d) z--;
1468 if(true) { // if(cgflags & DF_GEOM) {
1469 println(hlog, "last distance = ", cl.dists.back());
1470 println(hlog, "ball size = ", isize(cl.dists));
1471 println(hlog, "previous ball size = ", z);
1472 }
1473 if(isize(cl.dists) * z > expected_count * expected_count) d--;
1474 return ginf[geometry].distlimit[0] = cgi.base_distlimit = d;
1475 }
1476
1477 EX cell out_of_bounds;
1478 EX heptagon oob;
1479
1480 }
1481