Help needed with spawning


(Cody) #1

So recently I’ve been working on a game that involves random spawning but I don’t were to start.
But I would like it to choose a slot and spawn a tree in there🌲


(Pharap) #2

Some more information about the desired end result would be helpful.
For example, are you wanting to spawn in enemies or randomly generate terrain?


(Mike) #3

Well, since you don’t know where to start, let’s go to the beginning. That would be deciding whether or not you want to spawn a new thing, or maybe what thing to spawn. That’s something that will depend on the game, but there are at least three different ways to do that, one that depends on time (something like spawning a new thing every Nth turn, or with a probability of M every turn) or one that depends on space (like Conway’s game of life) or one that depends on a combination of the two. Once you’ve got your rule, if you need help implementing it let us know what it is for help doing that.

And as you hint at, you need a spot to put it. On something with restricted resources like the Arduboy, you typically create a fixed-size array and provide some method of keeping track of which ones are empty. For instance, if your things are relatively dense on the map, you might just make each map entry capable of holding one, and have some value that’s always positive that you set to zero to indicate that that spot is empty. Alternatively, you might create an array that holds the maximum number you can have at one time, the index of the next free spot in the array. When one dies, you swap it with the last one and decrease the index. On the map, you’d store the index or -1 to indicate that the spot is empty.


(Cody) #4

I’m not sure I understood all that sorry?


(Cody) #5

Generate terrain in a sense


(Pharap) #6

Terrain generation and spawning monsters are two very different things, which is why I asked. What you are looking for is known as “terrain generation”, “procedural content generation” or simply “procedural generation”.

If you’re trying to pseudo-randomly generate terrain based on a seed like Minecraft, roguelikes etc do then there are lots of different techniques you can use, but it depends on how your world is structured and what kind of game you want to make.

For example, if you’re making a game set in a series of caves one technique is to randomly place the rooms (making sure they don’t overlap) and then try to connect them with tunnels.

Another approach is called ‘drunkard’s walk’ (or ‘drunkard walk’ or ‘drunk walk’) where you have the world stored as a set of tiles and you generate the tunnels by making the code dig randomly in different directions. (e.g. 1. start with all tiles marked ‘full’, 2. pick a random direction, 3. move in that direction, 4. mark it as ‘empty’, 5. If not cavey enough goto 2)

Basic approaches like those tend to be flawed and produce weird results or not very interesting results though. There are lots of more advanced approaches that give better results, but typically the better the result the more complicated the code behind it has to be. Also there’s usually a lot of maths, trees or decision making involved with more advanced techniques.

Luckily there’s an entire wiki dedicated to listing techniques: Procedural Content Generation Wiki
Unfortunately it doesn’t always give examples of the techniques or explain how to do them, a lot of its articles are just overviews with a handful of external links.

Ultimately whatever technique you want to try you’ll probably have to look at a lot of different websites and experiment quite a bit because there’s no single best answer to generating terrain, a lot of it is trial and error.

A couple of things you might want to look into (although I’ll warn you, some of them can be pretty scary because of the amount of maths):

A Working example:

Different kinds of ‘noise’:


Post Script:

Nothing in nature is truly random, nature is full of patterns like fibonacci numbers. Out of interest, it’s completely possible for two snowflakes to be identical, just staggeringly unlikely.

Also this was incredibly long because I made it as general as possible. It really pays to be specific and give as many details as possible when asking questions.


#7

Randomly generate 2 values X and Y (min: 0, max: 5)

Draw on screen (X * Tree Width + horizontal offset, Y * Tree height + vertical offset)

if you want to choose a slot to spawn just set X and Y manually


(Pharap) #8

The one flaw with that approach is that eventually you get overlapping trees (and you end up finding out exactly just how random the number generator is when you get several clumps of trees instead of trees that are nicely spread out).

But if you just want something very simple and your world is made of objects instead of tiles then yes, that solution will work.


(curly) #9

well a simple way around that is to limmit the number of whateveres

or

if (tree2locx >= (tree1locx) && tree2locx <= (tree1locx + widthOfTree)) { randomly generate another x location for tree 2) }

something like this will check to see if the second tree is being put at the same horizontal location (locx short for location x) as the first tree and if it is or any part of tree would overlap put it in a different x location


(Pharap) #10

The problem with that is that the number of trees you have to check against grows with every tree added.

When you add tree N you have to check N - 1 existing trees for collisions.
e.g. Tree 1 has to check 0 other trees, tree 2 has to check 1 other tree, tree 3 has to check 2 other trees and so on.

If you add 8 trees you have to do 28 collision checks (minimum) in total (it follows the triangle number pattern).

If you get a failed collision you have to generate a new number and do the checks all over again. So say you’ve got 8 trees, the first 6 checks are ok, but the 7th check results in a collision, meaning you have to start again with some new coordinates (which might also fail).

Then there’s the fact that the more trees you add the more likely you are to get collisions (because of the birthday problem and/or pigeonhole principle).


There are other solutions though.

You could start with all your trees arranged in a grid formation, equidistant from each other, and then randomly shift them along the x and y axis slightly (if the shift is small enough you can completely avoid having to check for collisions).

You could have a tile based world and make the tiles random (or obey some sort of algorithm deciding placement), which completely avoids collision checking.

Or you could place trees by picking an existing tree and placing the new tree a random distance in a random direction away from the tree you’re picking. It still involves collision checking (via raycasting), but you can make sure the tree won’t collide when you’re actually selecting the spot for the tree so you don’t have to re-generate any locations. Every time you place a tree you pick the location only once.


(curly) #11

If you went in order per tree each tree would only need to check once and later trees wouldn’t check till the prior was set


(Pharap) #12

Each tree would have to check itself against every other tree to truly know that it wasn’t colliding with any other trees.
You could reduce the number of checks using a binary space partition or a quadtree, but there’s a lot of work involved in maintaining those.

Collision checking will always be a problem for as long as you use an approach where you’re picking a random area and then checking if the area is empty instead of verifying that an area is empty and picking randomly from that area.

In general if you’ve got a small number of trees the simpler approaches work fine, but they don’t scale well.


(curly) #13

I’ve done similar with the Rick and Morty game with @Celinebins each element has a set area it can be in so they can’t overlap anyway


(Cody) #14

this all good but ive already coe up with a system. sorry for not being able to read this stuff like most I offline