# Light up a Roguelike

Given a board, write the shortest program or function to display or return which characters are in sight of the player. A character is in sight if is possible to draw a line between it and the player, without crossing any characters that block vision.

Input:

• @ represents the player's position. There will only be one of these in the input.
• any character that matches the regex [#A-Z] blocks vision.
• any character that matches [ a-z] allows vision.
• there will be no invalid characters
• you are guaranteed a rectangular input

Lines are defined as follows:

• define vector to be a magnitude and a direction
• a direction is one of N,NE,E,SE,S,SW,W,NW
• a magnitude is how many chars along that direction to count
• let the initial vector be called d1; the second vector be called d2
• one of d1 or d2 must have a magnitude of 1; the other may have whatever magnitude
• d1's direction must be adjacent to d2's direction (e.g: N and NE)

A line is defined to be all chars along the path marked by applying d1, then d2, d1, d2 ....

Sample line (given by the .s):
d1 = (magnitude: 4, direction: E)
d2 = (magnitude: 1, direction NE)

               .....
.....
.....
@....


Output:

• each visible character in the right position, . substitutes for space.
• Space for each non-visible character.

Sample input:

@
K
J

L

o


Corresponding output:

@.........
....K.....
.J.....
..........
.. .L.....
..  . ....
... .. ...
...  .. ..
...   .  .
....  ..


Sample Input:

 B###M#  by
#Q   # Zmpq
# # aaa
@  m #
# ##P#
# ####
# ####
#M ###
######


Corresponding Output:

.B  #M
.# ..   Z pq
.#.#.aaa..
@..m.#
#.##P#
.#
.#
M.
#


Sample input:

  w

O  l   gg  rT
QQL      Ag  #b
qqqqq         XqQ
x     V# f@aa
Y        aaa
uU  E  l TaKK
e  dd  FF d opi
e       d


Corresponding output:

   ..........  .....
......... .....
O..l...gg..rT
...QQL......Ag..#b..
...qqqqq.........XqQ
#.f@aa......
Y........aaa.....
...uU..E..l.TaKK....
d..FF.d.op
.... .d. ...

• OK... bats, all kind of funghi, molds and snakes and even wraiths block the line of view, but giant mimics, hill orcs, mastodons, all kinds of other creatures or even fire vortices don't? Jan 27 '14 at 5:23
• @JanDvorak I was lazy and chose capital letters for blocking. Sort of like TALL monsters vs short monsters; which would you be able to see over. So yes. Jan 27 '14 at 5:24
• I don't know about quantum mechanics, but the bat and the gnome mummy might be an easy deal. The mimic might complicate things further, though. Also, those three ants might be fun, and the large group of assorted monsters on the north-east might already know about you. Yeah... it might be nasty. As for #3 - where's my teleporation scroll? Oops, that was destroy armor. Jan 27 '14 at 5:31
• Just a curious observation, but if I understand your definition of "line" right, it looks like there are some squares that won't be visible even without any obstacles. For example, if the player is at (0, 0), then the square at (5, 12) can't be reached by any line. It might've made more sense to, say, specify some canonical implementation of Bresenham's line algorithm for drawing a line between any two points, and define a square as obscured if the line between it and the player intersects an obstacle. Jan 28 '14 at 14:51
• @IlmariKaronen You are absolutely correct. That is just how I like it. :-). Jan 28 '14 at 19:00

.n?):L)[n*.]*1/:I'@'?{\+[{1$+}*]..{I=26,{65+}%"# "+\?)}??)<}+{[L~.).)1L)L.(-1L~]>2<{[.[~\]]{1/~2$*+L*.-1%}%\;~}+L,%~}8,%%{|}*{1$?)I@=.n=@|\.' '={;'.'}*' 'if}+I,,%''*n%n*  The input must be provided on STDIN. The output for the examples given above is slightly different. I verified the responses by hand and think they are correct. Example 1: @......... ....K..... .J..... .......... .. .L..... .. . .... ... .. ... ... .. .. ... . . .... ..  Example 2: .B #M .# .. Z pq .#.#.aaa.. @..m.# #.##P# .# .# M. #  Example 3:  .......... ..... ......... ..... O..l...gg..rT ...QQL......Ag..#b.. ...qqqqq.........XqQ #.f@aa...... Y........aaa..... ...uU..E..l.TaKK.... d..FF.d.op .... .d. ...  • This doesn't seem to work for single line inputs (which are valid rectangles...) Jan 30 '14 at 4:58 • @Quincunx The code assumes that you finalise your input with a newline. Alternatively prepend n+ to the code. Jan 30 '14 at 5:32 ## Ruby - 510 chars Quite a mammoth; but it is my first ever attempt at a golf. m=$<.read;w,s,o,p=m.index(?\n)+1,m.size,m.dup.gsub(/[^@\n]/,' '),m.index(?@);d=[-w,1-w,1,w+1,w,w-1,-1,-1-w];0.upto(7){|i|x=d[i];[i-1,i+1].each{|j|y=d[j%8];[1,nil].each{|l|t=0;catch(:a){loop{c,f,r=p,1,nil;catch(:b){loop{(l||r)&&(1.upto(t){|u|c+=x;n=!(0...s).include?(c)||m[c]==?\n;n&&throw(f ?:a: :b);o[c]=m[c]==" "??.: m[c];a=m[c]=~/[#A-Z]/;a&&throw(f ?:a: :b)};f=nil);r=1;c+=y;n=!(0...s).include?(c)||m[c]==?\n;n&&throw(f ?:a: :b);o[c]=m[c]==" "??.: m[c];a=m[c]=~/[#A-Z]/;a&&throw(f ?:a: :b)}};t+=1}}}}};$><<o  Input is by file specified as argument; I assume the input file to consist of a rectangular block of characters (so, trailing spaces included), and to have a trailing newline. This version makes extensive use of catch-throw to exit deep loops; I can possibly improve matters with bounds-checked loops instead. Unobfuscated code: # Read the map in map =$<.read

# Determine its width and size
width = map.index("\n")+1
size = map.size

# Create a blank copy of the map to fill in with visible stuff
output = map.dup.gsub /[^@\n]/,' '

# Locate the player
player = map.index('@')

dirs = [
-width,   # N
1-width,  # NE
1,        # E
width+1,  # SE
width,    # S
width-1,  # SW
-1,       # W
-1-width  # NW
]

0.upto(7) do |i1|
d1 = dirs[i1]
[i1-1, i1+1].each do |i2|
d2 = dirs[i2%8]

# Stepping by 0,1,2... in d1, work along the line.
# Write the cell value into the duplicate map, then break if it's
# a "solid" character.
#
# Extensive use of catch-throw lets us exit deep loops.

# For convenience of notation, instead of having either d1 or d2
# be magnitude 1, and always doing d1,d2,d1... - I have d2 always
# being magnitude 1, and doing either d1,d2,d1 or d2,d1,d2...

# Loop twice - first with d1,d2,d1... second with d2,d1,d2...
[true,false].each do |long_first|
step = 0

catch(:all_done) do
# This loop increments step each iteration, being the magnitude of d1
loop do
cell = player
first = true  # True until we've done the first d1
later = false # True once we've done the first d2

catch(:done) do
# This loop repeatedly applies d1 and d2
loop do
if long_first || later  # Don't apply d1 first if starting with d2
1.upto(step) do |dd1|
cell += d1 # Move one cell in d1
invalid = !(0...size).include?(cell) || map[cell]=="\n" # Out of range
throw :all_done if first && invalid # No point trying a longer step if the
# first application of d1 is out of range
throw :done if invalid # No point continuing with this step length

output[cell]=map[cell] == " " ? '.' : map[cell] # Transfer visble character
wall = map[cell]=~/[#A-Z]/  # Hit a wall?
throw :all_done if first && wall # Drop out as before
throw :done if wall
end
first = false
end
later=true

# Now repeat above for the single d2 step
cell += d2
invalid = !(0...size).include?(cell) || map[cell]=="\n"
throw :all_done if first && invalid
throw :done if invalid
output[cell]=map[cell] == " " ? '.' : map[cell]
wall = map[cell]=~/[#A-Z]/
throw :all_done if first && wall
throw :done if wall
end
end
step += 1
end
end
end
end
end

puts output


## Edit

Ilmari Karonen notes in the question comments that the given vision algorithm doesn't see all squares, even when there's no obstacle. Here's a demonstration of that, out to (40,40) away from the player.

@.......................................
........................................
........................................
........................................
........................................
............ ...........................
..............  ........................
............ ...   ..... ...............
.............. ...    .....  ...........
...............  ...     .....   .......
.................  ...      .....    ...
..................   ...       .....
..... . ............   ...        .....
.....................    ...         ...
...... . ..............    ...
...... .. ..............     ...
....... . ................     ...
....... .. ............. ..      ...
.......  .  .................      ...
........ .. ............... ..       ...
........  .  ............... ...       .
........  ..  ................ ..
.........  .  ................. ...
.........  ..  .................  ..
....... .   .   . ................ ...
..........  ..  ...................  ..
..........   .   ...................  ..
........ .   ..   . ..................
........ ..   .   .. ..................
...........   ..   .....................
......... .    .    . ..................
......... ..   ..   .. .................
......... ..    .    .. ................
.......... .    ..    . ................
.......... ..    .    .. ...............
.......... ..    ..    .. ..............
..........  .     .     .  .............
........... ..    ..    .. .............
........... ..     .     .. ............
...........  .     ..     .  ...........

• Hmm. This fails test 3. Needs debugging. Jan 27 '14 at 17:30
• are you sure? I could have made a mistake... Jan 27 '14 at 20:17
• Pretty sure - I can see the V behind the wall! I think I'm not detecting the newline after the previous line. Jan 27 '14 at 21:39
• Definitely should not be seeing that... Jan 27 '14 at 21:44
• Ah, it was a problem with my input; I had an extra space after XqQ. That said, your given answer for 3 doesn't match the testcase at all - it at least has an extra line at the top, and only one space between the O and l. Jan 28 '14 at 9:04