Algorithm: Finding shortest path through a dungeon in a game

Question

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:

1. Create a pairwise distance matrix with all rooms thus adding edges between all rooms.
2. Solve TSP using a standard solver (e.g. concorde)
3. 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?

Answer 1

Travelling Salesman Problem, even if you allow repeating nodes is NP-hard. See Computational Complexity of TSP.

Umans and Lenhart show hardness results for Hamiltonian Graphs in Solid Grid Graphs, 1997.

TSP for Euclideal Case (or graphs with triangle inequality) also imply NP-hardness of TSP with node repetition. TSP even for manhattan distance $L_1$ (or $L_\infty$) metric is NP-complete. See the original Papadimitriou's paper on the topic.

You may be able to prove NP-hardness of TSP for your case by adding arcs to nodes that have corresponding distance as length of shortest path between nodes which will simulate repetitions of the nodes. TSP for your special case looks like an NP-complete problem.

So either write a sufficiently good (heuristic wise) exponential branch and bound algorithm to compute a shortest tour (which may not be all that inefficient, if your graph is small) , or forget about optimization and calculate a good enough approximation.

Answer 2

You can treat this like a modified path coverage planning problem that you can solve in a few simple steps:

1) Construct an unweighted undirected graph from the grid- rooms, path junctions are nodes, and edges the paths between those nodes.

2) Find the minimum spanning tree from your start point using depth first search.

3) "Subdivide" the underlying grid so that your minimum spanning tree creates two "lanes".

4) From your starting point walk clockwise in the right-hand lane from node-to-node until you return to the starting point in the complementary lane.

This will give you a minimal tour of the rooms, in time proportional to the number of tiles in the dungeon, and is essentially the Spiral Spanning Tree Coverage path planning algorithm applied to a reduced setting. (Cf. "Spiral-stc: an on-line coverage algorithm of grid environments by a mobile robot")

Answer 3

In addition to the above answer, I would point out some TSP solvers already available.

1. Concorde TSP Solver
2. TSP solver provided by Stony Brooks University
3. TSP solver using Google Direction API
4. And Many more.