Implementation:Google deepmind Dm control Maze Covering

Knowledge Sources	Google_deepmind_Dm_control
Domains	Reinforcement_Learning, Locomotion, Simulation_Optimization
Last Updated	2026-02-15 04:00 GMT

Overview

A greedy algorithm that computes an efficient covering of text-based maze grids with rectangular wall segments, minimizing the number of MuJoCo box geoms needed to represent maze walls.

Description

The covering module addresses a critical performance optimization for maze-based locomotion arenas. When converting a text maze grid (where '*' characters represent walls) into a MuJoCo model, naively creating one box geom per wall cell would result in potentially hundreds of geoms for large mazes, degrading simulation performance. This module computes a covering using larger rectangular wall segments that collectively span all wall cells with far fewer geoms.

The _MazeWallCoveringContext class implements a greedy algorithm that scans the text maze left-to-right, top-to-bottom. When it finds an uncovered wall cell, it expands a rectangular wall by scanning rows downward while tracking the widest contiguous strip of wall cells. The algorithm maximizes the total number of cells covered by each rectangle, then marks those cells as covered and continues. An optional make_odd_sized_walls mode forces all wall segments to span odd numbers of grid cells, which is useful for MuJoCo's texture repeating algorithm.

The public interface is the make_walls function, which accepts a labmaze.TextGrid and returns a tuple of MazeWall namedtuples. Each MazeWall contains start and end GridCoordinates (y, x) namedtuples defining the top-left and bottom-right corners of a rectangular wall segment.

Usage

Use make_walls when building maze arenas from text maze representations. The returned wall segments are used to create box geoms in the MuJoCo model. This function is typically called internally by maze arena builders such as MazeWithTargets.

Code Reference

Source Location

• Repository: Google_deepmind_Dm_control
• File: dm_control/locomotion/arenas/covering.py
• Lines: 1-138

Signature

GridCoordinates = collections.namedtuple('GridCoordinates', ('y', 'x'))
MazeWall = collections.namedtuple('MazeWall', ('start', 'end'))

class _MazeWallCoveringContext:
    def __init__(self, text_maze, wall_char='*', make_odd_sized_walls=False):
        ...
    def calculate(self):
        ...

def make_walls(text_maze, wall_char='*', make_odd_sized_walls=False):
    ...

Import

from dm_control.locomotion.arenas import covering
from dm_control.locomotion.arenas.covering import make_walls, MazeWall, GridCoordinates

I/O Contract

Inputs (make_walls)

Name	Type	Required	Description
text_maze	labmaze.TextGrid	Yes	The text maze grid to compute wall covering for
wall_char	str	No	Character that signifies a wall cell (default '*')
make_odd_sized_walls	bool	No	If True, force all wall segments to span odd numbers of grid cells (default False)

Outputs

Name	Type	Description
return	tuple of MazeWall	Each MazeWall has start and end GridCoordinates(y, x) defining a rectangular wall segment

Algorithm Details

The greedy covering algorithm proceeds as follows:

1. Scan the grid left-to-right, top-to-bottom to find the first uncovered wall cell (the "start" of a new wall).
2. From the start cell, scan rows downward while expanding the rectangle. For each row, find the longest contiguous strip of uncovered wall cells starting at the same column.
3. Track the total cells covered by the rectangle at each row depth.
4. Select the row depth that maximizes total covered cells (or, if make_odd_sized_walls is enabled, the depth that maximizes cells while keeping both dimensions odd).
5. Mark all cells in the selected rectangle as covered.
6. Continue scanning from the end of the last wall until no uncovered wall cells remain.

The solution is not guaranteed to be globally optimal, but in practice produces significantly fewer geoms than one-per-cell approaches.

Usage Examples

from dm_control.locomotion.arenas.covering import make_walls, GridCoordinates

# Given a text maze (labmaze.TextGrid), compute wall segments
# text_maze might look like:
# *****
# *   *
# * * *
# *   *
# *****

walls = make_walls(text_maze, wall_char='*')

# Each wall is a MazeWall(start=GridCoordinates(y, x), end=GridCoordinates(y, x))
for wall in walls:
    print(f"Wall from ({wall.start.y}, {wall.start.x}) "
          f"to ({wall.end.y}, {wall.end.x})")

# Convert wall segments to MuJoCo box geoms
for wall in walls:
    height = wall.end.y - wall.start.y
    width = wall.end.x - wall.start.x
    center_y = (wall.start.y + wall.end.y) / 2.0
    center_x = (wall.start.x + wall.end.x) / 2.0
    # Create box geom at (center_x, center_y) with half-sizes (width/2, height/2)

# With odd-sized walls for texture compatibility
walls_odd = make_walls(text_maze, make_odd_sized_walls=True)

Related Pages

• Implementation:Google_deepmind_Dm_control_Locomotion_Arenas
• Implementation:Google_deepmind_Dm_control_Padded_Room
• Implementation:Google_deepmind_Dm_control_Labmaze_Textures