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

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.

• You'll increase the chances of people reading your question by adding well placed paragraph breaks. Jan 7, 2017 at 4:09
• Are there ever obstacles the path might need to route around? If not, you may be able to skip A* entirely and construct the path geometrically, without the incremental search. That would give very free control over the resulting shapes. Jan 7, 2017 at 5:38
• The way to do what DMGregory is describing is to use geometric drawing functions, and replace any calls to some_putpixel(x,y) with map[x][y]=SOME_TILE. He has a fair point, the same task could be accomplished even as my answer describes, by dividing the distance between two locations by two and drawing 3 lines with an algorithm such as Bresenhams line algorithm. Jan 15, 2017 at 19:50