PDA

View Full Version : Procedural world generation - ground and traps seems to not generating.

Darkhog
01-06-2013, 01:13 PM
I've got my terrain generator to working, but bad thing is it seems to not generate ground blocks and spikes even though it should.

Here are functions responsible for generating ground and spike blocks:

function TWorldGenerator._genStepGround(Chunk: TChunk): TChunk;
var chunksize,x,y:Integer;

begin
chunksize:=Length(Chunk);
for x:=0 to chunksize-1 do begin
for y:=1 to chunksize-2 do begin
//we start at Y=1 and end one index before end of chunk as we need to test block before that for being
//air and if there is something under.
if ((Chunk[x][y]=AIRID) and (Chunk[x][y-1]=AIRID) and (Chunk[x][y+1]=GROUNDID))
then Chunk[x][y]:=INVINCIBLEBLOCKID;
end;
end;
result:=Chunk;
end;

function TWorldGenerator._genStepTraps(Chunk: TChunk): TChunk;
var chunksize,x,y:Integer;

begin
chunksize:=Length(Chunk);
for x:=0 to chunksize-1 do begin
for y:=1 to chunksize-2 do begin
//we start at Y=1 and end one index before end of chunk as we need to test block before that for being
//air and if there is something under.
if ((Chunk[x][y]=AIRID) and (Chunk[x][y-1]=AIRID) and ((Chunk[x][y+1]=GROUNDID) or
(Chunk[x][y+1]=INVINCIBLEBLOCKID)) and (Random(101)<TrapChance)) then Chunk[x][y]:=SPIKEID;
//randomizing above is so whole ground won't be in traps.
end;
end;
result:=Chunk;

end;

And here is whole world generation unit (pastebin since it is quite big): http://pastebin.com/fLFjsC8Z

ChunkUtils is simple unit that contains only function that draws circles in chunk (for carving cave - carving step happens before generating blocks and spikes, so that isn't a problem). boolUtils is unit with just one function that checks if value is between two values. Nothing too fancy. Also don't worry about functions that doesn't return values - they're just stubs and aren't implemented yet.

laggyluk
01-06-2013, 01:29 PM
can you explain to me how it works? (because in the process you'll probably find the bug yourself )

Rodrigo Robles
01-06-2013, 01:33 PM
I've got my terrain generator to working, but bad thing is it seems to not generate ground blocks and spikes even though it should.

What exactly goes wrong? It generates in a way you not expected or just not generates anything?

User137
01-06-2013, 01:48 PM
First thing i would do is clarify the program with small change, maybe causing it to speed up in the process. Dynamic array might be reference-based by default, but i don't think it becomes very clear with this:

function TWorldGenerator._genStepGround(Chunk: TChunk): TChunk;
function TWorldGenerator._genStepTraps(Chunk: TChunk): TChunk;
You are passing a big array as parameter, and returning one aswell. You could simply refer to it, apply changes to it directly (because that's what already happens, right?), so:

procedure TWorldGenerator._genStepGround(var Chunk: TChunk);
procedure TWorldGenerator._genStepTraps(var Chunk: TChunk);

These would change too:

_genStepTerrain(Chunk);
_genStepCarve(Chunk);
_genStepGround(Chunk);
_genStepBlocks(Chunk);
_genStepTraps(Chunk);

I'm still pretty "new" to perlin noise, but aren't you supposed to combine many random waves. First ones smooth big ones, then smaller and sharper. From line 99+, you are using same frequency for all of them. Do i just misunderstand the code? :D
Could be the PerlinNoise2d() already does the multi-wave math for you.

Carver413
01-06-2013, 04:13 PM
I'm still pretty "new" to perlin noise, but aren't you supposed to combine many random waves. First ones smooth big ones, then smaller and sharper. From line 99+, you are using same frequency for all of them. Do i just misunderstand the code? :D
Could be the PerlinNoise2d() already does the multi-wave math for you.
it is my understanding that PerlinNoise does all that for you which is why it is so slow to begin with.

SilverWarior
01-06-2013, 05:54 PM
@Darkhog

You can set size of dynamical multidimensional array using SetLenght(array, XDimension, YDimension).
http://stackoverflow.com/questions/5530606/setlength-on-multidimensional-array

Also why not storing chink IDs in nuerical way. So you can have soething like this:
Air = 1, Water = 2 and all ground chunks have ID higher than 2.

So spike placment code would look something like this:

if ((Chunk[x][y]<3) and (Chunk[x][y-1]<3) and (Chunk[x][y+1]>2) and (Random(101)<TrapChance)) then Chunk[x][y]:=SPIKEID;

With this you get rid of yourself of that or statment. And becouse you would probably have multiple ground types in the future you saves yourself the need for checking each posib le ground id in the first place.

I would also split that multicondition if statment of your into several nested if statments. Why? When you are using multiconditional if statment all conditions get checked even if first condition isn't met already. So using nested if statments could speed up your code a bit since it won't be ckecking if other conditions are met, when the first condition has already failed to meet the requirements. Not to mention that such code would be more readable.

Darkhog
01-06-2013, 06:45 PM
can you explain to me how it works? (because in the process you'll probably find the bug yourself )

Sure! First program generates ground using Perlin noise, then it carves cave then it is supposed to place grass tiles (INVINCIBLEBLOCKID) and traps but it doesn't work.

@SilverWarrior: Yeah, I thought so about setting dimensions bu wasn't sure. Will change that bit of code. Also let's say I'd make 2d minecraft (which isn't something I want to do): Grass can only grow on ground, so it is unlikely I'll need to check for other ground tiles, especially in Super Heli Land where it is like 3-4 tiles max.

@User137: Thanks. But that is optimization part. I need first to make my code WORK. After that, I'll do as you say.

User137
01-06-2013, 06:57 PM
When you are using multiconditional if statment all conditions get checked even if first condition isn't met already.
This is not true. I can demonstrate that with simple example:

var sl: TStringList;
begin
sl:=nil;
// Version 1: No errors
if (sl<>nil) and (sl.Add('Test')>0) then exit;

// Version 2: Runtime error
If-statement ends in the (sl<>nil) condition, because any further conditionals wouldn't change the logical end result. If there was OR, instead of AND, then it would have to proceed to next comparison because (sl<>nil)=false.

edit: Have you double/triple-checked the drawing code, or done analyzing to the chunks to see if traps are actually generated, just hidden.

Darkhog
01-06-2013, 09:28 PM
OMG! Found issue. I was using byte for array of TChunk and AIRID was defined by -1. Me and my stupidity... Now it works nicely.

//edit: When I set chunk x/y when generating world to other number than 0, it generates same exact chunk no matter what I do :(.

//edit #2: This is most current version of my world generation class: http://pastebin.com/sPsfNWLD. I've applied optimization fixes suggested by User137 and SilverWarrior, but it is moot point since it generates exact same chunk no matter of what value I put into chunk x/y.

Darkhog
01-06-2013, 09:59 PM
Ok, I've figured what issue was: It turns out that I had to first generate one chunk before generating subsequent ones. I've also found out that ChunkX and ChunkY does nothing. WTH? Problem with chunks not adding up (seams) probably lies in carving step, however I don't know how to fix it.

Problem with ChunkX/ChunkY doing nothing... Well I don't even know what causes it (here's perlin noise unit I'm using, which might be relevant - I didn't wrote it nor I do understand it: http://pastebin.com/CSk62Jdf).

SilverWarior
02-06-2013, 07:13 PM
[QUOTE=Darkhog;95451]@SilverWarrior: Yeah, I thought so about setting dimensions bu wasn't sure. Will change that bit of code. Also let's say I'd make 2d minecraft (which isn't something I want to do): Grass can only grow on ground, so it is unlikely I'll need to check for other ground tiles, especially in Super Heli Land where it is like 3-4 tiles max./QUOTE]

Yes I understand that grass can only grow on land.
But we are talking about gamemap data structure whic would be used in other parts of the game aswell and not only to determine if there should be gras there or not. Si it is good to plan aghead when designing this as you can save yoursel lots of troubles in future.

And now for the reason why your perlin noise algorithm doesn't alows you to generate infinite maps.
If you take a look at its initalization procedure you will see that it uses deafult random number generator algorithm which ships with FPC and this algorithmonly accepts one input parameter (seed number).
If you want to make perlin noise generator which alows making infinite levels you need to integrate different kind of random number generator algorithm into it. This algorithm must be capable of accepting athleast two inputs (Seed number, Offset). As you may recal from one of my previous posts I did some serching for such algorithm in past but hadn't had much luck in finding it.

Carver413
02-06-2013, 10:47 PM
[QUOTE=Darkhog;95451]@SilverWarrior: Yeah, I thought so about setting dimensions bu wasn't sure. Will change that bit of code. Also let's say I'd make 2d minecraft (which isn't something I want to do): Grass can only grow on ground, so it is unlikely I'll need to check for other ground tiles, especially in Super Heli Land where it is like 3-4 tiles max./QUOTE]

Yes I understand that grass can only grow on land.
But we are talking about gamemap data structure whic would be used in other parts of the game aswell and not only to determine if there should be gras there or not. Si it is good to plan aghead when designing this as you can save yoursel lots of troubles in future.

And now for the reason why your perlin noise algorithm doesn't alows you to generate infinite maps.
If you take a look at its initalization procedure you will see that it uses deafult random number generator algorithm which ships with FPC and this algorithmonly accepts one input parameter (seed number).
If you want to make perlin noise generator which alows making infinite levels you need to integrate different kind of random number generator algorithm into it. This algorithm must be capable of accepting athleast two inputs (Seed number, Offset). As you may recal from one of my previous posts I did some serching for such algorithm in past but hadn't had much luck in finding it.

you only need to set the seed once. changing the seed will change everything and you will never get the chunks to match;

for y:=0 to height-1 do begin
for x:=0 to width-1 do begin
vNoise:=PerlinNoise2d(x+vOffsetX,y+vOffsetY,Persis tence,Frequency,Octaves);// Noise is -1 to 1;
vColor:=NoiseToColor(vNoise); //Clamp Color values to MinMax 0,255 because Noise isn't perfect.
Map(x,y):=vColor; //do not use multi dementional arrays for bitmaps must be a single block of memory.
end;
end;

1162

laggyluk
03-06-2013, 12:18 AM
Guess that infinite perlin noise should be calculated on the fly for given coordinates and seed rather than fill the predefined buffer with values (like in implementations i've came across)

Darkhog
03-06-2013, 06:35 AM
[QUOTE=SilverWarior;95468]

you only need to set the seed once. changing the seed will change everything and you will never get the chunks to match;

for y:=0 to height-1 do begin
for x:=0 to width-1 do begin
vNoise:=PerlinNoise2d(x+vOffsetX,y+vOffsetY,Persis tence,Frequency,Octaves);// Noise is -1 to 1;
vColor:=NoiseToColor(vNoise); //Clamp Color values to MinMax 0,255 because Noise isn't perfect.
Map(x,y):=vColor; //do not use multi dementional arrays for bitmaps must be a single block of memory.
end;
end;

Seed is only set once, when creating TWorldGenerator class (which in Create makes TPerlinNoise object and destroys it in Destroy). So perlin itself matches with each other. Problem is that caves don't (_genStepCarving, I think).

you need to integrate different kind of random number generator algorithm into it. This algorithm must be capable of accepting athleast two inputs (Seed number, Offset).

Can you point me to such algorithm?

User137
03-06-2013, 10:53 AM
Can you point me to such algorithm?
This should do the thing:

function Random2(const seed, offset: cardinal): double; overload;
var oldSeed: cardinal;
begin
oldSeed:=randseed; // Save old seed
randseed:=seed+offset; // Shouldn't need to check high(cardinal) ranges.
// Overflowing should still do the math perfectly.
result:=random();
randseed:=oldSeed; // Restore it afterwards,
// So that use of normal Random() outside of this function is not interrupted.
end;

function Random2(const n: cardinal; const seed, offset: cardinal): cardinal; overload;
begin
result:=trunc(Random2(seed, offset)*n);
end;
Edited second Random2() result type.

Darkhog
03-06-2013, 11:08 AM
So this code:

Randseed:= 3;
Num:=Random(30);
Num:=Random(30);
Num:=Random(30);
will behave same as

Num:=Random2(30; 3, 2);

right?

User137
03-06-2013, 11:48 AM
No, Num:=Random2(30, 3, 2); behaves like:

oldSeed:=randseed
randseed:=3+2;
Num:=Random(30);
randseed:=oldSeed;

If you do

Num1:=Random2(30, 3, 0);
Num2:=Random2(30, 3, 0);
Then Num1 = Num2. But if you change offset

Num1:=Random2(30, 3, 0);
Num2:=Random2(30, 3, 1);
Then Num1 and Num2 will differ. But you can always replicate those numbers again with same parameters.

Darkhog
07-06-2013, 11:51 AM
So why following program

program Project1;

{\$mode objfpc}{\$H+}

uses
{\$ENDIF}{\$ENDIF}
Classes, Crt;
{ you can add units after this }
var
num:Integer;
function Random2(const seed, offset: cardinal): double; overload;
var oldSeed: cardinal;
begin
oldSeed:=randseed; // Save old seed
randseed:=seed+offset; // Shouldn't need to check high(cardinal) ranges.
// Overflowing should still do the math perfectly.
result:=random();
randseed:=oldSeed; // Restore it afterwards,
// So that use of normal Random() outside of this function is not interrupted.
end;

function Random2(const n: cardinal; const seed, offset: cardinal): double; overload;
begin
result:=trunc(Random2(seed, offset)*n);
end;
begin
RandSeed:=3;
num:=Random(30);
writeln(num);
num:=Random(30);
writeln(num);
num:=Trunc(Random2(30,3,0));
writeln(num);
num:=Trunc(Random2(30,3,1));
writeln(num);
end.
gives me this output:
16
2
16
29

?

I need random function which will pass test, e.g. with offset of 1 it'll generate same value like second random.

Darkhog
07-06-2013, 12:37 PM
Anyway, I've made it working. Instead of putting circles at random, I've used worm algorithm (dunno if it is known one, I've made it on my own). Basically I'm carving map like worm passing through ground would do.

User137
07-06-2013, 08:05 PM
So why following program
...
gives me this output:
16
2
16
29
There's only 1 explanation that comes to mind, that normal Random() uses other internal variables for the result, not just seed.

I also changed the second function result to cardinal, only the first one was designed to return double. See that it uses Trunc in it, then you used it second time afterwards, which i didn't intend. But this doesn't change the outcome, such thing would seem to need a custom made random algorithm.

edit: No, it's just seed but it can advance the randseed one or 2 times on one call

random := int64((qword(cardinal(genrand_MT19937)) or ((qword(cardinal(genrand_MT19937)) shl 32))) and \$7fffffffffffffff);
genrand_MT19937()-function is used twice in the sentence there. Seems to be well over 99.999% chance for it to call it twice, because chances for first genrand returning 0 is slim.