Building an infinitely large open-world

Things are still progressing in my game engine. I think now is a good time to post on one of the core idea of that engine: Infinite open-world.

Basically, this engine should facilitate the creation of an open world RPG, which is a good thing given the initial direction I mentioned in this post.

Is it restrictive?

Not all games need an infinite open-world. In fact, nearly none of them have that except for games like "No man's sky".

But in my opinion, any game can fit within an open-world. If you just want a simple "pac-man" game, why not have it as a room within a giant open world. Perhaps you'd like to make a small platform game with a few levels. What if you could jump into a new are once you beat it?

In any case, the engine should accommodate whether you need a one-screen game, or a giant open-world.

Is it a bit too ambitious?

Definitely. But I think it's good to dream a little, and unlike my childhood dreams, this project is not completely undoable.

As a kid, I used to come up with ideas of inventions that came out straight of science-fiction. I remembered some kind of "roller-skate" that would propel the shoe's with lasers underneath, and allow sliding in any direction, which was not only undoable, but also impractical and... kinda useless 😛.

Now I did at some point also dream of a giant open world in space like "No man's sky". I imagine flying into space with your small ship, when suddenly another player revealing before you with a giant ship that just turned off its cloaking device.

It was undoable at that time, but things are different now. I do have an idea on how to build that!

This is part of the work I'm doing with my game engine, which now has many random names (Dok Engine, Bun Engine, NAPL...).

Anyway, this blog post outlines roughly how a giant-open world, filled with various decors and NPC, can be built... at the most basic level.

Cell generation of surrounding cells

We start by the most basic concept for generating our world:

The video above illustrate the idea behind generating cells using a seeded random generator.

• We first split the world into cells, and detect based on the (x, y, z) position when the character visits a new cell (cellX = round(x / cellSize), cellY = round(y / cellSize), cellZ = round(z / cellSize)).
• We mark the surrounding cells for generation. In the example above, we create a rectangle of roughly 7x7 cells around the character. In an actual game, those cells would be the ones visible on the screen.
• Every cell not yet generated within that range gets newly generated.
• Cells already generated within that range simply get bumped up.
• We have an allocated amount of cells to keep in memory (in this example, roughly 100). Outside those 49 cells surrounding the character, any cell that has not been visited recently are discarded. We could have simply discarded all cells outside those 49, but it's best to keep a buffer of cells, so that we don't keep discarding/regenerating the same cells when the player goes back and forth between two cell positions.

The random generation using a seed

One requirement to keep our open world realistic is that static objects need to stay consistent.
Let's say a cell gets discarded, all the tree placements within that cells get removed. We no longer have those tree positions stored anywhere.
But we can recreate those trees at the exact same position by using seeded randomness. Basically, the cell (x, y, z) has a tag of ${x}_${y},${z} which is passed into a random generator. Given that seed, the random generator will always generate the same series of number.

For instance, our position is (x=5, y=0, z=10). The tag is "5_0_10". The random generator with seed "5_0_10" generate the series of numbers: 3, 1, 3, 5, 2, -4, -9.
(Note: random generators usually create numbers between 0..1, so we just pass those through some fixed formula like (n=(x-.5) * 20) to generate the series above.

With that series, we can decide where to place the trees.
3 => Create 3 trees
(1, 3) => First tree will be at position (x + 1, y, z + 3)
(5, 2) => Second tree will be at position (x + 5, y, z + 2)
(-4, -9) => Third tree will be at position (x - 4, y, z - 9)

Traditionally, the generation range is large enough that it occurs outside the screen displayed to the user. That way, the trees generated appear offscreen, not suddenly in front of the user.

Generate environments that make sense

Using the random generator, we can arrange our world builder to produce elements that make sense. For instance:

• First, use a random number to decide whether a cell has water or grass.
• If there's water, the next random generator will determine the number of fishes. Otherwise, it determines the number of trees.
• If there are no trees, we can place a foe or NPC, depending on the next random number.
• If there's an NPC, we use a random number to decide which dialog it's going to speak.

Using that same random number generator, we can freely generate anything we want. Since the exact same thing will be generated the next time we visit the same cell, consistency is maintained within the world, and thus it stays realistic.

Generating smoother environment

What is Perlin noise

Using a purely random number, we would just get a pretty chaotic environment. To make it a bit smoother, we can use Perlin noise to generate our number. This ensures that values within the same areas are pretty close together, and as we move to other areas, the value moves smoothly rather than jump.

This is a good way to generate elevation in terrain, but it can also be used to ensure that clusters of trees are together in a forest.

Generating distant structures

The idea so far is to look at surrounding elements and generate around it. But that means we're not able to see those distant mountains, or perhaps we want to show large monuments like giant pyramids.

For that, we can use a separate layer of cell generation, one specifically for large objects.

In the example above, our cellSize can be 10 (which is really something arbitrary). So anything within the vicinity would be generated.
We could have another cell generator at cellSize 1000, which would only cover very large objects. Using that generator, we would not care about trees or NPCs, but we could generate mountains.
We could even have a larger cell generator at size 1000000 which generates planets.

Most cells would be empty, but using the same concept, we can decide to generate those large objects at a distance.

As we approach a mountain, the smaller cell generators take over, and large mountains turn into mountain terrains, showing rocks, snow, mountain goats...

Going into the micro level

What's magical about this concept is that you can apply it to any scale, even at the micro scale. Let's say we wanted to create the game based on the movie "Ant-Man". Our player could shrink down to the size of an ant, which would reveal smaller insects and grains of dusts. To do that, we simply turn on new cell generators at very small cellSize (0.001), while our regular size cell generators are turned into macro generators (where we can reduce the range, since we don't need to look that far when we're small).

One game that well illustrates that concept is Katamari Damacy. You start as a small ball rolling around, collecting small household items like dice, erasers, gums... As the ball grows bigger, the world changes and you end up rolling over buildings, dinosaurs, buses...

Mixing it up with user generated content

The basic idea is still to generate games, with stories, and custom made environment. Relying it on chance would just create a random mess, but what if we want nicely aligned trees for pleasingly aesthetic environments.

For that, we can simply add a level of override, so that the user can move / add / remove elements.

Well, how does it change from just placing all elements from scratch?

Trust me, it's far more difficult and time consuming to generate an entire world when it starts empty.

Furthermore, it would require far more space to store all those elements, unless you're ok having just a small set of elements, and vast empty space around it.

Penguin Quest

A while ago, I produced the game Penguin Quest and used that method. The vast majority of those elements were placed randomly, and I moved them around to ensure I have an environment where the penguin starts in an area surrounded by mountains, then first goes to a cave, then finds water, etc...

By integrating user generated content and random generation, we can produce a seamless infinite open world that remains interesting. Some areas would use random generation to produce environments with variation, while other would be designed by users, the same way the world itself is a mix of mother nature and human civilization.

Generating living NPCs using that same concept

In old JRPG games like Phantasy Star or Final Fantasy, you'd often find NPCs standing in one place in the world, and stay put for eternity. It's like they live at that exact spot and love to just stand still without moving.

That's enough for most games, but it would be much more realistic to see a crowd of people moving around, going on their daily lives. Like the scene below in the Matrix:

We could simply generate an environment that spawns random NPCs, and have them come in and out of existence. That would do the trick, and it's ok for most games. But for me, it's still not enough!

This is how I imagine the game:
Out of this crowd of NPCs, the player simply follows one of them (perhaps that lady in the red dress). While watching closely, the player is waiting until that NPC disappears, or until they hit an invisible wall where they cannot reach the NPC anymore, or... what else could be happening. Perhaps the NPC just aimlessly walks around the same path for eternity

But as they spend the whole day tracking that NPC, they realize that the NPC has an actual life. The NPC goes into a coffee shop, spends an hour or two talking with another NPC, then comes out, goes to the mall, grabs lunch, goes home, take some rest, come out for dinner, then goes home and goes to bed until the next morning. The next day, they go into an office, and work at a desk the whole day, goes to the gym, hook up with a stranger at a bar ...

It seems like the NPC is a real person living in a real world. In fact, following any NPC would lead to similar result. How is that possible? Does it mean the game continuously generate a daily routine for every NPC in the game?

Well, sort of. The same way a tree exists somewhere in a game when you're not looking at it, the life of all NPCs go on when you're not observing them. The way it works with the tree, is that it has a calculated position based on the random seed, which can discard and re-generate that same tree depending on how close you are to it, giving the illusion that it's always been there.

The same goes with any NPC. Using a seeded random generator, we can predict an entire routine of an NPC. Furthermore, we can predict its evolution over time. All of this can be pre-determined given a random seed.

Let's start with a basic example. We have the following numbers generated by the random generator:
100, 50, -40, 200, 100, -50...
With those numbers, the game can decide to do anything it wants. In one case, those could be the approximate location of an NPC over several months.

• In January, that NPC is at the closest town to position 100, 50.
• In February, the NPC moves to a different town, at position -40, 200.
• In March, the NPC then moves to 100, -50.

We could use Perlin noise or some other formulas to make the transition smoother, so that the NPC doesn't change town every month, but perhaps stays put for a few months.

The random generator can also determine if an NPC likes to travel a lot or not. So some NPCs will just stay within one town, while others will travel around the world.

We don't have to stop at location. Using the same random generator, we can decide how an NPC's personality evolves over time, and even how the relationship between two NPCs evolve over time.

The key to keep things realistic is to generate some sort of smooth cycle. An NPC wakes up in the morning, has some daily routine, and goes home at night and sleeps. Within that routine, there can be some variation, but all humans periodically follow a certain pattern for a while, before something changes in their lives.

So given a seed matched to a particular NPC, we have already pre-written its entire life, its daily routine, its evolution over time, and relationship with its surrounding. Therefore, it doesn't need to be stored in memory, it doesn't need to exist when the player is not close to it. We can simply discard and regenerate that NPC depending on its proximity to the player.

Hooking up realistic interactions using AI

At some point, the player would like to have a conversation with the NPC. This could pause a problem if everything the NPC does is pre-determined.

First of all, we're interrupting the NPCs routine. Furthermore, we can't have a real conversation if the NPC is pre-determined to say the exact same thing.

To address that, we can bend a few rules:

• As the player interacts with the NPC, we can break its routine and overwrite a new temporary routine. Let's say the NPC was supposed to catch a train, but it misses it due to us holding up that NPC for a conversation. Temporarily, the game engine can store that information for that particular NPC, then once the conversation is over, play catch up with where the NPC is supposed to be (It could re-arrange the NPC to take the next train, or just skip that for one day and just go back to the regular routine the next day).

• When going through the conversation, we can simply start by injecting the NPC's background information into a ChatGPT like AI. Given that background, the AI is able to respond as the NPC.
  We have all that background information simply because everything about the NPC is pre-destined, so we know where the NPC went the day before, who the NPC met, what color of shoes the NPC wore, etc...

This is an example of conversation with ChatGPT, which illustrates the idea:

Imagine you're a waitress at a restaurant. Your name is Wendy. You've had a rough day, you hate your job, you broke up with your boyfriend, you love horror movies. I'm having a conversation with you.

"Hello, what is your name?"

ChatGPT
Hey there, I'm Wendy. Welcome to [Restaurant Name], where the food's decent, the pay sucks, and the drama never ends. What can I get you?

User
I'd love to have some coffee. You seem to have a rough day, how are you?

ChatGPT
Ah, just another day in paradise, you know? sarcastically But hey, at least there's coffee. pours coffee So, what brings you here today? Just passing through or are you a glutton for punishment like the rest of us regulars?

User
Wow, you sound quite cynical. Tell me a bit more.

ChatGPT
Cynical? Nah, just seasoned, I guess. Been slingin' plates and pouring drinks for longer than I care to remember. It's not all bad, I suppose. Gives me plenty of time to indulge in my love for horror movies. You ever watch any? There's something therapeutic about diving into a good scare after dealing with the daily grind. Helps me forget about the endless parade of problems waiting for me outside these walls, if only for a couple of hours.

So using any proper AI agent, we can inject the background information into an initial prompt and have the AI pick up given those info and memory of the NPC. From there, we can generate a realistic conversation that reveals a bit about the NPC's life.

While this sounds all too theoretical, I am convinced that it is possible to generate an infinite open world with that technique, which could pretty much mimic our universe. But this poses an interesting philosophical question...

Are we in a simulation?

If indeed it is possible to create such a universe using this seeded random generation method, then perhaps the world around us is a simulation generated using that method. This would bring a terrible implication regarding our reality.

Imagine that this whole world is a simulation around only one person, perhaps that person is you, the reader of this post. Then it would mean that everything outside of your vicinity... does not physically exists. Everything is destroyed and re-generated to present to you only what you see, feel, hear. That means that pretty much everyone around you stops existing as soon as you stop looking at them. They are discarded, they simply become a random formula applied over time, waiting until you're looking at them again to restore its value.

But then what about your affect on the world?

Well, the simulation can still account on your actions in the world, storing their results. But the simulation doesn't really have to change everything because of you. Everything in life is temporary. Things get forgotten, wounds heal over time, everything lives and die, and at that point, the data that needed to be kept for a while can be discarded, and everything goes back to following the cycle of random formulas dictating the world.

It means that at the end, after a long time, no matter what actions you do, everything will end up going back to following a pre-destined path, so that any action you made, any trace of your existence, will have no effect on the course of history whatsoever.

Everything is written in advance, and no matter how we change it, it will always get back to the path that was written, a formula following a random generator. This lets the simulation discard anything it stores in memory... it's much more economical for it.

That's how I see things... as far as building a realistic infinite open world universe. But knowing that nothing will matter in the far future, let's just focus on the present when things do matter. Let's build this awesome game engine, and see what kind of wonderful open world RPGs we can create from it.

I'll leave you to sharing some of the projects I've worked on in the past, or the current one, relating to this concept of infinite open world.

Some past relevant projects

Musée

Musée generates walls randomly using a random seed based on position. It extracts images from a continuously growing list to be shown on the wall, which are images of cats generated by AI.

Ludum Maze

Ludum Maze is an old project in which a giant 3D dungeon that displayed entries of Ludum Dare on walls. You could click on the entry and it would take you to the game. Seeded random mapping to a list of game was used for this. As a result, this infinite dungeon would include all 2500 games that were submitted (even some associated videos).

Penguin Quest

Penguin Quest

As I mentioned, this game uses random generation for the initial setup of tiles in the game. I then manually moved them around to design the actual world of the game.

https://jacklehamster.itch.io/penguin-quest

Dok Engine

This is the current open source game engine in development which will allow generation of infinite open worlds.

https://github.com/jacklehamster/bun-engine