8
$\begingroup$

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. Darkest_Dungeon_Minimap

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?

| cite | improve this question | |
$\endgroup$
  • 6
    $\begingroup$ Your problem appears to be a special case of TSP. In many special cases you can do better than the general case. Have you looked into this direction? $\endgroup$ – Yuval Filmus Feb 17 '16 at 16:59
  • $\begingroup$ @YuvalFilmus Thanks for your comment. I have tried googling this question but was unable to find a straight-forward solution. As I am not a computer scientist, academic papers are mostly beyond my level of understanding. I hoped that this variant of the TSP is well-known and that maybe a solution already exist. I will probably ask a moderator to migrate this question to stackoverflow at a later stage. Thanks again for your help. $\endgroup$ – COOLSerdash Feb 18 '16 at 8:25
  • $\begingroup$ Thanks for all the comments, COOLSerdash. I think it would be helpful to edit your question to include all of the information you've been providing in the comments, in summarized form. $\endgroup$ – D.W.♦ Feb 18 '16 at 11:03
  • 1
    $\begingroup$ There can easily be more than one "shortest path from ... at least once", but 1.2.3. will provide a "shortest path from ... at least once". ​ ​ $\endgroup$ – user12859 Feb 25 '16 at 9:49
3
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thank you for your answer, Shreesh. Unfortunately, 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. Thanks again. $\endgroup$ – COOLSerdash Feb 18 '16 at 8:21
  • $\begingroup$ One easy way to go about this is add $^nC_2$ edges corresponding to shortest paths and then solve TSP with any existing algorithm. As you already know Concorde, it would be easy. $\endgroup$ – Shreesh Feb 18 '16 at 10:20
  • 1
    $\begingroup$ We have a grid graph with unit weights here. Is suspect that the problem is much easier than even Euclidian TSP. (cc @COOLSerdash) $\endgroup$ – Raphael♦ Feb 23 '16 at 20:00
  • $\begingroup$ No, if the grid is sparse, we basically have TSP with vertices at rational points and $L_1$ metric. However if your Grid is dense, i.e. basically you have to visit almost every point of the grid, no, you visit every point of the grid, then there is a very good ~$n^2$ path. See here and here. $\endgroup$ – Shreesh Feb 24 '16 at 12:57
2
$\begingroup$

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")

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Can you explain what it means to subdivide the grid? What if my graph isn't on a grid? i.e. imgur.com/a/KlnPO $\endgroup$ – jdelman Jan 22 '18 at 16:11
1
$\begingroup$

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.
| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks you for your answer. But as I stated, I already know how to solve TSP using concorde. As my problem is not directly suitable for the original TSP, I currently don't know how that is going to help me. $\endgroup$ – COOLSerdash Feb 18 '16 at 8:17
  • $\begingroup$ The shortest path would be the path which visits every room exactly once. Now by adding extra nodes you can reduce your problem to a TSP problem whose answer would directly give answer to your question. $\endgroup$ – Dib Feb 18 '16 at 8:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.