Find rectangles on the height map

Post Reply
twahm
Member
Posts: 14
Joined: Tue Sep 12, 2017 18:11
GitHub: twahm
IRC: twahm

Find rectangles on the height map

by twahm » Post

I am currently developing a mod that creates mazes and to put them on the map I need to be able to identify a flat terrain of the correct size, this is what I have:

Code: Select all

minetest.register_on_generated(function(minp, maxp, seed)
  local heightmap = minetest.get_mapgen_object("heightmap")
  local size = maxp.x-minp.x+1
  for z = 1, size do
    for x = 1, size do
      local y = heights[(z-1)*size+x]
      local pos = {x = minp.x+x-1,y = y,z = minp.z+z-1}
    end
  end
end)
Currently I only have the height map but I do not know how to find the rectangles inside it, any ideas?

hajo
Member
Posts: 606
Joined: Thu Oct 13, 2016 10:45
Location: DE
Contact:

Re: Find rectangles on the height map

by hajo » Post

twahm wrote:developing a mod that creates mazes .. need flat terrain of the correct size.. any ideas?
mg_villages does that for placing villages on the map, so go and look how it is done there.

Sokomine
Member
Posts: 4276
Joined: Sun Sep 09, 2012 17:31
GitHub: Sokomine
IRC: Sokomine
In-game: Sokomine

Re: Find rectangles on the height map

by Sokomine » Post

hajo wrote: mg_villages does that for placing villages on the map, so go and look how it is done there.
That's partly right. mg_villages needs suitable flat terrain as well. Trouble is: There isn't enough of that around. Thus, mg_villages cheats. It takes the landscape and flattens it so that villages can be placed. That way it is pretty independent of the actual mapgen and may work with almost all ones. With singlenode/air, you'll get floating islands with villages. With mapgens with extremely high mountains, you'll sometimes get villages more or less inside a mountain that turned out to be too high.

Based on what I've seen of most mapgens I'm afraid the search for a suitably large flat terrain will almost always be fruitless - unless the mapgen is a flat one or the maze is so trivial that the player will get lost searching for the maze instead of inside it. But that might not matter too much. Mazes are usually 2-3 nodes high (plus floor/ceiling) and lage in x and z direction. Placing them somewhere underground might even be better than above ground. That way, players can't just jump on top and take a look at the maze from above. The only real problem remaining would be to create an entrance that players passing by would actually notice.
A list of my mods can be found here.

twahm
Member
Posts: 14
Joined: Tue Sep 12, 2017 18:11
GitHub: twahm
IRC: twahm

Re: Find rectangles on the height map

by twahm » Post

But then how can I calculate the place to flatten, it can be easily determined when it is an ocean but for example a river or construction of other mods, how can I determine where these places are so as not to damage them?

Sokomine
Member
Posts: 4276
Joined: Sun Sep 09, 2012 17:31
GitHub: Sokomine
IRC: Sokomine
In-game: Sokomine

Re: Find rectangles on the height map

by Sokomine » Post

twahm wrote: But then how can I calculate the place to flatten, it can be easily determined when it is an ocean but for example a river or construction of other mods, how can I determine where these places are so as not to damage them?
You can't really. At least not fast and well enough to matter. Place your maze below ground where you want it to be regardless of the terrain. Depending on the size of your maze, you can eitzer add it by using the functions for schematics (probably easiest) or by using voxelmanip. If you use voxelmanip be aware that it only generates a part of the map in each call and has an overlapping shell. Most likely schematics will be best as your maze can't grow too big anyway (would reduce fun for the player).
A list of my mods can be found here.

User avatar
Deadlock
Member
Posts: 50
Joined: Mon Aug 28, 2017 06:47
In-game: Jimmey

Re: Find rectangles on the height map

by Deadlock » Post

I have been thinking about methods to get some usable information out of the heightmap.

what might be helpful in this case would be Connected-component labeling:
it can find blobs of connected regions. e.g. areas in the heightmap that have equal or similar height.

these blobs could be further analyzed with some Feature extraction methods, like Template matching

i haven't tried any of this, so i'm neither shure if this would be fast enough, nor if the results are usefull enough.

Sokomine
Member
Posts: 4276
Joined: Sun Sep 09, 2012 17:31
GitHub: Sokomine
IRC: Sokomine
In-game: Sokomine

Re: Find rectangles on the height map

by Sokomine » Post

Deadlock wrote: I have been thinking about methods to get some usable information out of the heightmap.

what might be helpful in this case would be Connected-component labeling:
it can find blobs of connected regions. e.g. areas in the heightmap that have equal or similar height.
That's fine. It could be very helpful for placing individual houses. Those *might* just find a place where they actually fit in. Anything bigger usually won't have much success with most mapgens. They're too small-scale.
A list of my mods can be found here.

User avatar
Deadlock
Member
Posts: 50
Joined: Mon Aug 28, 2017 06:47
In-game: Jimmey

Re: Find rectangles on the height map

by Deadlock » Post

i have been playing around with an idea to identify some spots on the map that are rather flat.

i used the built-in pathfinding function to check if 3 pathes ( between the center of the mapchunk and 3 other points) are possible.
results are semi-okayish:

Code: Select all

minetest.register_on_generated(function(minp, maxp, seed)
	-- do nothing if mapblock is below 0 or above 1000
	if ( (maxp.y < 0) or (maxp.y > 1000) ) then
		return
	end

	-- get the heightmap object for the chunk
	local hmap = minetest.get_mapgen_object("heightmap")
	
	local hm_i0, hm_i1, hm_i2, hm_i3, hm_i4, heightmatch
	
	-- only testing maximum one mapchunk per column of mapchunks at a given x/z-position	
	-- check if mapchunk cotains (most of) the terrain surface
	
	-- get heightmap index at current test positions, the edges of the mapchunk
	-- hm_i = (test_x - minp.x + 1) + (((test_z - minp.z)) * 80)
	hm_i1 = 1
	hm_i2 = (1) + (((maxp.z - minp.z)) * 80)
	hm_i3 = (maxp.x - minp.x + 1)
	hm_i4 = (maxp.x - minp.x + 1) + (((maxp.z - minp.z)) * 80)

	
	heightmatch = 0
	if (hmap[hm_i1] > minp.y) and (hmap[hm_i1] < maxp.y) then
		heightmatch = heightmatch + 1
	end
	if (hmap[hm_i2] > minp.y) and (hmap[hm_i2] < maxp.y) then
		heightmatch = heightmatch + 1
	end
	if (hmap[hm_i3] > minp.y) and (hmap[hm_i3] < maxp.y) then
		heightmatch = heightmatch + 1
	end
	if (hmap[hm_i4] > minp.y) and (hmap[hm_i4] < maxp.y) then
		heightmatch = heightmatch + 1
	end
	-- if less than 3 corners of the tarrain are in this mapchunk do nothing
	-- either mapchunk contains (mostly) no terrain-surface or it is to rough
	if (heightmatch < 3) then
		return
	end
	minetest.chat_send_all("Mapchunk selected for further processing " .. dump(minp.x + 40) .. " " .. dump(minp.z + 40))
	
	-- if the edges are below sea level (0) , bail out early
	if ((hmap[hm_i1] < 1) or (hmap[hm_i2] < 1) or (hmap[hm_i3] < 1) or (hmap[hm_i4] < 1)) then
		minetest.chat_send_all("Edges below 0")
		return
	end
	
	-- check if walkable pathes exist between the center and two other points
	
	-- center point (minp.x + 40) / (minp.z + 40)
	hm_i0 = (41) + (40 * 80)
	-- point 1 (minp.x + 40) / (minp.z + 60)
	hm_i1 = (41) + (60 * 80)
	-- point 2 (minp.x + 40) / (minp.z + 20)
	hm_i2 = (41) + (20 * 80)
	-- point 3 (minp.x + 20) / (minp.z + 40)
	hm_i3 = (21) + (40 * 80)
	-- if the testpoints are below sea level (0) , bail out early
	if ((hmap[hm_i0] < 1) or (hmap[hm_i1] < 1) or (hmap[hm_i2] < 1) or (hmap[hm_i3] < 1)) then
		minetest.chat_send_all("Testpoints below 0")
		return
	end
	
	-- find path between center and point 1
	local path1 = minetest.find_path({x = (minp.x + 40), y = (hmap[hm_i0] + 1), z = (minp.z + 40)}, {x = (minp.x + 40), y = (hmap[hm_i1] + 1), z = (minp.z + 60)}, 24, 2, 2, "A*_noprefetch")
	-- no path found, end
	if (path1 == nil)  then
		minetest.chat_send_all("Path 1 failed")
		return
	end
	-- find path between center and point 2
	local path2 = minetest.find_path({x = (minp.x + 40), y = (hmap[hm_i0] + 1), z = (minp.z + 40)}, {x = (minp.x + 40), y = (hmap[hm_i2] + 1), z = (minp.z + 20)}, 24, 2, 2, "A*_noprefetch")
	if (path2 == nil)  then
		minetest.chat_send_all("Path 2 failed")
		return
	end
	-- find path between center and point 3
	local path3 = minetest.find_path({x = (minp.x + 40), y = (hmap[hm_i0] + 1), z = (minp.z + 40)}, {x = (minp.x + 20), y = (hmap[hm_i3] + 1), z = (minp.z + 40)}, 24, 2, 2, "A*_noprefetch")
	if (path2 == nil)  then
		minetest.chat_send_all("Path 3 failed")
		return
	end
	
	-- still here, so found something
	minetest.chat_send_all("Found something at " .. dump(minp.x + 40) .. " - " .. dump(minp.z + 40))
	for i,v in ipairs(path1) do
		minetest.place_node({x = v.x, y = v.y, z = v.z}, {name="default:meselamp"})
	end
	for i,v in ipairs(path2) do
		minetest.place_node({x = v.x, y = v.y, z = v.z}, {name="default:glass"})
	end
	for i,v in ipairs(path3) do
		minetest.place_node({x = v.x, y = v.y, z = v.z}, {name="default:bronzeblock"})
	end
end	
)

User avatar
Hybrid Dog
Member
Posts: 2828
Joined: Thu Nov 01, 2012 12:46
GitHub: HybridDog

Re: Find rectangles on the height map

by Hybrid Dog » Post

You can test the heights along the 2d Hilbert Curve:
https://en.wikipedia.org/wiki/Hilbert_curve

Code: Select all

void get_hilbert(int *curve, int a)
{
	curve[0] = 0;
	curve[1] = 1;
	curve[2] = a + 1;
	curve[3] = a;
	int step = 0;
	int sidelen = 2;
	while (sidelen < a) {
		int cnt;
		switch (step) {
		case 0: // rotate right, write down
			cnt = sidelen * sidelen;
			for (int i = 0; i < cnt; ++i) {
				int x = curve[i];
				int y = x / a;
				x %= a;
				curve[cnt + i] = (x + sidelen) * a + y;
			}
			break;
		case 1: // mirror right, write right
			cnt = sidelen * sidelen * 2;
			for (int i = 0; i < cnt; ++i) {
				int x = curve[i];
				int y = x / a;
				x %= a;
				curve[2 * cnt - i - 1] = y * a + 2 * sidelen - x - 1;
			}
			sidelen *= 2;
			break;
		case 2: // rotate left, write right
			cnt = sidelen * sidelen;
			for (int i = 0; i < cnt; ++i) {
				int x = curve[i];
				int y = x / a;
				x %= a;
				curve[cnt + i] = x * a + y + sidelen;
			}
			break;
		case 3: // mirror down, write down
			cnt = sidelen * sidelen * 2;
			for (int i = 0; i < cnt; ++i) {
				int x = curve[i];
				int y = x / a;
				x %= a;
				curve[2 * cnt - i - 1] = (2 * sidelen - y - 1) * a + x;
			}
			sidelen *= 2;
			break;
		default:
			exit(EXIT_FAILURE);
		}
		step = (step + 1) % 4;
	}
}

‮‪‮
‮‪‮
‮‪‮
‮‪‮
‮‪‮
‮‪‮
‮‪‮
‮‪‮
‮‪

User avatar
Deadlock
Member
Posts: 50
Joined: Mon Aug 28, 2017 06:47
In-game: Jimmey

Re: You can test the heights along the 2d Hilbert Curve

by Deadlock » Post

interesting idea.
how would you decide if the area is "flat" after you measured the heights along the curve?

twahm
Member
Posts: 14
Joined: Tue Sep 12, 2017 18:11
GitHub: twahm
IRC: twahm

Re: Find rectangles on the height map

by twahm » Post

My maze is bigger than a chunk so this does not work, anyway thanks I think I'll make them look underground because on the surface they would take up a lot of space

hajo
Member
Posts: 606
Joined: Thu Oct 13, 2016 10:45
Location: DE
Contact:

Re: Find rectangles on the height map

by hajo » Post

twahm wrote:My maze is bigger than a chunk
Just pave over an area of water.

User avatar
Deadlock
Member
Posts: 50
Joined: Mon Aug 28, 2017 06:47
In-game: Jimmey

Re: Find rectangles on the height map

by Deadlock » Post

hajo wrote:Just pave over an area of water.
How would you identify an area of water bigger than a mapchunk during map-generation?

User avatar
Hybrid Dog
Member
Posts: 2828
Joined: Thu Nov 01, 2012 12:46
GitHub: HybridDog

Re: Find rectangles on the height map

by Hybrid Dog » Post

Deadlock wrote:interesting idea.
how would you decide if the area is "flat" after you measured the heights along the curve?
I would test along the curve until a different height is found. The known positions with the same height then are near each other, whereas when testing line by line instead of using the curve, less positions would be found and they'd rather form a line.
I think if you go along the curve and test with a height difference threshold, e.g. 2, more positions are found, you can then take away the positions with different height than the one from the start position and get a strangely delimited flat area. You could also set the threshold depending on the position, e.g. the distance to the start position.
Deadlock wrote:
hajo wrote:Just pave over an area of water.
How would you identify an area of water bigger than a mapchunk during map-generation?
You can calculate the heightmap in lua for the mapchunks other than the current one:
https://github.com/minetest/minetest/bl ... 6.cpp#L276

‮‪‮
‮‪‮
‮‪‮
‮‪‮
‮‪‮
‮‪‮
‮‪‮
‮‪‮
‮‪

Sokomine
Member
Posts: 4276
Joined: Sun Sep 09, 2012 17:31
GitHub: Sokomine
IRC: Sokomine
In-game: Sokomine

Re: Find rectangles on the height map

by Sokomine » Post

Deadlock wrote: i have been playing around with an idea to identify some spots on the map that are rather flat.
I'm not sure if pathfinding is the best way to go here (speed?). I like your connected-component labeling idea more as it might be more versatile.

Back when I wrote the integration of the villages into the landscape, I did consider using the hightmap. It was pretty new back then and didn't always work in all combinations. But mostly, entire villages consume too much space to truely be integrated into existing landscapes.

The situation is quite diffrent for individual houses placed randomly on the map. My random_buildings mod (now deprecated) more or less created a few walls as a socket for a lumberjack house. That did work to a degree. The lone houses in mg_villages use the same method as the villages do. Some houses are on too steep hills, while others lie in deep holes - neither of which looks particulary realistic on that scale. Of course quite a lot of houses are placed in an acceptable way as well.

If you take the heightmap and locate connected areas, you can modifiy the terrain so that it will still look good afterwards. Paramats highlandpools mod might also profit from such a height analysis method.

Segmentation according to Deadlocks algorithm (=colors) plus a very simple and fast detection of potential candidates for houses of a size of 5x5 (marked with mese; note that many of the candidates are not really small enough; the goal was to reduce their amount, not a perfect list yet):
Image
Attachments
detectheight.jpg
detectheight.jpg (195.97 KiB) Viewed 967 times
A list of my mods can be found here.

ShadMOrdre
Member
Posts: 1118
Joined: Mon Dec 29, 2014 08:07
Location: USA

Re: Find rectangles on the height map

by ShadMOrdre » Post

Two different ideas come to mind.

The first is to use a sample size. Rather that look at each node in a given area, use a sampling of the area to find suitable flat terrain. Example would be, assuming starting position of 0,0 for simplicity, and searching for an area of size 200, instead of looking at each of the 200x200 nodes to determine height, why not use every tenth node, so instead of traversing 40000 nodes calculating height for each one, you'd only have to traverse 400 nodes within the searched area. This should be considered for some of the code examples provided in previous posts.

Another method is to use algebraic slopes. m-(y2-y1)/(x2-x1). This provides a gradient between any two nodes. Search area is configurable, so you could find an area of size 10, 100, 1000 or even greater. In this above formula, y still equals height difference, while x equals, not the x axis of Minetest, but the distance between any two x,z coordinates on the map. Again, assume center position of searched area at 0,0. Using only the two 45degree diagonals and the two horizontals, you'd only need to calculate 4 slopes to find a suitable rectangle. As long as the slope between two points is flat enough, any deviation in between could be accommodated. It wouldn't really matter if there is a large steep mountain in the middle, because the edges of the square give you the "flat" area. Any "mountain" in the middle can be flattened, or "depression" raised to meet the terrain at the edges.

Forgive me if this seems overly simple, but I do believe that this provides for code speed as well as "solving" the problem.

Shad

User avatar
Deadlock
Member
Posts: 50
Joined: Mon Aug 28, 2017 06:47
In-game: Jimmey

Re: Find rectangles on the height map

by Deadlock » Post

Wow this whole thing gets quite interesting. It is seriously drawing me away from what i should be actually doing.
Hybrid Dog wrote:I would test along the curve until a different height is found. The known positions with the same height then are near each other, whereas when testing line by line instead of using the curve, less positions would be found and they'd rather form a line.
I think if you go along the curve and test with a height difference threshold, e.g. 2, more positions are found, you can then take away the positions with different height than the one from the start position and get a strangely delimited flat area. You could also set the threshold depending on the position, e.g. the distance to the start position.
Ah, i see. So you would end up with multiple lists that contain node-positions of areas with same/close to same height. I could sort these lists by size to get the largest flat area then. And if i take the largest and smallest X and Z values in one list, i can define a rectangle that confines that area.
The question is now, how do i find the largest rectangle that is confined in that area? (Maybe the same method Sokomine used)
Hybrid Dog wrote:You can calculate the heightmap in lua for the mapchunks other than the current one:
https://github.com/minetest/minetest/bl ... 6.cpp#L276
That is really good to know.
Unfortunately i'm not good enough at c++ to transfer that to lua myself. Also does this work for every mapgen?
Sokomine wrote:I'm not sure if pathfinding is the best way to go here (speed?).
Well, most certainly not. I was just hoping to offload some processing into a built-in function. While testing it felt quite slow. Sometimes i reached the border of the generated map and had to wait a bit until mapgen caught up. When testing longer paths (distance 80 blocks) i even crashed minetest.
And eventually all you get is a note that the center of a mapchunk is probably rather flat.
Sokomine wrote: I like your connected-component labeling idea more as it might be more versatile.
...
If you take the heightmap and locate connected areas, you can modifiy the terrain so that it will still look good afterwards. Paramats highlandpools mod might also profit from such a height analysis method.
Yes, i completely agree. But Hybrid Dogs hilbert-curve method loks promising, too.
Sokomine wrote:Segmentation according to Deadlocks algorithm (=colors) plus a very simple and fast detection of potential candidates for houses of a size of 5x5 (marked with mese; note that many of the candidates are not really small enough; the goal was to reduce their amount, not a perfect list yet):
Image
That image looks amazing.
Did you write a function for that? If so, can you share it? Please!
Sokomine wrote: Back when I wrote the integration of the villages into the landscape, I did consider using the hightmap. It was pretty new back then and didn't always work in all combinations. But mostly, entire villages consume too much space to truely be integrated into existing landscapes.

The situation is quite diffrent for individual houses placed randomly on the map. My random_buildings mod (now deprecated) more or less created a few walls as a socket for a lumberjack house. That did work to a degree. The lone houses in mg_villages use the same method as the villages do. Some houses are on too steep hills, while others lie in deep holes - neither of which looks particulary realistic on that scale. Of course quite a lot of houses are placed in an acceptable way as well.
I came to the same conclusion.
The amount and type of information you need, depends heavily on your goals.
Placing smaller things will probably benefit from something like connected-component labeling.
If you need larger spaces, you're better of remodeling an area which is loosely matching your demands; the pathfinding-method is a rather poor example of that.

Anyway, i think it would be great for the modding-community to have a selection of map analysizing functions.
I'll continue to try around.

Sokomine
Member
Posts: 4276
Joined: Sun Sep 09, 2012 17:31
GitHub: Sokomine
IRC: Sokomine
In-game: Sokomine

Re: Find rectangles on the height map

by Sokomine » Post

ShadMOrdre wrote: The first is to use a sample size. Rather that look at each node in a given area, use a sampling of the area to find suitable flat terrain. Example would be, assuming starting position of 0,0 for simplicity, and searching for an area of size 200,
That's in general a good idea and may simplify things (especially in real image processing). However, mapgen already hands us the full heightmap. The area returned is usually 80x80 nodes - that is 5x5x5 blocks a 16x16x16 nodes. It can be changed in the settings to some degree. 80x80 is 6400 - so there are not too many nodes to look at. Compared to any resulting map changes it will most likely be extremly fast. Sampling may help for general terrain analysis. Embedding a 200 nodes wide structure into a non-flat mapgen will be frustrating if you really search for existing terrain and don't just adjust it.
ShadMOrdre wrote: Again, assume center position of searched area at 0,0. Using only the two 45degree diagonals and the two horizontals, you'd only need to calculate 4 slopes to find a suitable rectangle. As long as the slope between two points is flat enough, any deviation in between could be accommodated.
To make such deviations of height look natural is not so easy.
Deadlock wrote: The question is now, how do i find the largest rectangle that is confined in that area? (Maybe the same method Sokomine used)
I thought about optimization and moving a rectangle about at first. It turned out that the easiest way was to take the heightmap and count for each row and column how many flat nodes have been found in that direction up to that location. If the current row (x direction) has so far come up with enough flat nodes, and the current and (however far we want to go in x direction) columns (z direction) as well, then there's enough space. Only disadvantage is that if you search for an area of i.e. 7x11 nodes, you'll have to search for 7x11 *and* 11x7 as those are diffrent. And you'll have to adjust the rotation of your building.

The search for flat land of a given size is pretty fast and ought to be unproblematic at mapgen time. What's taking time is the setting of nodes I do for visualization. It's mostly colored clay for the segments in the first new mapchunk generated, and mese lamps for places that are at least 8 in x and 7 in z dimenson large.
Deadlock wrote: Did you write a function for that? If so, can you share it? Please!
It's all still very much work in progress. The flat land detection works well. The segmentation as such works (currently for above sea level terrain), but the handling isn't well done yet. All those neighbours and tables I play around with do make it all a bit complicated.

The current state can be found on github: fiind_flat_land.
Deadlock wrote: Placing smaller things will probably benefit from something like connected-component labeling.
The find-flat-area-algorithm doesn't use any real labeling. The labeling/segmentation is used for identifying mountain peaks and holes/sinks/valley bottoms. The experimental code identifies the mountain top, sinks it into the ground as glass, and "raises" holes one up by filling them with obsidian glass. Then the find-flat-area-algorithm runs on the modified height map and finds more places than it would otherwise find.
A list of my mods can be found here.

User avatar
Deadlock
Member
Posts: 50
Joined: Mon Aug 28, 2017 06:47
In-game: Jimmey

Re: Find rectangles on the height map

by Deadlock » Post

Sokomine wrote:The current state can be found on github: fiind_flat_land.
Thank you.

Sokomine
Member
Posts: 4276
Joined: Sun Sep 09, 2012 17:31
GitHub: Sokomine
IRC: Sokomine
In-game: Sokomine

Re: Find rectangles on the height map

by Sokomine » Post

Update: Mountain tops (orange) and bottoms of valleys (yellow) can now be detcted thanks to the segmentation. In a second step they can be lowered/raised and the newly formed mountain tops (cyan) and bottoms of valleys (magenta) detected. The resulting height maps can be searched for flat spaces of a given size.

It works on the floor of the sea as well - good if you search a place for a sunken submarine or underwater station.

The replacement of terrain with wool as indicator does take some time and may cause lag. That is expected. It's just for illustration. If you want to test it, create a new map and search for deserts or cold landscapes. It is sometimes hard to see the colored areas below a jungle.
Image
Attachments
detectheight2.jpg
detectheight2.jpg (451.81 KiB) Viewed 967 times
A list of my mods can be found here.

Post Reply

Who is online

Users browsing this forum: No registered users and 1 guest