Jump to content


Recommended Posts

I would like to be pointed to information / resources for creating algorithms like the one illustrated on this blog, which is a subdivision of a polygon (in my case a voronoi cell) into several boxes of varying size:


In the comments a paper by among others the author of the blog can be found, however the only formula listed is about candidate location suitability:


Any language will do, but if examples can be given Javascript is preferred (as it is the language i am currently working with)

A similar question is this one, only the polygon is a rectangle: http://gamedev.stackexchange.com/questions/27055/what-is-an-efficient-packing-algorithm-for-packing-rectangles-into-a-polygon



I also posted this question on Stack Overflow, so if you want upvotes answer there :


Link to comment
Share on other sites

Assuming your Voronoi cells are convex polygons, you should be able to do something like this:

1. Pick a cell

2. Construct two parallel lines through the cell

3. Construct two parallel lines perpendicular to the first two lines where the first two lines intersect the cell

4. You've now inscribed a rectangle in the cell

5. You've also divided the cell into five or fewer pieces

6. Repeat from step 1 for the pieces of the cell that aren't rectangles

7. Stop when the generated rectangles get too small

That'll give you large rectangles in the center of your cells, with smaller rectangles packed around the edges.

Link to comment
Share on other sites

Hmm, that's a very nice way to approach this problem indeed, and far easier than i've been finding :)


I will definately use this if i ever get my game big enough to feature cities! I've for now found a different solution,

i changed the concept of cities to towns and i now have a working basic 'town generator'.


The 'algorithm' works this way:


1. pick a random vertex from all of the voronoi cells

2. check if this vertex has at least 3 outgoing edges that satisfy a length requirement (the edges will become the town streets)

3. designate the random picked vertex as a 'town candidate'.

4. for all 'town candidates', have some requirements to check for and filter for these. (currently i just select randomly for a maximum number of towns :> )

5. populate the town, put houses on each side of the edges (for me this was a shit ton of trigonometry, but still doable apparently haha)


Work in progress screenshots: http://d.pr/f/wJxe


The working version (no preloading, slow, unoptimized, etc. etc.) can be seen here: http://www.powergeek.nl/proj/mongento/versions/9/



As for other people running into the same problem: (also on S.O.)


As i was looking for my problem, it turned out to be a fairly complex one, both measured in difficulty to implement as algorithm, as algorithm complexity.
If anyone is having a similar problem, these problems are classified as 'packing problems' in general, with specific problems like the 'pallet loading problem'.
The problem i was interested in, is illustrated at the bottom of this page:
and a paper about this problem, with algorithm descriptions of how to solve the packing problem for convex polygons and curved shapes:
Some more information on these kinds of problems:
Link to comment
Share on other sites

  • 2 weeks later...

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.
Note: Your post will require moderator approval before it will be visible.

Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.


  • Recently Browsing   0 members

    • No registered users viewing this page.
  • Create New...