method for specialized pathfinding?

Question

I am working on a roguelike in my (very little) free time. Each level will basically be a few rectangular rooms connected together by paths. I want the paths between rooms to be natural-looking and windy, however. For example, I would not consider the following natural-looking:

       B       
       X       
       X       
       X       
      XX       
     XX        
    XX         
  AXX          

I really want something more like this:

       B       
       X       
       XXXX    
          X    
          X    
          X    
          X    
  AXXXXXXXX    

These paths must satisfy a few properties:

1. I must be able to specify an area inside which they are bounded,
2. I must be able to parameterize how windy and lengthy they are,
3. The lines should not look like they started at one path and ended at the other. For example, the first example above looks as if it started at A and ended at B, because it basically changed directions repeatedly until it lined up with B and then just went straight there.

I was hoping to use A*, but honestly I have no idea what my heuristic would be. I have also considered using a genetic algorithm, but I don't know how practical that method might end up.

My question is, what is a good way to get the results I want? Please do not just specify a method like "A*" or "Dijkstra's algorithm," because I also need help with a good heuristic.

Answer 1

Before you can figure out how to produce paths, you have to figure out a more precise way to state what you want. One way to do this is assign each path a score, then search for high-scoring paths. Here are some questions to consider:

1. Do you prefer long straight runs to short ones? How will you quantify this preference? (To get a search algorithm to converge, it will be easier if your scoring function is nonlinear.)

2. If you want not to go straight to your destination, you may want to reward steps that are off the main line. For example, on the path from A to B, consider each point, then take three steps and compute the direction between points. Now take the cosine of the difference of that direction and the direction straight from A to B. Negate it. Steps on the line count -1 against you, steps perpendicular are neutral, and steps away from the line count +1 for you.

Here are some good next steps:

• Think of several more scoring ideas.
• Draw a dozen paths by hand and rank order them by how much you like them.
• For each path, create a couple of small variations by hand.
• Run your scoring function on all the paths. Keep fiddling until you get a scoring function that likes what you like.

Then you'll be ready to think about search algorithms.