13 replies to this topic

[greep]

While I've managed to keep file size down for large world generation in a tile based game, I haven't been able to really manage speed well, and I don't think I can get it any faster. Admittedly if you'd left your computer on overnight you could generate a few hundred worlds, but it is a bit cumbersome. Since I'll eventually sell the game, I need to think about ways to work around this hurdle, or just make the worlds smaller. If it were free I'd just say suck it up and make about 10 worlds while writing an essay or something heh. What do you guys think of the following ways to alleviate the problem?

A) Having the downloadable game or demo start off with two or three pregenerated worlds. This way, you don't have to generate anything to start. Technically this may sometimes be longer than generating the worlds yourself, but I suspect people psychologically would rather a medium download and play immediately then a really short download and find they have to wait a few more minutes to play.

Keeping a database of some worlds on the internet (may do this anyways, as people may like to compare experiences of the same worlds or find and point out unusual worlds)

C) World gen is an entirely separate process and the rest of the game works via much smaller files generated from the world gen. I'm going to guess file writing (the main slowdown it seems) is a ton faster in C++ (haven't used it much TBH), so I'm considering writing a program in C++ that people can use to generate worlds. However, do you think people would find it annoying having to run a separate executable for the game?

And of course, any further ideas would be most welcome.

Edit: Current times: Small world (1.5 min) Standard world (6 minutes, bad!)

Edited by greep, 12 March 2012 - 08:14 AM.

[NicroGames]

Well, your game seems interesting, so I probably wouldn't mind a litte long level generation, but I think it would be a good idea to have 1 pre-generated level or something like that. The size of the levels also matters, so it's hard to give a perfect advice for your game.

Edited by NicroGames, 11 March 2012 - 08:54 AM.

[greep]

Well maybe knowing a little more will help then. Basically, if I can fix the following mini problem, I won't even have to worry about this, but I can't see how.

So, there's 4 world sizes currently, 10x10, 20x20, 30x30, and 40x40 "rooms files", each room being 180x180 tiles. The smallest takes ~1.5 minutes, which is perfectly acceptable. However, the world is divided up into "governments". Each has a 10x10 block. So 20x20, which has 4 governments results in a far more balanced world since you actually get some interaction between them. It's not completely necessary to have ultiple governments, the game is from the viewpoint of just one person, but it adds a lot to the game. However, as you can see it would take an entire 6 minutes for a 20x20 grid. Not a problem for people like me, but I can see that as a major turnoff for some.

I'd like to make the government blocks smaller or less "symmetric" so I could work with a 2-3 government world being the standard or something, but I just don't know how to do it. Thankfully the "world grid" info takes less than a second on even the colossal 40x40, and this is where governments/cities/forest/ blah blah is designed. It's the individual rooms, specifically individual tiles, that make up the time for world gen. So processing time certainly isn't a factor if I want to found some way of splitting up, say, a 15x15 grid into 2-3 governments, I just don't know how to do it.

Cities are sorta like fallout 1: Small cities have a single living district room on the world grid, larger ones have a living district immediately adjacent to a market, capitals have those two and a capital district. Currently, there's one capital, and about 4-5 other cities per 10x10 block. They need to be decently spaced out, so I couldn't just decide to make gov blocks 8x8 squares, 10x10 was the smallest I could cram the cities into without them looking too close.

Edited by greep, 11 March 2012 - 09:49 AM.

[Znyx]

Im also making a game which have world generation and i had the same problem as you, the world would take very long to generate. To solve this i rewrote pretty much the whole engine to instead of using tiles, save the generation to an array and then as you play the game will read from the array on what tiles/object that it will created in the players view area. This increased world generation time, from around 2 min to 20 seconds, which isent too bad as the world size is 24576x24576. Might not be the best solution but it works for my needs!

[PetzI]

You didn't actually say how long it takes for a world to be generated. Also, will the game need to generate worlds very often?

Edited by PetzI, 11 March 2012 - 12:18 PM.

[greep]

Im also making a game which have world generation and i had the same problem as you, the world would take very long to generate. To solve this i rewrote pretty much the whole engine to instead of using tiles, save the generation to an array and then as you play the game will read from the array on what tiles/object that it will created in the players view area. This increased world generation time, from around 2 min to 20 seconds, which isent too bad as the world size is 24576x24576. Might not be the best solution but it works for my needs!

That's actually what I'm using heh. Maybe I should try running this on a desktop, it could just be this laptop is slow.

To Petzi: the world gen times are in the second post, maybe I should update the OP really quick.

Edit: As far as how often, it's sort of mixed. I'm probably going to have a perma-death mode, in which case yes it would be kinda often. Otherwise, no it will be incredibly unoften as each player has a rather lengthy lifespan.

Edited by greep, 11 March 2012 - 07:58 PM.

[PetzI]

Sorry, I hadn't read the whole thread.

So what if you tried to generate the world while the game is running? Have the player wait while you generate the starting area, then maybe you could generate the rest of it while he's playing on that part of the map. You'd probably have to slow down the process, so you can run the game AND generate the world at the same time, but it might be feasible. Unless the player's starting area depends on the rest of the world.

[greep]

Well that's not too bad an idea, but I'd have to use seeding if I want it to generate the same way. And if I use seeding (still not sure exactly as to the process), it'd probably take a lot longer to generate tiles since you'd need to make a bunch of functions to ensure a decently random number based on the seed number.

Edit: The only other way would be to disallow saving for the first 10 minutes, but that sounds pretty lame.

Edited by greep, 11 March 2012 - 08:24 PM.

[LuminousBlack]

Well, I think this is a well-investigated area already, and you can surely find a lot of open-source engines and algorithms decomposed step-by-step on the Internet.
So all I will do is outline the essentials of tiled world-generation.

First, don't concern yourself with speed. Put more effort into how you put your generator together, make it modular -- then you can optimize each part at a later date. Don't make it perfect, make some crappy parts at first which gets the job done, and then replace them later on.

So why do you want to have a world-generator to begin with? What inspired you about it?

You will learn a great deal more if you are inspired! You will have a lot more fun and be able to progress, if you see interesting challenges instead of problems (slow map-generation, dealing with complex and confusing code, and so on).

So to break things down: ask yourself at what granularity you want your generator to work at. Granularity applied to 2D pattern generation would mean: what size of blocks that the generator works with. What size of blocks it manipulates; like taking a certain pre-made 8*8 block and turning it and adding noise to it.

You may decide to create different generators for the different granularities, like having a generator which only produces 8*8 blocks, which are all unique (like eigenfaces (Google it!)), and then having another generator for placing and combining these indexed blocks in the array.

If you think hard about the high-level design of the system, you will save a lot of time down the road.
If you get stuck: get back to the basics! Always remember that it's about 2D pattern generation, and there are a thousand different ways to go about it!
I suggest you keep the world small to begin with, and expand it when you've experimented for a while.

Get a small notebook, which you keep with you, like one with just blank drawing paper, and write down algorithms that comes to you, and make drawings to clarify how you want it to work.

You can have a lot of fun with this! I promise!

[greep]

Well, I think this is a well-investigated area already, and you can surely find a lot of open-source engines and algorithms decomposed step-by-step on the Internet.
So all I will do is outline the essentials of tiled world-generation.

First, don't concern yourself with speed. Put more effort into how you put your generator together, make it modular -- then you can optimize each part at a later date. Don't make it perfect, make some crappy parts at first which gets the job done, and then replace them later on.

So why do you want to have a world-generator to begin with? What inspired you about it?

You will learn a great deal more if you are inspired! You will have a lot more fun and be able to progress, if you see interesting challenges instead of problems (slow map-generation, dealing with complex and confusing code, and so on).

So to break things down: ask yourself at what granularity you want your generator to work at. Granularity applied to 2D pattern generation would mean: what size of blocks that the generator works with. What size of blocks it manipulates; like taking a certain pre-made 8*8 block and turning it and adding noise to it.

You may decide to create different generators for the different granularities, like having a generator which only produces 8*8 blocks, which are all unique (like eigenfaces (Google it!)), and then having another generator for placing and combining these indexed blocks in the array.

If you think hard about the high-level design of the system, you will save a lot of time down the road.
If you get stuck: get back to the basics! Always remember that it's about 2D pattern generation, and there are a thousand different ways to go about it!
I suggest you keep the world small to begin with, and expand it when you've experimented for a while.

Get a small notebook, which you keep with you, like one with just blank drawing paper, and write down algorithms that comes to you, and make drawings to clarify how you want it to work.

You can have a lot of fun with this! I promise!

Well, it's not so much the algorithm as speed of file writing. Fact of the matter is, if it takes X nanoseconds to write a byte to a file, it's not going to improve no matter what you do, save switching languages And don't worry, I am heavily inspired and hardly view this as an insurmountable problem.

Edit: Hmm.. oh you're saying I should design the "tiles" as numbered premade blocks and save them that way. Yeah doing that would certainly cut down time a lot. I'd mean crazy amounts of work, though since I have zillions of tile combinations. Thankfully, I can worry about this later, then, just so long as there's options. Also, then I would have to worry about what happens when the tiles change. Would I do world gen files one way, and then room save/load another when I need specific tile info?

Edit: Heh eigenfaces. As entertaining as using stuff from linear algebra is, I think that's a little too complicated for me.

What I'm doing currently for each world is sort of like dwarf fortress: Each world tile has a forest grade, a boolean for each present grass type, and other grades like rockiness. This makes for a realistic looking world, since I start at a dense grade and spread them out. If I go with pre-made blocks, this is going to be a difficult task, since I want the tiles in the room to be represented by their grade (i.e. a 9/9 forest 2/4 rockiness room should have lots of tress and some boulders). The only way I could think of to do it is to literally have like 20 blocks for each grade combination ("9 forest 1 grass A 1 Grass B 4 rocky", "9 forest 1 grass A 1 grass B 3 rocky", "9 forest 1 grass A 1 grass B 2 rocky" etc) which wouldn't really work because there's billions of combinations.

Edit: heh, okay this is a lot of reflection, but I think it's better brainstorming here than on a paper since I can get feedback. I'm not worried about people stealing ideas since World Gen is hardly going to be the most original part of the game. It may even be a non-issue if GM Studio improves the speed of basic things like file writing. So, anyways, I suppose I could save the rockiness/dirt/grass parts as separate grid pieces. Maybe do the rockiness as 10x10 patterns, and he grass and dirt as sort of "splashes" saved as a coordinate and a radius. But here's another problem: there's basically two tiles for every tile, and the second tile (the "top tile" like trees and plants) is based on the bottom tile, so it gets even more complicated saving the top tiles if the bottom tiles aren't saved as individual tiles.

I think for now I'll just do my normal map design and worry about this later lol

Edit: Shoot, not sure if there's some NDA I missed with gm studio (I doubt an open beta would have one), so I'll be vague. But GM studio is fast enough for me not to worry at all about this anymore.

Edited by greep, 12 March 2012 - 09:27 AM.

[Yal]

This makes for a realistic looking world, since I start at a dense grade and spread them out. If I go with pre-made blocks, this is going to be a difficult task, since I want the tiles in the room to be represented by their grade

That depends on what you save in such a "block", really. You could go to a really abstract level and say that each tile in the 8x8 block is either "field", "corridor", "dead end", "ambush", "block gate", "town site", "dungeon entrance" and so on, and then you generate the actual tiles using some algorithm that takes into account what the sub-block is on the abstract level. For instance a dead end must have "wall" tiles placed to obscure at least 3 of the edges completely.

Also, I think you could muster up lots of speed by doing all the computations first, THEN save them to a file. If you're using text files, you can turn a series of numbers into a string with newlines in it, and then save it to the file. The newline characters will be added properly, so you end up with a multiline file like, say, this:

0
1
6
2
1
0
0
0
0
0
1
2
2
3
3
3
1
1
4
5

I'm pretty sure batch-writing a 100-line string to the file will be loads faster than writing 100 one-character strings and 100 newlines separatedly.

[greep]

I do do the computations first Well for the numbers, I've just been doing binary files and skipping stuff like newlines altogether. Since I load the tiles in order, I can save a lot of time be just loading them in the same order I save and not worry about newlines. What I meant about the whole grade approach is that I don't want you to run to the edge if a "room" and suddenly view the edge of the next room as this weird line of dense trees. With the grade system, I can have the current room have "some" trees and the next have "a little more" so the "line" is there but barely noticeable.

But like I said, with the increased speed I'm not too worried to have to end up doing granulation. It's at the lower end of acceptable, but definitely fine, especially with the multi-worldgen.

Edited by greep, 20 March 2012 - 06:39 PM.

[ND4SPD]

There are .dlls that speed up file operations? Try one of those, perhaps.

[greep]

Ooo I'll check that out