Triangle Grids

https://kvachev.com/blog/posts/triangular-grid/

by jsnell • 4 years ago

247 42 4 years ago

axelerator• 4 years ago

Very inspiring! I just started out to play around with the wave function collapse algorithm [1]. I'm in the middle of porting it to a cube based 3d grid. And now I'm wondering what a triangle based volume presentation would look like

[1] https://github.com/axelerator/wave-function-collapse-2d

Someone• 4 years ago

How do you plan to fill 3D space with ‘triangles’?

You can’t do that with tetrahedrons. You can use triangular prisms, but IMO, that’s cheating. You can also split a cube into six pyramids with a square base and height ½, but I don’t think that’s a natural way to fill space.

Looking at https://mathworld.wolfram.com/Space-FillingPolyhedron.html, the Truncated Octahedron probably is the nicest alternative to the cube.

smegsicle• 4 years ago

Truncated Octahedron

looks to me like they fill space pretty nicely as an offset of cubes, in the same way as hexgrid is sort of an offset of squares

https://en.wikipedia.org/wiki/Bitruncated_cubic_honeycomb

jedharris• 4 years ago

From Wikipedia: The tetragonal disphenoid tetrahedral honeycomb is a space-filling tessellation (or honeycomb) in Euclidean 3-space made up of identical tetragonal disphenoidal cells.

https://en.wikipedia.org/wiki/Tetragonal_disphenoid_honeycom...

kragen2• 4 years ago

I think this question is sort of another way to phrase, "What are the crystal systems [or possibly lattice systems] other than primitive cubic?" And the answer is in https://en.wikipedia.org/wiki/Crystal_system; there are 6 or 31 answers depending on how you look at it. Or maybe the question is "What are the 3-honeycombs other than the cubic honeycomb?" which is discussed in https://en.wikipedia.org/wiki/Honeycomb_%28geometry%29 and to which there are an infinite number of answers.

Crystal systems are usually described in terms of point lattices, while you're talking about polyhedra, but the Voronoi polyhedra of the points in the lattice are the polyhedra you're looking for. (This is mentioned at the end of the Wolfram™Ⓡ MathWorld™Ⓡ article you linked.) One of my favorites is the cuboctahedral honeycomb corresponding to hexagonal close-packed crystals.

Even within cubic crystals, you could reasonably argue that face-centered cubic crystals "fill[] 3-D space with ‘triangles’".

Honeycombs do not, as I understand it, have to be periodic. In particular, any 3-D rep-tile can be used to tile space in a manner similar to the Penrose tiling, and usually the result is aperiodic. I wrote a 2-D demonstration of this process is at http://canonical.org/~kragen/sw/dev3/skitch#!ffffrrrfffffrrr....

scotty79• 4 years ago

https://mathworld.wolfram.com/RhombicDodecahedron.html

Rhombic dodecahedron looks quite nice.

And you could mix it with cube grid for artificial structures in your world.

lstodd• 4 years ago

I once did a 3d-space representation with https://en.wikipedia.org/wiki/Rhombic_dodecahedron

but in the end it turned out to be easier to just supersample everything down to cube grid, then put some n-vectors on top than to explain everyone how to calculate stuff in that grid.

Still have couple dozen ~3" cardboard ones somewhere from when I tried to understand how exactly do they stack. Made a nice lamp when stuffed with LEDs.

loupol• 4 years ago

Cool article. An excellent resource for grids of all kinds is Red Blob Games' site. It's mentioned in the article, but only with a link leading to a somewhat empty page and not this very useful one : https://www.redblobgames.com/grids/parts/

jiaaro• 4 years ago

I’m working on a triangle-grid board game, probably for playdate (wip builds: https://jiaaro.itch.io/3nclosure)

I was surprised to find play testers had a hard time internalizing the grid - e.g. making mistakes that result in losing the game in the opponents next turn.

Also, I used simple x, y coordinates for each cell with even-numbered indexes being the upward-pointing triangles and odds being the downward-pointing ones. Similarly odd-indexed rows were offset right by half a triangle to make them align properly

[edits]: added details

cragwind2• 4 years ago

I quite like triangle grids, but they definitely have more complications than squares or hexagons.

For a few years I've been working on a tri-grid RTS with buildable units: https://cragwind.com/blog/posts/triangle-text-grids/

I originally tried hexagons, but I ultimately chose triangles because they can compose into hexes and there were already so many hex-based games. First I tried a design using separate grids floating in continuous space but later switched to a complete grid-based world as it could make for a novel turn-based classic roguelike or strategy game. It's more limited than continuous space, although with tri- or hex-grids you get six rotations versus four with squares.

One difficulty with tri-grids is the poor spatial locality of triangles versus squares or hexes. For example, when calculating influence maps for AI on a triangle grid, each cell score is effectively stretched to the triangle vertices rather than representing a more consolidated or circular region (so for this purpose hexes would be ideal).

Like other grids, transforms (translation/rotation) on a tri-grid can be done with all integer math (and generally, if the game world is grid-based, everything but graphics/animations can be integer math). Rotations about a cell center are trickier (and are limited to three distinct rotations) but can be done by scaling up coordinates and then back down. I'll write up more details if anyone is interested.

0xMatt• 4 years ago

This project looks really good.

LkpPo• 4 years ago

Hello, what you could say about rotation is interesting me. I'm writing a 2D board game with a tri-grid for fun. For the moment I have only done the grid, the change of scale.

philipov3• 4 years ago

My favorite recent game with a triangle grid is Vagrus, a dark fantasy caravan management RPG. The number next to each line shows how many movement points it costs to travel that path. It makes it a little hard to see the visual style of the terrain underneath, but it functions well.

https://store.steampowered.com/app/909660/Vagrus__The_Riven_...

the_af5• 4 years ago

Thanks for pointing this game out: seems interesting, cool artwork, Dark Sun vibes, works on Linux --> autobuy.

That said, most reviews mention it's punishingly, almost unfairly difficult. I took the plunge anyway, sending my money to indie devs that want to try something new, but if I find it too difficult I'll probably end up giving up in frustration.

What was your experience with this game?

philipov3• 4 years ago

It's not an easy game, but less punishing than a game like Darkest Dungeon, because it doesn't force you to play on Ironman. You can save and reload if you need to.

wodenokoto• 4 years ago

I like how units in the screenshots have different grid sizes. One was a square another a hexagon. The way the mountains can form differently shaped peaks also looks great

swayvil2• 4 years ago

Kisrhombille grid. It's worth a look. It's free scaling, like triangles and squares. Has 6 axii. Nice.

https://en.m.wikipedia.org/wiki/Kisrhombille

https://github.com/johnalexandergreene/Geom_Kisrhombille#rea...

http://www.fleen.org/generative-art/i0.png

cragwind2• 4 years ago

Thank you for sharing this kind of grid. I've worked with that tiling before but didn't know the name of it. I like that it allows embedding a variety of shapes within the grid, but one drawback for use in a game is that the cells have more orientations and less symmetry than an equilateral tri-grid. So it may be most suitable for stylized art (see Hexels for a drawing tool that supports it).

I've prototyped the 3D equivalent, which is composed of tetrahedrons and 13 axes (I wonder if that 3D tiling has a name). The tetrahedrons aren't the same size, so it's a bit awkward to work with but might be suitable for 3D models/art.

swayvil2• 4 years ago

The term I've heard is "demiregular".

Yes it makes the map a bit ununiform and awkward. But.

Another way to use it would be to treat it as a substrate for a tesselation composed of a set of tiles. Like 2 or 5 or whatever basic shapes, all based on that awkward tessellation, arbitrarily fitted together to fill the space.

The image at that third link takes an approach like that. An alphabet of approximately 20 shapes. (A "self tiling system" I think.)

I'm not sure how useful that is but there you go

Karellen• 4 years ago

In the section "Directions and Adjacent Tiles", before it starts to consider diagonals, it says that triangle grids have 3 adjacent tiles and 6 directions of movement.

I don't follow this. Aren't 3 of the 6 directions it's considering going through the corners of the origin triangle? If so, how do those not count as diagonals? What is the definition of "diagonal" being used?

jameshart• 4 years ago

From an individual cell, there are three movements available. But there are two kinds of cell - north pointing and south pointing - and the set of three directions you can move in from each is different.

From a north-pointing triangle, you can move south, northwest or northeast. From a south-pointing triangle, you can move north, southwest or southeast.

So across the grid as a whole, six movement directions exist.

the_af5• 4 years ago

I'm likewise unconvinced by that section of the article (which is interesting to read nonetheless!).

The benefit of hexes is that every neighbor is the same. There are no "special" kind of adjacencies, like with squares or triangles, where you must decide how to consider corners, whether to allow diagonals, etc. So hexes are the only ones that don't mess up distances nor require separate kinds of adjacencies.

Also: if tracing a line from the center point of the origin triangle, some of those paths require crossing another adjacent triangle (different from the "direction" triangle). This to me signals this triangular grid is wonky for wargames/games.

klyrs• 4 years ago

I love hyperrogue, if more in concept than practice -- why settle for triangle grids when you can make a septagon grid! It's fun to get lost on a hyperbolic plane, though the gameplay itself is a little lacking. I'm hoping that somebody else will pick up the concept and do something even cooler.

citelao• 4 years ago

I thought the video was pretty, but it took me a while to find out what game it was from: Colossal Citadels. I think the blog poster works on it?

https://store.steampowered.com/app/1854570/Colossal_Citadels...

I wish the blog post just had a link to it :(

the_af5• 4 years ago

He probably does, since he wrote:

In Colossal Citadels I made walls and houses follow the triangular grid and I love how these procedurally-generated castles turned out [...]

Note in the sentence I quoted, "Colossal Citadels" is a link to http://colossalcitadels.com/ :)

alehlopeh• 4 years ago

Chinese checkers is an existing game that uses a triangle grid. Surprised the article didn’t mention that.

kragen2• 4 years ago

In the terms of the article, it uses a hex grid.

lbotos• 4 years ago

Anyone know the game on the square grid example here: https://kvachev.com/blog/posts/images/triangle-1.jpg

I thought it was advanced wars but I don't remember walker mech units?

theandrew168• 4 years ago

Appears to be Into the Breach [1].

[1] https://subsetgames.com/itb.html

the_af5• 4 years ago

It looks like Into the Breach: https://subsetgames.com/itb.html

janderson3• 4 years ago

Into the Breach. It's an excellent tactics game where each mission only has about five turns, and every move matters.

yellowapple2• 4 years ago

Another advantage of triangle grids: they work great for spherical maps, whether that sphere's mesh derives from a tetrahedron or octahedron or icosahedron. You'd need some fancier logic for movements around the edges of the "sphere's" base mesh, but once that's solved you're golden.

sparkie• 4 years ago

A really nice thing about this is there exists a continuous space-filling curve over a tetrahedron[1] where the end connects back to the start, like a Moore curve for squares. There's a clever way to use this curve to calculate the surface distance between two cells on the tetrahedron, and it works at arbitrary precision, requiring only 2-bits per granularity to identify cells. It's great for spatial indexing as you can use a quadtree.

[1] https://www.youtube.com/watch?v=pw_50szQfA0

yellowapple2• 4 years ago

That's indeed something I'm planning on using for my own very-WIP attempt at a spherical-map strategy game (except with an icosahedron instead of tetrahedron as the starting point), for those exact reasons :)

zelphirkalt• 4 years ago

A fact that I learned from some old DOS game many years ago, of which I do not remember the name: You can play "6 in a line wins" on a grid of triangles.

aidenn0• 4 years ago

This was over 20 years ago now, but some classmates of mine in high-school made an RTS, and my vague memory of the alpha version is that it used a triangle grid, but it's possible that just the terrain was generated that way.

matthewfcarlson• 4 years ago

I’ve been working on a RTS style game where the resources are the map itself. It’s mostly a simple proof of concept. But I was working with a hexagon grid but calculating all that was rather tricky. I like the idea of instead using a triangle grid. Way easier to manipulate and calculate. My thought was to basically treat it like a bunch of springs that try to reach equilibrium.

MalcolmDwyer• 4 years ago

Another interesting system is the messy organic grid from Townscaper.

https://andersource.dev/2020/11/06/organic-grid.html

personjerry• 4 years ago

Related - a video on why hexagons are the bestagons: https://www.youtube.com/watch?v=thOifuHs6eY

zenorogue• 4 years ago

Our article on various tile-based game maps might give some inspiration: http://roguetemple.com/z/hyper/geoms.php

See also the catalog https://zenorogue.github.io/tes-catalog/

Triangle Grids

Related Stories