Where to next with worldmap and new dungeon locations

A bit of a grandiose topic title, but I'd thought I open a discussion about what to do with the world map in IVAN.

About four years ago there was a memorable topic started by SquashMonster, about how to tackle some of the problems of introducing new worldmap locations and such. It is really interesting reading, particularly the bit about phase 1, and the bit about worldmap in its present form being fundamentally a gum solution. I'd like some help working out how to introduce some of these changes in a structured way.

Woah, that post was legendary indeed, and this idea sounds very promising and exciting. I'd love to help implement this but unfortunately I'm quite occupied for the next couple of weeks (at least). But after that I'm ready to turn my IVAN mode on.

Awesome. I will actually be travelling until the end of October myself, but this won't stop me from holding discussions.
Basically, I'm interested in finding out exactly what we want to get out of a functioning IVAN worldmap. Once we know what we want, then we can start to code it up.
There are heaps of things to consider, and I have been thinking about some of them.

First off, worldmap.cpp needs to be able to generate a world and populate it with dungeon locations in a way that doesn't strictly depend on shaking the box to get a continent with the right terrain types.

In the story, New Attnam is located on a warm tropical island with a climate suitable for growing bananas. Attnam on the other hand, is located in a snowy region, and the sea is meant to be frozen, so ships can’t sail from there to New Attnam. This suggests that locations have climate data associated with them.

Presently, the game generates a world based on an elevation model and temperature profile (in the z-direction and using latitude), and then hunts through all the continents of a certain size (25 < size < 1000 squares) looking for one that can accommodate all the over-world terrains (owterrains) – that is, dungeon/level locations – that it needs to.

Worldmap is broke and here's some reasons why: Presently, if we add more and more owterrains, then some bad things can happen in the code:
1. We might never find the right continent. Or we might have to wait too long for the right continent to be found. This happens because there are not enough different terrain types on the continent to support the diversity of the owterrains.
2. If a lot of the owterrains have the same ground world terrain type (gwterrain), then some of the locations can be set in the same place. In this case, they are overwritten and you will find that the number of dungeon locations on the same continent in the worldmap is fewer than you expect. In fact, some will simply go missing.

This suggests that we need to start with a list of the locations we want to put on the map, and then build up the rest of the world by using a model that is seeded by the climate data for each location.

In the plans of the original devs, they imagined other locations, cities, which the PC could visit on the worldmap. From sources we know of nine others of these locations. It is conceivable that these locations don’t need “unlocking” and that they are always available on the world map. These new cities might have their own child locations, in much the same way that Gloomy caves is a child location for Attnam. So you might pick up a quest at a particular city and that locks you into a particular quest dungeon. That is quite a lot of additional places to accomodate.

Then there is the question of how to place all these locations on the worldmap. At the moment, we have a multiplicity of continents, and all the locations appear on one continent. That is okay, because there are few locations, and the world generation only sometimes throws up a really big continent. Once we introduce more locations, then a small continent might start to feel too small.

We need to start with all the world locations (dungeons) that need to be placed on the map. Use their "climate data" to seed the map; then the build topography around this data and use that to fill in the remaining terrain types. Locations can be placed within an area using a statistical probability map, together with minimum and maximum bounds. This can be helped by making up new terrain types (gwterrain), to give the world a more natural look and feel. We want to increase the variety of terrain types and make them a little more nuanced. Like introducing mountains in places where the elevation supports this, volcanic plateaus, snowy forests and beaches.

Due to the increased number of dungeons, it will be necessary to ensure that these core locations remain accessible. We have yet another design choice; to continue using continents with a largely unperturbed wilderness, or a big Pangea continent with all-reachable squares. Continents are nice, and they are my personal preference, however they impede the PC from moving around the whole worldmap without resorting to gadgetry (belt) or magic (mushrooms). It is kind of the reason why everything is made to appear on one continent at the moment.
So a choice between:
1. Single continent with lakes and seas. New Attnam appears on a suitable island in a lake somewhere. Underwater tunnel goes under the lake. Everything is accessible from one big Gondwanaland.
2. Make an extremely sophisticated continental model that does exactly what we need. Maybe break the world up into bubble-like regions and have a continent appear in each region. Put all the locations on one large continent (800 - 1200 squares)? It would help if the continents were a round shape, rather than long, skinny ones. As part of the model, islands would be seeded in between continents and New Attnam could be placed on one of these.

So in summary:
- Dungeons/cities form part of a list, and each have their own data.
- Climatealogical data of each location provides a reference for seeding a world.
- Need to find a way of getting everything into one location: Change the world building method to one in which we start with a statistical map of dungeon locations, and topography is built around them.
- Have cities/dungeons appear in a range of terrains, for example, Gloomy Caves could be made to appear in either tundra or ice.
- Increase the number of terrain types to smooth things over.
- Terrain types have associated climate data.

What do people think of having the world built either on a Pangaea or on multiple continents?
How should the player access other locations on the map? Should they be in one place?
Should there instead be boats?
Am I overthinking things and should there just be magical transport and one dungeon per continent?

I say multiple continents. Makes things more interesting. Ideally you'd want an algorithm to only have so many cities on a continent so large, then have the rest placed on other continents. You could have simple bridges or gates to connect them, no monsters or loot so as to not to increase game length.

I'd also say more continents.

For one thing, you have a guaranteed source of permanent levitation, so you are able to get anywhere on the whole worldmap, even over the sees. For another, magical portals and/or bridge tiles for worldmap are nice possibilities how to connect several continents.

However, I'd really like to see the continents to become more island-like in appearance and more round, as well, with lakes and wider swathes of oceans in between, so that it's not that easy to fly from one continent to another.

Also, it would be incredibly nice to integrate worldmap encounters, so that you could be ambushed while travelling over the wilderness. I've seen some ideas as to the makeup of these encounters based on the tile biome on the wiki, but adding several more encounter types, like bandit groups and roving undead, would be ideal in my opinion.

That would require the generation of one-off map for the encounter, which could be also used to enable the player to enter the wilderness on his own. Basically, while travelling, you could be both forced into small scale map by an encounter, with some hostile creatures generated for you to fight, or you could enter (by '>' with no dungeon on the current tile?) the wilderness map, with no items, but some neutral animals and either trees, snow or sand (depending on biome) generated.

I love, love that last idea red_kangaroo.

I think being able to enter the wilderness would be awesome. Just a lot of wild creatures, like you said, very few items you can collect, but a good source of food, water, training your weapon skills, etc. And maybe some secret things to discover if you're lucky.

I also agree with everyone about multiple continents. The belt of levitation is guaranteed, yes, but I think most people who just play the game without visiting the forums or Wiki will have a hard time discovering it. So I think there should be one larger continent with Attnam and most of the worlds. Then a few smaller continents with various ways of getting there. Maybe the belt can only take you a few tiles over the ocean and if the continent is too far away it can't take you there and you have to use a portal or ship instead.

Ok, so we pretty much agree we like continents. Continents are certainly fairly unique to IVAN, as other roguelikes tend to have a single Pangaea to explore; I'm thinking of Dwarf Fortress, ADOM and the like.
But we need to balance this with being able to reach all the core locations in each game. Say we've done most of the dungeons, but the player would like to reach a specific dungeon that he has not explored yet. It would be bad design if that dungeon was on the other side of the map, in a remote location on a hard to reach island somewhere. It still strikes me that most of the locations need to be concentrated in a subregion of the map, say a square 32x32 (1024 squares - roughly the size of the largest continent allowed by the generator when looking for a place to put Attnam.
So to simplfy matters, I would go for a single continent in the middle, where you can find core locations, and the new world generator optimizes this continent to accomodate them. Then the generator creates every other continent.
Actually, as I write this, I think I've got it: Each dungeon/city location specifies whether it can be found on the main continent (Attnam, GC etc) or whether it can be found on another continent (next nearest continent).
Then the world generator places these locations on the map and generates these continents accordingly. After that, the generator places empty continents, up to a limit of say, 25. In fact, a good way of getting around might be to place ports on each continent, so you can sail out to the story arc that you want to pursue. 50gc each way?

That way, people creating new dungeons and story arcs can segregate their work from the original, and specify all this from scripts.


I love this idea as well This would call for procedurally generated dungeons, maybe one screen big for starters. The area would be created when it is entered, and then it would need to be saved. If you visit lots of locations, then it might increase the size of the savefile a bit, but this is the 21st century so the sky is the limit

Alternatively, you can try to space cities/dungeons x to y distance apart so that they're not too cluttered or too spread out.

I've been investigating the way that the worldmap is generated in IVAN, and ported the altitude map into python and came up with this map. It smoothes out random fluctuations in the terrain to create continents and landmasses

Next I am wondering about seeding the initial random map (frame 1) using dithering. We could superimpose bubbles or circles or hexagons on the random map to seed landmasses with more roundness, and possibly use fewer steps. IVAN currently uses ten steps in its terrain smoothing routine.

EDIT: Click on the attached image to see the animated gif.

I'll post the code here:

# -*- coding: utf-8 -*-
"""
Created on Wed Aug 19 23:02:21 2015

@author: W
"""

from random import randint
import matplotlib.pyplot as plt
import numpy as np
import matplotlib.cm as cm

class worldmap:
    def __init__(self, length, width, smooth, steps):
        self.__length = length
        self.__width = width
        self.__area = length * width
        self.__AltitudeBuffer = np.zeros((width, length))
        self.__OldAltitudeBuffer = np.zeros((width, length))
        self.__DisplayMap = np.zeros((width, length))
        self.__gen_initial_map(smooth, steps)
        
    def __gen_initial_map(self, smooth, steps):
        for x in range(self.__width):
            for y in range(self.__length):
                self.__AltitudeBuffer[x][y] = (4000 - randint(0, 8000))
        if smooth == 1:
            self.__smooth_altitude(steps)

    def __quantize_grid(self):
        LAND = 1
        SEA = 0
        for x in range(self.__width):
            for y in range(self.__length):
                if self.__AltitudeBuffer[x][y] > 0.0:
                     self.__DisplayMap[x][y] = LAND
                else:
                     self.__DisplayMap[x][y] = SEA

    def __smooth_altitude(self, steps):
        for c in range(steps):
            #self.show_world()
            self.__plot_landsea(c)
            for y in range(self.__length): 
                self.__safe_smooth(0, y)
            for x in range(1, self.__width - 1):
                self.__safe_smooth(x, 0)
                for y in range(1, self.__length - 1):
                    self.__fast_smooth(x, y)
                self.__safe_smooth(x, self.__length - 1)
            for y in range(self.__length):
                self.__safe_smooth(self.__width - 1, y)
        
        
    def __safe_smooth(self, x, y):
        HeightNear = 0
        SquaresNear = 0
        DirX = [ -1, -1, -1, 0, 0, 1, 1, 1 ]
        DirY = [ -1, 0, 1, -1, 1, -1, 0, 1 ]
        
        for d in range(0, 4):
            X = x + DirX[d]
            Y = y + DirY[d]
            if self.__is_valid_position(X, Y):
                HeightNear += self.__OldAltitudeBuffer[X][Y]
                SquaresNear += 1
            
        for d in range(4, 7):
            X = x + DirX[d]
            Y = y + DirY[d]
            if self.__is_valid_position(X, Y):
                HeightNear += self.__AltitudeBuffer[X][Y]
                SquaresNear += 1
        
        self.__OldAltitudeBuffer[x][y] = self.__AltitudeBuffer[x][y]
        self.__AltitudeBuffer[x][y] = HeightNear / SquaresNear
        
        
    def __fast_smooth(self, x, y):
        HeightNear = 0
        DirX = [ -1, -1, -1, 0, 0, 1, 1, 1 ]
        DirY = [ -1, 0, 1, -1, 1, -1, 0, 1 ]
        
        for d in range(0, 4):
            HeightNear += self.__OldAltitudeBuffer[x + DirX[d]][y + DirY[d]]
        for d in range(4, 7):
            HeightNear += self.__AltitudeBuffer[x + DirX[d]][y + DirY[d]]
        
        self.__OldAltitudeBuffer[x][y] = self.__AltitudeBuffer[x][y];
        self.__AltitudeBuffer[x][y] = HeightNear / 8;

    def __is_valid_position(self, X, Y):
        return ((X >= 0) and (Y >= 0) and (X < self.__width) and (Y < self.__length))
    
    def __plot_landsea(self, step):
        destination = str(r'c:\\picts\\%d'% step) + str(r'.png')
        self.__quantize_grid()
        fig = plt.figure()
        plt.imshow(self.__DisplayMap, interpolation='bilinear', origin='lower', cmap=cm.winter)
        CS = plt.contour(self.__DisplayMap, [0, 1], cmap=cm.winter) #coolwarm is ok too [64, 32, 16, 8, 0, -8, -16, -32, -64]
        CB = plt.colorbar(CS, shrink=0.8, extend='both')
        l,b,w,h = plt.gca().get_position().bounds
        ll,bb,ww,hh = CB.ax.get_position().bounds
        CB.ax.set_position([ll, b+0.1*h, ww, h*0.8])  
        plt.savefig(destination, bbox_inches='tight')
        #plt.show()

world = worldmap(128, 128, 1, 10)

In this double-post, I can show you what a little tinkering can do with the world map generation. By biasing the noise toward the center of the map (first image), it is possible to create a single continent in the middle, with some surrounding islands (some samples of this result in the subsequent 4 images). It could be possible to use this as a way of spawning smaller, round-shaped continental landmasses elsewhere in the map by introducing random parameters for locating these landmasses. It might be a good to introduce into the preferences, settings where the player can choose whether everything appears on one landmass, or whether he chooses to have continents.

# -*- coding: utf-8 -*-
"""
Created on Wed Aug 19 23:02:21 2015

@author: W
"""

from random import randint
import matplotlib.pyplot as plt
import numpy as np
import matplotlib.cm as cm

class worldmap:
    def __init__(self, length, width, smooth, steps, GENERATE_CONTINENTS):
        self.__length = length
        self.__width = width
        self.__area = length * width
        self.__AltitudeBuffer = np.zeros((width, length))
        self.__OldAltitudeBuffer = np.zeros((width, length))
        self.__DisplayMap = np.zeros((width, length))
        self.__gen_initial_map(smooth, steps, GENERATE_CONTINENTS)
        
    def __gen_initial_map(self, smooth, steps, GENERATE_CONTINENTS):
        #create initial random map
        HYBRID = 2
        if GENERATE_CONTINENTS == HYBRID or GENERATE_CONTINENTS == 1:
            for x in range(self.__width):
                for y in range(self.__length):
                    self.__AltitudeBuffer[x][y] = (4000 - randint(0, 8000))
        if GENERATE_CONTINENTS == HYBRID or GENERATE_CONTINENTS == 0:
            #create "splodges"
            for x in range(self.__width/2):
                for y in range(self.__length/2):
                    self.__AltitudeBuffer[x][y] += (randint(0, x*y)) - 800
            for x in range(self.__width/2, self.__width):
                for y in range(self.__length/2, self.__length):
                    self.__AltitudeBuffer[x][y] += (randint(0, (self.__width-x)*(self.__length-y))) - 800
            for x in range(self.__width/2):
                for y in range(self.__length/2, self.__length):
                    self.__AltitudeBuffer[x][y] += (randint(0, (x)*(self.__length-y))) - 800
            for x in range(self.__width/2, self.__width):
                for y in range(self.__length/2):
                    self.__AltitudeBuffer[x][y] += (randint(0, (self.__width-x)*(y))) - 800
        
        if smooth == 1:
            self.__smooth_altitude(steps)
            
        print "DONE"

    def __quantize_grid(self):
        LAND = 1
        SEA = 0
        for x in range(self.__width):
            for y in range(self.__length):
                if self.__AltitudeBuffer[x][y] > 0.0:
                     self.__DisplayMap[x][y] = LAND
                else:
                     self.__DisplayMap[x][y] = SEA

    def __smooth_altitude(self, steps):
        for c in range(steps):
            #self.show_world()
            self.__plot_landsea(c, steps)
            for y in range(self.__length): 
                self.__safe_smooth(0, y)
            for x in range(1, self.__width - 1):
                self.__safe_smooth(x, 0)
                for y in range(1, self.__length - 1):
                    self.__fast_smooth(x, y)
                self.__safe_smooth(x, self.__length - 1)
            for y in range(self.__length):
                self.__safe_smooth(self.__width - 1, y)
        
        
    def __safe_smooth(self, x, y):
        HeightNear = 0
        SquaresNear = 0
        DirX = [ -1, -1, -1, 0, 0, 1, 1, 1 ]
        DirY = [ -1, 0, 1, -1, 1, -1, 0, 1 ]
        
        for d in range(0, 4):
            X = x + DirX[d]
            Y = y + DirY[d]
            if self.__is_valid_position(X, Y):
                HeightNear += self.__OldAltitudeBuffer[X][Y]
                SquaresNear += 1
            
        for d in range(4, 7):
            X = x + DirX[d]
            Y = y + DirY[d]
            if self.__is_valid_position(X, Y):
                HeightNear += self.__AltitudeBuffer[X][Y]
                SquaresNear += 1
        
        self.__OldAltitudeBuffer[x][y] = self.__AltitudeBuffer[x][y]
        self.__AltitudeBuffer[x][y] = HeightNear / SquaresNear
        
        
    def __fast_smooth(self, x, y):
        HeightNear = 0
        DirX = [ -1, -1, -1, 0, 0, 1, 1, 1 ]
        DirY = [ -1, 0, 1, -1, 1, -1, 0, 1 ]
        
        for d in range(0, 4):
            HeightNear += self.__OldAltitudeBuffer[x + DirX[d]][y + DirY[d]]
        for d in range(4, 7):
            HeightNear += self.__AltitudeBuffer[x + DirX[d]][y + DirY[d]]
        
        self.__OldAltitudeBuffer[x][y] = self.__AltitudeBuffer[x][y];
        self.__AltitudeBuffer[x][y] = HeightNear / 8;

    def __is_valid_position(self, X, Y):
        return ((X >= 0) and (Y >= 0) and (X < self.__width) and (Y < self.__length))
    
    def __plot_landsea(self, step, maxsteps):
        destination = str(r'c:\\picts\\%d'% step) + str(r'.png')
        self.__quantize_grid()
        fig = plt.figure()
        plt.imshow(self.__DisplayMap, interpolation='bilinear', origin='lower', cmap=cm.winter)
        CS = plt.contour(self.__DisplayMap, [0, 1], cmap=cm.winter)
        CB = plt.colorbar(CS, shrink=0.8, extend='both')
        l,b,w,h = plt.gca().get_position().bounds
        ll,bb,ww,hh = CB.ax.get_position().bounds
        CB.ax.set_position([ll, b+0.1*h, ww, h*0.8])  
        plt.savefig(destination, bbox_inches='tight')        
        if step == 0:
            plt.show()
       
# useage: worldmap(XSize, YSize, use smoothing? [Y/n], number of steps in smoothing, 0=single island 1=lots of continents 2=continent with islands)
world = worldmap(128, 128, 1, 10, 2)

Awesome! But where's the gif?

You mean you wanna see a gif of the algorithm making an island?

Yeah the big island lol. Also is it possible to enforce that there's a certain # of medium sized islands? Or are we ok with the other islands all potentially being tiny

Nice.

BTW, how does biome distribution on the worldmap work? Does it take anything like climatic zones (ie. snow near the map edges, New Attnam and its jungle in the middle) into account?

Well, what we could do is seed a bunch of smaller versions of this continent on the worldmap, amongst the noise, and we would end up with rounded landforms. This would help to reduce the likelihood of a sprawling Pangea that we sometimes see in conventional IVAN map generation.
Attached is an animation of a single island-continent being generated (as before click on the image).

Yeah in the code, IVAN seems to take elevation above sea level, and latitude into account. Polar regions take on cold terrain types, while equatorial ones tend to yield desert and jungle types. High elevation areas still end up with snow caps

Hi all! Further to some of the work above, I've been doing some more investigating lately, muddling around with Python. To satisfy my cravings for more visual feedback, I decided to make use of some rather more powerful plotting features available in Python, and create 3d maps and contour projections below.
The code to generate the plots is a little bit clunky, but it seems to do the job. It can save the output to png format in a subfolder.

I attached an animated gif showing how IVAN smooths the initial random field, producing smooth features of varying elevation that resemble geographical features; mountains, seas, sometimes lakes (valpuri.gif).
I caused the plots to render the land and sea green and blue to distinguish between the two (see other attached png images).

The (ugly looking) code is in a specialized repository on GitHub.

Digging the (underwater) tunnel from both ends, I decided I would spend some time picking over some of the outstanding previous work of one Ketmar, a.k.a. vasiliy (from this forum).
I hoisted in a bunch of code from his repository by hand and compiled it. It worked, so I have advanced a pull request to include the changes.
He was able to split the dungeon files, and a whole lot more besides. I only thought to split the dungeon.dat files at this stage as it is the only part that is relevant to the world map.
I hope there are no serious errors as a result

From here, I propose to cause IVAN to place generic, mostly empty worldmap locations - 64 in total - as placeholders whereby someone can come along with no compiler, and create a new dungeon using only the script files. The new dungeon would simply fill in an available empty location slot.

EDIT: The locations would only populate the map once they are non-empty

Very nice. I like the idea of having the 64 locations so that non-coders can contribute more easily.

And that geography smoothing gif is fascinating. Is that the original devs' worldmap that it's charting or is that with your changes in?

That's the original devs' worldmap (:

So we've gotten to phase 2 have we? Anyone can create a dungeon of their own?

I like the sound of this!
I've had a particular kind of dungeon in mind, but at the same time it'd require more items/monsters.
Nothing I can't do with editing the script files but that's not helping development.

Also sounds like a good time to write up a dungeon.dat tutorial.

The latest effort is a step towards this, but creating a dungeon from script alone has not been implemented yet, but this is the next step. So yeah, not phase 2 just yet, but we will get there shortly.



Creating you own dungeon is time well spent, and counts as development. Azba, if you feel like starting on an idea for a dungeon, then please do so. If you need features added into the code to give the dungeon that x-factor, then by all means deliver me your specifications.

I'm excited about writing some practical dungeon building tutorials on the wiki, and perhaps explaining some of the features like randomization and the difficulty curves. Maybe even some calculator tools on the wiki?

I am going to follow SquashMonster's suggestion of creating alternate dungeons arcs which you can opt into by choice. Using the encrypted scroll can be the key to enabling this.
Think of Attnam and Gloomy Caves as parent and child locations respectively. In Attnam, you hand over the encrypted scroll, and this lets you find Gloomy Caves on the map, and the scroll disappears. Consider a new set of parent and child locations, let's call them the City of Rihajab and Crimson Ziggurat. You hand over the the encrypted scroll to the municipal authorities in Rihajab, who thank you for contributing to their military intelligence, and who reveal the location of Crimson Ziggurat, which they say you can have for your dominion, if you can defeat the ultimate evil residing there... and so forth.
I'm not a good writer, anyone who played CLIVAN can attest to that. But I just want to illustrate the possibility of using the encrypted scroll to lock out the other dungeon locations in a structural way, until a more general way of doing this can be implemented.

I do have a couple of dungeon ideas in mind from some years ago, but I'm going to need more than a tutorial. This tower idea was mine, you see.

I remember the tower idea! I like the risk posed by having trapdoors you can fall through.

I've been scratching around in the script engine and the database today, the goal being to move the gwterrains and owterrains into script files. Not much luck after having created a rat's nest of code. I pulled it all out again by stashing it. I really wish the devs had implemented a lua script engine or some such, instead of the bespoke "traction engine" we have serving us today...