I made a program which creates castles (Part of: /r/proceduralgeneration). This blog post describes how that program works.
My Castle Gallery: http://imgur.com/a/fbaM4
Included Here: Generating the data your program needs in order to create renderable geometry
Not Included here: Creating the renderable geometry. That article has already been written.
1. Create “Structures”
I started by creating “structures”. Each structure was basically a normal convex polygon (square, hexagon, octagon, etc...) and a height. The height was measured in “floors”. The example image above has three hexagons for it’s main structures. The largest has a height of 4 floors. The Medium one has a height of 8 floors, and the smallest one on the top has a height of 12 floors. I then added more structures which intersected the main structures. Some were randomized, some were strategic.
After creating these, I created a list of “Floors”. Each floor has the following data:
Some Technical terms, as they’ll be used in this blog:
This is important because each piece of data for the floors is stored either as a collection of polygons or a collection of paths.
After generating the structures, we begin filling in the data for the floors
2. Basic Data Gathering
For each structure, find the floor representing the roof of that structure. (E.g. for a 2 story building, you’d want the 3rd floor.) Add that structure’s shape to the Exterior Surface polygon collection for that floor. This will later become the pink sections in the example diagram. Also, add that shape (as a path) to that Floor’s collection of Parapet Walls. Remove any walls which are inside of another polygon.
3. Gather data from above
After gathering basic data for all structures, use higher floors to generate data for lower floors. For each floor, we need to determine the Interior Surface (Blue floors in the diagram). To do this, simply look at the floors above. Combine the Exterior and Interior Surface from the floor above and that creates the Interior Surface for the current floor.
We also need to modify the floor’s Exterior Surface because some of it may now be interior, but before we do, we need to set up some walls. We need the outline of the floor above us. You can generate it from the your brand new Interior Surface, or you can combine the previous floor’s External Walls and Parapet Walls. This set of walls (the walls coming down from above) will either be External Walls, or Roof Access Walls. To determine which, test to see which parts are inside the current floor’s (unmodified) Exterior Surface. If the wall is inside the Exterior Surface, then it’s providing roof access. If it’s not, then it’s a regular External Wall.
Since we’re modifying walls, go through the Parapet Walls and cut off any sections which enter the Interior Surface.
After you’ve divided up the wall sections, then you’re free to adjust the Exterior Surface. Subtract the Interior Surface from the Exterior Surface and you’ll be left with only the Exterior portions. NOTE: When subtracting one convex polygon from another convex poly the result can be:
4. Add Interior Walls
At this point, we have a basic Castle shape in place. The Floors (both inside and out), the External Walls, the Roof Access walls, and the Parapets are all done. Now to fill big interior spaces with hallways and rooms. The following is all done on a floor-by-floor basis.
My approach was to add lots of hallways and allow the rooms to exist as the space between the halls. I should note here that I enjoyed this approach, and I’m convinced of it’s merits, but it was the most time consuming and I did wind up cutting some corners due to time constraints. Rather than describe the flawed version I settled for, I’m going to describe how the code should eventually have worked, if I had leisure to polish it. Here’s the data for this process:
* Collision (Polygon(s))
* Walls (Path Collection)
* Doors (Path Collection)
* Hallway Leads (Array of Leads)
* Wall Leads (Array of Leads)
At this point create a several Hallway templates. Design Hallway Templates assuming that the origin comes off of an existing hallway. Add walls which flow forward and do normal hallway things. Add a collision polygon which is larger than the geometry you’ve created. Example Templates:
* Y Fork to two additional hallways
* X Fork to 3 additional hallways
* L Bend Right, and another to the Left
* Small Dead End, with a door on each side
Now create an “Open List” of Hallway Leads; seed the list with a known good value. I manually created a front door on the main level and seeded that level from there. On other floors, you can use two seeds, back to back, in the center of the level. Also create a list of Wall Leads; we’ll need that later. Now loop:
1) Remove a lead from the Open List. This is the “Current Lead”
2) Look through all the Hallway Templates.
a) For each one, check and see if it’s collision poly can go in front of the current lead.
b) If it can, add it to a list of valid candidates
3) Look through the valid candidates, get one with the highest priority. If there’s tie, choose one at random.
4) Insert the Template into the world at the Current Lead’s Location
a) Add the Template’s walls to the world
b) Add it’s Doors to the Floor’s list of doors.
c) Add it’s Hallway Leads to the “Open List” of Hallway Leads
NOTE: This algorithm assumes you can find at least one valid candidate. To ensure this happens do two things. 1) Make sure your collision for most Templates exceeds the actual walls you’re adding. 2) Have at least one tiny template that has no collision, or minimal collision (See Dead End example).
Finally, there are many locations where hallways stop and it’s handy to note that the area on the other end of the stop needs to be split. This is especially handy for the dead end Template and this is what the “Wall Leads” list is for. Simply iterate through the wall leads and locate a valid destination for the wall. My wall leads attempt to connect to other wall leads. If that fails, they look for a solid wall segment to connect to. You can see examples of these along the bottom and right hand side of the example image.
5. Add Windows & Doors
Creating windows and doors is fairly straightforward. I simply iterate through all of the External Walls placing windows then iterate through the Roof Access Walls placing windows and doors.
Placing a portal (a window or door)
For every edge on the given Path, I check to see if the edge is long enough to contain a portal, with a little extra room on each side. If it is, I create a Rectangle just inside the wall and check to see if the rectangle collides with an interior or exterior wall. If it does, I go a little farther down the edge and check again. If it doesn’t I create the portal, then break the path into two pieces. One path stops at the beginning of the portal and one starts again after the portal. I then continue checking the same edge (now in a new path) until the edge no longer has sufficient room to hold a portal. Then continue on to the next edge.
And that’s it. Your program should now have all the data it needs to generate renderable geometry for the entire castle.
Errors? Feedback? Suggestions? Bored? Go Here: WereCoder@AmpletiChao.com