ViewVC Help
View File | Revision Log | Show Annotations | Download File
/cvs/deliantra/server/random_maps/layout.C
(Generate patch)

Comparing deliantra/server/random_maps/layout.C (file contents):
Revision 1.4 by root, Thu Jul 1 01:27:14 2010 UTC vs.
Revision 1.5 by root, Fri Jul 2 03:40:14 2010 UTC

1/* 1/*
2 * This file is part of Deliantra, the Roguelike Realtime MMORPG. 2 * This file is part of Deliantra, the Roguelike Realtime MMORPG.
3 * 3 *
4 * Copyright (©) 2010 Marc Alexander Lehmann / Robin Redeker / the Deliantra team 4 * Copyright (©) 2010 Marc Alexander Lehmann / Robin Redeker / the Deliantra team
5 * Copyright (©) Crossfire Development Team (restored, original file without copyright notice)
5 * 6 *
6 * Deliantra is free software: you can redistribute it and/or modify it under 7 * Deliantra is free software: you can redistribute it and/or modify it under
7 * the terms of the Affero GNU General Public License as published by the 8 * the terms of the Affero GNU General Public License as published by the
8 * Free Software Foundation, either version 3 of the License, or (at your 9 * Free Software Foundation, either version 3 of the License, or (at your
9 * option) any later version. 10 * option) any later version.
… …
20 * The authors can be reached via e-mail to <support@deliantra.net> 21 * The authors can be reached via e-mail to <support@deliantra.net>
21 */ 22 */
22 23
23#include <global.h> 24#include <global.h>
24#include <random_map.h> 25#include <random_map.h>
26#include <rproto.h>
25 27
26Layout::Layout (int w, int h) 28Layout::Layout (int w, int h)
27: w(w), h(h) 29: w(w), h(h)
28{ 30{
29 int size = (sizeof (char *) + sizeof (char) * h) * w; 31 int size = (sizeof (char *) + sizeof (char) * h) * w;
… …
120} 122}
121 123
122///////////////////////////////////////////////////////////////////////////// 124/////////////////////////////////////////////////////////////////////////////
123 125
124void 126void
125Layout::print () 127Layout::print () const
126{ 128{
127 for (int y = 0; y < h; y++) 129 for (int y = 0; y < h; y++)
128 { 130 {
129 for (int x = 0; x < w; x++) 131 for (int x = 0; x < w; x++)
130 { 132 {
… …
335 337
336 border (); 338 border ();
337 isolation_remover (); 339 isolation_remover ();
338} 340}
339 341
342/////////////////////////////////////////////////////////////////////////////
343
344//+GPL
345
346/* puts doors at appropriate locations in a layout. */
347void
348Layout::doorify ()
349{
350 int ndoors = w * h / 60; /* reasonable number of doors. */
351 int doorlocs = 0; /* # of available doorlocations */
352
353 uint16 *doorlist_x = salloc<uint16> (w * h);
354 uint16 *doorlist_y = salloc<uint16> (w * h);
355
356 /* make a list of possible door locations */
357 for (int i = 1; i < w - 1; i++)
358 for (int j = 1; j < h - 1; j++)
359 {
360 int sindex = surround_flag (*this, i, j);
361
362 if (sindex == 3 || sindex == 12) /* these are possible door sindex */
363 {
364 doorlist_x [doorlocs] = i;
365 doorlist_y [doorlocs] = j;
366 doorlocs++;
367 }
368 }
369
370 while (ndoors > 0 && doorlocs > 0)
371 {
372 int di = rmg_rndm (doorlocs);
373 int i = doorlist_x [di];
374 int j = doorlist_y [di];
375 int sindex = surround_flag (*this, i, j);
376
377 if (sindex == 3 || sindex == 12) /* these are possible door sindex */
378 {
379 col [i][j] = 'D';
380 ndoors--;
381 }
382
383 /* reduce the size of the list */
384 doorlocs--;
385 doorlist_x[di] = doorlist_x [doorlocs];
386 doorlist_y[di] = doorlist_y [doorlocs];
387 }
388
389 sfree (doorlist_x, w * h);
390 sfree (doorlist_y, w * h);
391}
392
393/* takes a map and makes it symmetric: adjusts Xsize and
394 * Ysize to produce a symmetric map.
395 */
396void
397Layout::symmetrize (int symmetry)
398{
399 if (symmetry == SYMMETRY_NONE)
400 return;
401
402 Layout sym_layout (
403 symmetry == SYMMETRY_X || symmetry == SYMMETRY_XY ? w * 2 - 3 : w,
404 symmetry == SYMMETRY_Y || symmetry == SYMMETRY_XY ? h * 2 - 3 : h
405 );
406
407 if (symmetry == SYMMETRY_X)
408 for (int i = 0; i < sym_layout.w / 2 + 1; i++)
409 for (int j = 0; j < sym_layout.h; j++)
410 {
411 sym_layout[i ][j] =
412 sym_layout[sym_layout.w - i - 1][j] = col[i][j];
413 }
414
415 if (symmetry == SYMMETRY_Y)
416 for (int i = 0; i < sym_layout.w; i++)
417 for (int j = 0; j < sym_layout.h / 2 + 1; j++)
418 {
419 sym_layout[i][j ] =
420 sym_layout[i][sym_layout.h - j - 1] = col[i][j];
421 }
422
423 if (symmetry == SYMMETRY_XY)
424 for (int i = 0; i < sym_layout.w / 2 + 1; i++)
425 for (int j = 0; j < sym_layout.h / 2 + 1; j++)
426 {
427 sym_layout[i ][j ] =
428 sym_layout[i ][sym_layout.h - j - 1] =
429 sym_layout[sym_layout.w - i - 1][j ] =
430 sym_layout[sym_layout.w - i - 1][sym_layout.h - j - 1] = col[i][j];
431 }
432
433 /* need to run the isolation remover for some layouts */
434#if 0
435 switch (RP->map_layout_style)
436 {
437 case LAYOUT_ONION:
438 case LAYOUT_SNAKE:
439 case LAYOUT_SQUARE_SPIRAL:
440 // safe
441 break;
442
443 default:
444 sym_layout.isolation_remover ();
445 break;
446 }
447#endif
448 sym_layout.isolation_remover ();
449
450 swap (sym_layout);
451}
452
453//-GPL
454
455void
456Layout::rotate (int rotation)
457{
458 switch (rotation & 3)
459 {
460 case 2: /* a reflection */
461 {
462 Layout new_layout (w, h);
463
464 for (int i = 0; i < w; i++) /* copy a reflection back */
465 for (int j = 0; j < h; j++)
466 new_layout [i][j] = col [w - i - 1][h - j - 1];
467
468 swap (new_layout);
469 }
470 break;
471
472 case 1:
473 case 3:
474 {
475 Layout new_layout (h, w);
476
477 if (rotation == 1) /* swap x and y */
478 for (int i = 0; i < w; i++)
479 for (int j = 0; j < h; j++)
480 new_layout [j][i] = col [i][j];
481
482 if (rotation == 3) /* swap x and y */
483 for (int i = 0; i < w; i++)
484 for (int j = 0; j < h; j++)
485 new_layout [j][i] = col [w - i - 1][h - j - 1];
486
487 swap (new_layout);
488 }
489 break;
490 }
491}
492
493/////////////////////////////////////////////////////////////////////////////
494
495//+GPL
496
497/*
498 * Expands a layout by 2x in each dimension.
499 * H. S. Teoh
500 */
501
502/* Copy the old tile X into the new one at location (i*2, j*2) and
503 * fill up the rest of the 2x2 result with \0:
504 * X ---> X \0
505 * \0 \0
506 */
507static void inline
508expand_misc (Layout &newlayout, int i, int j, Layout &layout)
509{
510 newlayout[i * 2 + rmg_rndm (1)][j * 2 + rmg_rndm (1)] = layout[i][j];
511 /* (Note: no need to reset rest of 2x2 area to \0 because calloc does that
512 * for us.) */
513}
514
515/* Returns a bitmap that represents which squares on the right and bottom
516 * edges of a square (i,j) match the given character:
517 * 1 match on (i+1, j)
518 * 2 match on (i, j+1)
519 * 4 match on (i+1, j+1)
520 * and the possible combinations thereof.
521 */
522static int noinline
523calc_pattern (char ch, Layout &layout, int i, int j)
524{
525 int pattern = 0;
526
527 if (i + 1 < layout.w && layout[i + 1][j] == ch)
528 pattern |= 1;
529
530 if (j + 1 < layout.h)
531 {
532 if (layout[i][j + 1] == ch)
533 pattern |= 2;
534
535 if (i + 1 < layout.w && layout[i + 1][j + 1] == ch)
536 pattern |= 4;
537 }
538
539 return pattern;
540}
541
542/* Expand a wall. This function will try to sensibly connect the resulting
543 * wall to adjacent wall squares, so that the result won't have disconnected
544 * walls.
545 */
546static void inline
547expand_wall (Layout &newlayout, int i, int j, Layout &layout)
548{
549 int wall_pattern = calc_pattern ('#', layout, i, j);
550 int door_pattern = calc_pattern ('D', layout, i, j);
551 int both_pattern = wall_pattern | door_pattern;
552
553 newlayout[i * 2][j * 2] = '#';
554
555 if (i + 1 < layout.w)
556 {
557 if (both_pattern & 1)
558 { /* join walls/doors to the right */
559/* newlayout[i*2+1][j*2] = '#'; */
560 newlayout[i * 2 + 1][j * 2] = layout[i + 1][j];
561 }
562 }
563
564 if (j + 1 < layout.h)
565 {
566 if (both_pattern & 2)
567 { /* join walls/doors to the bottom */
568/* newlayout[i*2][j*2+1] = '#'; */
569 newlayout[i * 2][j * 2 + 1] = layout[i][j + 1];
570 }
571
572 if (wall_pattern == 7)
573 { /* if orig layout is a 2x2 wall block,
574 * we fill the result with walls. */
575 newlayout[i * 2 + 1][j * 2 + 1] = '#';
576 }
577 }
578}
579
580/* This function will try to sensibly connect doors so that they meet up with
581 * adjacent walls. Note that it will also presumptuously delete (ignore) doors
582 * that it doesn't know how to correctly expand.
583 */
584static void inline
585expand_door (Layout &newlayout, int i, int j, Layout &layout)
586{
587 int wall_pattern = calc_pattern ('#', layout, i, j);
588 int door_pattern = calc_pattern ('D', layout, i, j);
589 int join_pattern;
590
591 /* Doors "like" to connect to walls more than other doors. If there is
592 * a wall and another door, this door will connect to the wall and
593 * disconnect from the other door. */
594 if (wall_pattern & 3)
595 join_pattern = wall_pattern;
596 else
597 join_pattern = door_pattern;
598
599 newlayout[i * 2][j * 2] = 'D';
600
601 if (i + 1 < layout.w)
602 if (join_pattern & 1)
603 /* there is a door/wall to the right */
604 newlayout[i * 2 + 1][j * 2] = 'D';
605
606 if (j + 1 < layout.h)
607 if (join_pattern & 2)
608 /* there is a door/wall below */
609 newlayout[i * 2][j * 2 + 1] = 'D';
610}
611
612void
613Layout::expand2x ()
614{
615 Layout new_layout (w * 2 - 1, h * 2 - 1);
616
617 new_layout.clear ();
618
619 for (int i = 0; i < w; i++)
620 for (int j = 0; j < h; j++)
621 switch (col [i][j])
622 {
623 case '#': expand_wall (new_layout, i, j, *this); break;
624 case 'D': expand_door (new_layout, i, j, *this); break;
625 default: expand_misc (new_layout, i, j, *this); break;
626 }
627
628 swap (new_layout);
629}
630
631/////////////////////////////////////////////////////////////////////////////
632
633/* checks the layout to see if I can stick a horizontal(dir = 0) wall
634 (or vertical, dir == 1)
635 here which ends up on other walls sensibly. */
636static int
637can_make_wall (const Layout &maze, int dx, int dy, int dir)
638{
639 int i1;
640 int length = 0;
641
642 /* dont make walls if we're on the edge. */
643 if (dx == 0 || dx == (maze.w - 1) || dy == 0 || dy == (maze.h - 1))
644 return -1;
645
646 /* don't make walls if we're ON a wall. */
647 if (maze [dx][dy] != 0)
648 return -1;
649
650 if (dir == 0) /* horizontal */
651 {
652 int y = dy;
653
654 for (i1 = dx - 1; i1 > 0; i1--)
655 {
656 int sindex = surround_flag2 (maze, i1, y);
657
658 if (sindex == 1) break;
659 if (sindex != 0) return -1; /* can't make horiz. wall here */
660 if (maze[i1][y] != 0) return -1; /* can't make horiz. wall here */
661
662 length++;
663 }
664
665 for (i1 = dx + 1; i1 < maze.w - 1; i1++)
666 {
667 int sindex = surround_flag2 (maze, i1, y);
668
669 if (sindex == 2) break;
670 if (sindex != 0) return -1; /* can't make horiz. wall here */
671 if (maze[i1][y] != 0) return -1; /* can't make horiz. wall here */
672
673 length++;
674 }
675 return length;
676 }
677 else
678 { /* vertical */
679 int x = dx;
680
681 for (i1 = dy - 1; i1 > 0; i1--)
682 {
683 int sindex = surround_flag2 (maze, x, i1);
684
685 if (sindex == 4) break;
686 if (sindex != 0) return -1; /* can't make vert. wall here */
687 if (maze[x][i1] != 0) return -1; /* can't make horiz. wall here */
688
689 length++;
690 }
691
692 for (i1 = dy + 1; i1 < maze.h - 1; i1++)
693 {
694 int sindex = surround_flag2 (maze, x, i1);
695
696 if (sindex == 8) break;
697 if (sindex != 0) return -1; /* can't make verti. wall here */
698 if (maze[x][i1] != 0) return -1; /* can't make horiz. wall here */
699
700 length++;
701 }
702
703 return length;
704 }
705
706 return -1;
707}
708
709int
710make_wall (char **maze, int x, int y, int dir)
711{
712 maze[x][y] = 'D'; /* mark a door */
713
714 switch (dir)
715 {
716 case 0: /* horizontal */
717 {
718 for (int i1 = x - 1; maze[i1][y] == 0; --i1) maze[i1][y] = '#';
719 for (int i1 = x + 1; maze[i1][y] == 0; ++i1) maze[i1][y] = '#';
720 break;
721 }
722 case 1: /* vertical */
723 {
724 for (int i1 = y - 1; maze[x][i1] == 0; --i1) maze[x][i1] = '#';
725 for (int i1 = y + 1; maze[x][i1] == 0; ++i1) maze[x][i1] = '#';
726 break;
727 }
728 }
729
730 return 0;
731}
732
733void
734Layout::roomify ()
735{
736 int tries = w * h / 30;
737
738 for (int ti = 0; ti < tries; ti++)
739 {
740 /* starting location for looking at creating a door */
741 int dx = rmg_rndm (w);
742 int dy = rmg_rndm (h);
743
744 /* results of checking on creating walls. */
745 int cx = can_make_wall (*this, dx, dy, 0); /* horizontal */
746 int cy = can_make_wall (*this, dx, dy, 1); /* vertical */
747
748 if (cx == -1)
749 {
750 if (cy != -1)
751 make_wall (*this, dx, dy, 1);
752
753 continue;
754 }
755
756 if (cy == -1)
757 {
758 make_wall (*this, dx, dy, 0);
759 continue;
760 }
761
762 if (cx < cy)
763 make_wall (*this, dx, dy, 0);
764 else
765 make_wall (*this, dx, dy, 1);
766 }
767}
768
769/////////////////////////////////////////////////////////////////////////////
770
771/* function selects the layout function and gives it whatever
772 arguments it needs. */
773void
774Layout::generate (random_map_params *RP)
775{
776 switch (RP->map_layout_style)
777 {
778 case LAYOUT_ONION:
779 map_gen_onion (*this, RP->layoutoptions1, RP->layoutoptions2);
780
781 if (!(rmg_rndm (3)) && !(RP->layoutoptions1 & (RMOPT_WALLS_ONLY | RMOPT_WALL_OFF)))
782 roomify ();
783
784 break;
785
786 case LAYOUT_MAZE:
787 maze_gen (*this, RP->get_iv ("maze_type", rmg_rndm (4)));
788
789 if (rmg_rndm (2))
790 doorify ();
791
792 break;
793
794 case LAYOUT_SPIRAL:
795 map_gen_spiral (*this, RP->layoutoptions1);
796
797 if (rmg_rndm (2))
798 doorify ();
799
800 break;
801
802 case LAYOUT_ROGUELIKE:
803 /* Don't put symmetry in rogue maps. There isn't much reason to
804 * do so in the first place (doesn't make it any more interesting),
805 * but more importantly, the symmetry code presumes we are symmetrizing
806 * spirals, or maps with lots of passages - making a symmetric rogue
807 * map fails because its likely that the passages the symmetry process
808 * creates may not connect the rooms.
809 */
810 RP->symmetry_used = SYMMETRY_NONE;
811 roguelike_layout_gen (*this, RP->layoutoptions1);
812 /* no doorifying... done already */
813 break;
814
815 case LAYOUT_SNAKE:
816 make_snake_layout (*this, RP->layoutoptions1);
817
818 if (rmg_rndm (2))
819 roomify ();
820
821 break;
822
823 case LAYOUT_SQUARE_SPIRAL:
824 make_square_spiral_layout (*this, RP->layoutoptions1);
825
826 if (rmg_rndm (2))
827 roomify ();
828
829 break;
830
831 case LAYOUT_CAVE:
832 gen_cave (RP->get_iv ("cave_type", rmg_rndm (4)));
833
834 if (rmg_rndm (2))
835 doorify ();
836
837 break;
838
839 default:
840 abort ();
841 }
842
843 /* rotate the layout randomly */
844 rotate (rmg_rndm (4));
845
846 symmetrize (RP->symmetry_used);
847
848#if 0
849 print ();//D
850#endif
851
852 if (RP->expand2x)
853 expand2x ();
854}
855
856//-GPL
857
340#if 0 858#if 0
341static struct demo 859static struct demo
342{ 860{
343 demo () 861 demo ()
344 { 862 {

Diff Legend

– Removed lines
+ Added lines
< Changed lines
> Changed lines