Buildings, interiors, and seeing behind things in 3/4 and isometric view

Notes compiled 2026-11-05 for Elsewhere and the Tycho study. Target: plain JavaScript on a phone, an isometric 2:1 picture at 320x180, eight inks to a frame, everything deterministic from a seed and painted into palette-indexed buffers. Sibling notes: settlements_paths_vegetation.md (where houses go in a village), styles_resolution_perspective.md (projections), world_generation.md (Watabou, Parish & Müller). This note covers how one building is made (footprint, rooms, doors, furniture, roof), how its inside is shown, and how things are depth-sorted so a figure can walk behind and inside them.

Note on sourcing: Merrell et al. 2011, Mirahmadi & Shami 2012 (which restates Marson & Musse 2010) and Bruls et al. 2000 were downloaded and read as text (mutool). Marson & Musse 2010 itself sits behind a bot wall at Hindawi/Wiley and was not read; its method is taken from Mirahmadi & Shami’s summary and from abstracts. The Fallout 2 code is from the fallout2-ce reimplementation (alexbatalov/fallout2-ce, src/tile.cc and src/object.cc), read directly. The Ultima VII code is from Exult (gamewin.cc, objs/chunks.cc, objs/objs.cc), read directly; Exult is a reimplementation, so it shows one faithful way, not necessarily Origin’s code. Other items come from fetched pages; “(search summary)” marks claims seen only in search-result summaries. Times marked “bench” were measured with buildings_sorting_bench.js beside this note: Node v26.8.1 on a 2019 Intel i9-9880H at 2.3 GHz, one thread. No phone was measured.

1. Floor plans

Takeaway

Three families: subdivide a rectangle (treemaps, BSP), grow rooms from seeds inside a footprint (constrained growth), or fill a grid with a constraint solver (WFC, as Caves of Qud does). For a small house of 3 to 7 rooms the squarified treemap with zones (public, service, private) is the simplest that reads as a real plan: one recursive pass, microseconds, rooms near square. Doors come from a room graph laid over the adjacency of the rectangles; a corridor is needed only when a required link isn’t adjacent.

Cited findings

• Marson & Musse 2010, “Automatic Real-Time Generation of Floor Plans Based on Squarified Treemaps Algorithm,” Int. J. Computer Games Technology, doi:10.1155/2010/624817. As restated by Mirahmadi & Shami: the area of each room is drawn from a distribution by its function; rooms fall into a social area (living, dining), service area (kitchen, laundry) and private area (bedrooms, bathrooms); the zone areas are summed; rooms go into a hierarchy “starting from outside”; the squarified treemap places first the top level, then the rooms inside each zone; doors are placed “based on a connection graph which is randomly produced at a previous stage based on some rules. An example rule can be expressed as bedrooms should not be connected together”; “if the rooms that are supposed to be connected are not adjacent, a procedure is applied to place a corridor,” which Mirahmadi & Shami criticize because it “wastes some space in the house.” — arXiv 1211.5842; abstract at the British Library record.
• Mirahmadi & Shami 2012, “A Novel Algorithm for Real-time Procedural Generation of Building Floor Plans,” arXiv 1211.5842. Room count and bedroom count drawn from a census joint table (e.g., P(3 bedrooms, 6 rooms) = 0.106, the single most likely pair in their Table I). Corridor rule: “all of the rooms are connected either directly or via some corridors to the living room, as the center of activities”; a corridor is cut from the overlapping rooms along a shortest path when a room that must touch the living room doesn’t. Doors “are then placed randomly at the shared walls between the rooms. The door size is fixed”; windows the same way, on exterior walls, with rules such as “a window cannot be installed in bathrooms.”
• Squarified treemaps, Bruls, Huizing & van Wijk 2000 (PDF). Lay rectangles in a row along the shorter side; keep adding while worst(row) (the highest aspect ratio in the row) improves, else fix the row and recurse on the remainder. “A decreasing order usually gives the best results.” The example in the paper turns thin rectangles of aspect 16 and 36 into near-squares. Linear in the number of rectangles after the sort.
• Constrained growth, Lopes, Tutenel, Smelik, de Kraker & Bidarra 2010, GAME-ON (record): rooms grow from seed cells on a grid inside the footprint until they meet; designers set functional constraints and adjacency; handles non-rectangular footprints and multiple floors (abstract).
• Caves of Qud builds huts, crypts and lairs with Wave Function Collapse from small PNG templates in wavetemplates/ (e.g. huts11, compound), at e.g. 40x20 cells (WaveCollapseFastModel(Template, 3, 40, 20, ...)), and maps the output colors to wall materials; villages call VillageBase.addInitialStructures. — Qud wiki, Zone procedural generation. Each generated village gets its own “architecture” among other generated traits (Qud wiki, Village, search summary). A 2024 patch fixed “partial, garbled WFC-generated buildings” (devlog): WFC can fail and needs a fallback.
• Dwarf Fortress (2010-era talk): the generator picks a town center and spreads buildings outward, respecting the wall or keep, then fills them with workshops by population need. — DF Talk #13 transcript (search summary).
• Townscaper (Oskar Stålberg): an irregular quad grid made from a hex grid split twice into quads with points relaxed; a marching-cubes-like pass places corner modules, not whole blocks; WFC picks modules by neighbors with priorities (gardens only where walls enclose an area); decoration runs after placement; windows are cut with a stencil buffer; a re-skin is “somewhere in the region of 500 tiles,” Bad North “over 300.” — Game Developer, How Townscaper works. Lesson: a building’s look emerges from corner rules on a grid of occupied cells, so roofs, arches and stairs appear without a building grammar.

For Elsewhere (inference)

• A house is a rectangle (or an L of two) of 6x5 to 10x8 tiles. Treemap by zone, then a door graph: front door into the social room, every room reachable through social or a hall, bedrooms never door-to-door. With 3 to 7 rooms it never needs Mirahmadi’s corridor search; when a required link fails, cut a one-tile hall along the longer side of the social room.
• All of it is integer work on tens of cells: well under a millisecond, so a quest can build its houses at load or as the player walks.

2. Facades and grammars

• CGA shape, Müller, Wonka, Haegler, Ulmer & Van Gool 2006, “Procedural Modeling of Buildings,” ACM TOG 25(3) (SIGGRAPH history). A shape has a scope (an oriented box); rules replace shapes with shapes; the split rule divides a scope along an axis into parts with absolute or relative sizes; the repeat split tiles a part as many times as fit; the component split turns a volume into faces, edges and points. Snap lines and occlusion queries keep windows off hidden walls. CGA extends the set grammars of Wonka et al. 2003, whose splits suited “only simple mass models” (search summary).
• (inference) At 320x180 a house wall is 16 to 40 px wide. A repeat split of “window, gap” along each wall, with the door forced onto the front, is all of CGA a pixel house needs. The grammar earns more at the scale of a street of facades seen side-on.

3. Roofs from footprints

Takeaway

A hip roof over any simple polygon is its straight skeleton raised by a slope; a gable is the same with the end edges made vertical. For rectangles and rectilinear footprints this reduces to formulas: a rectangle w x d (w >= d) has a ridge of length w - d at height (d/2)·tan(pitch), and the four hips meet it at 45 degrees in plan. Rectilinear footprints can be cut into rectangles, each roofed, then merged (Laycock & Day 2003).

Cited findings

• Straight skeleton roofs: Laycock & Day 2003, “Automatically generating roof models from building footprints,” WSCG posters pp. 81-84 (record): a hip roof is the straight skeleton (Felkel & Obdržálek 1998); gable and mansard by changing the construction (mansard uses the distance of the first split or edge event); keywords include rectilinear polygons with merge cases (search summary of the PDF).
• Weights: Kelly & Wonka 2011, “Interactive architectural modeling with procedural extrusions,” ACM TOG 30(2) (Glasgow eprint): a sweep plane grows the roof upward with per-edge profiles, a weighted straight skeleton; Java code in twak/campskeleton. Held & Palfrader 2016 (arXiv 1604.03362) note plain skeletons give only hips, “with some postprocessing, gable roofs”; additive weights give gables directly. Blender’s bpypolyskel implements Felkel & Obdržálek with cleanups “suited to a hipped roof.”
• Climate and pitch: Li et al. 2021, Science Advances 7, eabh2601 (PMC8442921): roof height-to-span ratios of about 200 surviving buildings in northern central and eastern China rose and fell with extreme snowfall over roughly 750 to 1750 CE, lagging it by about 30 years (search summary; Eos). Flat roofs concentrate in arid regions and still slope “up to approximately ten degrees” (Wikipedia, Domestic roof construction, search summary). Stilts: in Samarinda, Indonesia, residents raised stilts from 60-130 cm to 170-270 cm as floods worsened (Unhas, search summary); Assam’s chang ghar are bamboo huts on stilts lasting about five years (Dialogue Earth).

For Elsewhere (inference)

Climate presets as numbers: snow (steep gable, about 50 to 55 degrees, timber, small windows, compact footprint), temperate (hip or gable about 35 to 40 degrees, plaster and tile), arid (flat roof with parapet, adobe, courtyard or L footprint, few small windows), wet lowland (stilts of about 1 m, steep thatch hip, veranda). The pitch values are design choices consistent with the trends above, not sourced numbers.

4. Furniture

• Merrell, Schkufza, Li, Agrawala & Koltun 2011, “Interactive Furniture Layout Using Interior Design Guidelines,” ACM TOG 30(4):87 (project, PDF). Guidelines as terms of a density function: clearance (Minkowski sums of each item with its required free space), circulation (connected components of free space, from robot motion planning), conversation (seats “roughly four to eight feet apart,” facing), balance, alignment, emphasis (a focal point). Sampled by parallel-tempered Markov chains, one per GPU warp, 10,000 iterations per warp on a GTX 480; suggestions in 0.73 to 1.03 s per room. Designers preferred assisted layouts in 4 of 5 rooms (p < 0.01).
• (inference) That’s a GPU second per room: wrong for a phone at load. The guidelines become cheap rules on a tile grid: each item has a footprint and a “front” cell that must stay free (clearance); beds and wardrobes against walls, head to the wall; tables in the middle with chairs on free sides; never block a door’s inner cell; after placing, flood-fill from the door and reject an item if any free cell or other door becomes unreachable (circulation). With 3 to 8 items a room, tries with a seeded rng and that flood fill take microseconds.

5. Showing the inside

Takeaway

Two families. Separate interior maps (Stardew Valley, most JRPGs): the door is a warp; no sorting or cutaway problem, but the house’s outside and inside need not agree. In-place cutaway (Ultima VII, Fallout 1/2, The Sims, Project Zomboid, RimWorld): the inside is under the roof, and the renderer hides what’s above or in front of the player. The two classic in-place rules are a height cut (Ultima VII: hide everything above the lowest thing over the avatar’s head) and a region flood (Fallout: hide the connected roof region the player stands under). Walls in front are handled by fading (Diablo II, Fallout’s “egg”) or cutting to stubs (The Sims cutaway).

Cited findings

• Ultima VII (Exult): each time the camera actor moves, set_above_main_actor(nlist->is_roof(tx, ty, lift)), where is_roof returns get_lowest_blocked(lift + 4, tx, ty), the lowest occupied lift at or above four lifts over the actor’s feet, or 255 for open sky; the renderer then skips every object at or above that lift (get_render_skip_lift). One column test per move, whole-screen effect: step under any roof and every roof and upper floor on screen goes. — exult/gamewin.cc, exult/objs/chunks.cc.
• Fallout 2 (fallout2-ce): roofs live on a square grid at half the hex resolution (roofX = tile % 200 / 2, a 100x100 grid per elevation), 12-bit tile id plus 4 flag bits. When the player’s roof square changes, tile_fill_roof re-shows the old region and flood-fills (4-neighbor, explicit stack) the new one, setting a hidden flag on every connected non-empty roof square. So only this building’s roof goes. — fallout2-ce/src/tile.cc, src/object.cc.
• Fallout 2’s “egg”: a “translucent egg effect around player,” an art mask positioned at the player. When a wall object is drawn, per-wall flags pick a test (e.g., tileIsInFrontOf(wall, dude) and/or tileIsToRightOf(dude, wall), by the wall’s orientation); if the wall should be seen through, the part of the wall sprite under the egg’s rectangle is drawn through the egg’s intensity mask (_intensity_mask_buf_to_buf) and the rest normally, as four rectangles around it. — same object.cc.
• Diablo II: walls in front of the character go transparent; D2R’s legacy mode keeps it, its new 3D mode lost it on some walls, a complaint in the Tower and Travincal (Blizzard forum, search summary). The DT1 tile format separates orientations: 0 floor, 1-14 walls (left, upper, corner parts, door walls 8-9), 13 shadow, 14 object, 15 roof (with a roof height: “the number of pixels the sprite is drawn above the floor”), above 15 “lower walls”; floors are about 160x80 px; walls are built from 32x32 RLE blocks at most 160 wide, heights multiples of 32. — DT1 format docs. Characters are composites drawn in an order given by a per-direction, per-frame table (Castle Engine forum, search summary).
• The Sims 4: three wall modes, walls up, cutaway (“visible if they are away from the camera, and hidden if they are near the camera”) and walls down; End and Home step through them; only the floor being viewed is cut; half-walls stay up; walls touching a roof stay up “for half a tile” (EA forums, search summary).
• Project Zomboid: early cutaways were “wholesale across the entire screen,” so the building artist saw buildings sliced most of the time; a “sims-style cutaway” was then built (PZ blog, search summary). Whether a room is an interior depends on closed walls: one stray post made a room “outdoors” (Steam, search summary).
• RimWorld: roofs aren’t drawn at all in the normal view; a roof overlay shows thin and mountain roofs in two greens (Steam, search summary).
• Stardew Valley: interiors are separate locations joined by warps; “all maps require a warp” (Stardew Modding wiki, search summary). Its layers: Back, Buildings, Paths, Front (“drawn over the player when the player is north of them and behind the player when the player is south of them”), AlwaysFront (over everything, for foliage cover) (Mapping, Modding:Maps, search summary). The Front layer is how a tile game lets a figure walk behind a tree with no sorting at all: the tree’s top is a separate tile layer.
• X-ray silhouettes: no technical write-up from Supergiant on Hades was found. The common technique: draw the occluded part of the character as a flat silhouette or outline over the occluder, using a mask of where the character is behind something (GDQuest, silhouette 2D); outlines per character can overlap.
• Dithered fade: screen-door transparency discards pixels by an ordered Bayer threshold instead of blending, so it’s cheap and stays within the palette (Godot shaders: screen door, camera occlusion dither); a small matrix shows a regular “screen door” pattern.

For Elsewhere (inference)

• Use Fallout’s rule, not Ultima’s: flood the roof region (the building id under the player) so the neighbors keep their roofs. The building id is known from generation, so the “flood” is a lookup.
• Fade the roof with a 4x4 Bayer threshold over 6 to 10 frames rather than alpha: the frame stays within eight inks and the GPU stand-in needs no new blend. Front walls of the entered building drop to stubs one or two pixels tall (The Sims’ cutaway), so furniture and people inside read.
• X-ray: draw the player a second time after everything, only where a mask says something nearer covered it, in one ink (the outline ink or the coat ink) with every other pixel or a 1 px outline. Per frame that’s one extra sprite blit plus the mask test.

6. Depth sorting

Takeaway

Sorting by a key (tile x + y, or base screen y) is correct only when every object fits in one tile. Tall and multi-tile objects (houses, long walls, a tree’s crown over the next tile) break it. The general fix is a dependency graph of screen-overlapping pairs ordered by 3D box separation, then a topological sort (Lebron; Exult; Russell’s River City Ransom: Underground). Cycles are rare with blocky objects and are broken by splitting or deleting one edge. The cheaper fix used by shipped tile games is to cut big things into tile-sized slices (Diablo II’s walls in tile pieces, Stardew’s Front layer), so the key sort works again.

Cited findings

• Shaun Lebron, IsometricBlocks (page): each box projects to a hexagon whose sides are parallel to three screen axes (x, y and h = (isoX - isoY)·cos 30°), so two boxes overlap on screen only if their ranges overlap on all three. If they overlap, find a separating axis: lower x or y is behind, lower z is behind. “A box should not be drawn until all the ones behind it are drawn”: a topological sort by depth-first search. Cycles exist; split a box or clip; detect with Tarjan’s SCC. Two boxes that don’t overlap on screen have no order (credited to a reader, Slime0). No timings given.
• Exult (Ultima VII): Game_object::compare first returns 0 (“dont_care”) if the two screen rectangles don’t intersect, then compares x, y and z ranges of the 3D boxes; flat objects are drawn first; small-on-large at the same base is drawn behind. Each object keeps a dependencies set that rendering walks. — exult/objs/objs.cc.
• Andrew Russell, River City Ransom: Underground (blog, 2016): objects are heightmaps with no overhangs; “depth slices” are precomputed per y; two objects compare bounding boxes, and only if those overlap compare the slice “at the lowest Y coordinate that the two objects have in common”; overlapping pairs become directed edges; “a topological sort” orders them; cycles are SCCs (“the painter’s dilemma”), broken by deleting as few edges as possible with a modified Tarjan; rare in practice because objects are blocky and collision uses the same data. Per-animation (not per-frame) bounds stop flicker in looped animations. A full z-buffer comparison “would be very expensive.”
• Godot: y_sort_enabled: “this and child CanvasItem nodes with a higher Y position are rendered in front of nodes with a lower Y position”; a child without y-sort draws its children together at its own y; only nodes sharing a z_index sort against each other. — Godot CanvasItem docs. One point per node, so a long wall needs its origin placed with care or splitting.
• Bench (buildings_sorting_bench.js, random boxes of 1-3 by 1-3 tiles, heights 0-4): 50 objects: key sort 0.011 ms, all-pairs overlap plus DFS topological sort 0.033 ms; 200: 0.037 vs 0.26 ms (584 overlapping pairs); 1000: 0.28 vs 4.4 ms all-pairs, 1.0 ms with a 32 px screen grid to find candidate pairs. A quest-sized scene of 50 to 200 sortable things costs a quarter millisecond on the laptop; (inference) a phone at 3 to 5 times slower is still under 1.5 ms, and the static scenery’s graph can be built once, with only moving figures re-inserted each frame.

Found building the occlusion demo (measured)

• Testing overlap on sprite rectangles instead of box hexagons gave 8,209 wrong pairs over the 195 cells the walker can stand on: two boxes whose rectangles meet can separate on x one way and on y the other, and the axis tested first may be wrong. With Lebron’s hexagon test (ranges of x - y, x - z, y - z) the edges exist only where pictures truly overlap, and then any separating axis is right.
• A sprite must lie inside its box’s hexagon. A tree boxed at its trunk (±0.3) while its crown spans ±1.2 tiles made a cycle back wall, tree, inner wall; a roof boxed from the eave height (below the wall tops) tied with every wall. Fixes: tree box = crown footprint (±0.7, z to 4.4); roof box = footprint plus overhang, z from the wall tops up.
• Intersecting boxes have no separating axis. Exterior walls along x own the corners; all other walls stop half a wall short; a cut wall’s stub and upper part touch at the cut. After these, 0 wrong pairs at all 195 cells with every object in the demo.

For Elsewhere (inference)

• Static scenery (houses, trees, fences) gets a topological order once at load. Each moving figure is a small box; per frame, test it against the static boxes it overlaps on screen (a handful) and insert it after the last one it must follow. That’s O(k) per figure.
• Or slice: cut every building into one-tile-wide vertical strips (as Diablo II’s wall pieces are) and give each strip its own key; then the key sort is right for a figure that fits in a tile. Slicing costs memory and draw calls (a 6x5 house becomes about 11 strips), so the graph is better for a few big buildings.
• Bridges and second floors: give each object a z range and sort in 3D (Lebron’s z test); walking under a bridge then works as long as the figure’s box and the bridge’s box separate in z.

Open questions

• No phone timings; the sort numbers are from a laptop in Node.
• Marson & Musse 2010 was not read in full; its exact treemap-by-zone ordering and corridor procedure are from a second-hand summary.
• No primary source found for Hades’ silhouette or Eastward’s interiors.