Procedural Content Generation for UO [Image Heavy]

Praxiiz

Praxiiz

Member
I am making this thread to document the development efforts of my latest project which is a procedural Map generator for UO. It is still in early stages of development, and as the project continues to reach milestones, I will be updating this thread.

The goal of the project is to be a full map generator that will generate an entire map including:
  1. Land Masses
    • Varied Elevations
    • Mountains
      • Caves
      • Volcanoes
    • Rivers
    • Lakes
    • Varies Regions with Foliage
      • Swamps
      • Deserts
      • Forests
      • Grasslands
      • Tundra
  2. Oceans
  3. Roads
  4. Dungeons
  5. Ruins
  6. Cities

Land Mass Generation Procedure
I am loosely following an article that shows a detailed procedure for generating islands. I am applying it to continents in much the same way. See this link for more detail ==> LINK <==

Stage One: Generate Random Points
stage1.png

Stage Two: Delaunay Triangulation
stage2.png

Stage Three: Voronoi Parsing
stage3.png

Stage Four: Voronoi Polygons Only
stage4.png

Stage Five: Cellular Automata for LandShape Generation
This ascii generation should be familiar to anyone who has played any of the Rogue-like games such as Angband. This is not the procedure for Dungeons, but rather the procedure for generating caves. See this link for more detail ==> LINK <==
stage5.png

Stage Six: Translation of Cellular Automata to Voronoi Polygon Map
stage6.png

Stage Seven: Marking oceans
Having the Voronoi Polygons available on the continents will allow calculation of rivers along the edges of the polygons, and marking polygons as specific regions to later decorate with Foliage.
stage7.png


Stage Eight: View of Land Mass only with no Voronoi showing
stage8.png
 
Last edited:
Great stuff Praxiiz, its definitely innovations like the ones you release and contribute that keep a 15 year old momentum chugging along.
 
This is scary cool because of how easy it will be for non experienced people to make maps, which is good and bad.
Combined with your LMS i can imagine a Giant uo world.
Nice work, keep it up!
 
You have done a lot of work on this. I will definitely take a look and try to use as much as I can. Thank you.
 
right now, my program handle the transparent water by default and transparent liquids.

I will show you some image as soon as i can.
 
Stage Nine: Assign elevations according to distance from each shoreline.
Note: This is a zoomed in portion of the map.
I may need to do some redistribution of elevations depending on how this looks in game. Also Polygons should be drawn using fuzzy lines to improve the smoothness of shorelines.
stage9.png[DOUBLEPOST=1385605183,1385604794][/DOUBLEPOST]As you can see, the Cellular Automata gets stretched quite a bit to fit a normal size map.
stage9a.png
 
This just shows rendered elevations. I am trying to decide if I want to take the simple approach and just base mountains off elevation, or if I should use some other type of algorithm.

The upside to using just straight elevations is that it is easy to implement. Anything above a certain altitude just becomes a mountain. The downside is that the mountains will always be in the middle of the continent, since I've set elevations according to distance from the coast.

Flat continent Shapes:
stage9b.png

Rendered Elevations:
stage9c.png
 
Last edited:
Stage 10: Mountain Generation - The Easy Way
Depending on the elevation distribution, the mountains can end up taking up a large percentage of the map.

I either need to refine the mountain making process, or make it so there are many caves and mountain passes.
stage10.png
 
Maybe it should be very better if you generate altitudes in a different bmp.
It will make your map-generation very easier.
 
You bring up a really good point. Generating the map files would be much easier if I generate a separate bitmap with the elevations.

Right now I'm using a model-view-controller pattern, and the screenshots I'm providing are just the graphical representation ( a single view) of the model. I have another view that renders the model directly to map.mul files without any intermediate bitmaps.

Originally I wasn't going to release this as a stand alone application, but just a server-side set of scripts to generate maps while the server was running.

Do people want to use this as a standalone application?
 
Last edited:
I think it would be cool if you could generate a random but naturally accurate map that could be put directly into UOLandscaper. By the looks of it now the colors aren't too far off. With the separate terrain and altitude file you could get topographically natural looking hills and such. Then with the terrain file you could have natural looking forests, deserts, etc.
One example i remember reading on a forum where people discussing making maps by hand is that on one side of a very tall mountain there is a jungle and on the other side is a desert because the mountains keep the moisture from crossing into the desert that formed over time.
I actually did a simple test of copying that screenshot in post 14 and pasted it onto a landscaper altitude.bmp with the correct colors for the altitude and did the terrain by hand, it turned out nice.
 
By server side did you mean on the fly map generation? Would these be optionaly saveable? Id think if it was then it would fit both applications?
 
http://khason.net/blog/how-to-high-performance-graphics-in-wpf/

Friend maybe you could be interested in this article, it seems to use an algorithm similiar to the yours.

Maybe you could be interested to integrate your map-generator to my map-maker, in this case we could cooperate. I use WPF-MVVM pattern too.


PS. Even if your server generated a good map it will be impossible to send it to the clients at runtime, so unfortunely it could become unuseful.

It's better to make the map with a map generator, modify it with a map-editor then use it in a server ;).
 
Thank you for that article. I will read through it, it seems to have some really good ideas to make things more efficient.

I think it would be great to integrate with your existing map-maker. I will post the source code soon.

My main goal is to build a complete end-to-end map generator including map, statics, spawns, and randomized loot.

Xen said:
PS. Even if your server generated a good map it will be impossible to send it to the clients at runtime, so unfortunely it could become unuseful.
Click to expand...

I've already solved this.

http://www.runuo.com/community/resources/ultima-live-map-streamer-and-editor.71/

To view this content we will need your consent to set third party cookies.
For more detailed information, see our cookies page.

To view this content we will need your consent to set third party cookies.
For more detailed information, see our cookies page.
[DOUBLEPOST=1385842138,1385839615][/DOUBLEPOST]
cmileto said:
By server side did you mean on the fly map generation? Would these be optionaly saveable? Id think if it was then it would fit both applications?
Click to expand...
The goal is on-the-fly map generation. The maps would be saved so that a shard could reboot when it needs to. Many of the existing map applications like dragon use bitmaps to do their map generation, so it would be useful to have this as a stand alone application as well. The purpose of the application that I have now is just to be a visualization tool and testbed, which is why I haven't put any effort into how it looks.

hank said:
I think it would be cool if you could generate a random but naturally accurate map that could be put directly into UOLandscaper. By the looks of it now the colors aren't too far off. With the separate terrain and altitude file you could get topographically natural looking hills and such. Then with the terrain file you could have natural looking forests, deserts, etc.
One example i remember reading on a forum where people discussing making maps by hand is that on one side of a very tall mountain there is a jungle and on the other side is a desert because the mountains keep the moisture from crossing into the desert that formed over time.
I actually did a simple test of copying that screenshot in post 14 and pasted it onto a landscaper altitude.bmp with the correct colors for the altitude and did the terrain by hand, it turned out nice.
Click to expand...

The original article that I've been following uses watersheds to determine the biomes where the different terrain types will eventually end up. The article tries to start with a decent looking map and then works backwards. I don't know if that's the best direction to take this project. UO maps seem to be quite flat compared to real terrain.

I would certainly like to look at making naturally accurate maps, the question is how to do it procedurally.

I know some map generators use things like fractals to generate shapes and elevations, and then they use erosion to make the terrain further detailed. It seems obvious to me that there is interest in having a separate map generator that will produce bitmaps for use with other tools. I don't think that will be too difficult - but it will probably happen toward the end of the project when I get the terrain model complete.
 
Last edited:
  • Like
Reactions: Xen
Praxiiz said:
Thank you for that article. I will read through it, it seems to have some really good ideas to make things more efficient.
I think it would be great to integrate with your existing map-maker. I will post the source code soon.
My main goal is to build a complete end-to-end map generator including map, statics, spawns, and randomized loot.

I've already solved this.
http://www.runuo.com/community/resources/ultima-live-map-streamer-and-editor.71/
To view this content we will need your consent to set third party cookies.
For more detailed information, see our cookies page.
To view this content we will need your consent to set third party cookies.
For more detailed information, see our cookies page.
[DOUBLEPOST=1385842138,1385839615][/DOUBLEPOST]

The goal is on-the-fly map generation. The maps would be saved so that a shard could reboot when it needs to. Many of the existing map applications like dragon use bitmaps to do their map generation, so it would be useful to have this as a stand alone application as well. The purpose of the application that I have now is just to be a visualization tool and testbed, which is why I haven't put any effort into how it looks.

The original article that I've been following uses watersheds to determine the biomes where the different terrain types will eventually end up. The article tries to start with a decent looking map and then works backwards. I don't know if that's the best direction to take this project. UO maps seem to be quite flat compared to real terrain.
I would certainly like to look at making naturally accurate maps, the question is how to do it procedurally.
I know some map generators use things like fractals to generate shapes and elevations, and then they use erosion to make the terrain further detailed. It seems obvious to me that there is interest in having a separate map generator that will produce bitmaps for use with other tools. I don't think that will be too difficult - but it will probably happen toward the end of the project when I get the terrain model complete.
Click to expand...

just a question, so are you telling me that if you do a change in a map (so you change a lot of tiles/statics) you can send the modifications to all the clients?


Another question : Is ultima-live a client-mod?
 
Last edited:
Yes. You make the changes server side, and when a client gets near a part of the map that has been changed, the server sends the new part of the map and the client updates immediately.


UltimaLive is a client mod. It's all open source, feel free to try it out. You can look at the source to see what it's doing. Both client and server code is provided.

To install into the client, you just rename Igrping.dll to Igrping_.dll, and copy the Igrping.dll from UltimaLive into the client folder. It is a very simple install.
 
Last edited:
but... do you need to compile the source in another part or you just need to place that dll file ?
 
For the client you just place the dll file.

On the server side, there are some custom scripts you place in your customs folder.
 
Stage 12: Calculate Temperature based off Latitude and Elevation
Latitude determines initial temperature. Elevation modified it. The result is in the tropical regions of the map you end up with the higher temperatures. If there's a mountain near the equator, it reduces the temperature.

stage12a.png

Stage 13: (Not shown) Determine moisture based closeness to rivers and lakes.

Stage 14: Using Temperature + moisture, determine the Biome of each non-water polygon.

Biomes:
  1. SNOW
  2. TUNDRA
  3. BARE
  4. SCORCHED
  5. TAIGA
  6. SHRUBLAND
  7. TEMPERATE DESERT
  8. TEMPERATE RAIN FOREST
  9. TEMPERATE DECIDUOUS FOREST
  10. GRASSLAND
  11. TROPICAL RAIN FOREST
  12. TROPICAL SEASONAL FOREST
  13. SUBTROPICAL DESERT
stage12c.png

The colors are way off and very ugly. I will come back to them and pretty them up. The important thing is that you get things like snow and tundra in moist/cold areas and deserts in dry/hot areas.

stage12b.png

I still need to work on better mountain ranges. They take up way too much of the continents.

The overland map also needs roads and bridges. After that is done, I can concentrate on the task of making random cities, caves, and mountain passes. Foilage should also be an interesting task, I will probably make good use of Perlin Noise.

Then I need to section off a portion of the map for dungeon space, and dive into random dungeon creation.
 
Last edited:
cool but... snow near the desert? °°"

I think you should make it dynamic, making it follow the configurations made by the user.

It means that the user will set the configuration and your program will generate the related map.[DOUBLEPOST=1385986466,1385985471][/DOUBLEPOST]you could just make the user select the weather of the selected texture group with an integer:


Code: 
sealed Class TextureGroup
{
string _name;
int weather; // you could even make an enum
Color color;
Transitions Transitions; //important if you want to generate a right map)
int index; //very useful for hashing
//.
//.
//etc
}


In this way your program will even know what TextureGroup will be able to be insered close to the next one

for example :


Code: 
static void IList<TextureGroup> DrawNext(TextureGroup tg, int weather)
{
	return new List<TextureGroup> (tg.Transitions.List.Select(o=>o.weather <= weather +5 && o.weather >=  weather -5));
}
 
void insertColor(IList<TextureGroup> tgs, int x, int y)
{
map.insert(x,y,randomfromlist(tgs))
}

I think this stupid example could make you work pretty easier, i hope so ^^".

pratically speaking i think it's important that in your data should be present a way to give to each element a semantic association that your should be able to get. It will make your algorithm faster and easier to understand to you and to the users.
 
True, but for purposes of on the fly generic map generation, which I believe is what Praxiiz is after, the way it currently generates seems fine to me. Customization is always available after generation, whether it be to remove the snow/desert entirely, or to swap out a different sand texture - that could be left to an individuals personal taste.
 
Thank you for the suggestions on how to make semantic associations between the weather model and the textures. I appreciate your feedback. It will be useful when I get to that stage of the project.

Right now I am focusing on getting the model correct and as accurate as I can make it. I want the model to be completely decoupled from the view. This may make the code less efficient, but I can profile and optimize later after I am done experimenting on the model.

The way that I am deriving moisture right now is from the rivers and lakes, but not the ocean. The author of the original article started with good rivers and lakes and worked backwards. He doesn't use the ocean to spread moisture at all. I may take a look at improving the way this is done. I'd like to come up with a better model that would be able to produce desert islands as well as tropical islands.
Tonight I have been experimenting with a different way to generate mountains. Right now I calculate elevation based on distance from the coast, and then I calculate which polygons are mountains based on their elevation. This puts the mountains at the center of the land masses. If the elevation setting for mountains is low, then the mountains take up most of the land. The author of the original article redistributes the elevations, and I may try that at a later time.

Instead of deriving mountains from elevation, I tried to derive mountains from fake fault lines. I have no intention of building a tectonic plate simulator, and so the fault lines are by no means representative of real fault lines. To generate the fault lines, I simply started with some random points and built another Voronoi grid.

These results are using straight edges. This results in the mountain ranges being too straight and line like. I may try to use noisy edges which would make the mountains less straight. I could also make where the mountains are drawn random.


Part of the reason that it looks odd is because the elevations are now completely wrong. Not all edges point down in elevation and end at the ocean. I will need to find rivers that end on land and make lakes out of the ending polygons.

The old method seems better to me at this point, but I will continue to experiment. The old method would never have mountains directly adjacent to water.

Old Method:
stage10-png.502
 
Last edited:
Yes, I could do a random switch between the two methods. I think the real problem is that there is no correlation between the randomly generated land masses and the fault lines. I think if I was going to do the fault line approach, I would need at least a rough simulation of plates moving. I would need to generate the land masses using the plates, and then I could simulate mountain ranges being created in a more realistic way. For now, I am testing other approaches.
 
I am trying a different approach to generating land and mountains. Here are some of the results. I have not translated them to a square / rectangle map yet. That will be the next step.


experiment_globe.png

It still needs some tweaking, and I still need to decide if I'm going to keep the Voronoi grid on the flattened map.

Credit goes to this webpage ==> LINK<==
 
I've been rethinking how I'm doing the moisture and biome model. The original method was basically making mountains in the center of the landscape, and then randomly generating rivers and lakes. And based on the rivers and lakes I would calculate moisture. This really didn't yield a decent moisture model. It caused any small strips of land to be desert if there wasn't a lake or river near by. Virtually all islands were low in moisture.

Now I am looking at generating winds based off temperature (hot air rises causing a draft and thus wind), and then using the winds to propagate moisture from the ocean upward onto land. This will also let me track salinity and factor that into the biomes as well. It will also let the model have features like rain shadows.

Dwarf fortress also calculates drainage, which I am still unsure how I want to do that. The combination of temperature, moisture, salinity, and drainage will determine the biome. This will also be really important for the lumber harvesting system that I'm cooking up because it will need to know what the local biome is in order to generate trees.

Here's an early back of the napkin concept of how moisture would be calculated based on wind direction and water source:

ai22.photobucket.com_albums_b347_Praxiiz_wind_moisture_model.png
The yellow lines show where dry areas would be, blue lines show moisture propagation. Of course rivers would be generated based on moisture propagation up the side of each mountain. Lakes will likely be added, but any lakes formed by the elevation and land generation process would propagate moisture and rivers would be back calculated to flow into them.


And of course, that's based on (there are lots of others): http://deckskills.tripod.com/cadetsite/id111.html
adeckskills.tripod.com_sitebuildercontent_sitebuilderpictures_global_wind_diagram.jpg
 
This is a system that I've been wanting to write since before I started on UltimaLive. UltimaLive was a method to enable this. I haven't been actively working on this system for a while, but I have not abandoned it. RL has just been busy.

My goal is to build up a decent model of a world.

Land mass generated first including mountains and ocean.
Elevation and distance from the sun used to calculate temperature.
Temperature used to calculate wind direction.
Wind direction + temperature + ocean location are used to calculate overland moisture.
Overland moisture used to calculate rivers and lakes.
Biomes are determined by temperature + moisture + salinity.
Vegetation is determined by biome.
Moisture and temperature are modified by vegetation.
Biomes and adjusted and recalculated over time.

Minerals could also be calculated during land mass generation, or could be randomly calculated later.

Once you have this model in place, it becomes possible to randomly generate a world and minimize the odd behaviors associated with other map generating techniques.

Each voronoi polygon represents a different biome. This information is tracked a long side the map. I was planning on experimenting with the delaunay triangulation (which is currently just used to calculate the voronoi polygons) to for roads. There is a lot of research that has been put into procedural content generation. It's out there just waiting for someone to scoop it up and build an entire world with it.

In UO Landmark, they use biomes, but they don't have a solid model to back up the world. That is why you see biomes next to each other that you wouldn't expect. They do handle the cave aspects well though. Unlike other voxel games that use really optimized compression algorithms, Landmark just gives you the same harvested resource over and over unless you are harvesting one of it's generated nodes. For example, it only has to store where the caves are and where players have mined. The rest of the "space " is just defaulted. This lets them store the world in the smallest way possible. I'd like to apply this same type of thing to Ultima / UltimaLive. The issue is that the range of +/- z only goes from -128 to +128 units, and players are about 20 units high.

The other aspect of this system that I am interested in is random city generation, and dungeon generation. There are a lot of dungeon and cave generation algorithms that are proven and just need to be implemented.

Random city and building generation is a bit more tricky, but I think it's doable just using a large number of building templates generated by hand and added to a city randomly.
 
Maybe lowering the range scale for the map height so the lands are bigger, mountains more thin, and more flat terrain, then when generated, processed to scale the mountains up to allow good looking mountains.
That is the only thing i can think about to fix the mountains and curved areas.
If the areas are too curved it will be really hard to place houses, cities, and such on it :p
 
You must log in or register to reply here.

Active Shards

Donations

Total amount
$0.00
Goal
$1,000.00
View
Back