More-onoi

More thinking about Voronoi regions, and using them to generate irregular game tiles.

Actually, I haven't done a lot of new thinking, but I've been meaning to jot down some notes and open questions, so when I get time to work on this, I'll make sure I'm not missing things.

Before the questions, though - maybe you want to hit this link:

http://bigdicegames.com/TheTwenty/IVor/index.html

And hit 'R' after things settle down to restart it.

What that tool is doing:

• places some number of "sites" (gray dots) on the screen, with a random radius from 24 to 40 pixels.
• for each pair of sites A and B, constrains them to be no closer than the sum of the two sites' radii
• for each site, constrains it to remain onscreen
• repeat the above until there's no remaining movement
• generate a voronoi diagram for the resulting locations
• draw the diagram, leaving out line segments to infinity

Simple stuff. I'm using https://github.com/jceipek/Unity-delaunay for my voronoi generation, which seems adequate. I tried some other (downstream) forks of that code, and couldn't get stuff to work. I may fiddle with this version and upload my own unmaintained fork, because we need more of that.

So, some thoughts about what I see in that demo:

• It's fast enough that I could probably regenerate the voronoi diagram every frame.
• The caption says "interactive", and aside from pressing 'R', it's not.
• I'm not entirely satisfied with the site topology - if you look at the bottom center of the picture above, you'll see one tallish thinnish tile with a bunch of sites clustered around it like a horseshoe or a little bit like the Saint Louis Arch. Maybe not very much like the Saint Louis Arch. It doesn't feel like the kind of connectivity I want. I suspect that if I get the Lloyd Relaxation step in, that kind of clustering might go away.
• I'm not defining what's wrong with the horseshoe/arch clustering. I'm not sure I have a good definition. I think what's bothering me is the short edges. You can see other short edges elsewhere, and they bother me, too.
• There are long edges in the diagram, like ones that go off the edge of the screen. I don't really care about those, as I intend to be generating these maps at larger than screen resolution.
• There are occasionally places where a tile will be drawn, but the gray dot won't be drawn. That's almost certainly a bug in the way that I'm drawing my gray dots. I'm using Vectrosity for my line and dot drawing, and I like it, but it's a "retained mode" API, and I think I'm updating the dot list incorrectly, leading to some dots getting lost.
• I generate all the dots at once. I could generate them adaptively, putting dots in areas that aren't densely filled.
• I want to stick in some obstacles (walls, trees) and terrain types (open, rough, water) and plop a player-controlled character on there to get the feel of walking around. I meant to do that a week ago, but have got distracted with other stuff.

Ok, so that's what I've done. The point of the post was meant to be what my concerns and open questions are about this whole approach, what I'm trying to answer with these experiments.

• This is a whole lot of work, is it worth it? That's the big question. I think most of the rest of the questions feed in to this one.
• How do you handle straight-line effects? There's two parts of this, and maybe they have different answers. Let's think of two spell effects that one might have: Explosive Fireball and Ray of Embitterment. The fireball's effect might be centered somewhere in a tile, and effect everything "nearby". Is "nearby" defined in terms of tiles? Probably not. In order to feel right, I suspect that I want to draw an actual circle in screenspace (or in cartesian worldspace, not tilespace) and use that as my area of effect. Similarly for the ray, I'll want to trace out a long, thin rectangle, and use that. These aren't hard to do for a computer game, and could be approximated for a miniatures game using rulers and whatnot. Seems like it can be done. A variant of this is how to handle flying movement, but that's really the same thing, I think.
• If the tiles represent different movement effects, what about directional effects like "uphill/downhill"? I think that I'm going to have to handle certain effects on a case-by-case basis. A short list of these features: uphill/downhill, rivers (going with, against, across the current), roads (some vehicles will be able to move at good speed as long as they stay on a road, that's logic inside the vehicle, not inside the map).
• How does one meaningfully author a map like this? For regular tiled grids, or "continuous" maps, you can use a tiled map editor or a 3d terrain editor. For this stuff, it feels like the editing pipeline is going to be hard to use. Right now, I'm guessing that the world will be laid out as vector features (a road is a spline with a width, a forest is a polygon) which will then be used to generate the grid.
• How does "facing" feel? One reason that I think that people like hex grids is that if your game mechanics takes facing into account, a hexagon provides a reasonable level of fidelity. Better than a square, and... well, there aren't a lot of other regular options to work with. I want to get some code running to really answer this for myself, but my feeling right now is that with short edges, facing will feel fiddly. With more uniform edges, maybe it'll feel better.
• Do the adjacent tiles feel close enough for tactical combat? In this demo, tiles are supposed to be pretty close to the same size, though even now, it's not entirely working. If I have a melee unit in a small tile, and the neighboring tile is 3x as big, does that feel unrealistically far away? Or, if I'm standing in a large tile, maybe I have a lot of nearby small tiles (in a horseshoe arch cluster, perhaps) - are they all able to engage me in melee?
• If a tile is large, should it permit multiple units inside it? Does that break the whole notion of tiles? I think I'm going to have to play around a lot to get the feel for this. Maybe with good smoothing, the problem goes away. I don't know yet.
• Supposing I want units of different sizes, ranging more than one order of magnitude - is that a problem? What if the units aren't roughly circular in footprint? I'll almost certainly have small creatures in the game. Rats, or spiders, or something suitable for an annoying first encounter in the basement of the first building you walk into. But I think I'll also want a rock giant. Maybe some colossal creature striding through the ocean that you encounter. There's lots of possibilities. I also have this half-baked idea of segmented monsters, a little like the dragon in "Space Harrier", or the tentacles in games like R-Type. It's maybe weird to think of using those kinds of approaches for a tiled, tactical, turn-based combat RPG. Maybe not. My current thinking is that a giant unit would have a center point that moves just like any other unit, so maybe there's nothing special about a giant. And segmented serpents might just have a sequence of adjacent tiles that they occupy. Now that I talk about it, there's a pretty good canonical segmented creature already in gaming.
• One thing that discrete tiles offer is a manageable set of choices, fighting analysis paralysis. Does getting rid of regularity work against this? Maybe. I'm hoping that with good UI, it'll be easier to decide where I'm going and be able to make a good selection.
• But keyboard control is basically out, right? Probably. If there's somewhere between 4 and 8 neighbors of each tile that you visit along your move, there's unlikely to be good key-bindings to select the correct neighboring tile.
• But let's say that some places you want regular tiling, can you support a square grid or a hex grid? Would it be possible to smoothly go from chaotic irregular grids to regular grids? Probably. A while ago, I did some experiments with this question, and the results weren't immediately successful, but I think there's potential.

Ok, so given all of those questions, I think my TODO list includes:

• make a map with some obstacles and some different terrain types
• put a character with facing on that map
• build a UI that allows movement (with facing) on that map
• put some other creatures on the map to "fight" with

So, yeah, basically make a game to figure out if this is how I want to make my game.