Author Topic: Room connection problem  (Read 27128 times)

Krice

  • (Banned)
  • Rogueliker
  • ***
  • Posts: 2316
  • Karma: +0/-2
    • View Profile
    • Email
Room connection problem
« on: May 31, 2009, 06:51:05 AM »
I'm using a routine that finds closest room and creates a corridor between. Of course in the end there are groups of rooms that are not connected together. How to determine the missing connections?

Anvilfolk

  • Rogueliker
  • ***
  • Posts: 374
  • Karma: +0/-0
    • View Profile
Re: Room connection problem
« Reply #1 on: May 31, 2009, 08:04:56 AM »
The simplest implementation is to use some sort of flood-fill algorithm to guarantee that the whole map is accessible through one point.

You can probably use some sort of boolean matrix system, where you copy the positive values of each line to the others as soon as a connection is made. You may also annotate the lines of the matrix with the ID of the connected component of the graph it represents. This might be faster than the flood-fill algorithm, if you don't have an absurd number of rooms.

The advantage of the matrix/graph system would be that you could immediately identify which rooms need to be connected in order for the whole map to be connected. Instead of a matrix you could probably have any other graph representation that you want.
« Last Edit: May 31, 2009, 08:08:15 AM by Anvilfolk »
"Get it hot! Hit it harder!!!"
 - The tutor warcry

One of They Who Are Too Busy

Krice

  • (Banned)
  • Rogueliker
  • ***
  • Posts: 2316
  • Karma: +0/-2
    • View Profile
    • Email
Re: Room connection problem
« Reply #2 on: May 31, 2009, 08:16:52 AM »
The advantage of the matrix/graph system

That's too advanced for me. An idea I got is floodfill everything and check how many disconnected areas there are, then go through those areas, pick one room and connect to other area's randomly selected room.

Anvilfolk

  • Rogueliker
  • ***
  • Posts: 374
  • Karma: +0/-0
    • View Profile
Re: Room connection problem
« Reply #3 on: May 31, 2009, 09:15:19 AM »
Haven't got a lot of time right now, unfortunately, otherwise I'd be happy to explain a bit further.

Either way, I doubt in modern computers using flood-fill would be slow :) You can just pick a non-wall square at random and flood-fill from there. After that's done, go over the whole map and see if there's any square that's not been filled. If there is, connect it, and repeat. Otherwise, you're done!
"Get it hot! Hit it harder!!!"
 - The tutor warcry

One of They Who Are Too Busy

Ex

  • IRC Communications Delegate
  • Rogueliker
  • ***
  • Posts: 313
  • Karma: +0/-0
    • View Profile
Re: Room connection problem
« Reply #4 on: May 31, 2009, 10:42:50 PM »

rdc

  • Newcomer
  • Posts: 41
  • Karma: +0/-0
  • You hear a *bump* in the dark...
    • View Profile
    • Clark Productions
    • Email
Re: Room connection problem
« Reply #5 on: June 01, 2009, 01:04:25 PM »
I use a pick list for connecting rooms. I place all the rooms into a list. I then select a start room and an end room and connect the rooms. The first room is marked connected. The second room picked above becomes the first room and I select another room. I go through the list until all rooms are connected.

When drawing a corridor from the start room to the end room and I encounter another room, I end the drawing and mark the start room connected. This doesn't leave orphans since either the target room is already connected, or will be connected when iterating through the list. You could also just continue until you reach the target room.

I found this to be the easiest method and it guarantees each room is connected to another room.

Krice

  • (Banned)
  • Rogueliker
  • ***
  • Posts: 2316
  • Karma: +0/-2
    • View Profile
    • Email
Re: Room connection problem
« Reply #6 on: June 01, 2009, 07:56:42 PM »
When drawing a corridor from the start room to the end room and I encounter another room, I end the drawing and mark the start room connected.

Thanks, but your suggestion doesn't help here, it's just entirely another way of connecting rooms.

Ex

  • IRC Communications Delegate
  • Rogueliker
  • ***
  • Posts: 313
  • Karma: +0/-0
    • View Profile
Re: Room connection problem
« Reply #7 on: June 02, 2009, 01:08:41 AM »
If you're only dealing with rooms, you can sort your rooms based on proximity to each other into a list. You can then traverse that list from the first to the last, linking the current room with the next room each time. This will ensure that every room connects to every other room.

Krice

  • (Banned)
  • Rogueliker
  • ***
  • Posts: 2316
  • Karma: +0/-2
    • View Profile
    • Email
Re: Room connection problem
« Reply #8 on: June 02, 2009, 11:54:49 AM »
You can then traverse that list from the first to the last, linking the current room with the next room each time.

No I can't. That's a chain, but I can't use it here.

Anvilfolk

  • Rogueliker
  • ***
  • Posts: 374
  • Karma: +0/-0
    • View Profile
Re: Room connection problem
« Reply #9 on: June 02, 2009, 12:27:06 PM »
I think the idea is that he's already got the rooms connected in the way that he wants them to be connected, through some special algorithm. The problem is that that algorithm does not guarantee that there aren't separated components of the map.

In this case, again, the easiest way would be to simply flood-fill from one point and see if all rooms are connected. If you just connected rooms, you can probably have some kind of data-structure which tells you which rooms are connected to which other rooms. You should work over this structure instead of flood-filling, as it will surely be easier. Here's some pseudo-code:

Code: [Select]
ConnectAll(Map<Room, Set<Room>> connections){ // For each room, connections this tells you all other rooms that it's connected to.
  while(true) {
    InitialRoom = getRandomFrom(connections.keys()); // Get some random room
    Set<Room> itStart = {}; // Set of rooms at the start of the iteration
    Set<Room> itEnd = {InitialRoom}; // Set of rooms at the start of the iteration
    while(itStart != itEnd) { // We'll stop once there are no more differences
      Set<Room> newAdded = itEnd - itStart; // These are newly added rooms to the component
      itStart = itEnd;
      forEach(i: newAdded)
        itEnd.addAll(connections[i]);
    }

    if(itStart.size < connections.size){
       Room connectionStart = getRandomFrom(itStart); // Get a random room from the totally connected component we just calculated
       Room connectionEnd = getRandomFrom(connections.getSetOfKeys() - itStart); // get a random room that does NOT belong to the component we calculated
       connections[connectionStart].add(connectionEnd); // connect them!
    } else {
       return;
    }
  }
}


Sheesh, "pseudo-code" is harder to write than actual code. Bleh. I hope it gets the idea through though.
"Get it hot! Hit it harder!!!"
 - The tutor warcry

One of They Who Are Too Busy

Ex

  • IRC Communications Delegate
  • Rogueliker
  • ***
  • Posts: 313
  • Karma: +0/-0
    • View Profile
Re: Room connection problem
« Reply #10 on: June 02, 2009, 04:21:29 PM »
If he just wants to make sure every tile connects, my previously posted algorithm works wonders.

Krice

  • (Banned)
  • Rogueliker
  • ***
  • Posts: 2316
  • Karma: +0/-2
    • View Profile
    • Email
Re: Room connection problem
« Reply #11 on: June 17, 2009, 06:45:24 AM »
This is interesting. I was programming the corridor routine and accidentally created a routine that leaves one of the room from a group with one connection (others have two). This means that I can connect those rooms and join everything together. I really don't know how it works. The number of real connections is different, but I don't think it's a problem.