Creating Streets using localized generation

Much of the work on urban simulation has been aimed primarily at realistic simulation of real-world environments. The creation of urban environments for gaming and entertainment applications has a slightly different criteria, with its own set of limitations and oppurtunites. The most salient difference between a simulation environment and an entertainment one is the criteria by which accuracy is measured. Realism is not necessarily the best criteria with which to judge environements that are created to evoke a specific mood or phsycological setting. One could refer to such environments as "affective environments", as they are created not to be a representation of a real-world place, but rather to mold the user experience.

When creating affective environements or designing systems that create affective environments, it is important to be able to exaggerate selected characteristics of "real" settings in order to achieve the desired effect.

The distinction between realistic re-creation and affective simulation also applies to the manner in which the content is generated. If the purpose is to accurately model real-world settings, the a top-down approach is likely the best choice, as it provides high-level control of the overall environment. If the primary purpose is to create an engaging environment for users to experience first-hand via some form of interactive walkthrough, global details become far less important. Since the user can only ever see a limited region at a time, it may not be necessary to provide global consistency. As long as the local details don't directly contradict the existance of high-level structure, that structure can be hinted at without being actively maintained at anything other than the local level. This can be taken advantage of to avoid both lenghty pre-processing and extensive memory storage as the environment could be generated on the fly as a response to a user's movement through the world.

While generating a large area of streets and geometry at a time can provide a number of benefits, with the most significant being a higher degree of correspondance to real-world data, it has several drawbacks:

a potentially lengthy pre-processing step where the region is generated from data
a finite area, with expansion requiring an additional round of pre-processing
complex, multi-dimensional input

The above criteria may or may not be significant, depending on the application. When that application is a large-scale interactive gaming environment, the first two become significant drawbacks. It the viewpoint is set at eye-level to simulate walking through the space, large-scale simulation of urban structures is not necessary. In other words, global realism, since it will never be directly experienced by the user, is not necessary- the system need only create spaces that are complex and compelling at the local level. There must still be vareity from local area to local area, but that can be accomplished without any kind of top-down global approach.

Given a large expanse that is to be filled with an artificially generated urban area, two problems immediately present themselves

the partitioning of the space into individual areas
the filling in of the local areas with geometry (buildings and etc)

It seems logical to make the partitioning of the virtual space synonomous with the creation of street patterns. However, to do that sucessfully requires some form of top-down approach. An alternative method is to break the space up into uniform grid units and generate streets solely within each unit. The benefits of such an approach are isomorphic to the drawbacks of the top-down approach, in that only a single grid unit is generated at a time (requiring no extensive pre-processing of data) and an infinte environment.

Of course, this approach comes with its own drawbacks. The major problems that must be avoided are:

ensuring that there is vareity from grid unit to grid unit. One could simply reuse the same grid unit over and over, but that would quickly become apparent to the user. It is also not enough to generate a set of tiles S and choose randomly from them, as for that to work, S would have to be a large number, and that re-introduces many of the issues we're trying to avoid
ensuring that grid units are coherent when aligned with each other. While the user will only ever experience one grid unit's worth of space at a time, that will include traversing the boundaries between neighboring grid units. At such times, it becomes critically important to make sure that the transition between two grid units is seamless.

As we will see, both of the above drawbacks are easily addressed using simple math based on psuedorandom numbers.

Given an expanse of virtual space, partition the space into an infinite expanse of grid units such as the one at right. For each grid unit G, points P0–P3 are the points that define its area, and they are connected with four edges E0–E3.

While the partioning may seem to imply a top-down global approach, it can be implemented simply by taking the actual position of the points P(0-3) modulo some width value W. Furthermore, the edges created by such a process, while important for the calculation of streets, need not be rendered as streets, making the divisions of grid units (potentially) dissappear.

Each point has an X (width) and a Z (depth) value, along with a possible Y (height) value, referred to as PN.x, PN.y, and PN.z.

Each grid unit is partitioned into streets via the following approach:

for each edge, determine a random number of nodes N_e to distribute randomly along its length
determine a random number of interior nodes N_i to create within the region defined by G via a Interior
for each node e in N_e, create a link from e to the nearest node i in N_i
create a link between each of the interior nodes N_i

Edge nodes (number and position) are determined using an Edge Function F(E)
Interior nodes (number and position) are determined using an Interior Function F(I)
Edge nodes and interior nodes are joined to interior nodes
Interior nodes are joined to each other
The finished street pattern for grid unit G

Many different schemas can be used to generate the positions of the edge and interior nodes. The simpliest would be to place a single node at the midpoint of each edge and one in the center of each unit, yeilding a conventional grid pattern. Randomized approaches are capable of much more interesting results, but would seem to require that large amounts of data be stored in order to ensure that a given grid unit will be the same should a user return to it, and that neighboring grid units will have streets that line up with each other. However, by using the strengths of pseudorandom numbers, both problems can be solved.

This is achieved by basing seeding the random number generation with values derived from the global coordinates of the corners of the grid unit. Since returning to the same area of world space will result in the same 4 points, all of the streets generated for that grid will be exactly the same each time they are generated, though no information is directly stored. Furthurmore, by basing edge node number and position on the coordinates of the endpoints of an edge, rather than all four points of the grid, streets in neighboring grid units are guaranteed to line up, even though each grid unit is independantly generated. If the coordinates of the two endpoints of the top edge of one grid unit result in a seed value X, leading to 2 edge nodes at positions Q and R along the edge, then the same calculations performed on the bottom edge of the grid unit directly above will also result in a seed of X and positions of Q and R for the edge nodes. This results in streets that line up with each other, and that remain unchanged upon the user's return to a location, even though they are never stored. Greuter et. Al [8] used a similar approach to maintain consistency with generated buildings, but did not apply it to street generation. As long as the seed values for the edge node generation are based on the endpoints of the edges, and the seed value for the interior node generation are based on all four grid points, the resulting map will be consistant and the neighboring grid units will have aligned streets.

By using different functions to select and position the edge and interior nodes and to join the nodes together to form street patterns, different street patterns can be generated. In the demo application created for the Infinicity project, the number of edge nodes is set to be either 1 or 2 per edge, the number of interior nodes is set to 2, and the nodes are joined by connecting each edge node to the nearest interior node, and then connecting the interior nodes to each other. This results in street grids such as the following: