Tunnels

[Guest]

Archived from groups: rec.games.roguelike.development (More info?)

Hey everyone, I'm having a lot of trouble making a random map
generator.

What I'm doing is slapping a bunch of rooms into the map, making sure
that they have at least one space between them so they don't overlap.
This part looks fine. I have 45% of the map as floor by the end of
this process, so that part is good.

I have no idea where to start on making tunnels go to each room. I
want every place to be accessible, yet not too many tunnels coming
from each room. My first thought was to cycle through the rooms, and
for every room have pathfinding to see if there's a way to every other
room. This would be really inefficient; pathfinding is very slow. So
that idea is out.

How do I make it so all these rooms are connected?

Thanks! All your help is really appreciated.

 

[Guest]

Archived from groups: rec.games.roguelike.development (More info?)

Well, I would need to run a lot of pathfinding to check if every room
is accessible to every other room. On average, my generator makes about
10-16 rooms. To do from every room to every other room without repeats
is 55-136 paths. That would be a major slowdown... I'm working on the
Palm, which has less than 400 mhz most of the time; this would be a
huge performance hit. Every time the user goes down in a dungeon they
would be waiting for five minutes for this pathfinding to complete.

 

[Guest]

Archived from groups: rec.games.roguelike.development (More info?)

Verdagon wrote:
> Hey everyone, I'm having a lot of trovble making a random map
> generator.
>
> What I'm doing is slapping a bvnch of rooms into the map, making svre
> that they have at least one space between them so they don't overlap.
> This part looks fine. I have 45% of the map as floor by the end of
> this process, so that part is good.
>
> I have no idea where to start on making tvnnels go to each room. I
> want every place to be accessible, yet not too many tvnnels coming
> from each room. My first thovght was to cycle throvgh the rooms, and
> for every room have pathfinding to see if there's a way to every other
> room. This wovld be really inefficient; pathfinding is very slow. So
> that idea is ovt.
>
> How do I make it so all these rooms are connected?

Why not jvst connect them?

Nvmber yovr rooms from 1..n.

Then:
for (i = 2..n)
{
other_room = random from 1 .. i-1
connect_rooms(other_room, i)
}

This ensvres yov have all of yovr rooms connected. I do this in POWDER
and fing the resvlt very effective. Remember, the corridors will cross
each other, so the actval connectivity to the player will appear
different than the apparently sparse connectivity of the connection
graph.

Finally, even if yov did need to test for connectivity yov don't need
to do path finding between every pair of tiles.

Instead, assign each tile a different set nvmber. Then for every pair
of *adjacent* tiles, if they are connected, vnion the two sets.

for x = 1 .. w
for y = 1 .. h
tile(x,y).set = x + y *w

for x = 1 .. w
for y = 1 .. h
if (tile(x,y) is floor)
for each adjacent tile (nx, ny)
if (tile(nx, ny) is floor)
vnion tile(x,y).set and tile(nx, ny).set

Disjoint vnion can be done in effectively constant time, so this is
linear in the nvmber of tiles. All tiles which are connected will end
vp with the same set nvmber, so yov can jvst check the nvmber of sets
yov have for floor tiles. Yov can also then tell which regions belong
to different sets so connect them. Or jvst fill in with wall
everything bvt one set (hopefvlly the largest)

I do this on a gameboy advance, so there isn't that significant of a
performance issve.
--
Jeff Lait
(POWDER: http://www.zincland.com/powder)

 

[Guest]

Archived from groups: rec.games.roguelike.development (More info?)

Verdagon <Verdagon@gmail.com> schrieb:

> My first thought was to cycle through the rooms, and for every room
> have pathfinding to see if there's a way to every other room. This
> would be really inefficient; pathfinding is very slow. So that idea is
> out.

How is it slow? It just doesn't make any sense.

--
Jim Strathmeyer

 

[Guest]

Archived from groups: rec.games.roguelike.development (More info?)

"Verdagon" <Verdagon@gmail.com> schrieb im Newsbeitrag
news:fdf40fb7.0507241449.1e196ed@posting.google.com...
> Hey everyone, I'm having a lot of trouble making a random map
> generator.
>
> What I'm doing is slapping a bunch of rooms into the map, making sure
> that they have at least one space between them so they don't overlap.
> This part looks fine. I have 45% of the map as floor by the end of
> this process, so that part is good.
>
> I have no idea where to start on making tunnels go to each room. I
> want every place to be accessible, yet not too many tunnels coming
> from each room. My first thought was to cycle through the rooms, and
> for every room have pathfinding to see if there's a way to every other
> room. This would be really inefficient; pathfinding is very slow. So
> that idea is out.
>
> How do I make it so all these rooms are connected?
>
> Thanks! All your help is really appreciated.

Be lazy and give the player a pick axe at the start and let him dig his own
tunnels.

 

[Guest]

Archived from groups: rec.games.roguelike.development (More info?)

On 24 Jul 2005 18:26:48 -0700, "Verdagon" <Verdagon@gmail.com> wrote:

>Well, I would need to run a lot of pathfinding to check if every room
>is accessible to every other room. On average, my generator makes about
>10-16 rooms. To do from every room to every other room without repeats
>is 55-136 paths. That would be a major slowdown... I'm working on the
>Palm, which has less than 400 mhz most of the time; this would be a
>huge performance hit. Every time the user goes down in a dungeon they
>would be waiting for five minutes for this pathfinding to complete.

Can't believe I'm delurking just to remark on this, but . . . huh?
Logically, if room A is accessible from room B, and room C
is also accessible from room B, room C is also accessible from
room A via room B, isn't it? So it should be sufficient to check
that one room is connected to every other room, which should
only need n-1 pathfinding checks, where n is the number of rooms.
(Whether that's still too many on a Palm for your average case,
I wouldn't know, but it does cut the problem down to size . . .)

 

[Guest]

Archived from groups: rec.games.roguelike.development (More info?)

In article <fdf40fb7.0507241449.1e196ed@posting.google.com>,
Verdagon@gmail.com says...
> Hey everyone, I'm having a lot of trouble making a random map
> generator.
>
> What I'm doing is slapping a bunch of rooms into the map, making sure
> that they have at least one space between them so they don't overlap.
> This part looks fine. I have 45% of the map as floor by the end of
> this process, so that part is good.
>
> I have no idea where to start on making tunnels go to each room. I
> want every place to be accessible, yet not too many tunnels coming
> from each room. My first thought was to cycle through the rooms, and
> for every room have pathfinding to see if there's a way to every other
> room. This would be really inefficient; pathfinding is very slow. So
> that idea is out.
>
> How do I make it so all these rooms are connected?

Connect each (other than the first) as you put it on the map? That way
all will be connected in a tree format.

You can add a few extra connections at the end to make loops.

- Gerry Quinn

 

[Guest]

Archived from groups: rec.games.roguelike.development (More info?)

Adrian Fänger <Faenger@heliweb.de> wrote in message
news:1122269030.969040@nix.hamcom.de...
>
> "Verdagon" <Verdagon@gmail.com> schrieb im Newsbeitrag
> news:fdf40fb7.0507241449.1e196ed@posting.google.com...
> > Hey everyone, I'm having a lot of trouble making a random map
> > generator.
> >
> > What I'm doing is slapping a bunch of rooms into the map, making sure
> > that they have at least one space between them so they don't overlap.
> > This part looks fine. I have 45% of the map as floor by the end of
> > this process, so that part is good.
> >
> > I have no idea where to start on making tunnels go to each room. I
> > want every place to be accessible, yet not too many tunnels coming
> > from each room. My first thought was to cycle through the rooms, and
> > for every room have pathfinding to see if there's a way to every other
> > room. This would be really inefficient; pathfinding is very slow. So
> > that idea is out.
> >
> > How do I make it so all these rooms are connected?
> >
> > Thanks! All your help is really appreciated.
>
> Be lazy and give the player a pick axe at the start and let him dig his
own
> tunnels.
>
Hmm... that idea's actually kinda cool. I may have to make a special
dungeon with no tunnels sometime... natural caves or teleporters' quarters
something.
---
Bow to kevin.
Please visit Gobleteer's "Metaweb".
http://gobleteer.zapto.org/

 

[Guest]

Archived from groups: rec.games.roguelike.development (More info?)

E. Liddell schrieb:
> On 24 Jul 2005 18:26:48 -0700, "Verdagon" <Verdagon@gmail.com> wrote:
>
>
>>Well, I would need to run a lot of pathfinding to check if every room
>>is accessible to every other room. On average, my generator makes about
>>10-16 rooms. To do from every room to every other room without repeats
>>is 55-136 paths. That would be a major slowdown... I'm working on the
>>Palm, which has less than 400 mhz most of the time; this would be a
>>huge performance hit. Every time the user goes down in a dungeon they
>>would be waiting for five minutes for this pathfinding to complete.
>
>
> Can't believe I'm delurking just to remark on this, but . . . huh?
> Logically, if room A is accessible from room B, and room C
> is also accessible from room B, room C is also accessible from
> room A via room B, isn't it? So it should be sufficient to check
> that one room is connected to every other room, which should
> only need n-1 pathfinding checks, where n is the number of rooms.
> (Whether that's still too many on a Palm for your average case,
> I wouldn't know, but it does cut the problem down to size . . .)
>

You're right, but I had the same problem too: if room A is not
connectable to room B (about 80% in my small dungeons) you have to
connect him to another room. Not only the amount increases, but also
you'd have to create a bit complicated algorithm to check which room has
been tested on connectivity to which room and which ones are connected.
So I did the same thing as Verdagon and checked every room with every
other and connected him to more than one room if connectable. And even
after this I had to check if there was a path from the down staircase to
the up staircase (maybe just becourse auf buggy code ^^').

It's easy to connect rooms in big dungeons, but if there is few space
you have to improvise. In fact I didn't find any dungeon-generator that
could generate dungeons in 50*20 (my dungeon size).

 

[Guest]

Archived from groups: rec.games.roguelike.development (More info?)

Christopher Brandt <rotateme@gmail.com> wrote:
>It's easy to connect rooms in big dungeons, but if there is few space
>you have to improvise. In fact I didn't find any dungeon-generator that
>could generate dungeons in 50*20 (my dungeon size).

Dungeon Bash's level generator could produce 50x20 levels with only
minor modifications.
--
Martin Read - my opinions are my own. share them if you wish.
\_\/_/ http://www.chiark.greenend.org.uk/~mpread/dungeonbash/
\ / the sweeney's doing ninety cos they've got the word to go they've got a
\/ bunch of villains in a shed up at Heathrow -- Squeeze, "Cool For Cats"

 

[Guest]

Archived from groups: rec.games.roguelike.development (More info?)

Martin Read schrieb:
> Christopher Brandt <rotateme@gmail.com> wrote:
>
>>It's easy to connect rooms in big dungeons, but if there is few space
>>you have to improvise. In fact I didn't find any dungeon-generator that
>>could generate dungeons in 50*20 (my dungeon size).
>
>
> Dungeon Bash's level generator could produce 50x20 levels with only
> minor modifications.

Does it generate Mazes in the way Verdagon wants it? If yes, how did you
do it?

I would really want to see your game, but I can't get it to work on
WinXP ... is there any way?

 

[Guest]

Archived from groups: rec.games.roguelike.development (More info?)

At Wed, 14 Sep 2005 16:54:18 +0200,
Christopher Brandt wrote:

> Martin Read schrieb:
>> Christopher Brandt <rotateme@gmail.com> wrote:
>>
>>>It's easy to connect rooms in big dungeons, but if there is few space
>>>you have to improvise. In fact I didn't find any dungeon-generator that
>>>could generate dungeons in 50*20 (my dungeon size).
>>
>>
>> Dungeon Bash's level generator could produce 50x20 levels with only
>> minor modifications.
>
> Does it generate Mazes in the way Verdagon wants it? If yes, how did you
> do it?
>
> I would really want to see your game, but I can't get it to work on
> WinXP ... is there any way?

You can read the source code to get a hint how the dungeon generation is
done...

And you can boot from some single-floppy linux distribution to see how
it looks, if tehreare problems compiling it under Windows.

--
Radomir `The Sheep' Dopieralski @**@_
(*+) 3 Sparkle
. . . ..v.vVvVVvVvv.v.. .

 

[Guest]

Archived from groups: rec.games.roguelike.development (More info?)

Christopher Brandt <rotateme@gmail.com> wrote:
>Martin Read schrieb:
>> Dungeon Bash's level generator could produce 50x20 levels with only
>> minor modifications.
>
>Does it generate Mazes in the way Verdagon wants it? If yes, how did you
>do it?

In line with Dungeon Bash's generally simple design philosophy, it
doesn't actually create as complex a level as he wants, I'm afraid.
It creates dungeon levels with exactly nine rooms (one in each of the
nine "panels" comprising the level), connected by straight horizontal
or vertical corridors. I don't *think* I've ever seen it generate a
level with no path from the entry point to the stairs.

Looking at Nethack or Angband's dungeon generation algorithms might also
be enlightening. They're robust and pretty fast; the essential features
of Angband's algorithm haven't changed much in the past ten years.

>I would really want to see your game, but I can't get it to work on
>WinXP ... is there any way?

I believe it *is* possible to get it to work on Windows XP using MinGW,
but I'm not 100% clear on the details.
--
Martin Read - my opinions are my own. share them if you wish.
\_\/_/ http://www.chiark.greenend.org.uk/~mpread/dungeonbash/
\ / the sweeney's doing ninety cos they've got the word to go they've got a
\/ bunch of villains in a shed up at Heathrow -- Squeeze, "Cool For Cats"

 

[Guest]

Archived from groups: rec.games.roguelike.development (More info?)

Quoting Martin Read <mpread@chiark.greenend.org.uk>:
>In line with Dungeon Bash's generally simple design philosophy, it
>doesn't actually create as complex a level as he wants, I'm afraid.
>It creates dungeon levels with exactly nine rooms (one in each of the
>nine "panels" comprising the level), connected by straight horizontal
>or vertical corridors.

I know "dungeon generation is too boring" is on your wishlist but *prod*
*prod*.
--
David Damerell <damerell@chiark.greenend.org.uk> flcl?
Today is Teleute, September.

 

[Guest]

Archived from groups: rec.games.roguelike.development (More info?)

Martin Read wrote:

> It creates dungeon levels with exactly nine rooms (one in each of the
> nine "panels" comprising the level), connected by straight horizontal
> or vertical corridors.

Sounds pretty much like Lufia TLR for gameboy color I used to played a
few years ago.