Minecraft mapping - Using NumPy to flatten the map

Previously, we put together some code to render a 2D array of tiles. But rendering a horizontal 2D slice of the 3D Minecraft world is not particularly helpful. Today we will use numpy to flatten the 3D terrain into a 2D map.

Essentially, we just want to cast a bunch of vertical rays towards the ground and find the spots where they meet the ground:

Note in particular that we want to allow the starting point to be in solid matter, and when it is, we don't want it to end until it first exits the solid matter and then hits the ground. This makes it easier to see relatively shallow caverns in amongst great depths of rock. In addition, we're going to allow specifying a height-field for the ray-starts. I think this will be useful later for mapping multi-level underground structures - I'm imagining either letting the user paint across the map with a "deeper" and a "shallower" brush, or calculating a starting height-field based on one or more seed points.

The blue ray doesn't hit any floor in the specified range. That's a cell that we'll either leave transparent or render some sort of "wall" texture into.

These two diagrams show different height-fields selected to catch different floors. Whereas the first image had some abrupt changes when the height-field of ray sources passed through floors, here we've avoided that by slightly changing the height-field.

That's the theory behind using a height-field here. In practice I haven't done much with the height-fields yet other than test that they work by making diagonal slices through the world.

This is the method on Volume that takes two height-fields, a low-limit one that specifies how far we let the rays go, and a high-limit one that specifies what height we shoot the rays from. It outputs another height-field of which cells contain the floors we want to render, and a Boolean mask array that distinguishes where we found floors from where we found none. Note that the input height-fields can be simple scalars - if so, they're expanded out to make height fields.

    def get_floor_heights_and_mask(
        low_limit_3d = numpy.atleast_3d(low_limit)
        high_limit_3d = numpy.atleast_3d(high_limit)

We use numpy.atleast_3d to extend the height-field (or height scalar) into a 3D array. This adds extra dimensions of size 1, and allows numpy to "broadcast" when we use it in an operation with another 3D array with large size.

        max_height = self.blocks.shape[2]
        shape = self.blocks.shape
        trimmed_shape = (shape[0], shape[1], shape[2]-1)
        cell_depth = numpy.indices(trimmed_shape)[2]

This creates cell_depth as a 3D array of the same size as the volume except one cell shallower, and with each cell having a value equal to its depth. (Actually, "depth" is a bit misleading. It increases in the upward direction. "Altitude" may have been more appropriate.)

        cell_is_selected = numpy.logical_and(
                cell_depth >= low_limit_3d,
                cell_depth < high_limit_3d)

This creates a Boolean array of the same dimensions that is true for the cells that fall within the range between our height-fields.

        selectable_substance = (
                if include_transparent
                else numpy.logical_not(

This takes all the blocks in the volume, minus the very top layer. We're going to use it in a Boolean expression shortly, so all that matters is if it's 0 or not. This method is used twice, once to search for non-transparent blocks, and again to search for partially transparent blocks. So when "include_transparent" is true, we just use the values of the blocks themselves, which will be non-zero for all cells apart from air. When "include_transparent" is false, we use a look-up table to decide whether each block is of a transparent or non-transparent type.

        potential_floors = numpy.logical_and(
                selectable_substance, cell_is_selected
This creates "potential_floors" as another 3D Boolean array, where true cells indicate that there's a block we might want to render that's within the range of the ray. But this will still select multiple cells in any given vertical column...
        potential_footspace = (
                if include_transparent
                else numpy.logical_not(
We define "potential_footspace" almost identically to "potential_floors", but it's shifted one cell upward.
        good_floors = numpy.logical_and(

Now we construct "good_floors" out of "potential_floors" and "potential_footspace", selecting all those cells in range where a solid cell has a transparent cell immediately above it. If we think back to the rays being cast, this corresponds to every point where the ray passes from air into a floor. We may still be selecting multiple cells in any given vertical column.

        floor_heights = (
                (max_height - 2) -
                numpy.argmax(good_floors[:,:,::-1], axis=2)

Here numpy.argmax does the magic. We're applying it to a Boolean array. In the case of ties, it always selects the cell with the lowest index. So if there are a mix of true and false values, it will pick the lowest index cell containing true, otherwise it will pick index 0. Since we actually want the highest index cell, we use a negative stride slice ("::-1") to vertically flip the array before the calculation.

        mask = get_cells_using_heightmap(
                good_floors, floor_heights)
        return (
                numpy.clip(floor_heights, low_limit, high_limit),

Finally we calculate the mask by checking whether the cells we finally selected were previously identified as suitable floors, and we clamp our floor heights to fall within our specified range. I've forgotten now why we need to clamp the floor heights. Perhaps that's now redundant.

I'm sorry this is a bit brief. I think I'm going to continue this once a week instead of twice, with posts on Tuesdays, because I don't think I can quite keep up the same pace, and I'm spending a lot of the time I would have used to experiment with new code just putting together the posts and their diagrams.

Please feel free to ask questions if there's anything you're curious about, or make suggestions about better ways to do things. I think there are quite a lot of bits that could be a lot more elegant, especially where the code has grown very organically and still has odd the odd vestigial appendix that has become quite redundant.

No comments:

Post a Comment