Sign in to follow this  

Pathfinding problem.

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

If you intended to correct an error in the post then please contact us.

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. [edit] Also, I'm not looking to get the shortest path between the two rooms. Any distance path works fine.

Share this post


Link to post
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 this post


Link to post
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 this post


Link to post
Share on other sites

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

If you intended to correct an error in the post then please contact us.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this