title: Traveling Salesman Problem With Exit directions
body: <p>Suppose I have a list of Grid Sectors, that have the possibility of having between 1 &amp; 4 exits per grid sector. Each grid sector consists of 50x50 x,y positions, and there can be any number of grid sectors. The &quot;Exits&quot; are guaranteed to be one of the <code>0,N</code> - <code>49,N</code> or <code>N,0</code> - <code>N,49</code> positions. How can I find the shortest path from any given position in a grid sector, through to the farthest position away. The list of grid-sectors, is not in any particular order. I must traverse each room in the list, even if I have to traverse a grid sector twice, for example, grid sectors with only one exit.</p>
  <p><a href="https://i.stack.imgur.com/Kv8qB.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/Kv8qB.png" alt="enter image description here" /></a></p>
  <p>In this screenshot, the <code>Green</code> would represent the starting position, and the <code>Light Blue</code> would represent the end position. Every other Grid Sector here MUST be visited at least once, starting with the closest, and ending with the farthest. Each red line represents an exit that shares a border with a nearby grid sector. Again, each is guaranteed to have at least 1 exit, and no more than 4.</p>
  <p>I'm really only looking for an optimal Grid Sector path from each grid to the next, given the exits, however BONUS POINTS to anyone that can also return an array of <code>X,Y</code> coordinates in order from the <code>25,25</code> position of the first grid sector. In order to do that, recognize that the top left of each grid sector is <code>0,0</code> and the bottom right is <code>49,49</code> And each room is organized in a similar fashion, albeit at a larger scale.</p>
  <p>I attempted to do something like this, but it got me a result that had grid sectors that were diagonally closest to farthest instead of pathed closest to farthest. Another solution I had considered was to use flood-fill to check each room, and add it only if it was connected to the next available position, but that also netted me unexpected results.</p>
  <pre><code>setFrontiers(room: Room) {
      let frontiers: string[] = []
      let currentRoomGlobalPos = Utils.Utility.roomNameToCoords(this.name)
      for (let wx = currentRoomGlobalPos.wx - 10; wx &lt;= currentRoomGlobalPos.wx + 10; wx++) {
          for (let wy = currentRoomGlobalPos.wy - 10; wy &lt;= currentRoomGlobalPos.wy + 10; wy++) {
              let prospectFrontier = Utils.Utility.roomNameFromCoords(wx, wy)
              let result = Game.map.describeExits(prospectFrontier)
              if (result != null &amp;&amp;
                  result != this.name &amp;&amp;
                  Game.map.getRoomStatus(prospectFrontier).status == Game.map.getRoomStatus(room.name).status) {
                  frontiers.push(prospectFrontier)
              }
          }
      }
  
      frontiers = _.sortByOrder(frontiers, (roomName: string) =&gt; {
          let roomGlobalPos = Utils.Utility.roomNameToCoords(roomName)
          let dx = roomGlobalPos.wx - currentRoomGlobalPos.wx
          let dy = roomGlobalPos.wy - currentRoomGlobalPos.wy
          return Math.abs(dx) + Math.abs(dy)
      }, 'asc')
  
      frontiers.splice(0, 1)
  
      room.memory.frontiers = frontiers
  }
  </code></pre>
  <p>The results of the above code, is this, however the starting position was from the center of the red circle.</p>
  <p><a href="https://i.stack.imgur.com/0IoiE.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/0IoiE.png" alt="enter image description here" /></a></p>