Temple of The Roguelike Forums

Development => Programming => Topic started by: JayPC on August 20, 2010, 09:06:26 AM

Title: Questions on Writing Roguelikes
Post by: JayPC on August 20, 2010, 09:06:26 AM: Hi everybody, Im a mid-experience Programmer, I'm starting to learn about the dungeon generation Process, but implementing the Process from ideas and concepts is proving difficult.

My main language is C# but im starting to wonder if other Languages might be better, mainly because of Mac support(I use both Windows and Linux), C++ was what I was considering, but its the weakest of my knowledge bases. Java I was considering, but I strayed away from java because Java tends to be slower(though if working in just text I should have no issue with speed)

the Game I'm working on needs 2 kinds of Map generation, not only the regular Procedural dungeon generation, but also some kind of Over-world Fractal Map generation. Both of which are harder then they originally appeared.

My end goal is a feel of the map in the 1997 Magic: The Gathering PC Game by MicroProse. Basicly its a Extremely large world map consisting of a bunch of random locations like Cemeteries and Churches, but also small cities, and in any of these you can find the entrance to a Dungeon which increases in depth and difficulty...

Mostly I need help with the implementation of Fractal Terrain Generation and Procedural Dungeon Generation, and any insight on what Language I should use would be wonderful.

Im looking at This for Fractal Generation: http://www.gameprogrammer.com/fractal.html

and this for Dngeon Generation: http://dirkkok.wordpress.com/dungeon-generation-article-series/

this one is a C# implementation of The Jamis Buck Method ive read just about everywhere but is confusing and uses booleans instead of, say, an array of Integers(0 = empty; 1 = floor; 2 = wall; etc.)
Title: Re: Questions on Writing Roguelikes
Post by: Etinarg on August 20, 2010, 09:47:30 AM: You could check out my Roguelike Game Kit. It's in Java, and maybe you can use the dungeon generation methods. There is a classical rooms-and-corridors dungeon generator included and a mines type generator.

It has a wilderness generator, but it is not fractal, and not suitable for particularly large maps, though.

Project page:
http://sourceforge.net/projects/rlgamekit/

Dungeon generator sources:
http://rlgamekit.svn.sourceforge.net/viewvc/rlgamekit/RoguelikeGameKit/trunk/rlgamekit/map/generators/

Wilderness would look like this:

(http://www.funkelwerk.de/data/roguelikegamekit/screens/wilderness_02_t.png)
Click to view full size.
(http://www.funkelwerk.de/data/roguelikegamekit/screens/wilderness_02.png)

Mines like this:

(http://www.funkelwerk.de/data/roguelikegamekit/screens/mines_chance_20_t.png)
Click to view full size.
(http://www.funkelwerk.de/data/roguelikegamekit/screens/mines_chance_20.png)

And the dungeons like this:

(http://www.funkelwerk.de/data/roguelikegamekit/screens/door_demo_t.png)
Click to view full size.
(http://www.funkelwerk.de/data/roguelikegamekit/screens/door_demo.png)

C or C++ look good to me as languages, if you don't want to use Java. Many roguelikes were written in C, and most of them are fairly portable.

Also, I have a collection of dungeon generation ideas in my library, maybe that will help, too:

http://www.funkelwerk.de/library/index.php?n=Library.ProcedurallyGeneratedMaps

That page also has a big links section to more dungeon and map generation ideas.
Title: Re: Questions on Writing Roguelikes
Post by: JayPC on August 20, 2010, 10:59:20 AM: Ill have to read into the Source Java files for the Mines and Dungeons. I learned in Java so that shouldent be too hard to read. Im glad its Documented! haha

as for the Fractal world map Im looking for a Generation similar to that of Dwarf Fortress like: http://i277.photobucket.com/albums/kk78/DrunkenGrognard/world_map-region3-300-1.jpg

Im slowly learning how the Terrain Generation works from that site, interesting technique. im trying to turn it into a Numerical array making a height map im going to need some time to think...

EDIT: Got it now!

Start with 4 corners
Code: [Select]
1 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1
take the 4 corners value average and add a random number in this case 2
Code: [Select]
1 0 0 0 1 0 0 0 0 0 0 0 3 0 0 0 0 0 0 0 1 0 0 0 1
Find the Diamonds center value (the center is found as the half way mark of the line segments of the original corners). in this case the Numbers wrap the Diamonds are 1 3 1 3. the centers become 2 3 4 and 3 because the average is 2 plus a random

Code: [Select]
1 0 2 0 1 0 0 0 0 0 3 0 3 0 4 0 0 0 0 0 1 0 3 0 1

this creates new squares S1233 S2134 S3331 and S3341 then calculate the centers

Code: [Select]
1 0 2 0 1 0 3 0 3 0 3 0 3 0 4 0 4 0 4 0 1 0 3 0 1
and the Diamond again, wrapping the edges
Code: [Select]
1 3 2 3 1 0 3 2 3 0 3 3 3 4 4 3 4 4 4 3 1 3 3 4 1

I like the Concept but I think I can make it more... Universal by ever expanding the formula to fit the width and height of whatever you need im working on a algorithm now.
Title: Re: Questions on Writing Roguelikes
Post by: getter77 on August 20, 2010, 11:46:45 AM: http://dev.largerussiangames.com/projects/show/sharplike

Depending on how progress goes, Sharplike might also be something to keep an eye on since it deals with C#

Also, welcome to Roguetemple JayPC and good luck on your project as it sounds like it'll have an interesting take on things.
Title: Re: Questions on Writing Roguelikes
Post by: ido on August 20, 2010, 12:33:17 PM: Quote from: JayPC on August 20, 2010, 09:06:26 AM
Java I was considering, but I strayed away from java because Java tends to be slower(though if working in just text I should have no issue with speed)

Funny you say so, as java tends to be about 3-4 times faster than c#.
Title: Re: Questions on Writing Roguelikes
Post by: JayPC on August 20, 2010, 01:19:36 PM: Quote from: ido on August 20, 2010, 12:33:17 PM
Quote from: JayPC on August 20, 2010, 09:06:26 AM
Java I was considering, but I strayed away from java because Java tends to be slower(though if working in just text I should have no issue with speed)

Funny you say so, as java tends to be about 3-4 times faster than c#.

I had lots of speed issues with a game I worked on in Java, mostly because of multi threading and using alot of Large List searches. I was considering Java mostly because of the Cross platform compatibility. I just havent used Java in a couple years.

Quote from: getter77 on August 20, 2010, 11:46:45 AM
http://dev.largerussiangames.com/projects/show/sharplike

Depending on how progress goes, Sharplike might also be something to keep an eye on since it deals with C#

Also, welcome to Roguetemple JayPC and good luck on your project as it sounds like it'll have an interesting take on things.

Ill have to look into that, as well haha! I try to change it up when I Design things... My last project died because I dident have the manpower to go where we had intended... we were working with XNA on a 4 player co-op twin stick shooter. hence my affiliation with C#
Title: Re: Questions on Writing Roguelikes
Post by: Slash on August 20, 2010, 02:04:18 PM: Quote from: JayPC on August 20, 2010, 01:19:36 PM
I had lots of speed issues with a game I worked on in Java, mostly because of multi threading and using alot of Large List searches. I was considering Java mostly because of the Cross platform compatibility. I just havent used Java in a couple years.
That looks more like a design issue than a platform issue :)

I have used java for all of my roguelikes without noticeable speed issues (unless there's an Object generation "leak", i.e. millions of objects being instantiated because of a bug).

The heaviest operation on Java is object creation, so you must be careful when creating new objects inside loop constructs I think, and think on reusing instances if possible.

Also, welcome to the temple :)
Title: Re: Questions on Writing Roguelikes
Post by: ido on August 20, 2010, 02:12:16 PM: My experience is the same as Slash's: I've been using java for 8 years now and never had performance issues.

For the record, I routinely code in c# at work and have coded quite a bit in other "fast" languages such as c - as far as I can see other than some pitfalls with swing (which nobody uses for games anyway) java is fast enough for me not to notice any speed difference between it and c.

In fact you'd be hard pressed to find *any* language apart from c and c++ that is faster than java for the vast majority of uses.

C# is most definitely slower than java, even tho it is still orders of magnitude faster than python and ruby.
Title: Re: Questions on Writing Roguelikes
Post by: Xecutor on August 20, 2010, 03:44:16 PM: - I don't like cats!
- You just don't know how to cook them right!

I'm not java developer. But I was taking part in optimization of a program written in java.
In the end the program was slow because of general algorithmic mistakes.
Presense of gc doesn't mean that you don't need to care about memory at all.
In multithreaded environment people tend to use 'synchronized' to much.

IMO there is a lot of algorithm descriptions and even samples for various generators.
Use google :)
Title: Re: Questions on Writing Roguelikes
Post by: JayPC on August 21, 2010, 06:27:12 AM: Quote from: Xecutor on August 20, 2010, 03:44:16 PM
In multithreaded environment people tend to use 'synchronized' to much.

Or not at all hahaha!

Anyway Looks like Ill be returning to my AP Computer Science class from high School, Java seems like a solid choice given everyones input. Now im working with the overworld map, I can create a one dimensional array with the shape I need no problem, but once I go 2d I get all kinds of confsed

for a Single Dimensional array the Formula is:
(Line Segment Point A + Line Segment Point B) / 2 = Center point value C +/- Random amount
Title: Re: Questions on Writing Roguelikes
Post by: Slash on August 21, 2010, 02:55:10 PM: For 2D there are 5 midpoints on each subsquare, the 4 side ones are easy, the middle one can be calculated using the four corners or the 4 mid points, with varying results
Title: Re: Questions on Writing Roguelikes
Post by: JayPC on August 22, 2010, 03:18:00 AM: Quote from: Slash on August 21, 2010, 02:55:10 PM
For 2D there are 5 midpoints on each subsquare, the 4 side ones are easy, the middle one can be calculated using the four corners or the 4 mid points, with varying results

I get that but its Applying it that gets me haha.

I feel like what your trying to say is like:

Code: [Select]
ABC DEF GHI (A+C+G+I)/4=E+Random (A+C)/2=B+Random (A+G)/2=D+Random (C+I)/2=F+Random (G+I)/2=H+Random
which finds the midpoints of the sides and the Center for each 9x9 my peroblem then becomes larger maps, if I handle each 9x9 seperately then I get a Extremely sporadic map. So its a matter of finding a way to start with a large map and work in from the corners hymmmmmmmm
Title: Re: Questions on Writing Roguelikes
Post by: JayPC on August 24, 2010, 10:51:57 AM: So for the Generator is coming Nicely

Code: [Select]
1 Itteration: 5 4 5 4 7 4 5 4 5 2 Iterations: 5 4 4 4 5 4 5 4 5 4 4 4 7 4 4 4 5 4 5 4 5 4 4 4 5 3 Iterations: 5 7 4 6 4 6 4 6 5 6 6 6 6 6 6 7 6 7 4 7 5 7 4 7 5 7 4 7 6 7 7 7 7 7 6 7 4 7 4 7 7 7 4 7 4 7 6 7 7 7 7 7 6 7 4 4 5 4 4 4 5 4 4 4 6 4 6 4 6 4 6 4 5 4 4 4 4 4 4 4 5 4 Iterations: 5 4 7 4 4 4 6 4 4 3 6 3 4 3 6 3 5 3 8 4 7 4 7 4 7 4 7 4 7 4 7 4 8 4 6 4 6 4 6 4 6 4 6 4 6 4 7 4 6 4 7 4 7 4 8 4 8 4 7 4 7 4 8 4 8 4 8 4 4 4 7 4 5 4 7 4 4 4 7 4 5 4 7 4 4 4 8 4 8 4 8 4 8 4 8 4 8 4 8 4 8 4 7 4 6 4 7 7 7 7 7 7 7 7 7 7 6 7 7 7 8 7 8 7 8 7 9 7 9 7 8 7 8 7 8 7 4 7 7 7 4 7 7 7 7 7 7 7 4 7 7 7 4 7 8 7 8 7 8 7 9 7 9 7 4 7 4 7 4 7 7 7 6 7 7 7 7 7 7 7 7 7 7 7 6 7 7 7 3 7 3 7 3 7 3 7 3 7 3 7 3 7 3 7 4 7 4 7 5 7 4 7 4 7 4 7 5 7 4 7 4 7 2 7 2 7 2 7 2 7 2 7 2 7 2 7 2 7 4 7 6 6 4 6 6 6 4 6 6 6 4 6 6 6 4 6 2 6 2 6 2 6 2 6 2 6 2 6 2 6 2 6 5 3 4 3 4 3 4 3 4 3 4 3 4 3 4 3 5
My source may have a logic error somewhere because the first 2 iterations are almost ALWAYS symmetrical Im Rechecking everything now...

T=Trees ~=water .=grass
Code: [Select]
......T....T~~~..T~~~~TT~~TT.......~.....T.....T. ..........~~~~~~..~~...~TT.T....TT............... ........~~.T~~T~~..T.~.~........TT.~............. ..T...~~~~..~.~~.~~.T.~..T...T...............T.T~ .....~..~...~~~~~~~......T.T.T.....T..........T.T .~~.T..~.~...~~~~~~~~~...........T.......T....... ...~...T.~.T.~~~~.~T~..............T.T........... ..~~~....~..~.~.~~~................T..TT........T ..~...~~..~.~~~~.T..T.......T....T............... T~~.TT~......T.~~............~...T............... .~TT....T...T...TT......T...~~~.................. ...........~.~.~~............T.....T....T........ .~.........TTT~~~....T.....T.~...T...........T... ~~~...........~.~.T.....T........T.T............. ~TT...........~..T........T.~.T...T.............. ...............T......~.......~...~..T......T..T. ...........T...~...T.~~..TT..~~...T..............
Im trying to work on a smoothing Algorythim to make the results more consistent.
Code: [Select]
after 1 smoothing pass ......T....~~~~~..~~~TT...T......TT......T..TT... .......T...~~~~~~~~.....T......TTTT........TT.TT. .......~~~.~~~~~~~~....TT....TTTT..........T..TT. ....T...~...~~~~~~~....TT.........T........T...T~ TT.TTT..~...~~~~~~~~~...........TTT.............T ....T...~...~~~~~~~~~.T...........T.............. ....TTT.....~~~~~~~~.T..........TTT.............. ....TTT.....~~~~~~..T...........................T .~..T...TT..~~~~~...T.........T.................. ....TT..TT........T....TTT.T..................... ~.........T.............TTT...................... ...T......TT...~...........T..................... ~~.T......................TT.TT..TT.............. ~.T..............T...TTT.TTT.TTTTT............... .T..........T....T.T.TTT..T.....TTT.............. ...........TTT..TTTT..T...T....TTT............... ...........T...~...T.~~..TT..~~...T.............. after 2 Smoothing Passes ........T..~~~~~~~~~.....T.....TTT........TTTTT.. ......T...~~~~~~~~~~....T......TTT.........TT.TT. .....T.....~~~~~~~~~....T.....TTTT.........TTTTT. ..TTT......~~~~~~~~~~..T........TT.............T~ T..TTT.....~~~~~~~~~~..T.........T..............T ...........~~~~~~~~~..T.........TT............... .....T.....~~~~~~~~..T..........TT............... ............~~~~~~...T..........................T .....TTT.....~~~~...T...TT.TTTTT................. ....TTTTTT........T.....TTTT..TT................. ....T.....T.......T......TTT..TT................. ~..T.......T......T......TT...TT................. ~...........T.....T....TTTT..TTTTT............... ..T.........T....TTTTTTTTTT....TTT............... T...........T....TTTTTTT.TT.....TT............... ...........TT....TT......TT....TT................ ...........T...~...T.~~..TT..~~...T.............. After 3 Smoothing Passes ......T...~~~~~~~~~~....TT.....TTT.........TTTT.. .....TT...~~~~~~~~~~....TT....TTTT.........TTTTT. ....TT....~~~~~~~~~~~...T.....TTTT.........TTTTT. TTTTT.....~~~~~~~~~~~..TT......TTT............TT~ ..........~~~~~~~~~~~..T.......TTT.............TT ..........~~~~~~~~~~..TT.......TTT............... ...........~~~~~~~~...TTT.....TTTT............... ...........~~~~~~~...TTTTTTTTTTTT...............T ............~~~~~...TTTTTTTTTTTT................. .....TTTT.....~~...T....TTTT..TT................. ....T....TT.......TT....TTT...TTT................ ~..T......TT......TT...TTTT...TTT................ ...........T......TTTTTTTTT....TTT............... .TT........TT.....TTTTTTTTT.....TT............... ...........TT.........TTTTT.....TT............... ...........TT..........T.TT....T................. ...........T...~...T.~~..TT..~~...T..............
Title: Re: Questions on Writing Roguelikes
Post by: JayPC on August 26, 2010, 10:50:00 AM: I had the Test Program Write the arrays down with colors so you can see the result more clearly.

http://shadowphantom.webs.com/Results24320111.html
http://shadowphantom.webs.com/Results1779917981.html
http://shadowphantom.webs.com/Results1761624888.html
http://shadowphantom.webs.com/Results1068689589.html