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.

Answer 2

I would say pathfinding is the wrong term here: usually that involves finding a valid route from A to B, and your problem is not the finding of that route but in creating routes to suit your purpose. You are deliberately creating sub-optimal paths and their quality will be hard to quantify. So I don't think a search algorithm with any heuristic would be the best solution for the problem. When you have one mandatory criterion (a working path) and some fuzzy, undefined criteria (natural-looking and winding), it's best to start out by meeting the mandatory requirements and attempt to mutate it towards the other requirements. That way you always have something that works.

I suggest, given that you seem to prefer horizontal and vertical paths turning at right angles, to start off with a straight, 2 segment path from A to B. (A* with Manhattan distance heuristic can find this for you, but it's just as easy to step it out yourself). Then take a random point along one of the two segments and one of the two end points for that segment, and move that subsection of the line parallel to itself by some random distance. Then add the 2 extra line segments to join the new position of the line to the old connection points. Your second example shows one iteration of this algorithm: if A is (0,0) and B is (5, 7) then you have picked the 2nd line segment (the vertical one) at random, picked the endpoint at (0,5) and a midpoint at (5,5), and pushed that section to the right by 3 units, before joining it back up.

Answer 3

Here's an idea ---

Start at A and make a move in a random direction -- left, up, or down. After each move, roll a random number to see if you turn. Lets say that 75% of the time you keep traveling in the same direction, and 25% of the time you'll turn. When you turn, always turn in a direction that leads closer to B. That will mean that if you're moving left or right, you'll have to turn up, and if you're moving up, make a right/left choice based on how far you currently are to the right or left of the goal. Also, if you hit one of the world boundaries, turn!

That shouldn't be too difficult to code. I have a feeling you're just trying to make this more complicated than it needs to be...