Jump to content
  • Advertisement
NikitaSadkov

Procedural Content Generation

Recommended Posts

Ok. You have random() function, but no idea of how to use it? If you just place map tiles or terrain heights at random, it will result into white noise - an unrealistic and unfun garbage. For example, if you launch some cellular automata with random rules to produce caves in your roguelike, these caves would look unnatural. So to properly generate a video game world, you can't use pure randomness, but need to constrain it by some laws of physics, which will declare what is possible given the context - i.e. you need to have statistics of chances of some world event happening; for example, a chance there will be a lake or a mountain at a given point on the planet. That naturally leads us to stochastic algorithms, like Markov Chains or ANNs.

So to create realistic looking caves, you need an example of real caves layout in a euclidean space (likely broken into some discrete graph nodes, because working with pixels would be hard). Now you train Markov Chains on that space, producing probabilities, that of tunnel going at a given angle, distance, curvature or forking, given the previous state of the tunnel. Now, you can start from cave entrance, and use the random() with probabilities to generating realistically looking cave system.

Similarly you can use ANNs, which will work on more complex context, or just modify the Markov Chains concept to capture more complex data cross-correlation.

There is just no simpler way - random() without probabilities and constraints is useless. You need statistics. You need some real world geology research. Even superficially simpler algorithms, like the one used in Spelunky, still use this concept, but have hardcoded unrealistic constraints.

Share this post


Link to post
Share on other sites
Advertisement

Not a Game Design & Theory topic - see this pinned topic explaining the difference between "design" and "development" - moving you to General and Gameplay Programming. :)

 

You seem to be talking (in very broad high-level terms) about procedural content generation - but I'm not sure why you've actually posted this... did you have a question about procedural content generation?  Or is this meant to be some sort of mini tutorial?

If it's meant to be a tutorial, it would probably be better off as a blog entry or an article rather than a forum topic, but probably needs more detail to actually be useful to anyone. :)

Share this post


Link to post
Share on other sites

Yes, it certainly can be, but it's still unclear why you posted this, and it seems to mostly focus on technical implementation details which (as per the linked explanation) don't generally fall under design.

Share this post


Link to post
Share on other sites
11 minutes ago, jbadams said:

Yes, it certainly can be, but it's still unclear why you posted this, and it seems to mostly focus on technical implementation details which (as per the linked explanation) don't generally fall under design.

Just shared my thoughts on the subject. Maybe someone can point where I'm wrong.

Share this post


Link to post
Share on other sites

You're not wrong, but as I already said, it's such a high level overview that it's not really useful as a tutorial (which would be better suited to an article or blog entry if that's what it's meant to be), and you didn't ask any questions to prompt discussion.

...and once again, we're now having multiple posts "discussing the discussion" rather than anything actually on topic - I'm inclined to just close the topic if it doesn't become useful/relevant.

Share this post


Link to post
Share on other sites

While this thread probably should have been a blog post due to it failing most criteria for posting on a forum (no question, no opportunity for discussion, no 'open' statements).

I'm going to ask a question to your answer...

Given you've stated that random without 'factors' being applied is 'bad', how do you propose to best manage the 'factors'? Maps, std::Vectors, standard arrays?

My approach was/is to create weighted pairs to determine the probability that something was going to spawn/happen, but only where it mattered or that i wanted to apply the weighting...What if there is no true differentiation between objects, 10 items that all equally have the chance to appear, why would Random(10) not be suitable in that case?

From a terrain generation perspective, particularly with 2d tilemap style games, could you just random the existence of particular room types and apply them and then link the 2 neighbors through some similarly randomized aspect?

Finally, How do you propose to handle the 'psudo-random' nature of most random functions?

Edited by Stragen
coherancy mainly... not enough coffee... cat walked over the keyboard... excuse excuse

Share this post


Link to post
Share on other sites

There's plenty of other ways. You can figure out how caves form, and simulate that process, no statistics necessary. Simulate an expanding foam, or the fractal hollowing out of erosion, or perlin noise, or simplex noise, or solidifying lava flows. Doesn't mean extrapolating random caves from some sort of template cave system collected via geological survey is bad. But there are other ways, that have varying amounts of convincing realism. Realism itself can be bad, as most caves in reality have impassable cramped spaces, ugly rubble covering up cool stuff, no gemstones sticking out of the walls, no freaky bioluminescence, no open pools of magma, etc. Guess I'm just saying YMMV. Simulations of existing (cool) cave systems can be a great thing to let people play with.

Share this post


Link to post
Share on other sites
28 minutes ago, cherryphysics said:

There's plenty of other ways. You can figure out how caves form, and simulate that process, no statistics necessary. Simulate an expanding foam, or the fractal hollowing out of erosion, or perlin noise, or simplex noise, or solidifying lava flows. Doesn't mean extrapolating random caves from some sort of template cave system collected via geological survey is bad. But there are other ways, that have varying amounts of convincing realism. Realism itself can be bad, as most caves in reality have impassable cramped spaces, ugly rubble covering up cool stuff, no gemstones sticking out of the walls, no freaky bioluminescence, no open pools of magma, etc. Guess I'm just saying YMMV. Simulations of existing (cool) cave systems can be a great thing to let people play with.

Such approach reminds me of Stephen Wolfram's idea of going from algorithms to phenomena, instead of taking phenomena and going to algorithm from it. In simpler games it may give passable result, if you just want a random environment to shot monsters in. But if you say want to build a realistic city for GTA style game, you will have to delve into civil engineering statistics, about car and pedestrian traffic, average building height, architecture, etc..  Same goes for simulations like Civilization, if you want to have realistic earth.

18 hours ago, Stragen said:

Given you've stated that random without 'factors' being applied is 'bad', how do you propose to best manage the 'factors'? Maps, std::Vectors, standard arrays?

My approach was/is to create weighted pairs to determine the probability that something was going to spawn/happen, but only where it mattered or that i wanted to apply the weighting...What if there is no true differentiation between objects, 10 items that all equally have the chance to appear, why would Random(10) not be suitable in that case?

From a terrain generation perspective, particularly with 2d tilemap style games, could you just random the existence of particular room types and apply them and then link the 2 neighbors through some similarly randomized aspect?

Finally, How do you propose to handle the 'psudo-random' nature of most random functions?

I guess implementation depends on your framework. It will have to fit with other components. But you will have to expose it somehow to game designers and map makers. And possible allow to modify it dynamically. I.e. if your GTA style city undergoes zombie apocalypse with a percent of population turned into zombie.

Regarding pseudo-random, that is a fundamental philosophical question. Some people don't believe in randomness at all. In 1955, RAND was tasked with producing numbers as random as physically possible, resulting into a million of random digits. In more modern times a challenge was established to compress these digits: http://www.drdobbs.com/architecture-and-design/the-million-random-digit-challenge/228701653

The challenge is still open, despite author even promising monetary reward for defeating these RAND engineers of the old. So my guess is that prefix "pseudo" can be meaningless, because all numbers are result of some process, it is just that people know nothing about it and think it is random (in some true divine sense) and start believing that God plays dice.

Share this post


Link to post
Share on other sites
31 minutes ago, NikitaSadkov said:

But if you say want to build a realistic city...

Build a realistic city, you say?

Quote

Some people don't believe in randomness at all.

Well I suppose if you close your eyes, you can pretend that the double slit experiment doesn't produce an interference pattern. But otherwise it's pretty clear that if every outcome were deterministic, the universe would look strikingly different from the way it does.

46 minutes ago, NikitaSadkov said:

So my guess is that prefix "pseudo" can be meaningless, because all numbers are result of some process

What you can do is measure Shannon Entropy which is basically the size of your random data after you compress the f**k out of it. The higher the entropy, the less information exists in your data, whether you know how to decode it or not. Or, that's the theory at least, and there'd be a considerable uproar if people disproved it, since you could decrypt uh... everything.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!