1 //------------------------------------------------------------------------------
2 // emNetwalkModel.cpp
3 //
4 // Copyright (C) 2010-2012,2014,2018 Oliver Hamann.
5 //
6 // Homepage: http://eaglemode.sourceforge.net/
7 //
8 // This program is free software: you can redistribute it and/or modify it under
9 // the terms of the GNU General Public License version 3 as published by the
10 // Free Software Foundation.
11 //
12 // This program is distributed in the hope that it will be useful, but WITHOUT
13 // ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
14 // FOR A PARTICULAR PURPOSE. See the GNU General Public License version 3 for
15 // more details.
16 //
17 // You should have received a copy of the GNU General Public License version 3
18 // along with this program. If not, see <http://www.gnu.org/licenses/>.
19 //------------------------------------------------------------------------------
20
21 #include <emNetwalk/emNetwalkModel.h>
22
23
Acquire(emContext & context,const emString & name,bool common)24 emRef<emNetwalkModel> emNetwalkModel::Acquire(
25 emContext & context, const emString & name, bool common
26 )
27 {
28 EM_IMPL_ACQUIRE(emNetwalkModel,context,name,common)
29 }
30
31
GetFormatName() const32 const char * emNetwalkModel::GetFormatName() const
33 {
34 return "emNetwalk";
35 }
36
37
SetAutoMark(bool autoMark,bool saveFile)38 void emNetwalkModel::SetAutoMark(bool autoMark, bool saveFile)
39 {
40 if (AutoMark!=autoMark) {
41 AutoMark=autoMark;
42 AutoMarkPiece=-1;
43 if (saveFile) Save(true);
44 }
45 }
46
47
GetPiece(int x,int y) const48 int emNetwalkModel::GetPiece(int x, int y) const
49 {
50 int w,h;
51
52 w=Width.Get();
53 h=Height.Get();
54 if (Borderless.Get()) {
55 x%=w;
56 if (x<0) x+=w;
57 y%=h;
58 if (y<0) y+=h;
59 }
60 else {
61 if (x<0 || x>=w || y<0 || y>=h) return PF_BLOCKED;
62 }
63 return Raster[y*w+x].Get();
64 }
65
66
TrySetup(int width,int height,bool borderless,bool noFourWayJunctions,int complexity,bool digMode,bool autoMark,bool saveFile)67 void emNetwalkModel::TrySetup(
68 int width, int height, bool borderless, bool noFourWayJunctions,
69 int complexity, bool digMode, bool autoMark, bool saveFile
70 )
71 {
72 emArray<char> undoBuf;
73 int i;
74
75 SaveToMem(undoBuf);
76 if (width<2) width=2;
77 if (height<2) height=2;
78 Width=width;
79 Height=height;
80 Borderless=borderless;
81 NoFourWayJunctions=noFourWayJunctions;
82 Complexity=complexity;
83 DigMode=digMode;
84 AutoMark=autoMark;
85 Finished=false;
86 PenaltyPoints=0;
87 CurrentPiece=-1;
88 AutoMarkPiece=-1;
89 Raster.SetCount(width*height);
90 for (i=1;;i++) {
91 Invent();
92 if (Solver(this).IsUniqueSolution()) {
93 emDLog("emNetwalkModel::Setup: Invented %d setups for finding one with unique solution",i);
94 break;
95 }
96 if (i>1000) {
97 TryLoadFromMem(undoBuf);
98 throw emException("Could not find any setup with unique solution.");
99 }
100 }
101 Shuffle();
102 Fill();
103 Dig(true);
104 if (saveFile) Save(true);
105 }
106
107
MarkOrUnmark(int x,int y,bool saveFile)108 void emNetwalkModel::MarkOrUnmark(int x, int y, bool saveFile)
109 {
110 int w,h;
111
112 w=Width.Get();
113 h=Height.Get();
114 if (Borderless.Get()) {
115 x%=w;
116 if (x<0) x+=w;
117 y%=h;
118 if (y<0) y+=h;
119 }
120 else {
121 if (x<0 || x>=w || y<0 || y>=h) return;
122 }
123 XorPiece(y*w+x,PF_MARKED);
124 if (saveFile) Save(true);
125 }
126
127
UnmarkAll(bool saveFile)128 void emNetwalkModel::UnmarkAll(bool saveFile)
129 {
130 bool changed;
131 int i;
132
133 changed=false;
134 for (i=Raster.GetCount()-1; i>=0; i--) {
135 if ((GetPiece(i)&PF_MARKED)!=0) {
136 XorPiece(i,PF_MARKED);
137 changed=true;
138 }
139 }
140 if (AutoMarkPiece>=0) {
141 AutoMarkPiece=-1;
142 changed=true;
143 }
144 if (changed && saveFile) Save(true);
145 }
146
147
Rotate(int x,int y,int angle,bool saveFile)148 void emNetwalkModel::Rotate(int x, int y, int angle, bool saveFile)
149 {
150 int w,h,i,p;
151
152 if (IsFinished()) return;
153 w=Width.Get();
154 h=Height.Get();
155 if (Borderless.Get()) {
156 x%=w;
157 if (x<0) x+=w;
158 y%=h;
159 if (y<0) y+=h;
160 }
161 else {
162 if (x<0 || x>=w || y<0 || y>=h) return;
163 }
164 i=y*w+x;
165 p=Raster[i].Get();
166 if (p&(PF_BLOCKED|PF_MARKED)) return;
167 p=RawRotate(p,angle);
168 if (CurrentPiece.Get()!=i) {
169 if (p&PF_TOUCHED) PenaltyPoints.Set(PenaltyPoints.Get()+1);
170 CurrentPiece.Set(i);
171 }
172 p|=PF_TOUCHED;
173 Raster[i].Set(p);
174 Fill();
175 Dig(true);
176 if (AutoMark) {
177 if (AutoMarkPiece!=-1 && AutoMarkPiece!=i) OrPiece(AutoMarkPiece,PF_MARKED);
178 AutoMarkPiece=i;
179 AutoMarkToSave=saveFile;
180 AutoMarkTimer.Stop(true);
181 AutoMarkTimer.Start(1000);
182 }
183 if (saveFile) Save(true);
184 }
185
186
Scroll(int dx,int dy,bool saveFile)187 void emNetwalkModel::Scroll(int dx, int dy, bool saveFile)
188 {
189 emArray<int> arr;
190 int i,j,cp,ap,n,x,y,w,h;
191
192 w=GetWidth();
193 h=GetHeight();
194 n=Raster.GetCount();
195 arr.SetCount(n);
196 for (i=0; i<n; i++) arr.Set(i,GetPiece(i));
197 dx=dx%w; if (dx<0) dx+=w;
198 dy=dy%h; if (dy<0) dy+=h;
199 cp=CurrentPiece.Get();
200 ap=AutoMarkPiece;
201 for (i=0; i<n; i++) {
202 x=(i+dx)%w;
203 y=(i/w+dy)%h;
204 j=y*w+x;
205 SetPiece(j,arr[i]);
206 if (cp==i) CurrentPiece.Set(j);
207 if (ap==i) AutoMarkPiece=j;
208 }
209 if (saveFile) Save(true);
210 }
211
212
emNetwalkModel(emContext & context,const emString & name)213 emNetwalkModel::emNetwalkModel(emContext & context, const emString & name)
214 : emRecFileModel(context,name),
215 emStructRec(),
216 Width(this,"Width",2,2,INT_MAX),
217 Height(this,"Height",2,2,INT_MAX),
218 Borderless(this,"Borderless"),
219 NoFourWayJunctions(this,"NoFourWayJunctions"),
220 Complexity(this,"Complexity",1,1,5),
221 DigMode(this,"DigMode"),
222 AutoMark(this,"AutoMark"),
223 Finished(this,"Finished"),
224 PenaltyPoints(this,"PenaltyPoints"),
225 CurrentPiece(this,"CurrentPiece",-1),
226 Raster(this,"Raster",4,INT_MAX),
227 AutoMarkTimer(GetScheduler()),
228 AutoMarkPiece(-1),
229 AutoMarkToSave(false)
230 {
231 PostConstruct(*this);
232 AddWakeUpSignal(AutoMarkTimer.GetSignal());
233 }
234
235
~emNetwalkModel()236 emNetwalkModel::~emNetwalkModel()
237 {
238 }
239
240
TryContinueLoading()241 bool emNetwalkModel::TryContinueLoading()
242 {
243 if (!emRecFileModel::TryContinueLoading()) return false;
244 if (Width.Get()*Height.Get()!=Raster.GetCount()) {
245 throw emException("file content not consistent");
246 }
247 return true;
248 }
249
250
Cycle()251 bool emNetwalkModel::Cycle()
252 {
253 bool busy;
254
255 busy=emRecFileModel::Cycle();
256 if (IsSignaled(AutoMarkTimer.GetSignal())) {
257 if (AutoMark && AutoMarkPiece!=-1) {
258 if ((GetPiece(AutoMarkPiece)&PF_MARKED)==0) {
259 OrPiece(AutoMarkPiece,PF_MARKED);
260 if (AutoMarkToSave) Save(true);
261 }
262 }
263 AutoMarkPiece=-1;
264 }
265 return busy;
266 }
267
GetNeighborIndex(int index,int angle) const268 int emNetwalkModel::GetNeighborIndex(int index, int angle) const
269 {
270 int w,h,x,y;
271
272 w=Width.Get();
273 h=Height.Get();
274 x=index%w;
275 y=index/w;
276 switch (angle&3) {
277 case 0:
278 x++;
279 if (x<w) break;
280 if (!Borderless.Get()) return -1;
281 x=0;
282 break;
283 case 1:
284 y++;
285 if (y<h) break;
286 if (!Borderless.Get()) return -1;
287 y=0;
288 break;
289 case 2:
290 x--;
291 if (x>=0) break;
292 if (!Borderless.Get()) return -1;
293 x=w-1;
294 break;
295 case 3:
296 y--;
297 if (y>=0) break;
298 if (!Borderless.Get()) return -1;
299 y=h-1;
300 break;
301 }
302 return y*w+x;
303 }
304
305
IsConnected(int index,int angle) const306 bool emNetwalkModel::IsConnected(int index, int angle) const
307 {
308 return (GetPiece(index)&A2PF[angle&3])!=0;
309 }
310
311
Connect(int index,int angle)312 void emNetwalkModel::Connect(int index, int angle)
313 {
314 int index2;
315
316 index2=GetNeighborIndex(index,angle);
317 if (index2<0) return;
318 OrPiece(index,A2PF[angle&3]);
319 OrPiece(index2,A2PF[(angle+2)&3]);
320 }
321
322
Invent()323 void emNetwalkModel::Invent()
324 {
325 static const int PR1[]={100,93,78,70,50};
326 static const int PR2[]={100,93,78,60,0};
327 emArray<int> arr1,arr2;
328 int as[4];
329 int w,h,a,i,j,k,ac,f,pr1,pr2;
330
331 i=Complexity.Get()-1;
332 if (i<0) i=0; else if (i>4) i=4;
333 pr1=PR1[i];
334 pr2=PR2[i];
335 for (i=Raster.GetCount()-1; i>=0; i--) SetPiece(i,0);
336 w=GetWidth();
337 h=GetHeight();
338 if (!NoFourWayJunctions.Get() && w>2 && h>2) {
339 if (Borderless.Get()) i=emGetIntRandom(0,w*h-1);
340 else i=emGetIntRandom(1,h-2)*w+emGetIntRandom(1,w-2);
341 SetPiece(i,PF_CONMASK);
342 for (a=3; a>=0; a--) {
343 j=GetNeighborIndex(i,a);
344 SetPiece(j,A2PF[(a+2)&3]);
345 arr1.Add(j);
346 }
347 }
348 else {
349 i=emGetIntRandom(0,w*h-1);
350 arr1.Add(i);
351 }
352 for (;;) {
353 if (
354 arr1.GetCount()>0 &&
355 (arr2.GetCount()==0 || emGetIntRandom(0,100)<pr1)
356 ) {
357 k=emGetIntRandom(0,arr1.GetCount()-1);
358 i=arr1[k];
359 arr1.Remove(k);
360 for (a=3, ac=-1, f=0; a>=0; a--) {
361 if (IsConnected(i,a)) ac=a;
362 else {
363 j=GetNeighborIndex(i,a);
364 if (j>=0 && GetPiece(j)==0) as[f++]=a;
365 }
366 }
367 if (f>0) {
368 if (
369 ac>=0 &&
370 (j=GetNeighborIndex(i,ac+2))>=0 &&
371 GetPiece(j)==0 &&
372 emGetIntRandom(0,100)<pr2
373 ) {
374 a=(ac+2)&3;
375 }
376 else {
377 a=as[emGetIntRandom(0,f-1)];
378 }
379 Connect(i,a);
380 arr1.Add(GetNeighborIndex(i,a));
381 if (ac==-1) arr1.Add(i); else arr2.Add(i);
382 }
383 else {
384 OrPiece(i,PF_TARGET);
385 }
386 }
387 else if (arr2.GetCount()>0) {
388 k=emGetIntRandom(0,arr2.GetCount()-1);
389 i=arr2[k];
390 for (a=3, f=0; a>=0; a--) {
391 if (IsConnected(i,a)) continue;
392 j=GetNeighborIndex(i,a);
393 if (j>=0 && GetPiece(j)==0) as[f++]=a;
394 }
395 if (f>0) {
396 a=as[emGetIntRandom(0,f-1)];
397 Connect(i,a);
398 arr1.Add(GetNeighborIndex(i,a));
399 }
400 if (f<=1 || NoFourWayJunctions.Get()) arr2.Remove(k);
401 }
402 else break;
403 }
404 i=emGetIntRandom(0,w*h-1);
405 AndPiece(i,~PF_TARGET);
406 OrPiece(i,PF_SOURCE);
407 }
408
409
Shuffle()410 void emNetwalkModel::Shuffle()
411 {
412 int i;
413
414 for (i=Raster.GetCount()-1; i>=0; i--) {
415 SetPiece(i,RawRotate(GetPiece(i),emGetIntRandom(0,3)));
416 }
417 }
418
419
Fill()420 void emNetwalkModel::Fill()
421 {
422 emArray<int> stack;
423 int i,f,a,j;
424
425 for (i=Raster.GetCount()-1; i>=0; i--) {
426 f=GetPiece(i);
427 SetPiece(i,f&~PF_FILLED);
428 if (f&PF_SOURCE) {
429 OrPiece(i,PF_FILLED);
430 stack.Add(i);
431 }
432 }
433 while (stack.GetCount()>0) {
434 i=stack[stack.GetCount()-1];
435 stack.Remove(stack.GetCount()-1);
436 for (a=3; a>=0; a--) {
437 if (!IsConnected(i,a)) continue;
438 j=GetNeighborIndex(i,a);
439 if (j<0) continue;
440 if (GetPiece(j)&PF_FILLED) continue;
441 if (!IsConnected(j,a+2)) continue;
442 OrPiece(j,PF_FILLED);
443 stack.Add(j);
444 }
445 }
446 for (i=Raster.GetCount()-1; i>=0; i--) {
447 f=GetPiece(i);
448 if ((f&PF_FILLED)==0 && (f&PF_CONMASK)!=0) break;
449 }
450 Finished.Set(i<0);
451 }
452
453
Dig(bool reset)454 void emNetwalkModel::Dig(bool reset)
455 {
456 int i,j,a;
457
458 for (i=Raster.GetCount()-1; i>=0; i--) {
459 if (DigMode.Get() && (GetPiece(i)&PF_FILLED)==0) {
460 for (a=3; a>=0; a--) {
461 j=GetNeighborIndex(i,a);
462 if (j<0) continue;
463 if ((GetPiece(j)&PF_FILLED)==0) continue;
464 if (IsConnected(j,a+2)) break;
465 }
466 if (a<0) {
467 if (reset) OrPiece(i,PF_BLOCKED);
468 continue;
469 }
470 }
471 AndPiece(i,~PF_BLOCKED);
472 }
473 }
474
475
RawRotate(int piece,int angle)476 int emNetwalkModel::RawRotate(int piece, int angle)
477 {
478 int c;
479
480 for (angle&=3; angle; angle--) {
481 c=piece&PF_CONMASK;
482 piece&=~PF_CONMASK;
483 if (c&PF_EAST ) piece|=PF_SOUTH;
484 if (c&PF_SOUTH) piece|=PF_WEST;
485 if (c&PF_WEST ) piece|=PF_NORTH;
486 if (c&PF_NORTH) piece|=PF_EAST;
487 }
488 return piece;
489 }
490
491
Solver(emNetwalkModel * model)492 emNetwalkModel::Solver::Solver(emNetwalkModel * model)
493 {
494 int i,n,p,a;
495
496 PieceCount=model->GetWidth()*model->GetHeight();
497 Pieces=new Piece[PieceCount];
498 Groups=new Group[PieceCount];
499 for (n=0; (1<<n)<PieceCount; n++);
500 n=PieceCount*(n+30)+100;
501 TBBuf=new TBEntry[n];
502 TBTop=TBBuf;
503 TBEnd=TBBuf+n;
504 for (i=0; i<PieceCount; i++) {
505 p=model->GetPiece(i);
506 Pieces[i].OrigDirs=0;
507 for (a=0; a<4; a++) {
508 if (p&A2PF[a]) Pieces[i].OrigDirs|=(1<<a);
509 Pieces[i].Neighbor[a]=model->GetNeighborIndex(i,a);
510 }
511 }
512 }
513
514
~Solver()515 emNetwalkModel::Solver::~Solver()
516 {
517 delete [] Pieces;
518 delete [] Groups;
519 delete [] TBBuf;
520 }
521
522
IsUniqueSolution()523 bool emNetwalkModel::Solver::IsUniqueSolution()
524 {
525 int i,a,d,found,cost;
526
527 GroupCount=PieceCount;
528 for (i=0; i<PieceCount; i++) {
529 Pieces[i].Dirs=Pieces[i].OrigDirs;
530 Pieces[i].Placed=0;
531 Pieces[i].Group=i;
532 Pieces[i].NextPiece=-1;
533 Pieces[i].FrontRing=-1;
534 Groups[i].FirstPiece=i;
535 Groups[i].PieceCount=1;
536 Groups[i].OpenCount=0;
537 for (a=3; a>=0; a--) {
538 if (Pieces[i].Dirs&(1<<a)) Groups[i].OpenCount++;
539 }
540 }
541 FrontRing=-1;
542 Current=0;
543 cost=0;
544 found=0;
545 TBClear();
546 TBStart();
547 L_TRACK_DOWN:
548 cost++;
549 if (cost>10000) return false;
550 PlacePiece(Current);
551 do {
552 if (CheckPiece(Current)) {
553 TBStart();
554 if (TBEnd-TBTop<100+PieceCount) {
555 emFatalError("emNetwalkModel::Solver: TBBuf too small");
556 }
557 if (UpdateGroups(Current)) {
558 TBSet(Current,FindAndGetBestNext());
559 if (Current>=0) goto L_TRACK_DOWN;
560 if (GroupCount==1) {
561 if (found>0) return false;
562 found++;
563 }
564 }
565 L_TRACK_BACK:
566 TakeBack();
567 }
568 d=Pieces[Current].Dirs;
569 d=((d<<1)|(d>>3))&0x0F;
570 Pieces[Current].Dirs=d;
571 } while (d!=Pieces[Current].OrigDirs);
572 if (Current>0) goto L_TRACK_BACK;
573 return found==1;
574 }
575
576
CheckPiece(int i) const577 bool emNetwalkModel::Solver::CheckPiece(int i) const
578 {
579 int j,a,d,m,d2,m2;
580
581 d=Pieces[i].Dirs;
582 for (a=3; a>=0; a--) {
583 j=Pieces[i].Neighbor[a];
584 if (j<0) {
585 if (d&(1<<a)) return false;
586 }
587 else if (Pieces[j].Placed) {
588 d2=Pieces[j].Dirs;
589 m2=1<<((a+2)&3);
590 if (d2&m2) {
591 m=(1<<a);
592 if ((d&m)==0) return false;
593 if (d2==m2 && d==m) return false;
594 }
595 else {
596 if (d&(1<<a)) return false;
597 }
598 }
599 }
600 return true;
601 }
602
603
PlacePiece(int i)604 void emNetwalkModel::Solver::PlacePiece(int i)
605 {
606 int a,j;
607
608 TBSet(Pieces[i].Placed,1);
609 for (a=3; a>=0; a--) {
610 j=Pieces[i].Neighbor[a];
611 if (j<0) continue;
612 if (Pieces[j].Placed) continue;
613 if (Pieces[j].FrontRing>=0) continue;
614 if (FrontRing>=0) {
615 TBSet(Pieces[j].FrontRing,Pieces[FrontRing].FrontRing);
616 TBSet(Pieces[FrontRing].FrontRing,j);
617 }
618 else {
619 TBSet(Pieces[j].FrontRing,j);
620 TBSet(FrontRing,j);
621 }
622 }
623 }
624
625
UpdateGroups(int i)626 bool emNetwalkModel::Solver::UpdateGroups(int i)
627 {
628 int a,j,k,g,g2,n,t;
629
630 for (a=3; a>=0; a--) {
631 if ((Pieces[i].Dirs&(1<<a))==0) continue;
632 j=Pieces[i].Neighbor[a];
633 if (!Pieces[j].Placed) continue;
634 g=Pieces[j].Group;
635 g2=Pieces[i].Group;
636 if (g==g2) return false;
637 if (Groups[g].PieceCount<Groups[g2].PieceCount) { t=g; g=g2; g2=t; }
638 n=Groups[g].OpenCount+Groups[g2].OpenCount-2;
639 if (n<=0 && GroupCount>2) return false;
640 TBSet(Groups[g].OpenCount,n);
641 TBSet(Groups[g].PieceCount,Groups[g].PieceCount+Groups[g2].PieceCount);
642 TBSet(GroupCount,GroupCount-1);
643 for (k=Groups[g2].FirstPiece;;) {
644 TBSet(Pieces[k].Group,g);
645 t=Pieces[k].NextPiece;
646 if (t<0) break;
647 k=t;
648 }
649 TBSet(Pieces[k].NextPiece,Groups[g].FirstPiece);
650 TBSet(Groups[g].FirstPiece,Groups[g2].FirstPiece);
651 }
652 return true;
653 }
654
655
FindAndGetBestNext()656 int emNetwalkModel::Solver::FindAndGetBestNext()
657 {
658 int i,j,d,n,nBest,iBest;
659
660 if (FrontRing<0) return -1;
661 iBest=FrontRing;
662 nBest=5;
663 for (i=FrontRing;;) {
664 j=Pieces[i].FrontRing;
665 n=0;
666 do {
667 if (CheckPiece(j)) n++;
668 d=Pieces[j].Dirs;
669 d=((d<<1)|(d>>3))&0x0F;
670 Pieces[j].Dirs=d;
671 } while (d!=Pieces[j].OrigDirs);
672 if (nBest>n) {
673 nBest=n;
674 iBest=i;
675 if (n<=1) break;
676 }
677 i=j;
678 if (i==FrontRing) break;
679 }
680 i=iBest;
681 j=Pieces[i].FrontRing;
682 if (i==j) {
683 TBSet(FrontRing,-1);
684 }
685 else {
686 if (FrontRing!=i) TBSet(FrontRing,i);
687 TBSet(Pieces[i].FrontRing,Pieces[j].FrontRing);
688 }
689 TBSet(Pieces[j].FrontRing,-1);
690 return j;
691 }
692
693
TakeBack()694 void emNetwalkModel::Solver::TakeBack()
695 {
696 TBEntry * t;
697
698 for (t=TBTop-1; t->Ptr; t--) *(t->Ptr)=t->Val;
699 TBTop=t;
700 }
701
702
703 const int emNetwalkModel::A2PF[4]={
704 PF_EAST, PF_SOUTH, PF_WEST, PF_NORTH
705 };
706