Angband Forums Looking for advice on procedural mapping an infinite dungeon.
 User Name Remember Me? Password
 Register FAQ Members List Calendar Search Today's Posts Mark Forums Read

 Thread Tools Display Modes
 November 5, 2012, 20:00 #2 Patashu Knight     Join Date: Jan 2008 Posts: 526 One way to do it might be to have a function that pseudorandomly, yet deterministically (and since the rest of the map is deterministic it could use data around it) determines if tile (X,Y) is a room starting tile. If it is, then it pseudorandomly, yet deterministically builds a room, again it can use the deterministic landscape around it to help guide the room to be placed well. __________________ My Chiptune music, made in Famitracker: http://soundcloud.com/patashu
 November 5, 2012, 20:41 #3 Derakon Prophet     Join Date: Dec 2009 Posts: 9,024 Okay, so, correct me if I'm wrong, but basically what you want to do is have an infinite playing area where you explore as far as you like in any direction, and then backtrack and have the area you came from be consistent, without actually having to store that area? Unfortunately, to keep the world consistent, you have to store something about it. That can be the entire world, or it can be a seed of some kind, but it has to be stored. Let's say you do store absolute world coordinates. For example, say you generate your world in 100x100 chunks. Each chunk has a position in X and Y; we combine those X and Y positions into a single 32-bit number (X * 2^16 + Y), and pass that as the random seed to your dungeon generator. Of course this isn't a truly infinite playing field, but in my example it's 6.5 million blocks on a side (2^16 * 100), which seems entirely adequate. If you needed more, then you could increase the chunk size (e.g. make the map in 1000x1000 chunks instead, now you have 65 million blocks on a side). Or you could use more than 32 bits to indicate position: 2^32 * 100 is about 430 billion. How much time do you plan to spend on exploring? You mentioned a "tree" approach. Presumably in this method, each sector would lead to the next sector. You'd be saved from having to store world coordinates, but you'd have to remember the "breadcrumbs" that lead from one node to another. For example, you start at node A, then you go to node B, then to node C. You want to backtrack to B, well, B has to remember that it attaches to A. For every node the player visits, you must remember not just the seed to generate that node, but also the connectivities to the other nodes. Now, this isn't much of a memory requirement, but it means you can't make a truly infinite world. It also has another, less pleasant consequence: the world has no loops in it. Each node is generated without knowledge of the structure or placement of other nodes, so they cannot connect (or, if they do connect, the connections are probably not Euclidean). When A was generated, it probably had several outbound connections, but we don't know what nodes those connections go to. When the player traveled down one connection, we said "Okay, this connection goes to B". Then we repeat that with B to get the player to C. Now, C might overlap A -- or it might be nowhere near A. We have no way of knowing, and thus no idea if it's sensible for C to connect to A.
 November 5, 2012, 20:54 #4 master.discord@gmail.com Rookie   Join Date: Nov 2012 Posts: 6 Hmm, perhaps using a noise generator to decide where room candidates might be, then check if they're appropriate, and so on. I *think* if I keep track of the offset from the spawn point, (say the noise grid is 100 tiles square, I just count to 99, rinse and repeat) I could use the character's position as the origin. Or something. :s Beginning to think that C++ is a bad idea this time. It's a great tool but I'm just not schooled enough in all the nuances, and other tools would likely be easier and as effective. (I'm particularly bad at managing memory and pointers, though I can use them when I need to they drive me nuts.) Since I do eventually want to play around with Minecraft mods, maybe Java would be a better option. I dunno. [EDIT] Derakon posted while I was typing. Unfortunately I don't have a deep or broad background in computer science, I've just been playing with it since I was a child messing with LogoWR and making Nibbles in QBasic crap itself. Anyway, I see what you mean about the world, and my example of Minecraft does exhibit the same limitation of EVENTUALLY reaching the limits of the generator. Certainly I didn't mean to imply I wouldn't save the seed, but if the world can be regenerated from the seed in some fashion, I'd rather not store the tile data at all. I did also consider the issue you mentioned with the tree format, and that's part of the reason I thought it might be less than ideal.[/edit] I'm definitely going to keep pounding on this problem, but I've come to the conclusion that I'll need a little more help/experience before I'm really ready to tackle it, so I'm going to start working on the other parts necessary for a playable game, putting in a cheap, file-based mapper while I try to figure it out. I have a general plot and setting figured out - though it's just a version of the cliche "you've been chosen by X, Champion! Go into the dungeon and find baws lewt!" I think it is a little different than what I've seen before. I've also got what I consider to be an interesting mechanic in mind for deaths, experience and equipment. I think I'll start off with turn-based combat, I've always preferred it to button mashing. I also have a mechanic in mind for doors/locks that may be fun and interesting, idk. I've always hated games in which you're blocked by some random wooden door/object, you have a fireball, or a Big Effin Axe but can't remove the obstacle (in one game I was blocked from my desired destination by a simple rope and my BFA was useless). Definitely gonna have door bashing. Last edited by master.discord@gmail.com; November 5, 2012 at 21:04.
 November 5, 2012, 21:05 #5 Nick Vanilla maintainer     Join Date: Apr 2007 Location: Canberra, Australia Age: 57 Posts: 9,367 Donated: \$60 I am doing this for http://nickmcconnell.github.com/Beleriand/ - most of the relevant C code for it is in this file. Essentially, I am using Derakon's world coordinates approach, with seed determined by coordinates (plus some per-game randomness). I keep a big list of all chunks that have been generated. The tricky part comes with how to do the looping thing - if you have to generate a chunk which will be adjacent to one previously generated, how do you make sure they fit together seamlessly? The two approaches I considered wereRegenerate any previously done chunks or Store details of the borders every time you generate a chunk. In the end I went with 2; the problem I saw with 1 is you could get a lot of recursion. __________________ One for the Dark Lord on his dark throne In the Land of Mordor where the Shadows lie.
 November 5, 2012, 21:15 #6 fizzix Prophet   Join Date: Aug 2009 Location: Madison, Wisconsin, US Posts: 3,025 I think you have to do this in chunks. Exploring far enough in one direction generates a new chunk. If you make chunks variable in size, then you can avoid some of the artificial blocking feelings that arise. If you feel a little freely about coordinates you can just have chunks connect to other chunks regardless of whether they actually "fit" on a large map. If you care about coordinates you can fit them in with long connecting corridors. If you want to have a fully scrolling map this all gets a bit tricky, especially around corners where 3-4 chunks may coexist. Of course depending on your approach. If you are ok with moving between chunks with a full screen refresh, you can get away with a lot of geometrical impossibilities. When you create a chunk you need to determine the number of connections between the chunks and what direction they lie relative to others. I would recommend starting with uniform chunks in a grid with a set number of connections between them. Then once you get that working let one of the dimensions (width) be variable but the other constant (or constant for an entire row). Once you get all that working, you can decide whether alternate sizings are necessary or whether this approach is close enough to the illusion you want to create. If you go room by room creation then dungeon structures that aren't trees are difficult to create. You can do it though. When a character goes down an unknown dungeon path it can choose to link up with a previously created but unexplored path. Random intersections and rooms can be placed along the way. You do need to keep track of quite a bit though and I'm not sure how much you actually gain over just creating a somewhat large section to begin with.
 November 5, 2012, 23:18 #7 master.discord@gmail.com Rookie   Join Date: Nov 2012 Posts: 6 More good ideas, and they're most certainly helping to solidify things in my mind. What if I were to generate a large block of noise, using something fast and low-overhead, based on a world seed. That block could be thousands or millions of units per dimension. The value of cel[x][y] would be the seed for chunk[x][y], and would begin to repeat, should the player reach the edge of the noise block. I'd probably have chunks link up like Wang tiles or Herringbone tiles, where each chunk is capable of connecting to other chunks only at certain points (center NSEW edge is what I'm thinking), and is otherwise self-contained. Not quite sure how I'd go about using variable sized chunks, unless they could fit together into larger, uniform chunks. Kinda thinking of a "deep roads" layout now, where there's a single wide highway that proceeds indefinitely in the horizontal axis with a small meander for interest, and other systems branch off of that. Some might be nobly furnished, others might just be caves or mines or even creature burrows. Hopefully discussing it and getting ideas from others will help cement things into something that I can actually build. If at all possible, I want to make this code compact, tight and reliable. It doesn't have to have all the bells and whistles, but it needs not be the War and Peace of map generators.
November 5, 2012, 23:25   #8
Derakon
Prophet

Join Date: Dec 2009
Posts: 9,024
Quote:
 Originally Posted by master.discord@gmail.com What if I were to generate a large block of noise, using something fast and low-overhead, based on a world seed. That block could be thousands or millions of units per dimension. The value of cel[x][y] would be the seed for chunk[x][y], and would begin to repeat, should the player reach the edge of the noise block. I'd probably have chunks link up like Wang tiles or Herringbone tiles, where each chunk is capable of connecting to other chunks only at certain points (center NSEW edge is what I'm thinking), and is otherwise self-contained.
There's no need to generate the large block of noise if you're just going to use it as a further seed. In fact, I believe that feeding the random number generator into itself actually reduces the noise you get (I've read that this is the case, but not read why it happens). Just use (x, y) as the seed for the chunk, as I suggested earlier.

 November 5, 2012, 23:53 #9 master.discord@gmail.com Rookie   Join Date: Nov 2012 Posts: 6 Sorry, I suppose I missed it the first time. Now that you mention it again, that makes perfect sense. No need to multiply randoms together or anything like that, it doesn't help.
November 6, 2012, 21:52   #10
Patashu
Knight

Join Date: Jan 2008
Posts: 526
Quote:
 Originally Posted by Derakon There's no need to generate the large block of noise if you're just going to use it as a further seed. In fact, I believe that feeding the random number generator into itself actually reduces the noise you get (I've read that this is the case, but not read why it happens). Just use (x, y) as the seed for the chunk, as I suggested earlier.
It's because skipping values makes the period of the RNG quicker.

A good case study of what happens when the RNG is called a variable number of times, based on earlier output of the RNG, is the board setting up RNG in Minesweeper: http://www.minesweeper.info/wiki/Board_Cycles
__________________
My Chiptune music, made in Famitracker: http://soundcloud.com/patashu

 Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)
 Thread Tools Display Modes Linear Mode

 Posting Rules You may not post new threads You may not post replies You may not post attachments You may not edit your posts BB code is On Smilies are On [IMG] code is On HTML code is Off Forum Rules
 Forum Jump User Control Panel Private Messages Subscriptions Who's Online Search Forums Forums Home Angband     AAR     Vanilla     Development     ToME     Sil     Variants     Competition The real world     Idle chatter     Oook! Obsolete     v4

 Similar Threads Thread Thread Starter Forum Replies Last Post Hajo Development 2 September 13, 2010 13:40 Derakon Vanilla 4 July 26, 2010 23:40 Hariolor Vanilla 12 May 1, 2010 00:41 Vilbo AAR 8 March 4, 2010 09:49 chris28 Variants 6 June 4, 2008 22:00

All times are GMT +1. The time now is 08:33.

 Contact Us - Angband.oook.cz - Archive - Top