Search Unity

  1. Megacity Metro Demo now available. Download now.
    Dismiss Notice
  2. Unity support for visionOS is now available. Learn more in our blog post.
    Dismiss Notice

[Updated: 2.0] Make It Tile: a tile and topology framework for tile-based games

Discussion in 'Assets and Asset Store' started by AndyGainey, Nov 19, 2016.

  1. AndyGainey

    AndyGainey

    Joined:
    Dec 2, 2015
    Posts:
    216
    News: Discontinued. goto details;


    A serious tile and topology framework for serious engineers.

    Unity Asset Store.

    View the full online documentation and check out the demos. The old thread for version 1.0 (known back then as Tile-Based Worlds) can be found here.

    Make It Tile is a framework for Unity to aid in the creation and usage of tile-based game worlds. Through its carefully engineered data structures, it is designed to be maximally flexible, applying just as easily to the simple 8x8 game world of chess as to a large hex grid in a strategy game or even an irregular arrangement of tiles on the surface of a sphere. It includes support for:
    • completely custom attributes for tiles, edges, or vertices
    • square, hex, and irregular grids
    • planar and spherical surfaces
    • world edge wrap-around
    • mouse picking
    • A* path finding
    • dynamic mesh generation
    • neighboring tile visitation
    As a bonus, and in support of tiled world generation, Make It Tile includes the full Make It Random and Make It Colorful libraries.

    In addition to the above features, the framework is very extensible, to support whatever tiling patterns, tile attributes, and algorithms you might need. Full source code is included.

    Scripting Note: Although the framework does contain some experimental high-level tools usable directly within the editor, it is not designed as a top-to-bottom solution, but is rather intended to be a foundation upon which many different game mechanics can be easily built. Additional scripting will therefore be necessary in almost all cases.

    For inquiries or suggestions, feel free to use this thread, or contact me on Twitter @AndyGainey or email againey@experilous.com.

    The Details

    Topologies
    • A topology data structure representing the vertices, edges, and faces of a 2D graph.
    • Easily enumerate the neighbors of a vertex or face.
    • Efficiently store and access arbitrary custom data for each vertex, edge, or face.

    Grids
    • Square, rectangular, and general parallelogram tiles.
    • Regular and irregular hexagonal tiles, with support for pixel-perfect integral sizes.
    • Spherical worlds based on subdivisions of the five Platonic solids.
    • Irregular tile randomization for any grid, planar or spherical.

    Wrap-Around Worlds
    • Data structures and algorithms that work naturally with wrap-around worlds.
    • Wrap around either the horizontal or vertical axis, or both.
    • Works for planar worlds with square, hexagonal, or even irregular tiles.

    Mouse Picking
    • Data structure to efficiently look up tiles.
    • Finds tile intersected by a ray.
    • Finds tile nearest to a point.
    • Works for any grid system regardless of world or tile shape.

    A* Path Finding
    • Efficient path finding methods implemented using the A* algorithm.
    • Can use custom tile or tile-to-tile path costs.
    • Can path between tile corners along tile edges.

    Dynamic Mesh Generation
    • Helper utility to construct a dynamic mesh for tiles in a game world.
    • Custom tile triangulation techniques supported.
    • Includes multiple tile triangulation techniques for common cases.
    • Handles large vertex/triangle count and splitting into multiple meshes.

    Tile Visitation
    • Easily implement searches and visitation over the tiles of a world.
    • Fast arbitrary-order adjacency visitation starting from one or more root tiles.
    • Breadth-first and depth-first searches, based on depth, world distance, or custom distance.
    • Proper random order adjacency visitation, good for randomly generating groups of tiles.

    Samples

    Here is a sample of creating a square grid and performing arbitrary operations over the elements of the resulting topology.

    Code (CSharp):
    1. using UnityEngine;
    2. using Experilous.MakeItTile;
    3.  
    4. // Create a square grid.
    5. RectangularQuadGrid surface = var grid = RectangularQuadGrid.Create(
    6.     Vector2.right, Vector2.up,         // 2D axes
    7.     Vector3.zero, Quaternion.identity, // origin and orientation
    8.     false, false,                      // axis wrap-around
    9.     new IntVector2(5, 3));             // grid size
    10. Vector3[] vertexPositionsArray;
    11. Topology topology = surface.CreateManifold(out vertexPositionArray);
    12. var vertexPositions = vertexPositionsArray.AsVertexAttribute();
    13. var faceColors = new FaceAttributeArrayWrapper<Color>(topology.internalFaces.Count);
    14. var edgeCosts = new EdgeAttributeArrayWrapper<float>(new float[topology.halfEdges.Count]);
    15.  
    16. // Element collections can be enumerated using a foreach loop:
    17. foreach (Topology.Vertex vertex in topology.vertices)
    18. {
    19.     Debug.LogFormat("{0}", vertexPositions[vertex]); // Log out the position of each vertex.
    20. }
    21.  
    22. // They can also be accessed by integer indices:
    23. for (int i = 0; i < topology.faces.Count; ++i)
    24. {
    25.     Topology.Face face = topology.faces[i];
    26.     faceColors[face] = Color.red;
    27. }
    28.  
    29. // The two subsets of faces, internal and external, can also be enumerated:
    30. foreach (Topology.Face face in topology.internalFaces)
    31. {
    32.     // do something with the face
    33. }
    34.  
    35. // The edges are accessible in three varieties, all representing
    36. // the same set of edges, but producing different behavior in
    37. // certain cases, as will be explained in other topics.
    38. foreach (Topology.HalfEdge edge in topology.halfEdges)
    39. {
    40.     edgeCosts = UnityEngine.Random.value + 1f;
    41. }
    42.  
    43. // While accessing all the elements, the neighbors of each
    44. // individual element can also be enumerated within inner loops.
    45. foreach (Topology.Vertex vertex in topology.vertices)
    46. {
    47.     // Automatic enumeration using the edges property
    48.     foreach (Topology.VertexEdge edge in vertex.edges)
    49.     {
    50.         Debug.LogFormat("From Vertex {0} to Vertex {1}, Edge Cost = {2}",
    51.             edge.nearVertex.index,
    52.             edge.farVertex.index,
    53.             edgeCosts[edge]);
    54.     }
    55.  
    56.     // Manual enumeration using the firstEdge and next properties
    57.     var firstEdge = vertex.firstEdge;
    58.     var currentEdge = firstEdge;
    59.     do
    60.     {
    61.         // do something with currentEdge
    62.         currentEdge = currentEdge.next;
    63.     } while (currentEdge != firstEdge);
    64. }

    Version History

    Version 2.0 (2016/11/08)
    • Includes the full Make It Random and Make It Colorful assets!
    • Improved the graph visitation algorithms and interface.
    • Added an extended graph neighbor concept (to support, for example, diagonal movement on square grids)
    • Added grid preview to inspector for quad/hex grid generators.
    • Improved the user's manual, with images and a complete API reference.
    • Miscellaneous bug fixes and iterations on design/architecture (not fully backwards compatible as a result).

    Quick Links
     
    Last edited: Nov 21, 2017
  2. neoshaman

    neoshaman

    Joined:
    Feb 11, 2011
    Posts:
    6,492
    Looks interesting, I'm in the process of coding spherical code, this seems like it could save time and add interesting topology. Would you say this would be useful for a no man sky planetary generation clone?

    I mean, can we generate the sphere 's tiles, such as we have any pattern's enumeration from a distance around an arbitrary point (flying over a sphere coordinate to the computed visual horizon limit or LOD). Can we automatically detect pole through a check? Can we differentiate tiles from different faces of the subdivided platonic for as region (because of poles and continuity of pattern)? Can we move the pole by flipping edges (not necessary but that's cool nerdy plus we can take advantage to have less predictable anomaly)?
     
  3. AndyGainey

    AndyGainey

    Joined:
    Dec 2, 2015
    Posts:
    216
    There might be some ways to use Make It Tile as one part of the procedural generation process for something like No Man's Sky, but there'd still be great deal of work that would need to be done to generate all the detail for a game that is not itself tile-based (or even tile-based games like the modern Civilization games with high-detail terrain).

    It could be useful if you were running a high-level generation phase that simplified the planetary surface into tiles and groups of tiles to represent terrain types, biomes, continents, bodies of water, and similar. There are indeed tools to take any point and determine which face of the surface that point is closest to, what the center position of that face is, the position of all the face's corners, which faces are neighboring that face, et cetera. Whatever data you wish to store per face, per corner, or per edge, Make It Tile can accommodate it.

    The visitation algorithms would let you start at a specific point, and enumerate all the faces in, say, a breadth-first order until you reached a particular LOD distance limit.

    I'm not certain what you mean by automatically detecting poles, unless you mean the same thing when I described finding the nearest face given a 3D point. If so, then yes, definitely supported.

    There's nothing built-in for tracking the platonic face that a subdivided face originally came from, but that data could be generated easily enough by creating two topologies: one subdivided and the other not. Then iterate over all the subdivided faces, look up the face's position on the platonic solid topology to find the origional non-divided face, and store data about the original face on the subdivided face. Or if you want more irregular regions, you can pick any number of "seed" faces, and then use the random visitation algorithm to grow those regions by randomly adding neighboring unassigned faces until all faces belong to one region or another.

    That's actually one of the design principles I've followed while developing Make It Tile: There are so many things a developer might want to do, and I can't foresee them all, so instead of trying to do just a few very specific set of things with one line of code or a simple interface in the editor, I try to enable many possibilities through a flexible API and with a moderate amount of code. As I go forward, I intend to further simplify common tasks, but the foundation is flexibility rather than one-liners.

    Finally, as for edge flipping, if you mean this sort of operation, absolutely! Make It Tile supports two operations which I call edge pivot and edge spin, which are basically generalizations of edge flipping for faces that could have any number of edges ("flipping" makes sense only with pairs of triangles.) It is used automatically by the topology randomization algorithm, and these operations can also be used manually if you need more precise control over how the topology is altered. (If you haven't run across my 2014 planet-generation blog post before, the edge spinning is how I achieved the randomized tile distribution to avoid having 12 predictable pentagons on an otherwise hexagonally tiled surface.)

    Like with most code libraries of some complexity, Make It Random isn't going to be something you can drop into your project and immediately get magic from. It'll take some learning to understand how it is designed and how to work with it. But once you are familiar with how it operates, it does indeed speed up a lot of tile-based programming, doing a lot of the generic algorithmic stuff for you (like navigating and enumerating graphs, a fair bit of geometric operations to calculate things like centroids, normals, UVs, doing raycasts against a topology to find a face). I'd recommend you peruse the conceptual topics in the documentation if you haven't already done so, to get a feel for if it work well with your programmatic needs and development style.
     
  4. neoshaman

    neoshaman

    Joined:
    Feb 11, 2011
    Posts:
    6,492
    haha! the reason I asked for pole shifting by edge flipping is precisely because o your article, I didn't knew you was the author :p

    As a gamedesigner with some soft coding skills, I tend to overanalyzed first in planning phase to then choose the path of least resistance later. Since now I'm trying to implement I'm concern about the gameplay breaking influence of poles. I tried once to implement a controller akin to mario galaxy, it tooks me 3 years to solve the poles problem as the locked the player into singularity.

    In term of planet generation if they are too predictable player can find them easily, and since they break things (in a creative voxel game, you wouldn't be able to copy and paste on top of them), because they need specific coding, I would like to explain them away with lore and gameplay. Having them not too regular would help make thing more organic. But detecting them become important because they are special case (especially if we multiply them by flipping meshes, though I'm curious to know how the query would work with generated pole without storing all node first, which at massive scale is a big no, so only for very highlevel?).

    But yeah, I was thinking about hi level generation, in fact it's related to the question I asked you in the other thread, if can query coordinate quickly at any grid size (like a massively big planet), I can hash them and turn them into whatever mesh generation I'm cooking, using the tile to place them spatially and generate them base on their position hash.

    About the face detection, it's a problem with isotropie (if this is the correct term), all tile on the same face have guarantee to have euclidean property. But every times you would cross an edges this is compromise, reference can change, it get worst as we get close to pole, this is just a property of non euclidean space, parallel line can intersect, but it might not make intuitive sense (like slowly deflecting the player movement awkwardly, that is solved by not using the topology for 3D movements).

    The reason I bring that last point up is because I'm not doing typical procedural generation, I'm attempting to generate circulation data on infinite map inspired by worley noise. RuneVision had a similar idea too, but I think his implementation over complicate things too much. The basic are the same, we generate local data and query neighbor data to create local circulation path. Hexagon offer a better structure with less neighbor (6 vs 8) better distributed (the diagonal are stretched in square grid and introduce bias in the distribution)


    Basically all these question converge toward a single goal, generate not only infinite terrain, big planet, but also infinite coherent and complex history (basically circulation through time) with only local generation. Think dwarf fortress but without long simulation baking time, you would just query a specific time frame, at any point in an infinite timeline (structured into time tiles), and have something that is still coherent with everything that happen first.

    And more specifically complex minute npc interactions, that is you query one tile at one time frame, and the system return back all npcs and their states without dependence on past states or geography, nor going through a huge list or simulation ticks (basically simulating infinite persistent NPC). And they travel across tile too :D. That's why I asked for the perfect hashing algorithm in that other thread and I'm now asking about querying tile position. If I want uniqueness of npc generation I need no collision.
     
    theANMATOR2b likes this.
  5. Cameron_SM

    Cameron_SM

    Joined:
    Jun 1, 2009
    Posts:
    915
    This looks great, I came across your blog a while back when doing some pre production research and now that I actually have time to start on it I was happy to discover that you've done all the painful half-edge structure stuff already. Really great documentation too, I know how much time that would have taken. So glad I don't have to try and write and debug a half edge structure and chase down and enforce all those pointers, was going to simply port Plankton's open source Half Edge library for Rhino/Grasshopper but now I don't have to.
     
  6. slimshader

    slimshader

    Joined:
    Jun 11, 2013
    Posts:
    187
    Error afer importing in 5.5.2f1:

    "Assets/Plugins/Experilous/MakeItRandom/RandomGeometry.cs(1299,67): error CS0177: The out parameter `quat' must be assigned to before control leaves the current method"
     
  7. slimshader

    slimshader

    Joined:
    Jun 11, 2013
    Posts:
    187
    Hey, to clarify: 2.1 update is only about MiR and MiC?
     
  8. AndyGainey

    AndyGainey

    Joined:
    Dec 2, 2015
    Posts:
    216
    Correct. I'd been hoping to get the winter updates to MiR and MiC (especially the quat bug fix) into a larger update for MiT, but the feature additions are taking much longer than I predicted, so I finally decided to push out a release that only included changes to the two support libraries.

    Sorry it's taking so long to get to MiT 3.0. Life has been, um, "life-y" recently, but I'm still pushing forward.
     
    slimshader likes this.
  9. slimshader

    slimshader

    Joined:
    Jun 11, 2013
    Posts:
    187
    Any ETA on 3.0? And / or road-map?
     
  10. AndyGainey

    AndyGainey

    Joined:
    Dec 2, 2015
    Posts:
    216
    I'm hesitant to make any claims about dates, other than April seems highly unlikely.

    As for road map, reviewing my 3.0 task list reveals that it could use some updating in light of certain recent engineering choices I made. Turns out one of my highly desired 3.0 features (high-quality contours around regions) needed support for voronoi diagrams, which was on the road map for 4.0 for other reasons, so that got moved forward. And while working on that, I ended up extensively reworking the underlying half-edge data structure to be cleanly separable from all of the topology/surface stuff. That has led to a tighter node/edge graph data structure, plus a node/edge/face topology data structure built on top of it, and these might end up released at some point as a smaller/cheaper graph/topology asset, just like MiR was.

    Aside from the contour/voronoi stuff, the plan has been to more extensively port my planet generation demo over to Unity, and in the process attempt to investigate a different style of editor integration. I put a lot of time into the first form of editor integration, but I think it was a failed effort for at least two reasons. 1) I was learning Unity's editor API at the time, which frequently makes early architectural decisions seem poor in retrospect. 2) I was trying to make one-size-fits-all editor utilities, which I no longer think is wise for this type of tool. So instead, I aim to provide helper classes and demos that have their own editor integrations that are specific to their particular use cases, such that they can be copied and modified appropriately for the unique use cases that users will have. The planet generation demo would be the first to utilize these changes; I already started in on that a while back, and am hopeful that it will offer a better direction forward for more extensive and user-friendly editor integration.

    Though I expect what comes with 3.0 will only be a start, and more will hopefully take advantage of the new foundation in later versions. Especially since 3.0 has taken so long to begin with, I'll be aggressively looking for ways to get 3.0 finished and tidied as early as possible, without biting off even more features that'll take months to develop.
     
  11. neoshaman

    neoshaman

    Joined:
    Feb 11, 2011
    Posts:
    6,492
    You should have signature with all your product, it's easier to find.

    Also will your half edge implementation can be use separately, I would need that for some experiment and I'm not a programmer, the less I code and focus on my thing the more I'm happy!
     
  12. AndyGainey

    AndyGainey

    Joined:
    Dec 2, 2015
    Posts:
    216
    Very likely, yes. The more I work with it, the more uses I find for it, and the more generic it is becoming as a result. It only makes sense to isolate those bits as a standalone utility. Though I'm still working out the details of exactly where to make the separation and how to package/price it. Regardless, it'll naturally be included as part of Make It Tile same as Make It Random was when the RNG stuff was extracted into its own thing.
     
  13. AndyGainey

    AndyGainey

    Joined:
    Dec 2, 2015
    Posts:
    216
    Announcement: Due to a major change in my career and life circumstances, I am deprecating this product on the Unity Asset Store. It might return again, or at least some parts of it, though I unsure what form it would be in if/when it does.

    More details here.