How do I get the shortest route in a labyrinth?

Question

I want to make a code giving the shortest route when given a labyrinth as a matrix.

In this case, the matrix representation of this labyrinth is as follows.

## [,1] [,2] [,3] [,4]
## [1,] 2 0 0 0
## [2,] 1 1 0 1
## [3,] 0 1 0 0
## [4,] 1 1 1 3
 , where  0 denotes inaccessible points, 1 denotes accessible points.
          2 denotes the starting point, and 3 denotes the destination.

And, the desired result is this : c(4,1,4,4,1,1), where 1 denotes East, 2 denotes North, 3 denotes West, and 4 denotes South.

I guess that one possible code might be a function giving the shortest route as a vector when it is given the matrix representation of a labyrinth.

In addition to this case, I want to know if the coverage could be extended to general cases, though it seems rather redundant. I would like to know whether a desirable code can be made so that it covers arbitrary n by m size matrix, although just 4 by 4 case suffices. And I wonder if the start point and the destination could be located at arbitrary points other than vertices, though vertices case is sufficient.

Answer 1

You could construct a graph to represent the valid moves between positions in the matrix:

# Construct nodes and edges from matrix
(nodes <- which(m == 1 | m == 2 | m == 3, arr.ind=TRUE))
#       row col
#  [1,]   1   1
#  [2,]   2   1
#  [3,]   4   1
#  [4,]   2   2
#  [5,]   3   2
#  [6,]   4   2
#  [7,]   4   3
#  [8,]   2   4
#  [9,]   4   4
edges <- which(outer(seq_len(nrow(nodes)),seq_len(nrow(nodes)), function(x, y) abs(nodes[x,"row"] - nodes[y,"row"]) + abs(nodes[x,"col"] - nodes[y,"col"]) == 1), arr.ind=T)
(edges <- edges[edges[,"col"] > edges[,"row"],])
#      row col
# [1,]   1   2
# [2,]   2   4
# [3,]   4   5
# [4,]   3   6
# [5,]   5   6
# [6,]   6   7
# [7,]   7   9

library(igraph)
g <- graph.data.frame(edges, directed=FALSE, vertices=seq_len(nrow(nodes)))

Then you could solve the shortest path problem between the specified start and end location:

start.pos <- which(m == 2, arr.ind=TRUE)
start.node <- which(paste(nodes[,"row"], nodes[,"col"]) == paste(start.pos[,"row"], start.pos[,"col"]))
end.pos <- which(m == 3, arr.ind=TRUE)
end.node <- which(paste(nodes[,"row"], nodes[,"col"]) == paste(end.pos[,"row"], end.pos[,"col"]))
(sp <- nodes[get.shortest.paths(g, start.node, end.node)$vpath[[1]],])
#      row col
# [1,]   1   1
# [2,]   2   1
# [3,]   2   2
# [4,]   3   2
# [5,]   4   2
# [6,]   4   3
# [7,]   4   4

Finally, you could determine the direction (1: east; 2: north; 3: west; 4: south) as a simple manipulation of the final set of nodes selected:

dx <- diff(sp[,"col"])
dy <- -diff(sp[,"row"])
(dirs <- ifelse(dx == 1, 1, ifelse(dy == 1, 2, ifelse(dx == -1, 3, 4))))
# [1] 4 1 4 4 1 1

This code will work for arbitrarily sized input matrices.

Data:

(m <- matrix(c(2, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1, 0, 3), nrow=4))
#      [,1] [,2] [,3] [,4]
# [1,]    2    0    0    0
# [2,]    1    1    0    1
# [3,]    0    1    0    0
# [4,]    1    1    1    3

Answer 2

I'd likely use functions from the gdistance package, demonstrated in another setting here:

library(gdistance) ## A package to "calculate distances and routes on geographic grids"

## Convert sample matrix to a spatial raster
m = matrix(c(2, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1, 0, 3), nrow=4)
R <- raster(m)

## Convert start & end points to SpatialPoints objects
startPt <- SpatialPoints(xyFromCell(R, Which(R==2, cells=TRUE)))
endPt   <- SpatialPoints(xyFromCell(R, Which(R==3, cells=TRUE)))

## Find the shortest path between them
## (Note: gdistance requires that you 1st prepare a sparse "transition matrix"
##  whose values give the "conductance" of movement between pairs of cells)
tr1 <- transition(R, transitionFunction=mean, directions=4)
SPath <- shortestPath(tr1, startPt, endPt, output="SpatialLines")

## Extract your direction codes from the steps taken in getting from 
## one point to the other. 
## (Obfuscated, but it works. Use some other method if you prefer.)
steps <- sign(diff(coordinates(SPath)[[1]][[1]]))
(t(-steps)+c(2,3))[t(steps!=0)]
## [1] 4 1 4 4 1 1

## Graphical check that this works
plot(R>0)
plot(rBind(startPt, endPt), col=c("yellow", "orange"), pch=16, cex=2, add=TRUE)
plot(SPath, col="red", lwd=2, add=TRUE)

Answer 3

One possibility consists in setting up a matrix with value 1 at the target and a decrease of the value at the rate of 0.9 for each square, as a function of the Manhattan distance from the destination. The obstacles would have the value zero, the starting point is arbitrary.

Once such a matrix is defined, the shortest path is obtained by iteratively going to the neighboring square with the largest increase in value.

This method is described, e.g., in the first chapter of the book "Statistical Reinforcement Learning" by M. Sugiyama.

So your matrix could look like this:

     [,1]  [,2]  [,3] [,4]
[1,] 0.53  0.00  0.0  0.00
[2,] 0.59  0.66  0.0  0.81
[3,] 0.00  0.73  0.0  0.00
[4,] 0.73  0.81  0.9  1.00

And the algorithm would be:

• Choose a starting square with non-zero value
• Move to the square that has the highest value among those squares that are one step away from you.
• Repeat the previous step until you reach the square with value 1

Note that the value [2,4] is de facto not accessible and should therefore be excluded as a possible starting point. The destination does not need to be at a corner.