Project Forge: Town Roads and Plot Zoning - Part 1

Last update I mentioned that the next post would likely be about NPC generation and simulation. Well, I started doing that and finished the generation algorithms; however it turns out simulation will require much more environmental input than I anticipated, requiring a development shift to town generation algorithms. This will give simulated NPCs much more of a "context" to work with, and will save me from much code refactoring when it comes time to tie all these modules together.

Town generation started out with the basics; each town would be defined from the seeded towns discussed in the last update, and would grow outward from a weighted center point of the town plot.

The initial boundaries of each town are defined by the local resources. Each pixel from the global map on the left corresponds with  16 pixels on the local map on the right. Each pixel in the map on the right represents one square meter.

The first step to generating towns is road generation. I made a critical mistake during my initial attempt at solving the problem, and locked myself into a solution that used templates to generate roads. This means that each town would have had a road system that inherited from a pre-defined template with several random variations. By the time I realized how awful of an idea this was, I had already blown most of my spring break programming it.

Example of one of the templated road systems. Purple lines represent roads, and green square represent  potential zones for residential development. 

I have a feeling that my initial idea was something based on L-systems like what this guy does, but the idea never actually came to fruition before I started actually programming. Looking back I have no idea what I was thinking; but on the bright side there were a few useful algorithms that had to be programmed to make templates work that can probably be reused elsewhere.

Okay - with that garbage out the window, I came up with a much more natural approach to the problem that likely emulates how roads are created in real life. The idea is to break the local map down into grids that contain several square meters of land. An entity that we'll call a road builder is spawned at a random location somewhere near the center of the local map. If the grid that the road builder lands on is not connected to a road, then it will construct a road connecting that grid to the main road system. By repeating the process and moving the road builder to another random spot on the grid, a kind of "crack" of roads is formed. 

Shit, it already looks better than that template crap.

In order to resolve the utter lack of interconnectivity on the road grid, an algorithm is executed which connects the endpoints of each path to other endpoints to increase connectivity and to make everything look a bit more natural. 

At least it doesn't look like a spider web anymore. Notice how the earliest built roads form a backbone for the network.

The nice thing about this road builder algorithm is that it works for any size town. It can be used to generate a town of only a few homes or even a metropolis of 500+ buildings. 

Road network from above seeded with building lots(green). There are about 200 buildings lots served by this road network.

Much larger network, unlike the ones above this one's "road builders" were bound by proximity to the road grid, rather than proximity to the origin point of the town. I think there's ~500 building lots on this one.

That's it for this update. Tune in next time for even more images of lines and boxes. 

-zalzane

Project Forge: World Generation and Town Seeding

Over the past few weeks, I have shifted design focus away from engine components and more onto the procedural generation components of the Forge. I have yet to make the decision on whether or not to use a graphics engine for Forge, or to use something lower-level like openGL.

Anyways the first procedural component I pumped out was a terrain generator. Right now it's nothing special and is just a placeholder until I can iron out all of the details. For the purpose of debugging and working on other features I'm using a 4km by 4km map, however in the future that will probably scale up to something much bigger like 16km by 16km, as long as memory restrictions allow. The placeholder terrain generator actually doesn't look all that bad, and because of how it works, some natural artifacts show up that may pass off as rivers at a later stage in development.

The brighter the blue color, the higher the pixel is from sea-level.

The next item on the itinerary was resource and town seeding. Each town would be seeded on areas of very high natural resource concentration, something I expected would normally happen for towns in real life. Several different resource maps were generated, each of which with their own unique density and spread. This is supposed to mirror how in real life, certain resources like fertile ground may be pervasive for many miles, however resources such as precious metals may only have deposits a few meters wide. Since the NPCs founding towns aren't supposed to be omniscient, they will only recognize areas as having a specific resource if the concentration of that resource passes a specific threshold. For example, an NPC would only recognize an area as having iron deposits because the concentration of iron in the local area is so dense that rocks of hematite or magnetite are found on the surface.

Example of a resource map for Iron. Areas of solid blue are where  traces of the metal are visible on the surface.

The average of these resource maps is taken, and a threshold is applied to the new cumulative map, symbolizing areas where potential settlers would recognize that there are plenty of local resources.

Each blue pockets represents an area with an unusually high resource concentration

For each of these high-density resource pockets, a town is founded. The next step was to connect these towns with roads, a process which turned to be much more painful than I had expected and added over 1000 lines of code to the project. 3 weeks and several cans of coffee later, I found the best solution for generating roads to be the use of Dijkstra's algorithm with a set of cost constraints based on how hard it is to travel through a certain area.

Red dots represent towns, green lines are roads.
Blue background is the cost map, with ligther blue having a higher cost.

For the pathfinding cost map, I did a threshold where if a pixel was deemed to be neigh-impossible to travel through (mountains, swamps, rivers,  etc), then the road would avoid traveling through it at all costs. However in some situations these areas must be crossed because there is no way around, in which case there will have to be bridges, massive elevators (I can dream), or stonework roads required to pass through. In the future it may be possible for NPCs to create their own roads after the initial batch in order to supplement the current system, but speculating that far down the development like probably isn't that good of an idea. 

That's it for this update. Next up in the queue is NPC generation and simulation, which is starting to look like a very interesting component to develop.

-zalzane

Project Forge Development

I suppose I'll start the blog with a post about a video game I've been working on: Project Forge. I want to see Forge become a relatively-believable, procedurally generated adventure game. It will likely be 1st or 3rd person point of view in a statically sized 3D world.

In terms of procedurally generated content, I want to have the game generate unique towns, cities, and entire civilizations for the player to interact with. Ideally these civilizations would function just like real civilizations, NPCs would have relationships with one another, they would go to work, go home, eat, sleep, wake up late, get fired, get knocked up, have kids, and all sorts of other fun stuff. I want to place a lot of emphasis on the realism factor of these civilizations so that they will grow, expand, and become unique entities all on their own.

In terms of gameplay, I'm not entirely sure of a direction to take. The idea that I play around with the most is having ruins scattered across each world for the player to explore and plunder, however I fear that such gameplay may become repetitive or boring after the first few exploration expeditions, an issue that crops up in a lot of other open-world adventure games like those in the Elder Scrolls series. The solution to this issue may take a lot of time to figure out, which is why I'm going to be working on the procedural civilizations/content before I start in on gameplay.

I'll try to work on Forge as much as I can in my spare time, but between college and work I cannot guarantee progress or blog updates on regular intervals. However on the bright side, I have already been working on the game on and off for the past few weeks, and have made a bit of progress in getting all of the 3D knick knacks working.

Here's a recent image I took of my inability to debug whatever the hell opengl uses to shade primitives. Kinda looks cool combined with the heightmap mesh forming some kind of pseudo-valley of darkness or something.