Procedural Generation vs Database Query

[stpinker]

Hello I'm new here.

I checked the forum but couldnt find anything approaching my idea for a new game. Ill let you discover what it is over the next posts.

The reason I started this topic is because I never found a straight answer to my question:

Which one is faster/better ?
   1 - A map pregenerated in a mysql table whereas you squery the visible tiles for the player
   2 - A map generated on the fly where infos are given by procedural generation
   3 - Maybe a mix of the 2


I assume for a small map, say 512x512, then answer 1 would be appropriate. But imagine a map of 65536x65536 that would make the database explode in gigas and probably be frikin slow. Where a well procedurally generated map would only require a few calculations.

So what's you ideas on this problem ?

[133794m3r]

personally, i was going to just put into the database teh nonblank tiles and set them up as maps with each area/zone being it's own table. When someone goes to some place this is then loaded into the array where the values are update accordingly and blank values are just blank.  It loads it and shazam, then when the map is being shown all 0s use whatever the area's ground tile and the rest are loaded and set when they go into the area also. Procedural map generation would be kinda good, but then it'd be harder for the players(if you're talking about just making it completely random) to actually have them be able to get used to an area. But if you did a pseudo-random area with set items that have be there, it'd be kind of ok in and of itself. I personally prefer using pregenerated maps for main areas, simply b/c quest design is simpler for things that require them to go find item x, it'd be simpler to program so to speak. Also, it'd make it better for players to write up guides and share them with others as everyone does it. However, if your'e lookign to try to avoid that at all costs, then procedural mapping would be best.

as far as performance goes, i have no idea really as this is my first venture with a game that wasn't single player. I was just looking at it from a design perspective.

[Chris]

4. AJAX/JS cached map

Personally, for myself I would recommend 2 (but only because I know how to do it and have low expectations about the outcome (actually, for myself I would recommend to drop the whole map althogether and make a game without it which would solve tons of my problems))

Generally, I would recommend 1 (since it is simple and easy and let's face it, if you are new (or old, this is not much difference anyway) the odds are your game will never reach any size that would require performance improvement)

For advanced users I woud recommend 4 (but if you are the one do do it properly you already know about the solution and not need my recommendation )


To clarify what you mean by faster/better. 1 is definitely overall "better" since it is faster in development time terms and the most flexible, 2-4 are faster in performance terms.

[Marek]

If I understand you, you're asking about creating new areas on the fly, and then storing them. And not just generating new random areas every time the player enters them.

There is probably an optimal point of generation time vs lookup time. But if your map is going to be slow once it's all generated, then that's going to be a problem eventually anyway. I think a better question to ask is how to make a scalable, performant map lookup system (which doesn't have an easy answer, either). The question about how to approach generation is just delaying the actual potential performance problem.

As an aside, the 3d exploration game "Noctis" has an interesting approach. Its universe is a galaxy with billions of stars and planets, each one being unique with an explorable surface. The game itself is only a few megabyte, so how can it contain billions of stars? The galaxy is procedurally generated using a preset seed. The game is singleplayer, but it could just as well be multiplayer and not require storing any data about the universe itself, because every player's client has the same seed and can generate the same world from scratch. All billion stars. There's a whole community centered around this game, where players explore stars and put their findings into an online database. And yet the universe is never downloaded or "saved". It just exists, inside a sort of a priori aether.

[stpinker]

If I understand you, you're asking about creating new areas on the fly, and then storing them. And not just generating new random areas every time the player enters them.

There is probably an optimal point of generation time vs lookup time. But if your map is going to be slow once it's all generated, then that's going to be a problem eventually anyway. I think a better question to ask is how to make a scalable, performant map lookup system (which doesn't have an easy answer, either). The question about how to approach generation is just delaying the actual potential performance problem.

As an aside, the 3d exploration game "Noctis" has an interesting approach. Its universe is a galaxy with billions of stars and planets, each one being unique with an explorable surface. The game itself is only a few megabyte, so how can it contain billions of stars? The galaxy is procedurally generated using a preset seed. The game is singleplayer, but it could just as well be multiplayer and not require storing any data about the universe itself, because every player's client has the same seed and can generate the same world from scratch. All billion stars. There's a whole community centered around this game, where players explore stars and put their findings into an online database. And yet the universe is never downloaded or "saved". It just exists, inside a sort of a priori aether.

You understood me correctly. As for Noctis, this is really gettin interresting. I played this game more than needed  and was actually amazed at how vast a simple pg game could be. The author of noctis as abandonned the sequel Noctis V who ( as the screenshots I saw) who'd have been amazing.

As you said the problem arise when you effectively try to "impact" the game and change a few things. That's what makes the difference between a game and a simple simulation where you only observe things. That's mostly what happened to Noctis, the whole game become rapidly a discover and rename game. You cant actually build or destroy things ( Ill start another thread on Build vs Destroy later ... ). Also the star dispersion in Noctis is based on a simple formula of distance from the center. The chance of having a star at one position is only dependant on its distance to the center of the "galaxy".

I circumvented this mostly uniform map to a real galaxy map using polar trigonometry and perlins. A for perfomance it can find the probablity of having a star at point x,y in about 0.001s

If I had ALL stars in a database and I would "SELECT * FROM table WHERE id=f(x,y)" to find if there is a star at this point from a table containing roughly 4billions (65536*65536) stars, wouldnt that take much more time ?

Also how should I actually store the events in a database on each planets so that:
 1 - doesnt take too much memory space
 2 - doesnt take too long to generate and store




As I said the problem is that for billions of planets

[Chris]

Oh, you mean planets. Then there is no brainer, generated map can be done easily (since you do not care about any patterns and all "tiles" are completely independent from each other).

So, the only question is events and planet destruction. Since most planets will be never visited even once, make the default values non database. Once the planet is changed or destroyed then create DB entry. Sort of opposite to natural way of thinking, if something exists you do not have it in DB, but if something does not exist then you have it recorded

Events can be generated only upon visiting the planet.
If planet has not been visited for X days then remove the event fro DB unless permanent event). The counter when planet was visited last time is stored with event (default: never visited).

If I had ALL stars in a database and I would "SELECT * FROM table WHERE id=f(x,y)" to find if there is a star at this point from a table containing roughly 4billions (65536*65536) stars, wouldnt that take much more time ?

It would Index alone (4 bytes) would take 16GB (1GB=1 billion bytes, you need 4x4=16). All this assuming you store only ID, but if you wanted x+y+z (without ID or any indexes) then the table would be 16+16+16=48GB (I assumed they are not tight packed ant there is some space between planets so 4 bytes not 2 per coordinate used). In short, trying it on 32-bit OS would be pointless.

[stpinker]

So, the only question is events and planet destruction. Since most planets will be never visited even once, make the default values non database. Once the planet is changed or destroyed then create DB entry. Sort of opposite to natural way of thinking, if something exists you do not have it in DB, but if something does not exist then you have it recorded

Events can be generated only upon visiting the planet.
If planet has not been visited for X days then remove the event fro DB unless permanent event). The counter when planet was visited last time is stored with event (default: never visited).

That the way I'm thinking going into. Pretty hard since I did not see many development in this area.

The first problem is one of generating coherent random ... you want planets and stuff on it to be different but not completly hazardous. That is kind of the easy part for me. There is plenty of litterature about coherent noise to be able to make such a thing as a galaxy star prob generator who give probs at x,y,z fastly enough.

But the second problem which is also my question ... the amount of events to be recorded ( many events for each planets ) would surpasse the number of planets recorded ?

If say I have 1000k planets possibles, 10% of them have events so 100k needs events logging, they could only have an average of 10 events each before surpassing the planets indexing.


As you said this problem arise when you have many players, this I never experimented, but this kind of system could generate a huge problem at that level if not properly designed at first.


Also there is the problem of permanency ...

What would be considered permanent as an event ? Destruction of a planet ( or star ) ? Couldn't the planet regenerate ( say if we delete the destruction event ) ? Is there such a thing as an event that need to be considered permanent ? Other that the state of the player itself ...
I rather like the idea of having almost no permanent events other that the "starting" matrix. Maybe the timeline could go forward Perlin style!

And for non-permanent events what should be the timeline ... how long before we delete a destruction event ?
I think we need to introduce the idea of regeneration ... just like in good old rpg games.

[Chris]

Check Elite, they made an endless universe for 8bit machines (which means below 64Kb memory usage total and 1MHz CPU speed). You are making things overly complicated.

The first problem is one of generating coherent random ... you want planets and stuff on it to be different but not completly hazardous.

What for? Players will not notice anyway.

If say I have 1000k planets possibles, 10% of them have events so 100k needs events logging, they could only have an average of 10 events each before surpassing the planets indexing.

You can not make 10% of 1 billion, you can not make 1%, you can not make even 0.1%. These are still too huge numbers. Your thoughts are going in the wrong direction.

Couldn't the planet regenerate ( say if we delete the destruction event ) ?

What for? Do you even need events in the first place?


You have basicly a choice. You can either go for small but complex universe or infinite but very simple one. Trying to go for infinite and complex will probably result only in yours (and your server's) misery.

[stpinker]

You have basicly a choice. You can either go for small but complex universe or infinite but very simple one. Trying to go for infinite and complex will probably result only in yours (and your server's) misery.

Thats exactly what I tought for a really really long time. KISS they say, Keep it simple ...

But then I wandered into philosphy,logic,fractals,noise and so on ...
I discovered that most of the pregenerated stuff could be done on the fly from maps to quests in a coherent yet renewable world. The rule is simple: most thing don't need to exists at most time. Yet they need to be there at one time. Thats for infinite.

As for complexity there is interresting results in ether Wolfram's or Wallace's work. Complexity can be generated upon very simple basics.

If we have small generation of an infinite world and simple complexity then we build a line from small and simple to infinite and complex.

I do agree to some part we need a db to serve as a memory, at least to keep the players datas. But I need to find where to draw the line between what needs to be kept for the user and what need to be left to the variations of the virtual world.

[Chris]

If we have small generation of an infinite world and simple complexity then we build a line from small and simple to infinite and complex.

Amusing... You praised "KISS" just a few lines above and then posted that "thing". And you probably do not see anything strange in these two statements coexisting in one post. Split personality to its fullest

[stpinker]

If we have small generation of an infinite world and simple complexity then we build a line from small and simple to infinite and complex.

Amusing... You praised "KISS" just a few lines above and then posted that "thing". And you probably do not see anything strange in these two statements coexisting in one post. Split personality to its fullest

I agree this goes out of the common roads. But I have some nostalgia of the old programming school were you had to do anything with so less code. Probably a big headache to restrain ourselves while building a big thing. But now that memory and speed is freely available it seem lazyness is the same as simplicity. You can have something really simple but yet have given it long enough thinking. Simple is not evident ... its just well simple!

Have a look at perlin noise ... the result is interrestingly complex, while the code is straight simple. You might say well it is kind for graphics, where I say shape it in a galaxy form and you get precise stellar density at any point fastly and nicely. You can also use the same data to get the probability of gas,nebulae, etc ...

I do like to keep the code simple, not the results.

[jannesiera]

Oh, I love this stuff! Only have the feeling that I haven't had enough math yet to really get into building something very sweet...

[stpinker]

Oh, I love this stuff! Only have the feeling that I haven't had enough math yet to really get into building something very sweet...

Funny, I did not too ... failed many calculus classes. But most of this when you put the time in it is simple. For example Perlin noise is simply reverse thinking the way we construct waves signals. You just look around for the nearest random point and curve a bit. Its all about coherency ... bringing order from predeterminated chaos.

I don't think you really need math more than philosophy or at the least logics.

[jannesiera]

Oh, I love this stuff! Only have the feeling that I haven't had enough math yet to really get into building something very sweet...

Funny, I did not too ... failed many calculus classes. But most of this when you put the time in it is simple. For example Perlin noise is simply reverse thinking the way we construct waves signals. You just look around for the nearest random point and curve a bit. Its all about coherency ... bringing order from predeterminated chaos.

I don't think you really need math more than philosophy or at the least logics.

Yeah, that's true, but without that math learning all that stuff will take much more time. Luckily I get much math and physics at school .