Skip to main content
Game Development

Return to Answer

added 114 characters in body
Source Link
Sid Datta
Sid Datta
  • 127
  • 2

I believe you already have great answers, but here is my $0.02 of theoretical solution to the problem.

What you want is NOT the longest path, but longest shortest path. You want the room that is the farthest away, given you are considering the shortest path to the room. This probably sounds confusing, but it is very easy to calculate.

  1. Start at your starting room. Mark each of its neighbors 1. They are distance 1 away from the starting room.
  2. For each room marked 1, visit each of its UNMARKED neighbors and mark them 2. They are 2 distance away from the start.
  3. Continue until you have covered all the rooms. The room with the maximum number is farthest away from the start.

Computing an actual longest path (wont take too long for say 10 rooms) will not work because you cannot make the player take that longest path. So putting the entry and exit in two rooms farthest away from each other is your best bet. To find this, calculate the farthest roomsroom from a random room. Then, for everyfrom that room, find the farthest room. This is called finding the diameter of a Graph, please Google it.

I believe you already have great answers, but here is my $0.02 of theoretical solution to the problem.

What you want is NOT the longest path, but longest shortest path. You want the room that is the farthest away, given you are considering the shortest path to the room. This probably sounds confusing, but it is very easy to calculate.

  1. Start at your starting room. Mark each of its neighbors 1. They are distance 1 away from the starting room.
  2. For each room marked 1, visit each of its UNMARKED neighbors and mark them 2. They are 2 distance away from the start.
  3. Continue until you have covered all the rooms. The room with the maximum number is farthest away from the start.

Computing an actual longest path (wont take too long for say 10 rooms) will not work because you cannot make the player take that longest path. So putting the entry and exit in two rooms farthest away from each other is your best bet. To find this, calculate the farthest rooms, for every room.

I believe you already have great answers, but here is my $0.02 of theoretical solution to the problem.

What you want is NOT the longest path, but longest shortest path. You want the room that is the farthest away, given you are considering the shortest path to the room. This probably sounds confusing, but it is very easy to calculate.

  1. Start at your starting room. Mark each of its neighbors 1. They are distance 1 away from the starting room.
  2. For each room marked 1, visit each of its UNMARKED neighbors and mark them 2. They are 2 distance away from the start.
  3. Continue until you have covered all the rooms. The room with the maximum number is farthest away from the start.

Computing an actual longest path (wont take too long for say 10 rooms) will not work because you cannot make the player take that longest path. So putting the entry and exit in two rooms farthest away from each other is your best bet. To find this, calculate the farthest room from a random room. Then, from that room, find the farthest room. This is called finding the diameter of a Graph, please Google it.

Source Link
Sid Datta
Sid Datta
  • 127
  • 2

I believe you already have great answers, but here is my $0.02 of theoretical solution to the problem.

What you want is NOT the longest path, but longest shortest path. You want the room that is the farthest away, given you are considering the shortest path to the room. This probably sounds confusing, but it is very easy to calculate.

  1. Start at your starting room. Mark each of its neighbors 1. They are distance 1 away from the starting room.
  2. For each room marked 1, visit each of its UNMARKED neighbors and mark them 2. They are 2 distance away from the start.
  3. Continue until you have covered all the rooms. The room with the maximum number is farthest away from the start.

Computing an actual longest path (wont take too long for say 10 rooms) will not work because you cannot make the player take that longest path. So putting the entry and exit in two rooms farthest away from each other is your best bet. To find this, calculate the farthest rooms, for every room.