Pathfinding problem.
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.
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]
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]
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.
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.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement