Can A* path finding cost functions allow for path following shapes?

Question

Recently I begun developing a game prototype which could create procedural generated dungeons using a collection of room types. To ensure the hallway paths between these rooms would always be connected I implemented a A* path finding algorithm following along the tile map of randomly placed rooms.

The problem with doing this however is I was not necessarily trying to find the shortest path between rooms which in most cases would be a diagonal. Since being thematically a 'dungeon' I wanted them to twist and turn at 90 degree angles. By using a Manhattan distance for the heuristic I managed to get the intended shape but I've ended up with one final problem which I come to you kind people to help me with :).

Though now using 90 degree angles to move the path, its saves doing the run till the end of path(See picture below). This makes the whole thing at a distance feel cramped in places instead of using all the space effectively. Seeing how simply changing the heuristic from distance to Manhattan distance has made a difference my question is, is there a cost function I could implement that would give the desired results of this non conventional path? Any answers would be appreciated, thank you.

Note: The algorithm also has access to the normal direction of the start and end goals.

Answer 1

Your problem is simple, and as such the solution is too. What you want essentially, is for any time that your A* connects two rooms whose doors are 90 degrees from each other to remain standard, when the doors connecting two rooms are 180 degrees from each other, use the A* algorithm twice in the generation phase, from the door to the separating midpoint (rounded to that nearest tile of course) and from that tile to the next door.

Answer 2

Manipulate the tile cost function to make use of the distances (as the crow flies) from start to destination, in addition to the Manhattan distances. Add weights to these halves of the cost function so that you can prioritize the Manhattan distance, and produce a desirable result with little effort.

The smaller weight you apply to the crow-distance relative to the Manhattan distance, the more likely the desired Manhattan distance will take over. If your current algorithm has a 50/50 choice, you want to sway the decision into picking a tile further from your room.

Answer 3

I think the easiest way would be to implement a penalty for straightaways longer than a certain amount; say, half the distance between the two points you're trying to connect, rounded down to the nearest unit of measurement you're using (grid square?).

A harder way would be to take the solution and break it up into pieces; for instance, if the solution is up 5, over 5, you could break it into up 2, over 5, up 3. The problem with this solution is it might not be a valid path -- my first suggestion is better because you are modifying the algorithm to find a better path that will always work instead of taking a path and making it better such that it might not work.