Procedural Generation Placing Spawner

Hi! I have figured out idea for procedural generation.
I decided to have pre-made tiles of terrain. Than I spawn empties who hold property that refers to the mesh. Once player gets close enaugh to the empty, terrain is spawned, once player goes away, the terrain gets deleted, but empty stays. This would be effecient enaugh. I also think of spawning empties only when player goes close enaugh. However, I have no idea how to position spawner correctly to spawn all around the player. Could somebody help me by kinda telling the algorythm? Thank you!:slight_smile:

Place them in the middle of the tile. Each tile near your camera can be shown, tile outside of that range should be hidden.

It might be easier to use the build-in LOD. You could use a mesh without vertex as last level.

I want it to be randomly procedurally generated. I mean how to place spawner in grid around player like so:

  • = spawned empty
    o = player

+++++
+++++
++o++
+++++
+++++
And so on. All the time and never spawn 2 empties in one place. How do I calculate where to place empty next?

It looks like a grid.

So you can add a constant value to the coordinates.

Be aware, lots of empties eat processing power too.

Hm… Than how to store grid data? Maybe I must use globalDict/pickle/seperate class to save later? I am not sure what is the best. About incrementing coordinates all the time - I’d need lots of spawners(from player to south, from player to north, from player one grid field on east towards south etc.). I think there must be more advanced method(e.g. spiral type movement around player). Is there kinda procedural algorythm? Another thing may be storing coordinates in file. And once player gets close enaugh to those coordinates, place empty and spawn object. That would also give more control over checking near-by objects. Hm… I must think of that:D
P.S. I’ve almost never had problems with processing power. As my GPU latency shows like 80-95% all the time…

Your computer wont have much trouble with having a large number of objects in the scene except if it is trying to render them. So set visible=false rather than deleting and respawning them.

You can add objects in a grid by using an x-y loop.

for x in range(20):
    for y in range(20):
        tile = own . scene.addObject("tile",own,0)
        tile.worldPosition = [x,y,0]

For working on your map you can save the data in an array;

map=[ [0 for y in range(20)] for x in range(20)]

the “0” is your map data, you could use an int or a string or a list or anything there.
Then in the map placer get the data like this;

tile_data=map[x][y]

Separate your model from your view from your control.

The map should be stored internally in some python structure. In cavefly I use a map class:


class Map():
    EMPTY = 0
    WALL = 1
    size = 0
    def __init__(self, size):
        self.map = []
        self.size = size
        for r in range(0, self.size):
            self.map.append([])
            for c in range(0, self.size):
                self.map[r].append([])
                self.map[r][c] = 1

    def get_point(self, x, y):
        if x not in range(0, self.size) or y not in range(0, self.size):
            return self.WALL
        else:
            return self.map[x][y]
        
    def set_point(self, x, y, value):
        if x not in range(0, self.size) or y not in range(0, self.size):
            raise Exception('Trying to access co-ordinate not in map')
        else:
            self.map[x][y] = value
            
    def get_num_neighbours(self, x,y):
        total = 0
        for r in [-1,0,1]:
            for c in [-1,0,1]:
                total += self.get_point(x+r,y+c)
        return total
            
    def __str__(self):
        outstr = ''
        for r in range(0, self.size):
            if r != 0:
                outstr += '
'
            for c in range(0, self.size):
                if self.map[r][c] == self.EMPTY:
                    outstr += '  '
                elif self.map[r][c] == self.WALL:
                    outstr += '[]'
                else:
                    outstr += str(self.map[r][c])
        return outstr

Then, using an algorithm, whatever algorithm you like (cellula automata etc.) you can populate it.

Then you have to convert your map into game objects. To be efficient, you only want the ones around the player.
So lets get the player position:


pos = player.worldPosition
x_pos = int(pos.x)
y_pos = int(pos.y)

What terrain should be visible? Well, only the things around the player. Let’s say we want to load only the tiles exactly adjacant to the player, it:


0 0 0
0 x 0
0 0 0

So we can figure out what each tile should be using our map class:


placed_pieces = set()
placed_pieces.add(place_piece(map.get_point(x_pos, y_pos))) #Should be in a for loop of some sort
placed_pieces.add(place_piece(map.get_point(x_pos+1, y_pos)))
placed_pieces.add(place_piece(map.get_point(x_pos-1, y_pos)))
...

So now we will dynamically place the pieces as the player moves around. We should also remove them as the player moves away.
We can do this something like:


to_remove = old_placed_pieces - placed_pieces
for piece in to_remove:
    remove_piece(to_remove)

And voila, now the pieces will vanish behind the player.

Notice that with this method we never calculate distance to objects! We never explicitly check distances to empties. This is because we can simply look this information up in the map class. We find out what objects to place by looking at the points around the player.

Can you use this same system but with LinV to start preloading asynch?

A ‘loading bubble’ that changes shape (stretching on the forward axis with Speed)

Maybe something like
If the thing local y is less than value adjusted by speed?

Can you gracefully dynamically load a terrain made by a seed?

Made of pre made chunks of course.

Edit: Dynamically move lamps?

I agree with sdfgeoff.

Keeping your model in Python is more flexible than having thousands of empties set in the scene. (And yes it will have impact … at least on scene graph).

This allows you to use procedural model generation on the fly. The alternative is to use large data volumes to store model data. I think the most sufficient method is somewhere in the middle. There is no problem in using both ways.

According to your requirements,

… you have defined following tasks:

A) find tiles that stepped into the camera’s view/range
B) find tiles that leave the camera’s view/range

Both base on the same basic algorithm to find objects within a certain range. With a model in Python you need to perform that on your model.

Lets assume you use a grid based model. You look where your camera is at the model. Then define all tiles that are 10 around x and 10 around y as inside and all others as outside. This way you get a set of in-sight-tiles (model data, not game objects).

To find out what stepped into it, your compare that set with the set from previous check. Everything that was not in the previous set, must be new (A), everything that is not in the new set must have left the range (B).

C) Update your View (Scene) with the changes from model
With the results from A) you go and create new game objects. Each tile should tell you what type to add and where in the scene it should be added.
With the results from B) you go and remove the game object that belongs to a tile.

Hint:
You can do use generated terrain without Python too. But it is complicated too.

OK! You all use interesting methods and I am looking at them and they seem good, but - they all have limit. It is for loop with limited range. There is never generated infinite map. I’ve got a question - would this actually be problem in the game? Especially if I always kinda set map to be around 0,0,0 position(to avoid floating point inaccuracies).

Adrians, I have a script for infinite procedural generation on my notebook at home, but I’m at work. Remind me in something like 9 hours over skype and I’ll send you the file.

Sent from my LG-H440n using Tapatalk

This is no big deal. At a certain distance you can place all objects be an offset (e.g. worldPosition.x +=100BU). But this is a different topic.

Infinite procedural generation is another step again. You then chuck out my map class from above and instead delve into some far heavier math. The thing is that you want it to be the same when you come back to the same point. There is an excellent video made by the creators of No Mans Sky outlining their method for infinite terrain. I can’t find it now, but they essentially do a planet-sized fourier tranform: ie build their planets out of combinations of sine waves.

Fourier transofrms are quite simle really, you add together sine waves of different frequencies and different amplitudes and you can create any repetitive waveform you like. A square wave can be made from sine waves, as can sawtooths and any other scribble you can draw. It allows generation similar to above, except instead of doing a lookup in a map class, you generate the terrain value on the fly using some function of the co-ordinates. Height is easy to understand. So if we want to find the height at point x=3, y=7, you could do:


height = sin(x) + sin(y)

That would be very boring terrain, as it is just endless perfectly aligned mounds. But if we chuck in a couple other waves:


height = sin(x) + sin(y) + 0.8*sin(5x) + 0.5*sin(2y)

Then we can get more interesting terrain.
THe thing is: this is deterministic. Each set of coefficients will result in the exact same terrain every single time.
One disadvantage is that it repeasts based at the fundamental frequency. In the above cases the fundamental frequency is 1, so it repeats every unit. By using fractional numbers to control the amplitudes, the frequency can be made arbitarily large. In the case of no-mans sky, they simply make their fundamental frequency the same size as their planets - which results in 100% seamless non-repeating planets. For whatever you’re trying to do, you’ll simply have to make it large enough teh player will never see the same place twice for several hours walking in a straight line.

Now it doesn’t have to be used only for terrain height. If we treat the generated number as a bitfield, we can use it to place treasure or buildings, or whatever we like. (note that for treasure you have to store the treasures you have picked up so they aren’t replaced when you leave an area and come back).

Now, this heightmap example doesn’t allow for caves. If we want those we have to generate a volume field. We can do that by feeding a varying Z value in and then looking at density to determine if a block should be placed:


density = f(x,y) + k*z
if density > 0.5:
    place block
else:
    don't place plock

This will generate a mostly flat terrain. If we add in a sine wave to our z component we get caves, pockets, floatin mountains etc.
Note that at this point, we are generating voxel data, as such we have to polygonize it - using a method such as marchin cubes or simply placing preset tiles (if you’re lazy like me).

These maps are still finite, but are generated on the fly arbitarily large, by setting a really massive findamental frequency you can add features many many thousands of blender units across with no effort at all. However, a determined player could in theory, reach the edge. To make a truly edgeless world that is fully deterministic, you have to be far far cleverer than me.

Darn it adrians, you’ve got me interested in this now. I may have to stop being theoretical about this and actually try it!

I just use an “Array Modifier” on my terrain tiles, Then I don’t have to spawn anything. The downside is each block of terrain is exactly the same. and has to be spaced on it’s local axis. So I might use several different terrain tiles, along with different trees, rocks, plants, buildings, hills, etc, that also have an array modifier on them wherever possible, to make it look different.

It’s not infinite, or perfect, but it allows me to make a fairly large playing area, at a reduced cost.

Whilst you’re at it, why not write a meshing tool that uses bpy (as module)/a blender instance to generate a mesh (streamed via socket or file) and libload it in? :wink:

With only eight parameters (two of which being coordinates r, phi) you can generate natural looking shapes with relative ease - https://en.wikipedia.org/wiki/Superformula, and extend this to three dimensions by taking the spherical product with another superformula (I think this is how No Man’s Sky does it). There are several algorithms commonly used to generate things like foliage and so on.

Procedural generation really appeals to programmers, as they often need only develop a much smaller set of assets (especially if they use modular asset-creation to further reduce unique asset requirements), at a cost of control and variation.

This is most definitely not a beginner project.

This makes me want to look at a few experiments, myself.

Wow… So I see 2 professional people interested in this topic. sdgeoff, I get your idea well, but I have no idea how to do it in Blender. I think that if you both with aggose77 can figure out something, maybe combine each others ideas, than you can make awesome generator:D Hm… If it wouldn’t be very complex, than I may try to implement it in UPBGE or plugin:D
Good luck! I don’t wanna fold my brain knowing that you can figure this out faster so I will rather learn C++ for UPBGE and make game assets:D

I’d argue (probably not for the first time) against infinite, or even very very large terrain in game.
For a thought experiment it is very interesting, but as a game I don’t think it’s going to be fun or good looking.

When you think of procedural generation there are some downsides:

  • Repetitive features (either because the features are not specific enough, so are too generic and seem repetitive, or because they are specific, but drawn randomly from a limited set of prefabricated assets)
  • bad flow or narrative (without delving too much in to prefabs),
  • overall sameness (an ice planet is all ice, a desert map always desert, though there are variations of desert and ice).

And as you scale up a map you only make these problems worse. That tree you’ve seen 15 times already, this same village, this same group of orcs you just ran in to 15 minutes ago and you’ve been on this ice planet for hours!

The best hand made levels have unique locations (even though they may be made from prefabs or tilesets), they have variation of types (ice planet, but then you go in to a settlement and there is an agro dome inside and suddenly you’re in an artificial jungle), they also have flow and narrative (you move from one scripted encounter to another).

Procedural generation can mimic the good points about hand made maps, as long as you keep it to a limited scale. If there are 15 types of trees, it doesn’t matter because there are only 5 trees in the map. Prefabs can be more spread out over time so you don’t find them all in the same map. You can write gameplay which helps to channel movement and provide narrative. An example would be having a small number of objectives on a map. If you have 10 objectives there are very many ways to move between them but usually you end up following a grid or a spiral pattern. 3 objectives creates a graph with fewer connections, so the action is more focused and hopefully seems more intentional and less random. You can allow agents from one area to interact with another area (reinforcements can be called, monsters might patrol around the map) without worrying about a run away effect where agents from 50 different areas all dogpile the player. Also once you finish a mission, you can move on to another area, ice-planet > interior of building > moonbase > spaceship > etc… creating more variety without having to think about how to procedurally handle seamless transitions.

So it’s better IMHO to create a game with a smaller map size where possible.

  • Find a way to make that more interesting, find ways of blocking the player’s view so you can’t see the whole level at once.
  • Try to locate the objectives (and thus the action) towards the middle of the map to avoid the player running in to the “edge” of the world.
  • Make sure gameplay has natural barriers against progressing too quickly; locked doors, very dangerous areas, objectives that need to be completed in sequence. This will also help to generate narrative.
  • One other thing is to make sure the edge of the world is a natural barrier, if you are inside a building or spaceship that’s easy but for outside maps you need to block movement outside the area with features such as cliffs, rivers, swamps and other impassable terrain (not the plain edge of the map).


Fog of war can also do a lot to make a finite map SEEM infinite.
Here’s what I’m doing with terrain at the moment. On the left you can see the edge of the map, (very ugly and makes the whole world seem smaller) but on the right you can’t, since it is part of the “fog of war”. You just get to a point where you can’t advance any further and it’s not possible to see past the fog. Since all the action is towards the center of the map, that doesn’t really matter. You don’t have any reason to go there.

I am making what’s known as open world crafting survival game(OWCSG). This game genre fits well with procedural generation and is very fun in my opinion. Although this thing is complex, some people are already trying to write this which makes me so excited. Imma look at josip’s results soon and see what he approaches. In my theoritics the terrain generation isn’t difficult. But now I will see it in action:D

Java may be confusing for some of peeps here, however - this resource can be useful. Just noticed it in my subscriptions videos posted few mins ago:D

Thanks for linking that vid! I’ve been trying to start working with OpenGL but I couldn’t find a good tutorial series. I’m going to start working with it now! :slight_smile: