LÖVE

A bunch of libraries for various forms of procedural generation, including lots of methods for subdividing a plane.



The eventual goal of the library is to become a goto, for resources pertaining to the creation of procedural content generation algorithms.

The license is extremely dismissive, so feel free to look at, copy and learn from the code. This project is a way to spread the joy of procedural generation.

Currently the library contains:

• Voronoi: By using Fortune's Algorithm, it is possible to quickly and easily generate a voronoi tessellation of a space with any set of points. See the voronoi module.
  Binary Space Partioning: A technique usually used for storing points, it can be used for dividing a space into interestingly formed areas. See the bsp module.
  Random Points: Module for generating a large number of points, with different noise frequencies. Allows generating within any arbitrary polygon. See the points module.

Click here for download, source, examples, and documentation

Not bad. I think through profiling, the speed could be improved further.
Probably doesn't need to optimized at all if it's used strictly for map generation.

There are some trivial optimizations that can be done, like

(arc.p.x^2+(arc.p.y-point.y)^2-point.x^2)/(2*arc.p.x-2*point.x)

Could become:

local ap = arc.p
(ap.x^2+(ap.y-point.y)^2-point.x^2)/(2*ap.x-2*point.x)

Better yet, you could avoid using "point" objects altogether or at least manage them in a pool.

Robustness is another factor that should be considered,
but I'm not qualified enough to comment there.

Good start though.

I think those types of optimizations are trivial in more ways than one. They are really only useful when looking at a often used variable, but become insignificant when dealing with variables that are only used a few times.

ivan wrote: Better yet, you could avoid using "point" objects altogether or at least manage them in a pool.

It was my plan to eventually implement my own heap to distribute with the library. I haven't really looked into how heaps function yet, but hopefully it would be possible to implement one with optimizations specific to the library, including storing the points in a pool instead of having point objects, but that would raise the question of how to store events.

ivan wrote: Robustness is another factor that should be considered.

In what way?

Now that the library is capable of finding the faces of the graphs, I find it somewhat complete.
Bugs and other issues will of course be ironed out, as they appear, but I am very satisfied with the library as it appears now, and will begin working on the project for which this code was originally meant.
Cheers

Heads up - there seems to be some buggyness with voronoi.find_faces_from_edges( edges ) - it will sometimes generate cells that have a very large number of nodes ( >40), and which cause problems. It would be nice if this was fixed - I don't have the code chops to do it in a neat way, my method of generating faces from lines is extremely slow (involves walking the lines and checking angles)

deströyer wrote:Heads up - there seems to be some buggyness with voronoi.find_faces_from_edges( edges )

Yeah, I've noticed that, and am working on it. I'm not entirely sure how to fix it yet.
Say, would it be possible for you to share your version? It would really help in generating correctness tests.

Sure, man!
https://www.dropbox.com/s/n3ft0m1ideck9 ... 1.zip?dl=0

It's pretty gross I'm afraid, it was never intended to be looked at by anyone else, but I have set it up so you can switch between my solution and the voronoi.find_faces_from_edges() approach.

hit "a" to use my approach, or "v" to use the one from voronoi.lua (you can rerun them simply by hitting the button again). There is no debug printing, you can just add that in where you need to, but it will show whatever cell and lines it thinks are closest to where the mouse is. When using the voronoi.lua algorithm, keep an eye on the cells that get the same color and that are missing their cell ID (usually printed at the centroid)

You *should* only need to fix the voroni.find_faces_from_edges()-function to get a correct result in this setup.

Good luck! My approach is not very efficient, but it has been accurate so far with my testing, so I think it can be used to check for correctness. Let me know if you have any questions about how this thing is set up - but like I said, you should only really need to fiddle with voronoi.find_faces_from_edges()

Thanks for the help! I've now got an accurate implementation.
I decided that I couldn't save my own code, so I took your algorithm and stripped all the OOP, did some optimization and changed the interface. It's a bit faster now, and fits in 150 lines of code.
Now find_faces_from_edges requires the original points to find the faces, which isn't ideal, but still much better than non-working code.

Now to improve the other areas of the library...

Awesome, now we can all pile in and procedurally generate terrain!

http://www-cs-students.stanford.edu/~am ... eneration/

That was the article to introduce me to voronoi graphs some years back. Great stuff.