I am writing a rogue-like game and have created some 2D rooms/rectangles. Now I wish to link up the rooms using corridors and was wondering if A* pathfinding would be appropriate? I have never done anything like it before and so don't want to end up coding something for hours, only to realise it wouldn't work or that I could have done something simpler. Here is a bit of info on my code: 1. 6 rooms created with random sizes and positions 2. Room data is stored in a 2 dimensional array called Map(60,40) 3. Empty space is symbolised in the array by 0's, floors by 1's and walls by 2's example: 000000000000000000000 000000000000000000000 000000000000000000000 000222222222222220000 000211111111111120000 000211111111111120000 000211111111111120000 000211111111111120000 000222222222222220000 000000000000000000000 000000000000000000000 000000000000000000000 Any accounts of previous attempts at 2D dungeon generation or something similar are welcome. Cheers. [Edited by - Skateblind on July 20, 2008 8:46:23 AM]

A* will work for pathfinding, but pathfinding is different than dungeon generation. What are you trying to do... find shortest possible paths between rooms to make into corridors?

I think that A* is fully appropriate for enviroments like yours. I suggest you to use it.

Quote:Original post by Sneftel
A* will work for pathfinding, but pathfinding is different than dungeon generation. What are you trying to do... find shortest possible paths between rooms to make into corridors?

Yes :)

There's a couple of problems with using A* for that. First of all, A* finds the shortest path from a single start node to any of one or more goal nodes. In other words, you can't (efficiently) use it to determine the best point on each of the rooms to use to place the corridor, only to find the best point on the second room, given a point on the first room. Secondly, A* is not going to produce interesting-looking or varied paths. Assuming 8-way movement, each corridor will simply be a straight diagonal segment followed by a straight axial segment. Offhand I could think of a couple of hacks to A* to improve things a little, but given the trivial nature of the paths being found I really doubt A* is the way to go.

Quote:Original post by Sneftel
There's a couple of problems with using A* for that. First of all, A* finds the shortest path from a single start node to any of one or more goal nodes. In other words, you can't (efficiently) use it to determine the best point on each of the rooms to use to place the corridor, only to find the best point on the second room, given a point on the first room. Secondly, A* is not going to produce interesting-looking or varied paths. Assuming 8-way movement, each corridor will simply be a straight diagonal segment followed by a straight axial segment. Offhand I could think of a couple of hacks to A* to improve things a little, but given the trivial nature of the paths being found I really doubt A* is the way to go.

The starting and finishing points are randomly picked on a wall, so there is no problem with that. At the moment I am not worried about have interesting corridors, lol, but I can see why that would be a problem. I am sure it wouldn't be too difficult to add a bit of randomness to its path choosing though.

If not A* pathfinding, what would you suggest for connecting two points with?

Thank you for the help, I really appreciate the fact that you have detailed reasons why it is or isn't a bad idea. I am sorry to say this George109, but your reply was next to useless, thanks anyway. :)

Quote:Original post by Sneftel
First of all, A* finds the shortest path from a single start node to any of one or more goal nodes. In other words, you can't (efficiently) use it to determine the best point on each of the rooms to use to place the corridor, only to find the best point on the second room, given a point on the first room.

Finding the shortest path from multiple start nodes to multiple goal nodes is also possible. You push all start nodes into the open list, like you would do with a single start node. You can also sort them by initializing the costFromStart to a different value for each start node.

Quote:Original post by Skateblind
The starting and finishing points are randomly picked on a wall, so there is no problem with that.

You can just pass all the points to A* as start and goal nodes and the A* will find the shortest path.

Quote:Original post by Skateblind
The starting and finishing points are randomly picked on a wall, so there is no problem with that.

Just make sure you pick them on the right side of the room. Otherwise many of your corridors will wrap around the sides of the room, which I assume you don't want.

Quote:At the moment I am not worried about have interesting corridors, lol, but I can see why that would be a problem. I am sure it wouldn't be too difficult to add a bit of randomness to its path choosing though.

Adding randomness to A* is a surprisingly tricky thing, though you could postprocess the generated paths, I suppose.

Quote:If not A* pathfinding, what would you suggest for connecting two points with?

In many ways, this is a much easier problem than that which A* is designed to solve. You're not constrained in any way; you've got a full 2D grid to tunnel through. One thing that might work is an extremely simple agent-based approach. Put a "digger" at the starting door, and have him tunnel. In a loop, he goes forward one space, and then has a 25% chance of turning and a 75% chance of not turning. If he turns, he has a 75% chance of turning towards the target room and a 25% chance of turning away. He stops when he hits the target room. You'd probably want to tweak these values a lot, and include special purpose handling for rooms which are very far away or very close, and to avoid self-intersecting corridors. Still, it would be a pretty flexible approach, and worth a try. Before you do any of this stuff, though, you should probably check out how existing roguelikes do it.

I am not worried about corridors wrapping round rooms.

I have looked at how other rogue-like create dungeons and most of them start with a maze and then build rooms off of that, then they remove dead ends. Most of the code looks pretty easy, but will involve a lot of effort for me since I have never done anything like it before.

@George109, was your last post concerning the creation of doors that are closest to each other when linked with a corridor? If so, then I am not looking to create the shortest path to a room, just a path in general, so long as it doesn't turn into a maze I am happy.

You both have been very helpful and I have decided to try A* pathfinding out, it shouldn't take very long to implement, so if the results are unsatisfactory I won't mind trying a different method.

That digging method is probably the first thing I shall try if this A* pathfinding is a flop. I will post updates in this thread to let you know how I am getting along.

Feel free to keep posting ideas or tips, anything is appreciated.

Thanks! :)

*UPDATE*

I have finally managed to link my rooms/rectangles with corridors/lines.

I used A* pathfinding to achieve the corridor creation between rooms. At the moment it only connects two rooms together, but it won't take to long to make it pick random rooms to connect up, I just don't have the time to code at the moment.

I made a video to show step by step how the A* pathfinding works at linking rooms with corridors.
The map looks small, but that is only because I changed the display values so that I could show the whole map without scrolling.



*UPDATE*