Random World Generator

Hi,

Thats a screenshot



http://picasaweb.google.it/marco.servetto/JmeData/photo#5188678567606301842



and a video



http://it.youtube.com/watch?v=4KjP8YsQG20



Look and than read after.



So what is special?

Graphic is good but non exceptional, frame rate is not exceptional…

but that was not the focus of my attention:



The objective was to generate random maps.

so what means random here? that is how much it is random?

Well:



The position (and rotation and scale) of trees and grass is random, :wink: (ok not difficult i jus use an algorithm of bacteria expansions.

The shape of the mountains is random. XD

The path of the road is random :-o

The river is random }:-@

The shape of the leaves of the trees is random :?

The shape of the rocks is random  :D(yes, I dinamically generate the geometry for all the rocks…)



I will share the code as soon as I finish to clean it,

but If there is enought interest in the community for this project, I could try to write a little guide to use and customize it.

Some help to write this will be very appreciated.

So, give me some feed back!

Hello!



You've done an impressing 3D stuff! I remember you sending me a patch for jcrpg. Wow, I'm impressed how you managed this random thingy. While I'm doing a hash based thingy currently in jcrpg, this sounds a better method for some of my generations too. I will read about things like this algorithm, next iteration of jcrpg will need such cool ideas… and your world's displayed so fluently, your 3d code must be well done too. Congrats!



cheers,

Paul

1 question of mine: is your world generated on the fly or stored in files for loading?



Do you plan to add shadows - and what kind of shadow implementation if so?

Nice looking vid

Awesome, randomness ftw!  :smiley:

How does the "shape of the leaves" thing work? Do you pregenerate the textures? How do you shape the rocks? Can you sketch out or name the algorithms behind all this? Or is there (or will there be) a paper about the project?

hevee said:

Awesome, randomness ftw!  :D

The base of "ALL" is the bacterical expansions, that is in fiew word:


take a matrix of null, put some seeds, and than
while(lots)
  (x,y)=randomPointOn(matrix);
  if(matrix[x][y]!=null)
    make the points near x,y equal to matrix[x][y]



ok, there are lots of criterion and variation about what is the meaning of
  "put some seeds"
and
  "the points near x,y"
but i'm sure you get the idea

hevee said:

How does the "shape of the leaves" thing work? Do you pregenerate the textures?

I have writed a simple algorithm that compose an image from other, something like


m=new MyImage(x,y)
m.sum(image1,pos,rot,scale);
m.sum(image2,pos,rot,scale);
m.sum(image3,pos,rot,scale);


whith this and 6 leaves I put a seed on the center of a matrix, i expand it (so i obtain a irregular shape like a circle) and I put a random leaves in any point of the shape.

hevee said:

How do you shape the rocks? Can you sketch out or name the algorithms behind all this? Or is there (or will there be) a paper about the project?

Ok, that is the most difficoult part. (except the river)
There are tree main step:
I generate a random shape like for the leaves
I convert it in a polygon
I symplyfy the shape of the polygon
Then i have written a class ClosedFlatPolygon that admit me several operation like
triangulate the polygon
connect two polygon
deform polygon
and using this base operation i obtain roks,
infact the stuff is quite powerfull, and I will use it in the future to make random walls, and so on...


There is no a paper on it.
But I'm a researcher, so it could be interesting to write one paper on it, but, you realy thing that there is something with the value of a publication inside here?
Naelh8 said:

you realy thing that there is something with the value of a publication inside here?


Let me answer that by quoting you :)
Naelh8 said:

I generate a random shape like for the leaves
I convert it in a polygon
I symplyfy the shape of the polygon
Then i have written a class ClosedFlatPolygon that admit me several operation like
triangulate the polygon
connect two polygon
deform polygon
and using this base operation i obtain roks,
infact the stuff is quite powerfull, and I will use it in the future to make random walls, and so on...

I think that's plenty of stuff that would make for a very interesting read! Esp. with the outlook of making other, not rock-shaped geometry as well. I can already see somebody (me? :D) scribbling up the Blender plugins to generate rocks, trees, houses and whatever else...
But I am not up to date in what's new in geometry generation research these days. Maybe this all exists already, and I just don't know where to look for it.

Well I for one am interested of how you dynamically created the leaves textures…



Relly cool stuff all round

Umm, I have writed it without looking too much around, just because I was seeing the way to code it.



One of the most difficoult task was to convert a polygon from a discrete representation on a booealn matrix to a vectorial rapresentation.

But I "hope" that it was not something considered "computationally impossible" before now.



To triangulate the non convex polygon I use an ear elimination tecnique (that is take three consegutive point on the polygon such that the triangle is inside the shape and erase it)



It seams that my ClosedFlatPolygon is intrest for us, so I will release it as soon as possible.

But we now, nothing that involve only one man is going to be maintained, so if you want to help me in this part, it will be great!


Mindgamer said:

Well I for one am interested of how you dynamically created the leaves textures...

Relly cool stuff all round


http://www.jmonkeyengine.com/jmeforum/index.php?topic=7116.msg56225#msg56225

Here I was posting the code for merging images, if it is what you was interest in.
If your interest is in bacteria expanding, just wait a little bit, I'm going to clean the code to can post it.

I have done some other screens



http://picasaweb.google.it/marco.servetto/JmeData/photo#5188732752913708194

(lakes)



http://picasaweb.google.it/marco.servetto/JmeData/photo#5188732757208675506

(lakes)



http://picasaweb.google.it/marco.servetto/JmeData/photo#5188732761503642818

(forests)



:slight_smile:

Neat! :slight_smile:

Impressed ! ! !  If you are a lot into randomness, is a "random behaviour" AI doable ?

orelero said:

Impressed ! ! !  If you are a lot into randomness, is a "random behaviour" AI doable ?

depending of what is behaviour and AI for you , yes is possible, the standar tecnique for what I know is to write something like 10 different IAs and than define some moment in witch the "personality" is random swapped.

Ok  :slight_smile: Also can you use the bacteria algo to generate "human" constructions like villages or bridges ?

Really promising and good looking. One question, though… When you say your paths are randomly generated you mean that you go and change the geometry to flatten it and do some splatting on it?.. and the same goes for rivers? (except not with splatting, obviously)



Finally, are you creating with paged terrains? and what is your scene graph structure? Quad tree?

timong said:

You've done an impressing 3D stuff! I remember you sending me a patch for jcrpg. Wow, I'm impressed how you managed this random thingy.

Ah, you are the developer of jcrpg, I have to thanks you lots, reading your code was a good introduction for JME, and peraphs, ekem, some texture that I'm using are still from your project....


timong said:

While I'm doing a hash based thingy currently in jcrpg, this sounds a better method for some of my generations too.

what do you mean with hash based thing?


timong said:

I will read about things like this algorithm, next iteration of jcrpg will need such cool ideas... and your world's displayed so fluently, your 3d code must be well done too. Congrats!
1 question of mine: is your world generated on the fly or stored in files for loading?

It is all generated on the fly. The generation tooks someting like 20 seconds, but I hope to can reach 10 with some optimization I'm working on.
Peraphs being all random remove any chances of store files.

BTW, I think you should think about saving your generated world because, in the end, the loading time should be reduced in the final game as a courtesy to the player.  :wink:

duenez said:

Really promising and good looking. One question, though... When you say your paths are randomly generated you mean that you go and change the geometry to flatten it and do some splatting on it?... and the same goes for rivers? (except not with splatting, obviously)

Yes
roads and river generation is in 3 phases
draw the road/river shape
modify the heigth map in a way that support road/river
dinamically generate the Image with the alpha for the splatting (and than continue like testIsland).


duenez said:

Finally, are you creating with paged terrains?

Yes I use a terrain page.

duenez said:

and what is your scene graph structure? Quad tree?

Umm this is more hard to explane.
I have a parametric optimization strategy, that is i have an  Optimizator to wich I add Models.
a Model is a TriMesh+ Set<RenderState>
at the end I ask to the Optimizator, that can do (teorically) various things.
Principally it do geometry istancing with some criteria.
duenez said:

BTW, I think you should think about saving your generated world because, in the end, the loading time should be reduced in the final game as a courtesy to the player.  ;)

At the opposite,
The game that I want to create is all about random maps,
That is make a room of players and create an unique map every time.
It is going to be something more similar to Quake respect to WOW.
Do you know GUNZ?