• Hey Guest! Ever feel like entering a Game Jam, but the time limit is always too much pressure? We get it... You lead a hectic life and dedicating 3 whole days to make a game just doesn't work for you! So, why not enter the GMC SLOW JAM? Take your time! Kick back and make your game over 4 months! Interested? Then just click here!

Voronoi Algorithm

Rivo

7014
Hi, I'd like to use the Voronoi diagram to generate territories for my game, but looking it up online, im confused as to how I could write this for Game Maker. I would like to first understand how to code one in game maker so I can apply this knowledge to my own project.

So if anyone knows how i could make a voronoi diagram based of randomly placed points. Or, anything at all on this, please let me know. Thanks!
 
P

ph101

Guest
It depends on your experience I think for something like this. In general break down into steps what you want to do and how you want you regions to be stored... I guess, you could iteratively create a set or primitives following whetever implementation of the algorithm you choose.

edit. just saw the link above. Nice.
 
Last edited by a moderator:

Rivo

7014
I've just gotta understand things like >
double, unsigned char, inline, void, fflush etc. :/ ill get there. Thanks for the link.
 
F

farkraj

Guest
double is numeric type variable, any gm variable will work the same.
unsigned char is a single character, in gm you can use string with a single character like "a" for that.
inline you don't need and can't use in gm, it's information for compiler to process the function faster.
void means function returns nothing, thats default state of gm script if you dont specify the return value (i think).
fflush is for stream operations, it forces buffered data to a stream, in gm you can use built in buffers, just read documentation about how to achieve same thing as std streams.

there a couple other things that may seem confusing, you need to read a bit about them and you'll be fine. In gm you dont have to deal with pointers and memory allocation so you have kinda easier job but you lose some flexibility.
 

Juju

Member
The crudest way of performing Voronoi sectioning is to follow the examples on GMLscripts then iterate over the surface to find intersection points using some basic edge detection. surface_getpixel is unfortunately pretty slow, though you may have better luck going via the buffer functions. (Edit: Thinking about it, you can accelerate edge detection by making yourself a shader that does the edge detection in parallel on the GPU, then you come along on the CPU and turn that into actual geometry.)

Delaunay triangulations are the dual of Voronoi diagrams. I solved unconstrained Delaunay last week though I've not looked into translating that into a proper Voronoi diagram (and I likely won't any time soon).
 
H

Harrison Vanderbyl

Guest
i saw an implementation once where you draw a cone from each point using d3d_draw_cone with an orthagonal projection and the depth buffer would only display the color of the closest cone as the closer the cone is the closer in the depth buffer it is
 

Rivo

7014
The crudest way of performing Voronoi sectioning is to follow the examples on GMLscripts then iterate over the surface to find intersection points using some basic edge detection. surface_getpixel is unfortunately pretty slow, though you may have better luck going via the buffer functions. (Edit: Thinking about it, you can accelerate edge detection by making yourself a shader that does the edge detection in parallel on the GPU, then you come along on the CPU and turn that into actual geometry.)

Delaunay triangulations are the dual of Voronoi diagrams. I solved unconstrained Delaunay last week though I've not looked into translating that into a proper Voronoi diagram (and I likely won't any time soon).
Yeah, shaders sounds like a whole other conversation tbh. But in my game I want to make a map using this algorithm just once each new game, so I'm sure hoping having the player wait a few moments for it to generate won't be too much of a hassle (im doing this so each save for the player is different) And since the theme is in space I suppose i can use Delaunay triangulation to connect the stars together (either for appearance or gameplay idk)
 
Last edited:
Top