Generative Art - Project 2 - Populous

02/22/2022

Over the last few days, I've been reading a paper that uses L-systems to procedurally generate a city. The city creator consists of two components: a road generator, and a building generator. I found the generated roadmaps in the paper to be quite appealing and wanted to generate more with my input parameters. Here's an example from the paper, with the basic style I'm looking to imitate:

Another possibility was to render the resulting roadmap with the visual style of games like Mini Metro:

The Harry Beck tube maps that Mini Metro's style is based on are famous for their minimalism. However, I do want to preserve the geographic locations of streets so I will be largely following the example from the paper.

The authors created an L-system template generator to make the city creator extensible without having to constantly update many production rules every time they wanted to add something. They would then supplement the template with parameters derived from input data such as population density image maps. Finally, they combined these with one or more rules that dictate the general "layout" of the roads that emphasized the following: density-dependent, rectangular raster, radial, elevation-dependent, and potentially many more patterns. Throughout the process, they would use functions to fill in the rest of the template and modify the generated road parameters based on their immediate surroundings.

I'm excited to implement this paper because getting each of the components to work together will be quite the challenge. I will need:

• A token parser and replacer to generate the L-system template and successors, which follows the appropriate syntax
• A graph or k-d tree to store each created road segment (nodes signify the junctions or crossings)
• A global goals function to generate parameters from the defined ruleset
• A local constraints function to adjust individual roads to fit environmental constraints as needed, with intersection checking and the ability to search around the endpoint for other streets/intersections to attach to

• A rudimentary L-system parser and renderer (to demonstrate L-system correctness)

As for beyond this project (project 3), here are some other things I could add:

• A subdivision scheme to smooth any roads with a high curvature (post-generation)
• An image loader to import map data
• A renderer to display a 3D mesh of the elevation data, and layer the generated road system on top of it

Reading this paper has also left me with many questions that I will need to answer:

• How are successive road angles and road lengths set?
• How can we keep track of all the different rules as they are updated?
• What is the structure of ruleAttr and roadAttr as defined in the paper's production rules?
• How will distinctions between highways and roads be made?
• pDel is an array of attributes for branch creation and deletion, but how are they set?
• How are the parameters assigned and unassigned within the text of the L-system?
• As new roads are created, what happens to the already-created ones in the L-system? Are they still there in the form of rudimentary symbols that are used in the rendering of the system output itself?
• How are angles and lengths defined in those "output sequences"?

And on top of that, I'm working to understand the following production rules:

Those are just for the template generation; the parameter setting functions haven't been covered yet! As was mentioned in the critique, it would already be a lot to get just the L-system generator working.

I did find a blog post by Sean Barrett that decomposes this very L-system into an algorithm using a priority queue. The page where I found the link to that explanation will also be a good one to read.

02/23/2022

After reading the two links I posted above, I know how to simplify some parts of the project.

I also learned that Chris Delay of Introversion Software used this algorithm (or a variant) in his project Subversion - cool! I remember him from the monthly update videos he made for Prison Architect, another game of his.

The paper has a somewhat hand-wavy approach towards the actual generation and modification of road parameters, and there are many of them. For example, the stochastic processes used to determine many of the attributes in their example, such as the starts and ends of highways, are completely glossed over. Of course, only so much can be explained in a couple of pages.

The second link contains a repository containing an implementation of the paper in CoffeeScript. I don't want to copy it entirely, but skimming the code helped me to come to some conclusions that hadn't been clear in the paper. It also helped me with my implementation, by giving me the idea to use a quadtree to store segments instead of a k-d tree (though both would require rebalancing at points).

The upside of using an algorithm instead of generating the entire L-system is that I no longer need to devote time to the token parser and can focus more on the actual road generation procedure and its aesthetics.

02/24/2022

Here is a non-exhaustive list of what the program needs, from research.

• A priority queue and while loop to handle the generation system
• Many parameters for highways, roads, and the land
• Algorithms to check for if a line crosses into/over the forbidden areas
• Image readers to accept maps
• A simple mesh based on a heightmap, with generated roads being projected on it as an updating texture

There is much, much more in addition to this.

02/26/2022

I'm slowly getting a better handle on de-formalizing that L-system. It was complicated, but I now have a good picture of what each of my road-building functions is doing. My intended program design does not rewrite strings using a list of production rules - it no longer employs an L-system under the hood.

Following this, I plugged away at my renderer for a while. Over the last month, I've been working on a geographic information system visualization tool with Dr. Ergun Akleman and several others. Some of the code that I wrote for it is reused here. Specifically, I was already able to load multiple image maps into pixel arrays, render a 3D mesh using one of those image maps (that I had designated as a height field) as vertex data, and project a satellite image onto it. The applet also allowed users to look around using the mouse.

However, I also needed to superimpose roads onto the mesh's surface. This is done by using Xiaolin Wu's line plotting algorithm (albeit with the antialiasing turned off for clarity for the time being) onto another texture, which is then blended with the projected satellite image. Simple lines will be all that's needed to demonstrate the capabilities of the road generator for project 2. To test out my rasterizer, I generated 200 random line segments. Below is an image of these random lines colored red and strewn about San Francisco:

The generated roads follow the slope of the mountains, but it will be unlikely for the "L-system" generated roads to be placed there as those areas will tend to have low population density. According to the basic pattern of road generation, most roads will steer clear of areas with lower population density in general.

Next, the satellite photo of San Francisco already includes the city's actual road system. The generated road system will understandably not match. Moreover, my estimation of population density will be discerned from the satellite map and will be a rough approximation at best.

I also learned about using modules to better manage my multiple-file JavaScript project.

02/28/2022

I focused on dropping my roads into the render system. Since JavaScript doesn't include a seedable random function, I found another one on the internet to use. Also, I needed to find a way to draw thicker lines, since Wu's algorithm only creates antialiased lines that are 1 pixel wide.

Additions:

• random function with seeding (used Mersenne Twister JS implementation found online)
• thicker line rasterizer (it handles the antialiased line pixel replacements by using the same line algorithm to repeatedly draw lines at increasing distances on either side of the original line)

Here are two images of my progress with the above functionality. The first one shows generated highways and streets of any length, while the second one shows generated highways and streets fixed to a length of 100 pixels.

03/02/2022

I finally generated some road networks with a basic version of the paper's global goals system.

One of the methods I used to avoid having too dense of a road network was to cull roads with a 10% base chance, and then check to see if there were too many other connections in the immediate vicinity.

Because the local constraint algorithm isn't finished, and because some roads are pretty long, this doesn't look quite like a logical road system just yet. There are some neat parts though - for example, the generated network follows the actual network along the coast.

When I run local constraints, I will be scanning the nearby area for any intersections that new roads can connect to. I do not expect there to be more than 5000 or so road connections at any one time. In this case, I could sort my connection list by x coordinate and then do linear searches within bounding boxes of a certain size for my local constraints, although it would be much more inefficient than using an organized structure like a quadtree.

This method wouldn't cover any roads that might be intersected with or are close to being intersected with; that is yet another corner case. For example, if a road begins at the top left corner of the map and ends at the bottom right corner of the map, I'd still need to check for intersections across its entire length. Using a bounding box to find nearby endpoints would not always yield a result.

Perhaps, I could condition the bounding box size to be at least twice the longest possible length of a road.

• implemented global goals
• I thought of an aesthetic possibility - Jay Foreman's series on Unfinished London includes a timelapse diagram of the city street map growing over time

Several next steps:

• add local constraint algorithms
• switching between a turn-table view and an orthographic view from above
• to prepare for a sort of "timelapse" render, I wanted to include a segment delta system - lines aren't just added but split/replaced, so I'd need to keep track of these to generate an animation of a growing road network (Actually, this is not required! Lines never need to be erased from the road texture, because only the new lines themselves are adjusted as necessary when they are being added.)

Additional corner cases for constraints to think about:

• find closest connections
• find closest spanning line segments
• find closest interfering line segments
• if I am to use quadtrees, what if a line segment spans multiple quadtree cells?

03/03/2022