Author Topic: Keeping room lists after dungeon generation  (Read 10804 times)

darrellp

  • Newcomer
  • Posts: 3
  • Karma: +0/-0
    • View Profile
Keeping room lists after dungeon generation
« on: September 28, 2011, 06:35:45 PM »
I'm in the process of playing around doing a RL.  I've got my
generation algorithm going and am happy with the result.  I'm going
through a few extra cycles to keep around a detailed room/corridor
graph which keeps track of all rooms and corridors and which other
rooms/corridors they're linked to. I haven't started putting items
down yet, but my thought was that there are various parts of that
process that depend on individual room locations.  Making a "monster
room" or "treasure room" for instance.  When I start letting monsters
loose I figured that a graph of individual rooms would make the path
finding go a lot faster also - I determine the shortest path in the
room graph and then only have to have each monster search inside the
current room for the appropriate exit rather than having to search the
whole map.

So I'm wondering whether other people do it this way.  It seems pretty
incompatible with some of the Perlin noise generated algorithms.  I
think maybe other people just carve out the map and then forget about
the individual rooms.  That would make some things simpler - I'm
thinking here in particular of potential tunneling on the part of the
adventurer who creates new passages.  I think I could handle this by
just adding any tunneling on to the room the adventurer is in and if a
new path is created between rooms, incorporating it into the room
graph when it occurs.


In the end, do you folks think it's worth keeping this information
around?  Maybe it's not "good" or "fair" having any monsters make a
direct beeline for the adventurer.  Certainly, I think there's got to
be something that moderates it - you don't want your entire dungeon to
close in on our hapless adventurer and empty the rest of the dungeon.
Maybe only certain monsters?  Maybe the beeline gets slightly elevated
probability in their wandering - higher as the adventurer gets
closer?  Is this valuable information to keep around or should I just
chuck it after excavating and rely on one big map of terrain?  Are
there other things I might use this for?  I'm interested in hearing
people's opinions.


Thanks!


Darrell Plank



Z

  • Rogueliker
  • ***
  • Posts: 905
  • Karma: +0/-0
    • View Profile
    • Z's Roguelike Stuff
Re: Keeping room lists after dungeon generation
« Reply #1 on: September 28, 2011, 10:18:11 PM »
Keeping the list of rooms in the memory is a good idea as long as you have any use for it, or it is just more trouble to delete it than to keep it. ;)

If your game features digging, I think it is logical if monsters remember the room layout of the dungeon and use it, even if you have created shortcuts. I think it is not fair if monsters immediately know about any shortcuts you make. Knowing the location of PC if not seen is unfair unless you give some reason for it (sound, smell, monsters call other monsters). (And pathfinding to a PC that is seen is obvious unless the game features impassable translucent terrain.) If you do give such a reason, then this could make an interesting game, I think.

Are you sure there is any reason to optimize pathfinding? My Hydra Slayer does DFS each turn and that is certainly fast enough.

darrellp

  • Newcomer
  • Posts: 3
  • Karma: +0/-0
    • View Profile
Re: Keeping room lists after dungeon generation
« Reply #2 on: September 29, 2011, 12:14:26 AM »
Well, no - I'm not sure I need this for optimizing pathfinding.  That's part of the question.  If you're going to have all monsters do full pathfinding from all parts of the level, then at some size of dungeon that would get overwhelming.  I'm not sure what that size is.  Nor am I sure that I actually want all monsters at all parts of the dungeon doing full pathfinding.  I think some people must do it by using only monsters that have seen the hero.  In that case, no you probably don't need full pathfinding anywhere in the dungeon since any monsters will be relatively close to their ultimate destination.  I suppose I should actually glance at some of the code that's out there to see what others are doing.

But over and above pathfinding, I'm wondering about "room effects".  Do any games have these?  I'm thinking along the lines of different rooms having different colors and some items working better in different colors - something along those lines - or maybe certain rooms emit a "strange aura".  This would really, though, only require identification of the room "color" or "aura" in the map - the graph of room connections wouldn't necessarily be helpful.  Other than pathfinding I'm not sure that I can come up with a great reason to keep the full map around.  Perhaps some sort of "room by room" creep - say gas that invades the next room over.  That doesn't seem terribly compelling and the connection map would only be of limited help there anyway.

I think I'll keep it in for the moment - it will be easier to yank out in the future when I don't need it than to reimplement it if I decide I do.  I would be interested though if anybody knows any creative uses for such a thing.

NON

  • Rogueliker
  • ***
  • Posts: 349
  • Karma: +0/-0
    • View Profile
    • Infra Arcana
    • Email
Re: Keeping room lists after dungeon generation
« Reply #3 on: September 29, 2011, 06:56:32 AM »
But over and above pathfinding, I'm wondering about "room effects".
I do it in Infra Arcana. Each turn a room handler asks every room "is the player inside your room now?", and if so "run your event stuff".
The room list is also used for turning common rooms into special decorated rooms. Without this list this would need more code and be slower to execute.
Happy is the tomb where no wizard hath lain and happy the town at night whose wizards are all ashes.

Bear

  • Rogueliker
  • ***
  • Posts: 308
  • Karma: +0/-0
    • View Profile
Re: Keeping room lists after dungeon generation
« Reply #4 on: September 30, 2011, 06:41:45 PM »
As already expressed here, keeping a room list around is fine as long as you have a use for it.

I handle most pathfinding using "gradients." Any creature that actually does pathfinding winds up knowing how many steps from their location to the player, and before they move they can write a gradient number to the square they're on.  The gradient number is the current turn times the dungeon width, minus the current distance to the player. 

Other creatures can follow the gradients, as long as they're not too old.  If you find that you are standing on a square with a gradient, and you want to go to the player character, just step to the adjacent square with the highest gradient number.  So I don't have to have all the creatures do pathfinding.  One goblin comes by doing pathfinding, then 30 more goblins follow in his footsteps before the gradient gets too old, and the 32nd goblin has to do pathfinding again.

And the player himself sets gradients (representing monster FOV) as we process his field of view.  Every time the player sees a square, that square gets a gradient number.   This allows
any monster standing on that square to know that the player is in the monster's FOV, this turn. This also allows a simple and effective "chase the player" behavior on the basis of purely local decisions on the part of monsters not currently in sight of the player; just keep stepping to the adjacent square with the highest gradient number. 

In fact, with the player laying down gradient numbers in his FOV, you don't even really have to do pathfinding, as such, unless you want to. 


Krice

  • (Banned)
  • Rogueliker
  • ***
  • Posts: 2316
  • Karma: +0/-2
    • View Profile
    • Email
Re: Keeping room lists after dungeon generation
« Reply #5 on: October 02, 2011, 01:25:46 PM »
I'm in the process of playing around doing a RL.  I've g

Don't double post here and rec.games.roguelike.development. It's annoying.

darrellp

  • Newcomer
  • Posts: 3
  • Karma: +0/-0
    • View Profile
Re: Keeping room lists after dungeon generation
« Reply #6 on: October 02, 2011, 03:07:28 PM »
Sorry - I didn't realize you weren't allowed to gather information from both communities.

Z

  • Rogueliker
  • ***
  • Posts: 905
  • Karma: +0/-0
    • View Profile
    • Z's Roguelike Stuff
Re: Keeping room lists after dungeon generation
« Reply #7 on: October 02, 2011, 05:17:22 PM »
I think Krice is just trolling, not everybody is reading both and there is nothing very wrong with double posting. After all, in both communities similar topics are discussed again and again sometimes.

Krice

  • (Banned)
  • Rogueliker
  • ***
  • Posts: 2316
  • Karma: +0/-2
    • View Profile
    • Email
Re: Keeping room lists after dungeon generation
« Reply #8 on: October 02, 2011, 05:31:18 PM »
not everybody is reading both

I think everyone is reading rgrd and some of those this forum. That's why it's double posting. If you want an answer you need only post it here or rgrd. There are only some purists using rgrd because they don't want to use forums like this and they have text only user interface in their linux.

guest509

  • Guest
Re: Keeping room lists after dungeon generation
« Reply #9 on: October 03, 2011, 08:28:58 AM »
  Hey Krice I am only reading this forum. Though I dabble on other game programming forums. You think I'm missing something not reading the rgrd?

UltimaRatioRegum

  • Rogueliker
  • ***
  • Posts: 318
  • Karma: +0/-0
  • Username says it all, really.
    • View Profile
    • Ultima Ratio Regum
    • Email
Re: Keeping room lists after dungeon generation
« Reply #10 on: October 03, 2011, 11:49:36 PM »
Chance of creatures zeroing in on the player as the player gets closer is how I did it, and - I think - how most roguelikes do it. Give them a value that determines how observant they are, or intelligent, or whatever, and the higher this is, the quicker they notice you, or the longer the distance they can notice you from. Tie that to giving them their own field of view to make sure they can't magically see you through walls when you're in range! Unless, of course, you WANT them to be able to do that, and all the creatures are x-ray-vision-wielding fiends.
« Last Edit: October 03, 2011, 11:51:25 PM by UltimaRatioRegum »