Public Group

# Pathfinding problem.

This topic is 3958 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

I will use this image to help explain my problem: I'm writing a dungeon generator. It's pretty much finished, except for one problem. The dungeons are a bit too linear. They're not completely linear, but they could definitely have more loops in them. That's what I'm trying to do. The idea is to randomly pick two rooms. Then, use a pathfinding algorithm to get a path from the first room to the second room, and then dig a tunnel there. Currently, my pathfinding gives a path similar to the one colored in green. That, however, is not what I would like the path to look like. I want it to actually look like the one highlighted in red. Got any ideas? If you'd like to post code, please use either C++ or pseudo-code. I'm using a language that I'm sure most of you don't know about. Anyway, thanks.  Also, I'm not looking to get the shortest path between the two rooms. Any distance path works fine.

##### Share on other sites
Hi Koyeall,

After giving an initial answer, I've completely edited my post once I was a bit more awake, here goes:

Pseudo:
Let(S_x, S_y) be the center of your Start-Dungeon
Let(G_x, G_y) be the center of your Goal-Dungeon
Let (C_x, C_y) be (S_x, S_y)

if( |S_x - G_x| < |S_y - G_y| )
Increase( C_y, G_y )
Increase( C_x, G_x )
else
Increase( C_x, G_x )
Increase( C_y, G_y )

Increase( coord, goalCoord )
if( coord < goalCoord )
While( coord != goalCoord ) coord += 1
else
While( coord != goalCoord ) coord -= 1

// Make this position on the map white
SetWhite( (C_x, C_y) );
End Increase

This will move along the axis on which the distance between the dungeons is greater first.

Good luck!
Tristan

[Edited by - Tristan85 on February 8, 2008 3:01:54 AM]

##### Share on other sites
In addition, you could put in a random element as to where the corridor meets each room :

Let(S_x + (random()*S_width), S_y + (random()*S_height))
Let(G_x + (random()*G_width), G_y + (random()*G_height))
Let (C_x, C_y) be (S_x, S_y)

might just make things a little more interesting.

##### Share on other sites
Thanks for the help, it works nicely now. ;)

1. 1
2. 2
3. 3
Rutin
23
4. 4
5. 5
khawk
14

• 9
• 11
• 11
• 23
• 12
• ### Forum Statistics

• Total Topics
633653
• Total Posts
3013162
×