Solve an Ice Maze

Question

Ice mazes have been one of my favorite staples of Pokémon games since their debut in Pokémon Gold and Silver. Your task will be to make a program that solves these types of problems.

Ice mazes primarily consist of, as the name suggests, ice. Once the player moves in a direction on ice they will continue to move in that direction until they collide with some obstacle. There is also soil which can be moved across freely and will stop any player moving across it. The last obstacle is stone. Stone cannot occupy the same space as the player and if the player attempts to move into it they will stop moving before they can.

You will receive a two dimensional container of values, such as an list of lists or a string separated by newlines, containing 3 distinct values for each of the 3 types of flooring (Ice, Soil, and Stone). You will also receive two pairs (or other equivalent two value containers) that indicate a start and goal coordinate in the maze. These may be zero or one indexed.

You must output a list of moves (4 distinct values with a bijection onto N,E,S,W) that would cause the player to arrive at the end when carried out.

Input will always have a closed perimeter of stone around the maze so you do not have to worry about the player exiting the maze

This is code-golf so the fewest bytes wins

Test Cases

Here . will represent ice, ~ will represent soil, and O will represent a stone. Coordinates are 1 indexed. Each letter in the solution represents the direction beginning with that letter (e.g. N= North)

---

Input

OOOOO
OO.OO
O...O
OOOOO

Start : 3,3
End   : 3,2

Output

N

---

Input

OOOOOOOOOOOOOOOOO
O........O.....OO
O...O..........OO
O.........O....OO
O.O............OO
OO.......O.....OO
O.............OOO
O......O.......~O
O..O...........~O
O.............OOO
O.......O......OO
O.....O...O....OO
O..............OO
OOOOOOOOOOOOOO~~O
OOOOOOOOOOOOOOOOO

Start : 15,12
End   : 16,8

Output

N,W,N,E,N,E,S,W,N,W,S,E,S,E,N,E,N

---

Input

OOOOOOOOOOOOOOOO
O~~~~~OOOOO~~~~O
O~~O~OOOOOOO~~OO
O...O..........O
O........O.....O
O..............O
OO.............O
O.............OO
O....~....O....O
O..............O
O..............O
OOOOOOOOOOOOOOOO

Start : 2,2
End   : 14,3

Output

E,S,S,W,N,E,N

---

Input

OOOOOOOOOOOOOOOOOOO
O~~~~~~~OOOOOOOOOOO
O~~~~...OOOOOOOOOOO
OO~O~..OOOOOOOOOOOO
O..OO.............O
O..............O..O
O....O............O
O.O............~..O
O........OOOO.....O
O.......OOOOO.....O
O.......O~~~O.....O
O.......~~~~~.....O
O.......~~~~~.....O
O..........O......O
O..O..~...........O
O...............O.O
O.....O...........O
O.................O
OOOOOOOOOOOOOOOOOOO

Start : 2,2
End   : 11,11

Output

E,E,E,E,E,S,S,E,N,W,S,E,N,N,N

Answer 1

Mathematica, 247 bytes

(p=x#[[##&@@x]];m={c,v}Switch[p[c+v],0,m[c+v,v],1,c+v,_,c];g=Cases[Array[List,Dimensions@#],c_/;p@c<2,{2}];a=cm[c,#]&/@{{1,0},{-1,0},{0,1},{0,-1}};e=Flatten[Table[#->c,{c,a@#}]&/@g,1];Normalize/@Differences@FindPath[Graph[e],#2,#3][[1]])&

With line breaks:

(
p=x#[[##&@@x]];
m={c,v}Switch[p[c+v],0,m[c+v,v],1,c+v,_,c];
g=Cases[Array[List,Dimensions@#],c_/;p@c<2,{2}];
a=cm[c,#]&/@{{1,0},{-1,0},{0,1},{0,-1}};
e=Flatten[Table[#->c,{c,a@#}]&/@g,1];
Normalize/@Differences@FindPath[Graph[e],#2,#3][[1]]
)&

My immediate idea was to represent the ice and soil positions as nodes in a graph with directed edges corresponding to legal moves, then use FindPath. One might think that determining the legal moves would be the easy part and finding the solution would be the hard part. For me, it was the opposite. Open to suggestions on how to compute the edges.

First argument # is a 2D array where 0 represents ice, 1 represents soil, and 2 represents stone.

Second argument #2 and third argument #3 are the starting and ending points, respectively, in the form {row,column}.

 is the 3 byte private use character U+F4A1 representing \[Function].

Explanation

p=x#[[##&@@x]];

Defines a function p which takes a list x of the form {row,column} and outputs #[[row,column]]; i.e., the ice/soil/stone value at that coordinate.

m={c,v}Switch[p[c+v],0,m[c+v,v],1,c+v,_,c]

Defines a function m which takes a starting position c and direction vector v and recursively determines where you would end up. If c+v is ice, then we continue sliding from that point, so it returns m[c+v,v]. If c+v is soil, then we move to c+v and stop. Otherwise (if c+v is stone or out of bounds), you don't move. Note that this is only intended to be called on ice or soil positions.

g=Cases[Array[List,Dimensions@#],c_/;p@c<2,{2}];

Defines the list g of ice and soil positions (p value less than 2).

a=cm[c,#]&/@{{1,0},{-1,0},{0,1},{0,-1}}; 

Defines a function a which takes a starting position c and returns the results of moving in the {1,0}, {-1,0}, {0,1}, and {0,-1} directions. There may be some redundancy. Again, this assumes that c corresponds to ice or soil.

e=Flatten[Table[#->c,{c,a@#}]&/@g,1];

Defines the list e of directed edges representing legal moves. For each position # in g, compute the table of edges #->c for each c in a@#. Then since we'll end up with a sublist for each position #, I flatten the first level. There may be some loops and multiple edges.

Normalize/@Differences@FindPath[Graph[e],#2,#3][[1]]

Graph[e] is the graph where the nodes are the legal positions (ice or soil) and the edges represent legal moves (possibly bumping into a stone and not moving). We then use FindPath to find a path from #2 to #3 represented as a list of nodes. Since FindPath can take additional arguments to find more than one path, the result will actually be a list containing a single path, so I take the first element using [[1]]. Then I take the successive Differences of the coordinates and Normalize them. Thus up is {-1,0}, down is {1,0}, right is {0,1} and left is {0,-1}.

Test cases

Answer 2

JavaScript (ES6) 180 183

(m,[x,y],[t,u],o=~m.search`
`,s=[[x-y*o,[]]],k=[])=>eval("for(i=0;[p,l]=s[i++],k[p]=t-u*o-p;)[-1,o,1,-o].map(d=>k[q=(M=p=>+m[p+=d]?m[p]<8?M(p):p:p-d)(p)]||s.push([q,[...l,d]]));l")

Using a BFS, like I did to solve this related challenge

Input
The maze map is a multiline string, using O or 0 for stone, 8 for soil and any nonzero digit less than 8 for ice (7 look good).
Start and end position are zero based.

Output
A list of offset, where -1 is W, 1 is E, negative less than -1 is N and a positive greater than 1 is S

Less golfed

(m,[x,y],[t,u])=>{
  o=~m.search`\n`
  s=[[x-y*o,[]]]
  k=[]
  for(i=0; [p,l]=s[i++], k[p]=1, t-u*o != p;)
  {
    [-1,o,1,-o].map(d=>(
      M=p=>+m[p+=d] ? m[p]<8 ? M(p) : p : p-d,
      q=M(p),
      k[q]||s.push([q,[...l,d]])
    ))
  }
  return l
}

Test

Solve=
(m,[x,y],[t,u],o=~m.search`
`,s=[[x-y*o,[]]],k=[])=>eval("for(i=0;[p,l]=s[i++],k[p]=t-u*o-p;)[-1,o,1,-o].map(d=>k[q=(M=p=>+m[p+=d]?m[p]<8?M(p):p:p-d)(p)]||s.push([q,[...l,d]]));l")

function Go(maze) {
  var map = maze.textContent;
  var [sx,sy, dx,dy] = map.match(/\d+/g)
  --sx, --sy // zero based
  --dx, --dy // zero based
  map = map.split('\n').slice(1).join('\n') // remove first line
  var result = Solve(map.replace(/\./g, 7).replace(/~/g, 8), [sx,sy], [dx,dy])
  S.textContent = result
  Animate(maze, map, result, sx, sy)
}

function Display(maze, map, pos) {
  var row0 = maze.textContent.split('\n')[0]
  map = [...map]
  map[pos] = '☻'
  maze.textContent = row0+'\n'+map.join('')
}

function Animate(maze, map, moves, x, y) {
  console.log('A',moves)
  var offset = map.search('\n')+1
  var curPos = x + offset * y
  var curMove = 0
  var step = _ => {
    Display(maze, map, curPos)
    if (curMove < moves.length) 
    {
      curPos += moves[curMove]
      if (map[curPos] == 'O')
      {
        curPos -= moves[curMove]
        ++curMove
      }  
      else 
      {
        if (map[curPos] == '~') {
          ++curMove
        }
      }
      setTimeout(step, 100)
    }
    else
      setTimeout(_=>Display(maze,map,-1),500)
  }
  step()
}

td { 
  border: 1px solid #888;
}

Select maze<pre id=S></pre>
<table cellspacing=5><tr>
<td valign=top><input type=radio name=R onclick='Go(M1)'><br>
<pre id=M1>3,3 to 3,2  
OOOOO
OO.OO
O...O
OOOOO</pre></td>
<td valign=top><input type=radio name=R onclick='Go(M2)'><br>
<pre id=M2>15,12 to 16,8
OOOOOOOOOOOOOOOOO
O........O.....OO
O...O..........OO
O.........O....OO
O.O............OO
OO.......O.....OO
O.............OOO
O......O.......~O
O..O...........~O
O.............OOO
O.......O......OO
O.....O...O....OO
O..............OO
OOOOOOOOOOOOOO~~O
OOOOOOOOOOOOOOOOO</pre></td>
<td valign=top><input type=radio name=R onclick='Go(M3)'><br>
<pre id=M3>2,2 to 14,3
OOOOOOOOOOOOOOOO
O~~~~~OOOOO~~~~O
O~~O~OOOOOOO~~OO
O...O..........O
O........O.....O
O..............O
OO.............O
O.............OO
O....~....O....O
O..............O
O..............O
OOOOOOOOOOOOOOOO</pre></td>
<td valign=top><input type=radio name=R onclick='Go(M4)'><br>
<pre id=M4>2,2 to 11,11
OOOOOOOOOOOOOOOOOOO
O~~~~~~~OOOOOOOOOOO
O~~~~...OOOOOOOOOOO
OO~O~..OOOOOOOOOOOO
O..OO.............O
O..............O..O
O....O............O
O.O............~..O
O........OOOO.....O
O.......OOOOO.....O
O.......O~~~O.....O
O.......~~~~~.....O
O.......~~~~~.....O
O..........O......O
O..O..~...........O
O...............O.O
O.....O...........O
O.................O
OOOOOOOOOOOOOOOOOOO</pre></td>
</tr></table>

Answer 3

Python3, 439 bytes

def f(b,s,S,e,E):
 q=[(s,S,[[(s,S)]],'')]
 for x,y,d,p in q:
  if(x,y)==(e,E):return p
  for D,X,Y in[('E',0,1),('W',0,-1),('N',-1,0),('S',1,0)]:
   if'~'==b[x][y]and(T:=[(x+X,y+Y)])not in d and'O'!=b[x+X][y+Y]:q+=[(*T[0],d+[T],p+D)]
   elif'.'==b[x][y]:
    T,Q,W=[],x,y
    while 1:
     if(S:=b[Q+X][W+Y])in'.~':
      T+=[(Q+X,W+Y)];Q+=X;W+=Y
      if'~'==S:break
     else:break
    if(U:=sorted(T))not in d and U:q+=[(Q,W,d+[U],p+D)]

Try it online!