Map Generator

[Baxnie]

Hello,

There's been a while since I don't post here at OTLand.
Last week I've decided to research a subject that has been my interest for years: pseudo-random map generation.

This weekend I've made the first prototype:

I've chosen Remere's Mapeditor as the base code because it already has proper map editing functions and will reduce a lot of work related to map viewing, editing, automatic borders and more. The main subject here is pseudo-random, not map editing.

The goal of this first attempt was to generate a simple island.
My research began with the Perlin Noise, which I knew it was used by other game developers to generate pseudo random levels.
This repository saved me some time because it has a single header implementation of perlin noise that could be easily integrated to Remere.
By inputing a XY coordinate value to the noise function, we get a 0 to 1 value which is random, but not completely random. Changing the seed, usually using current time in seconds, we get new values for the noise function.

The first code was really simple. A 100x100 grid which each tile was assigned a noise value from 0 to 1.
Using a simple rule, we can decide what should be the ground ID for each tile.
If we think that noise is the terrain elevation and 0.3 means the sea level, we could say:
0.0 <= noise < 0.3 means 'water'
0.3 <= noise < 0.8 means 'grass'
0.8 <= noise < 1.0 means 'mountain'

Using the Remere's borderize function I thought that the first result would show something nice.



But it was garbage.

So I've added a simple window so I could play with the noise parameters.



X and Y are the top left coordinates where the map will be generated.
Width and Height are the size of the generated map.
Scale is a factor multiplied by each tile coordinate. We could say that this is the noise frequency value.
Octaves are the number of times that the noise function is called.

Spoiler: Octaves Side Note

Gotta study more, but here're my thoughts for now:
From what I've seen octaves gives how much detail the noise has. It reminds me of the Fourier Series.
So, the first time the noise function is called, it has a small frequency and high amplitude. This gives us the bottom of the sea and high ground terrains.
As we advance on the octaves, we get smaller amplitudes, but higher frequencies. This way we get the detail on the bottom of the sea and on the high ground terrains.

After some fine tuning on parameters, it improved quite a bit.



But it still doesnt look like an island. It's more like a clip from a big continent.
Thinking about an island:
- It's surrounded by water (low heights there)
- The middle of it has land, and maybe some mountains (high heights)

So, in addition to the noise, another math function could be added.
The map center is located at:
centerX = left + width / 2
centerY = top + height / 2

The radius of the island could fill the whole generated map area, so:
radius = width / 2.

Spoiler: About radius

Thinking about it, probably using a smaller percentage of the width would give better results, as we'd have a larger portion of water, making the island to be 100% surrounded by water.

So for every tile, we'd like to reduce the height value if it's far from the center and increase it near the center.
heightIncrease = 1 - distance to center / radius

Adding it to the height generated by the noise function, we start to get some nice results, which are shown in the video.



This is it for this post. I'm not sure if I'll continue researching this as it's just a hobby for now.
The goal here is not to replace the mapper, but just aid the development of new maps.
For the next post I'll probably try to generate the path of hunting caves.

 

[Sajgon]

Impressive progress just over the weekend. Keep it up! Large parts of maps are very time consuming to build and your tool could help with development for projects that wouldnt happend. IMO a goal could be you couldnt tell whats autogenerated or not. And I like the idea about caves, hunting spawns from Tibia such as scarabs, ancient scarabs, dara rotworms could be easily generated instead.

I know about a guy, Forby, who made something similar. He also made a tool converting OTMB maps to JSON and other way around, thats how he can generate maps with JSON with some help. If you don't know about him you can find his work here and look into the code.

GitHub - Inconcessus/OTMapGen: Uses random noise to generate realistic OTBM terrain with auto-bordering.

Uses random noise to generate realistic OTBM terrain with auto-bordering. - Inconcessus/OTMapGen

github.com

There is also an online version of the application you can use

Open Tibia Map Generator

Open Tibia Map Generator

inconcessus.github.io

You could also try to speak with curl for support and ideas, for example he made a tool to auto generate houses, with serveral floors.

 

[issler92]

sup

 

[Amiroslo]

Looks good, good luck

 

[XeekXeek]

This may look useless, but to me (although I am not a professional programmer), it's a lot useful if you want to make a map more dynamic and changing over the course of time (I am sure it's possible somehow).

A "Dynamic + Random" tibia server. I hope someone makes a use of this.

 

[Tony32]

Nice job
Here is another example but with placeholder sprites. Just click play and u can adjust the sliders.
Its generating the map every frame which is incredibly slow (and dumb for that matter) but you might get some ideas.
EDIT: Its apparently broken. But the scale slider works at least. Feel free to copy and work on it however you want

p5.js Web Editor

A web editor for p5.js, a JavaScript library with the goal of making coding accessible to artists, designers, educators, and beginners.

editor.p5js.org

 

[Evil Puncker]

here is a lua one:

Generating maps?

What do you think about generating areas such as surfaces or dungeons as other games did before? Imagine spawning different structures on certain places and changing it without restarting the server. All we need are good structure spawners and even greater auto-border. However, I wanted to go...

otland.net

 

[Tony32]

Would be cool if someone made a dungeon crawler/rougelike tibia game, with levels and random items, much like Enter the gungeon. Would be pretty cool tbh!

 

[kay]

Would be cool if someone made a dungeon crawler/rougelike tibia game, with levels and random items, much like Enter the gungeon. Would be pretty cool tbh!

Exactly my thought, when I saw this thread. Rogue-tibia to play alone, or even multi with friends, that would be insane.

 

[Baxnie]

After a long time I've resumed the map generator.

As said on the first post, the goal here is to generate the path of a hunting cave.
For that, I've chosen to study Cellular Automaton.
Basically we create a simple set of rules to determine the state of a Tile over several iterations.
Here, tile states are 'walkable' or 'not walkable'.
The rules are:
1) If our tile has more than 4 walkable tiles around, it becomes walkable too.
2) If our tile has exactly 4 walkable neighbours, it stays the same.
3) If our tile has less than 4 walkable neighbours, it becomes not walkable.

We setup an initial condition by filling random tiles as walkable or not walkable.
Using a fill rate of 53 percent walkable tiles and iterating 20 times yields to the following result:



It kinda looks like a cave, but its shape is quite bad.
Changing the parameters a bit, like the fill rate and the maximum number of iterations didn't result in better caves.
Searching a little on the subject, I came across this article that was really helpful: Improving procedural 2D map Generation based on multi-layered cellular automata and Hilbert curves
Basically, it suggests generating a fixed path, and then applying the cellular automaton.
I didn't really like the results of the Hilbert Curves suggested by the article, and didn't want to implement it at this moment.
So, using a simpler approach, I've generated some random points and drawn a line path between them. The image below is an example of that.



It's a bad path for a hunt, but it's something for now.
My next try probably is going to implement a Delaunay Triangulation:



For generating circular caves it'll probably give good results.

Continuing to the next step, after generating the path, cellular automaton should be applied.


It seems like a usable hunt, but it took me several tries (20+) to find this one.

As improvements here, I've thought about using Delaunay Triangulation and using Bresenham's Algorithm to plot lines.
For the next post, I still haven't decided what to do.
Maybe investigating about decoration or monster respawn.

 

[Evil Puncker]

I know someone who were interested about it back in time @zbizu

 

[kay]

@Baxnie
Thought you might be interested in this:

How do roguelikes generate levels?

Roguelikes are my favourite genre of game and Brogue [official site] is one of my favourite roguelikes. It has the genr…

www.rockpapershotgun.com

It's an interview with Brian Walker, creator of Brogue game (classic roguelike) about levels generation. It is brilliantly made and he describes it all in details step by step with animated presentations of the whole logic.
Here you can also watch his 'lecture' on the same topic:

The game is an open-source, and since it's a classic 2D with tiles (represented by ASCII) it could be easily related to Tibia map with only slight modifications. The code is also clean and well commented (pure C).

I think it's one of a great explanation how to create a good map generator with an interactive environment. Hope it may help.
Good luck with your work

 

[zbizu]

I know someone who were interested about it back in time @zbizu

I'm more interested in something that could be automated for the server purposes (either direct generation or something that can be loaded from external file without the need of user input in long run)

I recommend hunt and kill algorithm for caves. It's really solid and can work in 3d space if you alter it a little.

 

[Evil Puncker]

I've found something really interesting and wanted to post it here just in case anyone needs a future reference:

Map creator.

Custom map creator. Create a basic custom map as the basis of your own world.

rollforfantasy.com

scroll all the way down to "random map"