Proposal: Graphs (the graph theory kind, not the X/Y-axis kind)

[JesseTG]

Placing "nodes" of some kind is easy (just make them tiles), but what about establishing relationships between those nodes? Could be very useful for establishing waypoints for AI, or for map screens, or similar.

And, even better, what about tools to automate creation of certain kinds of graphs based on the layout (e.g. using the slab method to create AI waypoints automatically, based on the tiles in the current map)?

[bjorn]

In terms of adding rich relationships between objects, which is a use-case that also comes up when people want to add joints to constrain collision objects, my plan is to add these as objects on their own, with their own properties like "bodyA" and "bodyB", with which they refer to other objects by ID. The general feature is covered by issue #707.

For waypoints, I think often a polygon or polyline object suffices, but if you want dynamic pathfinding you need meshes. So I could consider this a feature request for adding support for mesh editing.

The last part about automating is best solved by a custom script I think. Once the primitives to support the use-case are there, a script could go over the map and set them up as needed. Adding scripting is covered by issue #949.

[JesseTG]

Yeah, a mesh. That's probably a better word for what I'm proposing (so long as nodes and edges--maybe closed faces, too--can have properties)

[bjorn]

Hmm, people have also requested properties on polygon nodes. I'll have to consider how this could be supported without making things too heavy-weight.

Regarding meshes the main challenge will be the tool(s) to edit them. I'm not personally familiar with any mesh editing tools so I'd have to look into that.

[JesseTG]

I'm saying that Tiled would be the tool.

[bjorn]

@JesseTG That'd be great, but I'll need to take an example from somewhere. I mean, maybe look at how Blender does it and for sure there are other tools specifically for 2D mesh editing. :-)

[JesseTG]

Actually, I was thinking something like Inkscape. Or, hell, even one of those mobile graph theory apps for CS students.

[bjorn]

Inkscape only does paths, not meshes. I've already looked at Inkscape extensively regarding object selection and polygon editing, and there's more things i'd like to take from there. But still, I'd like to try a 2D mesh editor before setting out to add that to Tiled.

[JesseTG]

AKA a graph. Ever hear of Rocs or SocNetV?

Also, even though Inkscape doesn't do meshes, I think we can learn some valuable lessons from it about how nodes should be moved around, and what happens to the edges that are attached to them.

[bjorn]

AKA a graph. Ever hear of Rocs or SocNetV?

Haven't heard of either, but I'll look them up.

Also, even though Inkscape doesn't do meshes, I think we can learn some valuable lessons from it about how nodes should be moved around, and what happens to the edges that are attached to them.

Is there something different about it than moving polygon nodes around in Tiled?

[JesseTG]

To be honest, I don't know. I haven't used the polygon tool in Tiled for quite some time.

[bjorn]

Ok I looked at Rocs, but there was really nothing interesting there. Its graph editing options were quite basic, more so than the polygon editing options in Tiled at least. The nice thing of course is that it allowed custom properties on the nodes as well as the edges, though that also resulted in a huge overhead regarding the saved graph file.

SocNetV graph editing operations where really limited and labor-intensitive. Nodes are created in random locations and creating edges requires entering a node index manually while going through two popups. It seems to rather expect that you will import the data from somewhere and offers many interesting ways to visualize that data, but I see nothing there that would serve as example when adding mesh editing to Tiled.

To be honest, I don't know. I haven't used the polygon tool in Tiled for quite some time.

Basically I think it mostly already does what Inkscape does apart from some more advanced stuff like resizing/rotating a multi-selection of nodes. I do want to add such things eventually, but regarding mesh editing I'd be more interested in operations specific to that use-case.

Actually, I think the most important thing currently missing in Tiled is the ability to easily extend a polygon with additional nodes. The only way to introduce new nodes currently is by splitting existing segments.

[JesseTG]

I think the main applications would be for AI. You know, let the designer put down a bunch of waypoints and a robot will figure out how to move between them using Djisktra's or A* or something.

This could also be useful for world maps, a la Super Mario Bros. or Fire Emblem Awakening, or any other scenario where the player's motion is governed by a finite set of paths (as opposed to grids or physical laws).

As for Tiled-specific tools? Auto-generating these meshes based on the world's layout, possibly with some parameters to decide how fine-grained said mesh should be.

Also, if you have an Android device, check this out.

[bjorn]

Alright, I guess the graph editing use-case is actually quite different from the mesh editing use-case. I'm not entirely convinced anymore that it makes sense to put both in the same tool.

[JesseTG]

Wait, what? No, I'm trying to argue that it's the /same/.

[bjorn]

No, I envisioned the mesh editing tool similar to the polygon editing tool, and mostly for visual purposes (so it would include editing of texture coordinates for example). For such a thing there needs to be a much higher level of editing comfort and the result is mostly not about the nodes or the edges but about the faces. A mesh would in this case be a single object, and it needs an efficient storage method for a large amount of data.

In contrast, judging by the three tools you've pointed me to, the graph editing tool would be all about defining connections between objects, and the connections would also be objects in their own right.

Now, for AI navigation, I think either tool could be used. You can create a navigation mesh object that is just about indicating walkable areas, but can't have custom properties on the nodes or edges. Or you can set up a number of waypoint objects and connect them arbitrarily with line objects to form a graph, allowing more flexibility like assigning weights or direction to the connections, giving names to the waypoints, etc. You could even do both for different purposes.

[JesseTG]

Instead of treating meshes and graphs differently, why not have a "compact" mode for a graph (that's maybe toggled with a checkbox) that makes said graph more efficient to store at the cost of not being able to store properties in individual nodes, faces, and edges? Where as an "ordinary" graph would allow the nodes, edges, and faces (as well as the full graph itself) to have properties.

Now, for AI navigation, I think either tool could be used.

This smells like a recipe for confusion borne of overlapping responsibilities.

You can create a navigation mesh object that is just about indicating walkable areas, but can't have custom properties on the nodes or edges.

Actually, I think having properties on AI-walkable areas is exactly what I would want.

• "This point (aka vertex) is on higher ground, so stop here for a bit and look out for players on the other team."
• "Be careful on this stretch of the road (aka edge), there's a hairpin turn up."
• "This rock (aka face) is impassable, don't worry about anyone coming over it."

But, TBH, I don't think this should be seen in terms of AI. Ellipses, polygons, and even plain old tiles have tons of game-independent uses, and are treated as such; why can't graphs (or meshes, pick your favorite word) be thought of the same way?

[bjorn]

A mesh is a somewhat well defined rendering primitive, and it does not make sense to represent it by randomly connected objects of various kinds. For the same reason there is a polygon object rather than expecting users to create polygons manually by connecting a set of point objects with line objects in some specific way and then somehow configuring this group of objects to be saved as a polygon.

So there are really two features here. A basic mesh primitive in the same vein as the already available polygon and polyline objects, and a "connection" object type along with a tool for conveniently adding such connections between arbitrary objects.

[JesseTG]

I wasn't thinking connections between arbitrary objects; just connections between nodes, which are their own thing. Possibly even on a separate layer.