Procedural Generation – Chaos and Order

In the previous post, we explained how we came to implement the new 2-dimensional grid system. This was needed for our plans to make the levels of Highrisers procedurally generated.
So, now we had a nice and fancy grid, and we knew what area was covered by each specific item; we called that the slot size, measured in x and z direction:

The slot grid; the area covered by items shown red.

So, in this pic the trophy has a slotsize of (1, 1), the crossbow needs (2, 1) and the turret requires an area of (3, 2).

What next? In procedural generation, every time a player enters a new level, you want him to feel as if he has never seen this arrangement before. This is reached through high levels of randomization – the more randomness and chaos you have, the lower the risk of a player saying: “Wait a second… I’ve seen that before.”

On the other hand, every environment, and especially a man-made environment like a building, there is a certain order that a player would expect. Furniture is placed and arranged in a certain way that feels proper – nobody places his fridge in front of a window; chairs are normally placed facing towards a table; books are placed in shelves, and so on.

When aiming for minimum risk of rediscovering the same set of objects, we could let a random generator run over the available objects, let it place them wherever there was space, and then see what we get. It would be a happy mess.
In order to get a certain grade of order, we thought of tagging certain objects to be belonging to a certain type (like “tools” or “kitchen stuff” and the like); and we could also define certain rules like “put furniture close to the walls”; but we still wouldn’t end up with what we wanted.

For a believable building, we needed more order, so we decided to hand-craft certain small groups of objects and furniture that were arranged in a way that makes sense and are visually pleasing, and then let those be placed in the levels in smart ways.

For that, we needed an tool to assemble and arrange those groups. We came to call it the Furniture Group Editor:

As you can see, it enabled us to position objects, to cycle through object variants and to adjust parameters like directional facing. Progress in object modularization also made it possible to create a vast amount of furniture looks with a minimum effort:

So we’ve created a selection of groups, we’ve tagged them so that a floor would have a consistent theme, and we defined certain rules of how to find positions for placement.
These are some of our current results:

So, what’s next? If you look closely, you can still see the imperfections of the current approach.

There are groups that are repeated often; the reason for that is that we only have a limited number of groups in our collection yet.

Then, there is the issue that groups are static, which makes it very obvious to recognize them again – if there is the exact same dresser with the exact same aloe plant on top, people will recognize it. But if next time the dresser is reused, there are books on them, or clothes, or maybe nothing – then it gets harder to see the pattern.

And finally, there is the question of positioning. Currently, the algorithm is still quite dumb; it identifies corners of rooms and then tries to place groups in those. Then, if there is still space in between, it tries to fill them.
Improvements here could create a more dynamic, more natural object distribution.
We’ll keep you updated with what we come up with!

The base grid of everything: Slots

Procedural generation is the state of the art for all rogue-lite crafting games, and it is also the goal we’ve set for ourselves. The game structure of Highrisers requires that whenever you restart the game, the buildings you encounter in are all different and new.

So, how has that worked out so far?

For that, we have to go one step back and look at how objects are placed and stored in Highrisers.

Highrisers uses a grid-like structure we dubbed “slots”, where interactive objects are placed in. That’s also a pretty basic system that has been around for a long time:

Building placement in StarCraft utilizes a grid

So, it seems pretty obvious that we would be using something similar for Highrisers right?
Well… actually, we do now, but for a very long time, our slots were nothing more than a 1-dimensional line.
Why didn’t we see right from the start that a grid would be much more useful?
The answer lies in the history of our project. Our earliest prototype looked like this:

Early Highrisers prototype with dummy Megaman X sprite.

Do you note the flat perspective with depth in z-direction? When you do not have any depth of the floor visible, why should there be a need for a 2-dimensional grid?
Objects, like the apples, where simply placed one by one next to each other.

Later, though, we found it much more useful, realistic and aesthetically interesting to change the perspective of the game so that the top surface of floors and objects would become visible. The slots remained a one-dimensional string; we just added second line in the back. So, slots became something like this:

Highrisers slot system

The front row was reserved for gameItems – small objects that can be picked up; while the back row was only for gameFurniture – large furniture objects that could hold gameItems and that can only be disassembled.

The first drafts of auto-furnishing thus worked like this:

GameFurniture in the back; GameItem in front.

Basically, the program checked where there were any empty slots, randomly selected a fitting object and then placed it. As you can see, this does not exactly make for exciting furniture arrangements.
In the worst case, the algorithm would place 8 copy machines in one row and be done with it.
Even putting a chair in front of a desk would not have been possible under that system (as a chair is not a gameItem – it cannot be picked up, and the front row was reserved for gameItems).

The obvious solution – the change of the 1-dimensional slot line into a 2-dimensional slot grid – would also help us address another issue.

So, we worked to change our slot system into the new one. This touched nearly all parts of our object system and reached deep into the code. In the end, it turned out to have taken several month, but now we could create believable furniture group arrangements and have a proper z-layering and occlusion of all objects, thus solving the dreaded washing machine problem, too.

Current 2-dimensional slot grid

Now, it seems hard to believe how we ever worked without the grid system. In the next entry, we’ll explain more how this affected procedural level generation.

The washing machine problem

The world of Highrisers is purely made of 2D sprites. We use a cabinett projection in order to generate a 3 dimensional impression. That’s a kind of drawing technique that works without a vanishing point. It’s well suited to the dollhouse-like look of Highrisers and for pixel art in general, as the “straight” lines running inot the back are at a 45 degree angle. Which works well with pixels.

We further enhance that impression by clever usage of light and shadows, but at its core, it’s all just plain 2D.

This means we can create levels quickly and simply, and the performance will be great even on older machines – we’re just moving 2D-sprites after all. We won’t be able to do stuff like the change of the looking angle as you might have seen in “This War Of Mine”, but that’s fine.

However, we now also encountered limitations when it comes to arranging items and walls.
We have dubbed this issue the “washing machine problem”, due to the nature of our example object. Simply put, it’s about this:

It might not be obvious why this issue should arise. But always remember: Those walls have no depth. They’re just flat wallpapers creating the illusion of depth.

Until now, our building (all the walls, floors, ceilings, pillars, etc.) have been based on a tilemap, and it has always been completely in the background. That means that all other game objects like furniture, equipment, the dreamers and the players, everything was in front of all the walls.

If you played the demo, you might have noticed that in some cases, this is not always entirely true:

What about that red barrel on the right of the workbench? Isn’t that clearly covered by the protruding wall?

Well – unfortunately, no. Like all objects, the sprite of the barrel is actually placed in front of the wall and looks like this:

I have manually set a clipping rectangle for the sprite and cut off the part that should be visually behind the wall.

For the dreamers that are hidden in the walls behind closed doors: They are only spawned once the door is opened, so again – no occlusion of objects by walls.

This worked fine for our static tutorial level, but of course this would not work once we integrate the procedural generation.

And as we were overhauling our building tilemaps to make them fit for the proc gen, we also decided to address this occlusion issue.
Object placement in Highrisers generally works like this:

Every object has an anchor point, which is the bottom left far corner of the object.
Remember that the object is purely 2D, so we only need to store the x/y offset. There is no real z-depth!
Since our perspective is vanishing to the right, we place objects from left to right, so that leftmost objects are occluded by their right neighbors.

The idea now was to have different possible layers where a horizontal wall can be placed, and a corresponding layer of object slots, which would place objects in front of their walls, but behind the next wall.

Slots are positions where an object can be placed. They offer an anchor point for alignment and help to avoid overlaps, as they prevent two objects from occupying the same space.

3 different wall layers and their corresponding slot rows
When placing objects in the slots, the walls and objects of a hihger level cover walls and objects of a lower level

Sounds nice and easy, and would have worked with our current level architecture. But when you think about it further, problems arise:

While this case would still work with our layering concept, it falls short for other combinations:

As we can see, the long right washing machine is placed on the yellow level, but it is so long that it covers the red wall. But read walls are supposed to cover objects on the yellow level?!

This can also happen for horizontal walls placed in the front:

We have not yet decided how we are going to address this.

We could simply limit our architecture so that we don’t run into such situations. No walls in the front, no walls portruding into the scene. As the architecture of Highrisers is stylized anyway, this would well be possible.

We could also limit our object design so that we simply don’t have such looooong objects reaching into the front. Or have them only placed horizontally only.

We could also change the rendering algorithm for our objects, drawing them only from one layer to the next, from left to right. That way, the right occlusion will always be selected, no matter where the anchor point of that object is. I would require to transform our flat tilemap walls into wall objects that interact with the slots.

Concept of layer by layer rendering

Oh, who would have thought that washing machine placement would be this troublesome?

Highrisers Background Story Timeline

2020 – Breakthroughs in plant genetics revolutionize agriculture with tremendous speed: so called mnc-crops, which contain several serially connected ribosomes promise bountiful harvests in no time. Jobs get lost in the traditional farming, a rural exodus starts.

2025 – Urbanization is not ebbing away; it is rather fueled by massive movement of refugees, longer life expectancy and lack of perspective in rural areas. In the USA, racial tensions are increasing; many members of ethnic minorities emigrate to Europe.

2027 – Turkey leaves the NATO. Russian provocations are daily fare; the US military increase their presence on European mainland again. In the Middle East, local conflicts are spreading. Northern Africa, unable to purchase the expensive mnc-crops, is suffering from several years of drought; millions are fleeing. China is flexing its muscles in world trade. Mutual economic sanctions paralyze the conflicting parties.

2028 – Due to the constant exceedance of pollutant limits, the EU is forcing European governments – despite their fierce resistance – to enforce driving bans for diesel and gasoline driven cars in inner cities. The still stagnant progress in electromobility is further halted by a resource crisis and economic embargoes. Especially transportation of goods is strongly affected.

2029 – Housing space is becoming a rare commodity in every large city in the world. Rents are unaffordable to most in all major conurbanations. In Germany, the efforts of the state to mitigate the effects of the rural flight fall flat without any significant effect. At the same time, broadband expansion is still stagnating in the countryside, despite the grandiose promises of government and service providers. Especially the young are driven into the cities, starting a vicious circle, since their exodus makes investments in rural internet connections even less profitable.

2031 – In addition to the widespread housing shortage, Germany is also hit by an energy crisis. The combined phase-out of nuclear energy and coal, together with Russian gas embargoes become noticeable. Without marketable storage technology and a reliable high voltage network, brownouts and voltage fluctuation occur with increasing frequency.
Some blackouts are also attributed to attacks of Russian hacker groups. Riots happen in the streets, and in the dark nights the wrath of the poor and left behind leashes out in looting and vandalism. There are also claims that blame Russian hackers and bot-nets for having manipulated social media in order to incite the unrests, but there is no proof.

2032 – The Federal Government pulls the emergency brake. In the fourth version of the reform of federalism, it gains wide concessions from the states and the municipalities over the planning and building laws. Objections against power lines and other infrastructure projects, as well as new housing constructions in conurbanations are now next to impossible. In return, the states win more autonomy in the fields of internal security, public health and border protection – this was an important issue for Bavaria, where the State ministry for Infection control, General health, Media and Anti-riot, SIGMA, is founded.

2033 – There is a nationwide conformation of building regulations. Every new building in a metropolitan area must now have a minimum of 35 floors. Concern of urban development and historic preservation are mostly ignored. Long time residents protest fiercely, but in the end to no avail.

2035 – Property speculators pay top prices for developed land in cities, to tear them down and rebuild them in accordance to the new building regulations. There is a gold rush mentality. The former residents are pushed towards moving out, sometimes by all means; the social gap is increasing. Protests and demonstrations are now a common sight. The face of the cities is changing with enormous speed. The construction boom in the inner cities causes even more traffic congestions. The transportation cost of goods are now so high that even production facilities in urban areas, so called vertical factories, are profitable.

2038 – The first documented case of the sleeping disease occurs in Romania: The worker Radu Bădescu is goind to sleep on the evening of April 23rd, as every day, but on the next morning, he can’t be woken up. Doctors are clueless. He seems to be trapped in an eternal REM-phase. He is put under surveillance and is fed artificially.

2039 – All over the world, there are new cases of the mysterious sleeping disease, seemingly without connection. The wildest rumors are flying around – Russian bioweapons are to blame, or the consumption of mnc-food, imported diseases of African refugees or a side effect of vaccinations. Pogroms and violence against minorities are on the rise. Patient 0, Bădescu, is now suffering from skin lesions, cerebral alterations and morphologic adaptations of his inner organs. His body has become sensitive towards bright light and his skin produces dark pigmentation. The WHO is still in the dark as to what the cause of the disease or the route of infection could be; they suspect prions.

2040 – First cases of the sleeping disease in Germany. Rumor has it that sleep deprivation could halt the outbreak. The WHO is now sure that prions are the cause and recommends isolation of the infected and an exhaustive decontamination of the affected buildings. There is word from the USA claiming the WHO insights are in truth fake news engineered by foreign powers in order to hurt the already struggling American economy. Authorities are trying to keep things under control with increasing levels of desperation: Curfews are imposed, the internet is censored, and looters are ordered to be shot. Public confidence in the media and the government is at an all time low.

2041 – The sleeping disease, now also called Black Rot, due to the skin alterations, is spreading rapidly. Hospitals are crowded with infected. Various governments are now willing to enforce quarantines and border closures after all. In Bavaria, SIGMA is taking control of the containment measures. The supply situation is critical.

2042 – News of the “Awakening” of the first dreamers go around the globe. Everywhere, their blackened bodies are rising, and they are shambling around without orientation, as if sleepwalking. Panic is spreading. Studies seem to confirm, that those who avoid the deep sleep phases can avoid the transformation. Some try to prevent the outbreak of the disease by not going to sleep at all or by exposing themselves to bright light all the time.

2042 – First in South America, than everywhere over the world, the same reports: Dreamers are attacking the healthy people. In a mindless rage, they beat them into an unconsciousness from which they won’t wake up again. Soon, their transformation also begins. Within a few days, public live collapses. Most of those who barricade themselves succumb to exhaustion after a few weeks and despite all precautions, fall into deep sleep from which they don’t awake.
Yet, some seem to be immune. A motley crew of four survivors has gathered upon the rooftop of a high-rise in the Bavarian metropolitan area, with one goal: To escape the city