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.