No valid solutions found when there is one.

[kburavskij]

Hi!

So I have been trying all ways possible to understand why that is happening but failing to do so. I need this specific maze for my own purposes.

from mazelib import Maze
from mazelib.solve.ShortestPath import ShortestPath
import numpy as np
import matplotlib.pyplot as plt

g = np.ones((25, 25), dtype=np.int8)


g[1] =   [1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1]
g[2] =   [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
g[3] =   [1,1,1,0,0,0,0,0,1,1,0,0,0,0,0,1,1,0,0,0,0,0,1,1,1]
g[4] =   [1,0,1,0,0,0,0,0,1,1,0,0,0,0,0,1,1,0,0,0,0,0,1,0,1]
g[5] =   [1,0,0,0,0,0,0,0,1,1,0,0,0,0,0,1,1,0,0,0,0,0,1,0,1]
g[6] =   [1,0,1,0,0,0,0,0,1,1,0,0,0,0,0,1,1,0,0,0,0,0,1,0,1]
g[7] =   [1,0,1,0,0,0,0,0,1,1,0,0,0,0,0,1,1,0,0,0,0,0,1,0,1]
g[8] =   [1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1]
g[9] =   [1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1]
g[10] =  [1,0,1,0,0,0,0,0,1,1,0,0,0,0,0,1,1,0,0,0,0,0,1,0,1]
g[11] =  [1,0,1,0,0,0,0,0,1,1,0,0,0,0,0,1,1,0,0,0,0,0,1,0,1]
g[12] =  [1,0,1,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1]
g[13] =  [1,0,1,0,0,0,0,0,1,1,0,0,0,0,0,1,1,0,0,0,0,0,1,0,1]
g[14] =  [1,0,1,0,0,0,0,0,1,1,0,0,0,0,0,1,1,0,0,0,0,0,1,0,1]
g[15] =  [1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,0,1]
g[16] =  [1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,0,1]
g[17] =  [1,0,1,0,0,0,0,0,1,1,0,0,0,0,0,1,1,0,0,0,0,0,1,0,1]
g[18] =  [1,0,1,0,0,0,0,0,1,1,0,0,0,0,0,1,1,0,0,0,0,0,1,0,1]
g[19] =  [1,0,1,0,0,0,0,0,1,1,0,0,0,0,0,1,1,0,0,0,0,0,1,0,1]
g[20] =  [1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1]
g[21] =  [1,1,1,0,0,0,0,0,1,1,0,0,0,0,0,1,1,0,0,0,0,0,1,1,1]
g[22] =  [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
g[23] =  [1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1]



m = Maze()
m.solver = ShortestPath()
m.grid = g

m.start = (3, 3)
m.end = (12, 12)

plt.xticks(np.arange(0, 25, 1.0))
plt.yticks(np.arange(0, 25, 1.0))
plt.imshow(m.grid, interpolation='none')
plt.show()

print(str(m))
m.solve()

[kburavskij]

Hello!

Sorry for the long wait for a reply. I was in the middle of moving a few thousand miles and lost track of things for a while.

The reason "ShortestPath" didn't find a path through your maze is your maze has those big, empty rooms in it. It turns out, very few maze-solving algorithms can solve mazes with those big, empty rooms. (That is, all "classic" maze-solving algorithms only work with mazes that are all one-cell-wide hallways.

I suppose this isn't described well in the documentation, so I should find a way to document that. Though I feel like it will be hard to describe the issue you're having without a lot of detail. Hmm

Thanks for the reply nonetheless. I hope your moving went smoothly!

Well, I figured that might be the case and filled the unnecessary space in the rooms with "walls", that haven't really solved the issue, it still finds any path to any of the outer rooms, but not the center for whatever reason. I will provide a 2D maze later when I'm back home :)

[john-science]

Hello again!

Okay, on closer inspection, I found the problem. It turns out the problem is the maze you generated is invalid. Take a look at this slightly modified input maze, it works like a charm.

The problem is something like this. You drew a map with your 2D array there. But if you were to run a maze-generating algorithm, you would find that hallways, starts, and ends are always on odd-numbered squares. This is because the NumPy representation of a maze puts hallways on odd tiles and walls on even tiles. But you put double-width walls between your rooms. Which LOOKS right to the human eye, but it broke all the maze-solving algorithms.

Sorry, if you haven't used .generate() much in this library, you might not have seen that before.

Does this make sense? This works immediately and perfectly:

from mazelib import Maze
from mazelib.solve.ShortestPath import ShortestPath
import numpy as np
import matplotlib.pyplot as plt

g = np.ones((23, 23), dtype=np.int8)

g[1] = [1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1]
g[2] = [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
g[3] = [1,1,1,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,1,1,1]
g[4] = [1,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,1]
g[5] = [1,0,0,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,1]
g[6] = [1,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,1]
g[7] = [1,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,1]
g[8] = [1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1]
g[9] = [1,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,1]
g[10] = [1,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,1]
g[11] = [1,0,1,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,1,0,1]
g[12] = [1,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,1]
g[13] = [1,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,1]
g[14] = [1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,0,1]
g[15] = [1,0,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,0,1,1,1,0,1]
g[16] = [1,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,1]
g[17] = [1,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,1]
g[18] = [1,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,1,0,1]
g[19] = [1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,1]
g[20] = [1,1,1,0,0,0,0,0,1,0,0,0,0,0,1,0,0,0,0,0,1,1,1]
g[21] = [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1]
g[22] = [1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,1,1,1]

m = Maze()
m.solver = ShortestPath()
m.grid = g

m.start = (3, 3)
m.end = (11, 11)

plt.xticks(np.arange(0, 23, 1.0))
plt.yticks(np.arange(0, 23, 1.0))
plt.imshow(m.grid, interpolation='none')
plt.show()

m.solve()
print(m)

The output of this maze solution looks like this:

#######################
####               ####
#######################
###S    #     #     ###
# #+    #     #     # #
#+++    #     #     # #
#+#     #     #     # #
#+#     #     #     # #
#+################### #
#+#     #     #     # #
#+#     #     #     # #
#+#     #  E++++++  # #
#+#     #     #  +  # #
#+#     #     #  +  # #
#+###############+### #
#+###############+### #
#+#     #     #  +  # #
#+#     #     #  +  # #
#+#     #     #  +  # #
#+++++++++++++++++  # #
###     #     #     ###
#######################
####               ####

Unless you have further questions, I'm just going to go ahead and close this ticket. Feel free to keep chatting in this ticket if you have questions though.

[john-science]

Thanks for the reply nonetheless. I hope your moving went smoothly!

Well, I figured that might be the case and filled the unnecessary space in the rooms with "walls", that haven't really solved the issue, it still finds any path to any of the outer rooms, but not the center for whatever reason. I will provide a 2D maze later when I'm back home :)

Good news! I just noticed that your input maze was very slightly malformed, so the solving algorithms work in the end. Check out my most recent comment, with a code update!

[john-science]

@kburavskij Hello again!

Okay, thinking more about this, I think there is a problem here. It is one of documentation.

I always thought it would be nicely invisible to the user that the even / odd numbered cells in the grid had different uses. I spent a while developing this solution as one that was (mathematically) arbitrarily general. And the only difference between a maze with thick or thin walls was one of how you displayed it to the user. But the math solutions would be the same either way.

This was all find and well when it was just me doing some math for lawls. But what you've shown me is this needs to be clearly documented for the user. Otherwise a clear person encountering the library will do exactly what you did 50% of the time when designing their own maze.

I have opened a ticket for this documentation issue, and it is here:

#119

Thanks for the help!