11
\$\begingroup\$

Today, we'll be generating a map for a roguelike RPG!

Example Map:

##########
####    F#
####    ##
##    C#C#
#     ## #
# C   #E #
####  #  #
#        #
#P       #
##########

# are walls, P is the player's starting location, F is the finish that must be reached, C are coins that can be collected, and E are enemies that can be fought.

Map specifications:

  • Height and Width should both be between 10 and 39, inclusive. Height does not have to equal width.
  • The maps borders should be filled in with walls.
  • P should be placed in the bottom left corner.
  • F should be placed in the top right corner.
  • There should be between 1 and 3 enemies.
  • There should be between 2 and 4 coins.
  • There should be some amount of walls in the middle. There should be a path to get from P to Every C, E, and F, keeping in mind that the player cannot move diagonally.
  • Every possible combination should have some chance of occurring.

Rules

  • Fewest byte program wins.
  • Your program should not take any input.
  • Your program may not exit with an error (non-fatal output is STDERR is ok, but we can't have our rogue-like crash after map generation!)
  • A single trailing newline is allowed and trailing space is allowed.
  • No other output is allowed.
\$\endgroup\$
  • 3
    \$\begingroup\$ It's roguelike, just fyi. \$\endgroup\$ – Rɪᴋᴇʀ Dec 13 '16 at 18:31
  • 2
    \$\begingroup\$ Can you clarify "every possible combination should have an equal chance of occurring"? Do you literally mean that all the valid maps (in particular, all maps where P can reach all the C/E/Fs) must occur with equal probability? If so, it seems that the only possible algorithm is to generate maps uniformly at random and then check that P can reach everything, discarding invalid maps until that happens. \$\endgroup\$ – Greg Martin Dec 13 '16 at 19:15
  • \$\begingroup\$ Can you also clarify - "There should be some amount of walls in the middle", what if I place only 2 walls all the time? \$\endgroup\$ – Gurupad Mamadapur Dec 13 '16 at 19:17
  • 1
    \$\begingroup\$ @GregMartin I'll change it too "Every possible layout should have a chance of occurring", not necessarily an equal chance. \$\endgroup\$ – Pavel Dec 13 '16 at 19:20
  • 2
    \$\begingroup\$ What about unreachable empty squares surrounded by walls? Is it a valid layout or should they be avoided altogether? (In other words: should each empty square be reachable?) \$\endgroup\$ – Arnauld Dec 14 '16 at 10:19
5
\$\begingroup\$

Perl, 293 bytes

-9 bytes thanks to @Dom Hastings

{$==7+rand 30;@r=$"=();@a=((C)x4,(E)x3,("#")x1369,(" ")x1369);for$i(0..7+rand 30){$r[$i][$_]=splice@a,rand@a,1for 0..$=}$r[0][$=]=F;$r[-1][0]=P;$_=$r=join$/,$v="#"x($=+=3),(map"#@$_#",@r),$v;1while$r=~s/F(.{$=})?[^#F]/F$1F/s||$r=~s/[^#F](.{$=})?F/F$1F/s;$r!~/[CEP]/&&/C.*C/s&&/E/?last:redo}say

Add -E flag to run it:

perl -E '{$==7+rand 30;@r=$"=();@a=((C)x4,(E)x3,("#")x1369,(" ")x1369);for$i(0..7+rand 30){$r[$i][$_]=splice@a,rand@a,1for 0..$=}$r[0][$=]=F;$r[-1][0]=P;$_=$r=join$/,$v="#"x($=+=3),(map"#@$_#",@r),$v;1while$r=~s/F(.{$=})?[^#F]/F$1F/s||$r=~s/[^#F](.{$=})?F/F$1F/s;$r!~/[CEP]/&&/C.*C/s&&/E/?last:redo}say'

However, it takes a long time to run, so I recommend using this version instead:

perl -E '{${$_}=8+rand 30for"=","%";@r=$"=();@a=((C)x4,(E)x3,("#")x($v=rand $=*$%),(" ")x($=*$%-$v));for$i(0..$%-1){$r[$i][$_]=splice@a,rand@a,1for 0..$=-1}$r[0][$=-1]=F;$r[$%-1][0]=P;$_=$r=join$/,$v="#"x($=+=2),(map"#@$_#",@r),$v;1while$r=~s/F(.{$=})?[^#F]/F$1F/s||$r=~s/[^#F](.{$=})?F/F$1F/s;$r!~/[CEP]/&&/C.*C/s&&/E/?last:redo}say'

Try it online!

Explanation

{                     # enter a block (which is used as a loop)
    {$==7+rand 30;                   # randomly select the width of the map -2
                                     # (-2 because we don't include the borders yet)
    @r=$"=();                        # reset @r, and set $" to undef
    @a=(                             # create a list of the character that can be on the board
     (C)x4,                          #  4 coins 'C'
     (E)x3,                          #  3 enemies 'E'
     ("#")x1369,                     #  37*37 '#'
     (" ")x1369);                    #  37*37 spaces
    for$i(0..7+rand 30)                # create the 2D map (7+rand 30 is the height, which is generated just now)
      for$_(0..$=-1){
        $r[$i][$_]=                    # index [$i][$_] receives ...
           splice@a,rand@a,1           # .. a random character from the list previously generated
                                       # (the character is then removed from the list thanks to 'splice')
      }
    }
    $r[0][$=]=F;                       # add the finish cell
    $r[-1][0]=P;                       # add the start cell
    $_=$r=                             # here we generate a string representation of the map
          join$/,                      # join the following elements with newlines
            $v="#"x($=+=3),            # a first line of # only
            (map"#@$_#",@r),           # add a # to the beginning and the end of each line
            $v;                        # the last line of #

    1while                # the following regex will replace every accessible cell with a F
       $r=~s/F(.{$=})?[^#F]/F$1F/s  # a cell on the right or the bottom of a F cell is replaced  
         ||                         # or
       $r=~s/[^#F](.{$=})?F/F$1F/s; # a cell on the left or the top of a F cell is replaced
    $r!~/[CEP]/         # if there is no C, E or P on the map (meaning they were all accessible)
     && /C.*C/s         #  and there are at least 2 coins
     && /E/ ?           #  and 1 enemy
      last:             # the the map is valid, we exit the loop
      redo              # else, start over
}
say                     # and print the board

It takes a long time to run, because the list from which we randomly pick the characters to put on the board (@a) contains 1369 whitespaces and #, and only 4 coins and 3 enemies. So if the size of the width and height are small, there are a lot of spaces and # compared to the coin and the enemies, so it's quite likely that a random map won't be valid. That's why the "optimized" version is faster: the list from which we pick the characters is just a little bigger than the map (the list is @a=((C)x4,(E)x3,("#")x($v=rand $=*$%),($")x($=*$%-$v)) : a random number $v of # (inferior to the size of the map), and size of the map - $v whitespaces).

\$\endgroup\$
  • \$\begingroup\$ I don't really know perl, but looking at the syntax highlighting you appear to have an unmatched quote in ($")x$=**2);. Out maybe the highlighting doesn't work right and that's a feature. Also, whitespace can be unreachable. \$\endgroup\$ – Pavel Dec 14 '16 at 14:52
  • 1
    \$\begingroup\$ @Pavel $" is a legit Perl variable, but the syntax highlighting doesn't know about it, that's why it looks like that. Ok, I'll delete the comment about unreachable spaces. \$\endgroup\$ – Dada Dec 14 '16 at 16:10
5
\$\begingroup\$

PHP, 422 417 415 309 373 369 364 361 bytes

function w($p){global$r,$h,$w;for($q=$p;$r[$q]<A;)for($r[$p=$q]=" ";($q=$p+(1-(2&$m=rand()))*($m&1?:$w))%$w%($w-1)<1|$q/$w%$h<1;);}$r=str_pad("",($w=rand(10,39))*$h=rand(10,39),"#");$r[$w*2-2]=F;w($p=$q=$w*(--$h-1)+1);$r[$p]=P;for($c=rand(2,4);$i<$c+rand(1,3);$p=rand($w,$h*$w))if($r[$p]<A&&$p%$w%($w-1)){w($p);$r[$p]=EC[$i++<$c];w($p);}echo chunk_split($r,$w);

operates on a string without linebreaks; digs random paths between the extras. Run with -r.

Note: The paths are created by walking in random directions. The choice of direction for every step will mostly generate maps that are wide open; and the example map is very unlikely to appear; but it is possible.

breakdown

// aux function: randomly walk away from $p placing spaces, stop when a special is reached
function w($p)
{global$r,$h,$w;
    for($q=$p;
        $r[$q]<A;                               // while $q is not special
    )
        for($r[$p=$q]=" ";                          // 3. replace with space
            ($q=$p+(1-(2&$m=rand()))*($m&1?:$w))    // 1. pick random $q next to $p
            %$w%($w-1)<1|$q/$w%$h<1;                // 2. that is not on the borders
        );
}

// initialize map
$r=str_pad("",
    ($w=rand(10,39))*$h=rand(10,39) // random width and height
    ,"#");                          // fill with "#"
$r[$w*2-2]=F;                       // place Finish
w($p=$q=$w*(--$h-1)+1);             // build path from Player position to F
// $h is now height -1 !
$r[$p]=P;                           // place Player

// place Coins ans Enemies
for($c=rand(2,4);$i<$c+rand(1,3);   // while $i has not reached no. of coins+no. of enemies
    $p=rand($w,$h*$w))              // pick a random position
    if($r[$p]<A&&$p%$w%($w-1))      // that is neither special nor out of bounds
    {
        w($p);                      // build path from there to another special
        $r[$p]=EC[$i++<$c];         // place this special
        w($p);      // additional path to allow special in the middle of a dead end tunnel
    }

// insert linebreaks and print
echo chunk_split($r,$w);
\$\endgroup\$
  • \$\begingroup\$ In your explanation you're generating height and width to 37, not to 39. \$\endgroup\$ – Pavel Dec 14 '16 at 14:49
  • \$\begingroup\$ @Pavel fixed; thanks for noticing \$\endgroup\$ – Titus Dec 14 '16 at 15:10
  • \$\begingroup\$ Outputs it's own source code when I tried in on Try it online \$\endgroup\$ – Pavel Dec 14 '16 at 17:05
  • \$\begingroup\$ @Pavel you need to surround the code with <?php .... ?> \$\endgroup\$ – Dada Dec 14 '16 at 17:38
  • 1
    \$\begingroup\$ Ok, I did that, and I noticed that the walls are generated in regular rectangular chunks. It should be able to generate something like the example map. It also doesn't always generate Es. \$\endgroup\$ – Pavel Dec 14 '16 at 17:47
3
\$\begingroup\$

C# (Visual C# Interactive Compiler), 730 bytes

var R=new Random();for(;;){char P='P',C='C',E='E',Q='#';int w=R.Next(8,37),h=R.Next(8,37),H=h,t,g=99,W,i,j,r;string l,s,p=new string(Q,w+2);var m=new List<string>();for(;H>0;H--){l="";for(W=w;W>0;W--){r=R.Next(999);l+=r<3?C:r<6?E:r<g?Q:' ';}m.Add(l);}m[0]=m[0].Substring(0,w-1)+'F';m[h-1]=P+m[h-1].Substring(1);s=String.Join("#\n#",m);t=s.Split(E).Length-1;if(t<1||t>3)continue;t=s.Split(C).Length-1;if(t<2||t>4)continue;while(g>0){g--;for(i=0;i<h;i++)for(j=0;j<w;j++)if(m[i][j]!=Q&&m[i][j]!=P&&(i>0&&m[i-1][j]==P)||(i<h-1&&m[i+1][j]==P)||(j>0&&m[i][j-1]==P)||(j<w-1&&m[i][j+1]==P))m[i]=m[i].Substring(0,j)+P+m[i].Substring(j+1,w-j-1);}if(String.Join("",m).Split(E,C,'F').Length>1)continue;Console.Write(p+"\n#"+s+"#\n"+p);break;}

Try it online!

Ungolfed:

var R = new Random();
for (;;)
{
    char P = 'P', C = 'C', E = 'E', poundSymbol = '#';
    int width = R.Next(8, 37), height = R.Next(8, 37), HeightTemp = height, testVariable, goThroughLoop = 99, WidthTemp, i, j, rand;
    string line, strMap, poundSymbolPadding = new string(poundSymbol, width + 2);

    var map = new List<string>(); //initialize map
    for (; HeightTemp > 0; HeightTemp--)
    {
        line = "";
        for (WidthTemp = width; WidthTemp > 0; WidthTemp--)
        {
            rand = R.Next(999);
            //add a character randomly.  Re-use the goThroughLoop variable here, which gives approx. 1 wall per 10 spaces.
            line += rand < 3 ? C : rand < 6 ? E : rand < goThroughLoop ? poundSymbol : ' ';
        }
        map.Add(line);
    }
    //add finish and player
    map[0] = map[0].Substring(0, width - 1) + 'F';
    map[height - 1] = P + map[height - 1].Substring(1);

    strMap = String.Join("#\n#", map);
    //check proper # of enemies, regenerate if invalid
    testVariable = strMap.Split(E).Length - 1;
    if (testVariable < 1 || testVariable > 3)
        continue;
    //check proper # of coins, regenerate if invalid
    testVariable = strMap.Split(C).Length - 1;
    if (testVariable < 2 || testVariable > 4)
        continue;
    //map out areas Player can access.  Iterates until all accessible places have been marked as such.
    while (goThroughLoop > 0)
    {
        goThroughLoop--;
        for (i = 0; i < height; i++)
            for (j = 0; j < width; j++)
                if (map[i][j] != poundSymbol && map[i][j] != P && ((i > 0 && map[i - 1][j] == P) || (i < height - 1 && map[i + 1][j] == P) || (j > 0 && map[i][j - 1] == P) || (j < width - 1 && map[i][j + 1] == P)))
                    //mark this space as accessible
                    map[i] = map[i].Substring(0, j) + P + map[i].Substring(j + 1, width - j - 1);
    }
    //if player cannot access all features (defeated enmies, collected coins, arrived at finish), regenerate map.
    if (String.Join("", map).Split(E, C, 'F').Length > 1)
        continue;

    //output our final map
    Console.Write(poundSymbolPadding + "\n#" + strMap + "#\n" + poundSymbolPadding);

    break;
}

Edit: saved 8 bytes, made it slightly less efficient by locking the player accessible test loop to 99 iterations. I know it'll never really compete with the other answers here, but I'm having fun!

\$\endgroup\$
  • \$\begingroup\$ @GregMartin Now it's your turn to implement it in F# ;-) \$\endgroup\$ – Bence Joful Dec 20 '16 at 19:04
  • 2
    \$\begingroup\$ A simple modulation to the subdominant, no problem :) \$\endgroup\$ – Greg Martin Dec 20 '16 at 19:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.