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.