Rule Design – More Complex Grid Parks

Recursion in Grid Parks

Grid rule can be used recursively to implement more elaborate results.

  • PathWidth = 2
  • Region -> Grid(3 {2, 6, 2} , 2 {6} ) { NestedRegion } { CementPath }
  • NestedRegion -> Grid { TreeRegion } { StonePath }

First of all we set the path width to 2m. First of all we create a grid with 2/6/2 meter long along x axis and 6 meter long along y (or z) axis.

The path can be changed wen supplied as the second structure (second expression in the curly braces).

When the size of the grid is not given, it tries to automatically fit the elements within, pacing path areas in between.

Irregular Grids

There are a lot of examples of parks with non-rectangular grids. One of the park examples is give above.

The two pictures sow the same park from different perspective. This also quite an elaborate example with a building and a curved outer region.

We require to provide another parameter – angle. In addition we require to supply variance of the values.

Grid should also be able to work without the paths in between. For that we can specify empty braces.

An example park will work as follows:

  • Region -> Grid (3 {[7,15]a[-15,15]}, 2) { NonWalkableRegion }
  • NonWalkableRegion -> Grid (2 {a[-5,5]}, {[1.5,4]a[-25,25]}) { PlantedRegion } {}
  • PlantedRegion -> Choose { GrassRegion, BushRegion, Plant1Region, Plant2Region /*, … */ }

In the second grid the size is omitted. Which is fine because the size parameters are given in curly braces – let the grammar decide how many regions it should split the park into. Empty second struct means no paths in between.

Rule Design for Construction of Multi-celled Grid Parks

Multi-celled Parks

Parks can be constructed by generating each cell invidually and joining them along the common regions, for example paths or grass areas.


Basic Grid

Construction of a grid by combining the paths does not work as I will submit in the next post, but joining the individual elements should work quite well.

The first picture shows the most basic construction of a part of a mark in Mexico. The procedure for construction is as follows:

  • Region -> grid(x, y) { CellRegion }
  • CellRegion -> Grass

Repeating Region Park

Even though the second picture shows quite an elaborate park we consider the simpler subset and concentrate division of the region into the two cells.

We wish to simplify the regions between the cells into simply grass area or tree decorated grass area for simplicity.

We ignore the complex outer polygon and the area between it and the grid region.

If we ignore the spaces between the cells with circles in them we get a variant of the grammar in the example above:

  • Region -> grid(2, 1) { CellRegion }
  • CellRegion -> SimplePark

Were SimplePark could be the the model of the first square park described above for example.

Looking at the second picture we produce rules for the regions in between, units are meters:

  • Region -> Grid(5 {3, 15}, 3 ) { CellRegion }
  • CellRegion ->
    • case (w == 15 && h == 15): SimplePark
    • case (w == 3 && h == 3): TreeRegion
    • else: GrassRegion

This produces tree different regions, 15×15 larger squares for a more complex park park and 3×3 smaller squares where the trees are planted. The remaining rectangles are simply grass areas.

Notice that only x dimension gets the size, y dimension automatically receives the same set of sizes. They can overridden with custom sizes, of course.

The paths sizes used default values, where 3m would be a reasonable value.

Split Structure Park

We can also use different instances for the cell of park grid. For instances we consider the subset of the park in the third picture with three different cells:

  • Region -> Grid(1, 3) { SomeSquarePark  | PoolRegion |  SomeSquarePark }
  • SomeSquarePark -> Choose { SquarePark1, SquarePark2, SquarePark3}

Analysis of Square Grid Parks

Square Parks


We consider a simple rectangular park first.

The first two images correspond to the layout and the photograph of the actual park.  Second park has more elaborate centre, entrances, corners and tree placement, but it still has the same structure and topology.

The third park also has a rectangular shape, however topology is different in that it has different number of entrances at each side and in addition it has 4 “dead-end” components.


Simple Park

A possible set of operation of construction of such a park

  • Create pathways
    • Add crossroads
    • Add Romb at the centre
    • subtract octagon shape from the centre for the fountain
  • Non-walkable regions
    • Extrude of split the outer rim
      • distribute trees equidistantly within the non-walkable strip
    • Add bush volumes
      • certain distance from the outer edge
      • different distances for the inner (path) edges
        • on one of the axes one more branching/turn is added
    • Position trees in the middle of the grass regions
      • tree region is inserted in the middle
  • Fountain
    • construction of the fountain considered separately. Static asset inserted

 Cornered Park

The additional operations can be added as follows:

  • Corners
    • Subtract Circles areas from the most outer (both edges of the vertices are outer) corners
    • Offset corner vertex from the centre
    • Place Tree regions
    • NOTE optional, consider that the outer area is walkable
  • Bush placement
    • Bush placement along the perimeter
    • Inner corner (those opposite to the outer corners) – different bushes
      • assumed circular extraction
      • take the are until the adjacent edges (dominant)
  • Trees
    • at some distance within the path edges

Oval Centred Park

Symmetry in one axis only.  New operations:

  • Closed/cul de sac regions
    • Rectangular regions subtracted, path inserted
    • bench inserted
    • Tree placed at the back
    • Space partitioning/collision detection (advanced)
  • Once side can have one or two or more paths going to the centre
  • Larger area subtructed from them middle
  • Subset-park operation!
    • Internal regions treated as a new park.
    • Bushes around the edge
    • Trees scattered (even if one)
  • Bush placement based on the collision/occlusion

Object placement

We need to place the benches and street-lights along the path. Although more generic placement mechanism may involve more elaborate placement strategies in the future.

In the previous post arrows were seen to be placed in the middle of the path. I have replaced arrows with simple ‘pick’ triangles, as it easier to compute direction with a triangle then more complex arrow object.

Where the object should be placed I add a Isosceles triangle with the small base and the ‘vertex angle’ vertex moved further away from the centre of mass. The direction is the vector from the midpoint of the base to the ‘angle vertex’ vertex, which is obtained by selecting the vertex which does not belong to the base. Base is the shortest edge. I select the centre as the average of the angle vertex and the midpoint of the base (because of placement strategy, logically however centroid or centre of mass makes more sense).

Angle of rotation is can be obtained using arctan function but SketchUp already provides a Vector3d::angle_between member function.

Resulting park looks like this:


SketchUp – First Park

CityEngine demo version is expired so I have turned to Google SketchUp for park generation. I would like to apply the same technique of first generating OBJ input shape and then filling it with objects.

SketchUp is not particularly known for procedural content generation, however Ruby scripting and, even native plugin development can be employed, which could be sufficient for tree/flower/… placement.

SketchUp also has “Components” which could be instanced multiple times; they also appear to have special transformation anchors. I am not sure of the scope of component functionality yet, perhaps instances with random parameters is possible.

First bump in the ride that I have come across is that OBJ is not supported natively in SU. Luckily a free plugin (by TIG) did the job.

Scatter function is also not present in SketchUp. I had to go through a number plugins until I stopped at MatrixProximity (also by TIG). It allows to distribute copies of a selected component instance into a matrix. Random translation on the ground plane, rotation around the Up axis, and optionally scaling is added. On top of that I have introduced the following:

  • Multiple components allowed (just sample the array)
  • Place components inside the Group/Face
    1. Fit the component instances into the bounding box
    2. Add border equal to that of random a radius (max value) – to limit the placement inside the; additional border, to stay further from the edge, is possible
    3. Cast ray to the face, if the face is not met, discard the instance
    4. If group is selected, do the same operation for every face in the group
  • Minor re-factoring included separation of functionality; a few setters were added, for example group_transformborder_offset...

The final script fill_park1.rb expects the group names provided with imported obj file.

Picture below demonstrates the park with Trees, Flower pots and Pedestrians (different pedestrians sampled).

obj park - item placement in sketchup
Park created from an imported OBJ shape in Google SketchUp

Object placement

We would like to place benches and street lights along the paths. Even if paths are curved they are represented by polylines (linestring type of boost::geometry).

The idea is together with the previous post (region partitioning) to generate a simple park similar to a one of SimCity’s Large Parks.


In this simple example two paths (that connect the opposite edges) intersect somewhere close to the centre. To facilitate object placement we:

  1.  Split each of the polylines in two at the intersection point.
  2. Parametrise the polyline by length, add the start buffer and end buffer to the ends resulting in the segment in the middle.
  3. That segment we split into (i-1) times, where i is number of objects we want to place.
    • a single object is simply placed in the middle of the segment
  4. Compute tangent (because the path can be curve, even if represented with a polyline), and when placing objects they are rotated by arctan of the resulting value.

Below we show the result where the placed objects are arrows.


Non-walkable region partitioning

The regions are the faces that result from partitioning the park with paths. Actually paths are extruded, but regions are considered separately. The regions are non-walkable, but can represent park partitions like flowerbeds or patches of grass, or a place where the tree is planted.

This is enchancement of the centered partitioning described in the previous post.

The new procedures were created

  1. Contraction
    All vertices are moved towards a centroid by a relative distance to it (distance to centroid/centre is 1, move range clamped to [0 . .0.9].
  2. Edge Partitioning
    Every edge is split with level n, for n = 0 no splitting occurs, for n = 1 we add one vertex in the middle, for n = 2 we evenly place two new vertices on the edge, splitting it into three edges.
  3. Smoothing
    Every vertex is reposition into the sum of two adjacent vertex and itself (v_curr + v_prev + v_next)*1/3; alternatively weight_middle, by default 1/3 can be used to adjust the neighbour weight (e.g. 0.5 means neighbours get 0.25 of weight each).

The image below shows on the example of a simple flowerbed partitioning with the application of Contraction, Edge Partitioning and then multiple Smoothing for the first inner loop, and additional Contraction for the most inner polygon.


Park shape generation

I have experimented with squared parks with 4 entrances at each side.

The first example shows just two paths crossing in the middle. A small round square is place at the intersection, which could be a square, rombus etc.


A second type of the park is where the regions are cut ellipses centred at the park corners. there is more place to fit something in the centre (a fountain, statue, flower beds etc.).




Bezier curves can alternatively be used to smooth the corners. Any degree can be used, determined by the number of points in the corner region.



Bezier curves also produce interesting results when the points control points are permuted randomly. Perhaps it may give a slight impression that a (human) designer has modelled it.

Bezier with random offsets



I have decided to work on generation of parks. This should be pluggable into the existing city creation framework.

The input to the system should be

  1. A polygon on the plane
    We consider a park on the flat surface for simplicity.
  2. Street network (optionally)
    The park can contain a street network that has been constructed externally, perhaps automatically by the same module that generates the city street network.

The output is a set of geometry that is based embedded into the plane that represents the park. Geometry can be abstract so that the rendering system is free to choose how to interpret the representation, for example to render the tree foliage as a series of polygons for fast preview or creating an instance of a tree with individual leaves.

Park polygonal composition

Major part of park construction is partitioning of the input polygon into subregions that shall represent the functional components of the park. For example the basic park would contain a flowerbed in the middle surrounded by a green area (two polygons).

simple-park-layout1 - polygon with a hole

The polygons considered here are composed of line segments, and arcs or polynomial curves are not allowed. An internal will might contain curves, but these will be parametrised into polygons or polylines for simplicity and for compatibility for now (CityEngine cannot handle polynomial regions for instance).

The problem with placement on one another as seen in the picture above is that the inner polygon is completely contained within the outer one. So if we decide to populate the outer polygon with trees, they will also be placed over the inner one which represents a flower bed.

Task: It is required to cut the outer polygon to make a whole for the inner polygon.

One solution is to simply cut starting from the outer boundary of the first polygon to the boundary of the inner polygon.

simple-park-layout2 no holes

Second solution is to split the Polygon1 into to polygons and then subtract the Polygon2 from it. CityEngine park example is partitioned this way, by my assumption – manually.

  1. Preconditions are that we have two simple polygons and that Polygon2 is contained entirely within the Polygon1.
  2. Compute the centre of the Polygon2P2c.
  3. Select the largest side of the Polygon1 – S1.
  4. Partition Polygon1 with the line passing through P2c and the middle of S1 into Polygon1a and Polygon1b.
  5. Subtract Polygon2 from (Polygon1a + Polygon1b).

simple-park-layout3 - max-side-middle-cut


There can of course be problems when, for example either of the shapes are concave (not convex) – and even then it is not selection of S1 as a start of the cut line is not guaranteed to be optimal.