1. This site uses cookies. By continuing to use this site, you are agreeing to our use of cookies. Learn More.

Procedural Content Generation for UO [Image Heavy]

Discussion in 'Think Tank' started by Praxiiz, Nov 24, 2013.

  1. Praxiiz
    Offline

    Praxiiz Active Member

    Joined:
    Oct 22, 2013
    Messages:
    310
    Likes Received:
    87
    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
     
    #1 Praxiiz, Nov 24, 2013
    Last edited: Nov 24, 2013
    • Like Like x 4
    • Winner Winner x 1
  2. Milva
    Offline

    Admin Moderator

    Joined:
    Mar 3, 2013
    Messages:
    3,536
    Likes Received:
    389
    Wow very nice indeed! Thanks for sharing I know so many will be interested in this :)
     
  3. cmileto
    Online

    cmileto Member

    Joined:
    Nov 18, 2013
    Messages:
    173
    Likes Received:
    7
    Omg. This is really neat.
     
  4. Insanity
    Offline

    Insanity Active Member

    Joined:
    Mar 2, 2013
    Messages:
    276
    Likes Received:
    61
    Wow, rather impressive. Can't wait to see the project pumping out some unique maps.
     
  5. m309
    Offline

    Admin Moderator ServUO Developer

    Joined:
    Mar 3, 2013
    Messages:
    1,243
    Likes Received:
    130
    Great stuff Praxiiz, its definitely innovations like the ones you release and contribute that keep a 15 year old momentum chugging along.
     
  6. Hank
    Offline

    Hank Active Member

    Joined:
    Nov 14, 2013
    Messages:
    972
    Likes Received:
    152
    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!
     
  7. Xen
    Offline

    Xen Member

    Joined:
    Mar 10, 2013
    Messages:
    73
    Likes Received:
    5
    • Like Like x 2
    • Two Thumbs Up Two Thumbs Up x 2
  8. Praxiiz
    Offline

    Praxiiz Active Member

    Joined:
    Oct 22, 2013
    Messages:
    310
    Likes Received:
    87
    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.
     
  9. Xen
    Offline

    Xen Member

    Joined:
    Mar 10, 2013
    Messages:
    73
    Likes Received:
    5
    right now, my program handle the transparent water by default and transparent liquids.

    I will show you some image as soon as i can.
     
  10. Praxiiz
    Offline

    Praxiiz Active Member

    Joined:
    Oct 22, 2013
    Messages:
    310
    Likes Received:
    87
    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
    --- Double Post Merged, Nov 27, 2013, Original Post Date: Nov 27, 2013 ---
    As you can see, the Cellular Automata gets stretched quite a bit to fit a normal size map.
    stage9a.png
     
    • Like Like x 2
  11. Xen
    Offline

    Xen Member

    Joined:
    Mar 10, 2013
    Messages:
    73
    Likes Received:
    5
    #11 Xen, Nov 28, 2013
    Last edited: Nov 28, 2013
  12. Praxiiz
    Offline

    Praxiiz Active Member

    Joined:
    Oct 22, 2013
    Messages:
    310
    Likes Received:
    87
    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
     
    #12 Praxiiz, Nov 29, 2013
    Last edited: Nov 29, 2013
  13. m309
    Offline

    Admin Moderator ServUO Developer

    Joined:
    Mar 3, 2013
    Messages:
    1,243
    Likes Received:
    130
    Coming along very nicely, Praxiiz!
     
  14. Praxiiz
    Offline

    Praxiiz Active Member

    Joined:
    Oct 22, 2013
    Messages:
    310
    Likes Received:
    87
    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
     
  15. Xen
    Offline

    Xen Member

    Joined:
    Mar 10, 2013
    Messages:
    73
    Likes Received:
    5
    Maybe it should be very better if you generate altitudes in a different bmp.
    It will make your map-generation very easier.
     
  16. Praxiiz
    Offline

    Praxiiz Active Member

    Joined:
    Oct 22, 2013
    Messages:
    310
    Likes Received:
    87
    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?
     
    #16 Praxiiz, Nov 30, 2013
    Last edited: Nov 30, 2013
  17. Hank
    Offline

    Hank Active Member

    Joined:
    Nov 14, 2013
    Messages:
    972
    Likes Received:
    152
    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.
     
  18. cmileto
    Online

    cmileto Member

    Joined:
    Nov 18, 2013
    Messages:
    173
    Likes Received:
    7
    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?
     
  19. Xen
    Offline

    Xen Member

    Joined:
    Mar 10, 2013
    Messages:
    73
    Likes Received:
    5
    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 ;).
     
  20. Praxiiz
    Offline

    Praxiiz Active Member

    Joined:
    Oct 22, 2013
    Messages:
    310
    Likes Received:
    87
    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/



    --- Double Post Merged, Nov 30, 2013, Original Post Date: Nov 30, 2013 ---
    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.
     
    #20 Praxiiz, Nov 30, 2013
    Last edited: Nov 30, 2013
    • Like Like x 1
    • Two Thumbs Up Two Thumbs Up x 1
Similar Threads: Procedural Content
Forum Title Date
General Discussion Using custom contentv Apr 22, 2017
Archived Bug Reports Missing Content Aura Abilities & Monster Stealing Jan 22, 2017
Archived Bug Reports Custom Content in SmugglersLiquor Aug 15, 2016
SA & High Seas Updated SA content Dec 17, 2014
ServUO Discussion ServUO and OSI Content Question Mar 6, 2014
Windows Support SA Content Feb 16, 2014