Background
I was playing the PC-Game "Darkest Dungeon" recently. In the game, you have to explore dungeons, which consist of connected rooms as shown in the picture below.
Here are the rules:
- You start in fixed room (Entrance). You cannot choose where to start.
- The goal is to visit every room at least once
- The distance between adjacent rooms is the same for all rooms.
- You can visit rooms and walk paths as often as you'd like
Question
What is the shortest path from the entrance that visits every room at least once?
Subquestions:
- What algorithm(s) could be used to solve this problem?
- Are there implementations that are free (and fairly simple) to use for someone like me?
What I tried
I have found other questions such as this or this without finding an answer. I am familiar with the (basic) TSP and are able to code and solve simple TSPs. Hamiltonian paths didn't solve my problem, because it doesn't allow for multiple visits. The Chinese postman problem does also not apply here in its basic form because I don't have to visit every edge.
Update
As I have stated in the comments, I'm not a computer scientist and am not interested in proving a mathematical statements (maybe I'll post this question on stackoverflow at a later stage). Also, I'm not a programmer and the chances that I'm able to code a solution myself are pretty slim. But I suspect I'm not the first one dealing with a problem of that nature.
According to @Shreesh and @Dib, the following procedure could be applied:
- Create a pairwise distance matrix with all rooms thus adding edges between all rooms.
- Solve TSP using a standard solver (e.g. concorde)
- Starting from the Entrance, visit all rooms according to the solution. For non-adjacent rooms, substitute the shortest distance between those rooms.
Will this procedure provide the answer to the problem?