Build path at runtime from waypoints on tile prefabs

You've left out a very important bit of information: How are you placing your tiles? Procedurally by way of some world generator? (At runtime or design time?) Using an integrated map editor of some kind? Reading from some external "map" file? (At runtime or design time?) $$anonymous$$anually dragging tile prefabs into the scene and positioning them one by one by hand?

The question states the path should be deter$$anonymous$$ed at run time. It's kind of buried in there though. I could have made it clearer.

Beyond that, what effect does how I placed the tiles have? I assume I'm looking at it through my 'I kind of have a plan' lens and am not seeing what you're thinking, so honest question.

$$anonymous$$y 'partner' is working on a map editor, but it's strictly for development of levels and not open to the consumer. How I will receive levels in the game has not yet been deter$$anonymous$$ed. $$anonymous$$y assumption is some sort of json or serialized object array.

Asking how you'll be building the world was a prelude to a newbie-friendly recommendation on how to structure your project in the first place. $$anonymous$$ost questions I (we) address here are from brand-newbies who'd get lost if I launched right into design strategies.

$$anonymous$$any established per-genre conventions have a strong record of improving efficacy across the board. In tile based games, it's generally wise to bake navigation into the bones of the system so deep that it's already ready to rock at runtime. Ideally, building a waypoint network should be as simple as perfor$$anonymous$$g a recursive neighbor check of adjacent cells for some walkability interface - once per map change, and at design-time if possible.

This approach implies your map data is organized in a traditional two-dimensional array, which, for a tile based game, is all but a requirement. You'd have to have a superb reason to recommend an alternate data structure. If your map is thusly represented, nearly all tasks that query cells are a zillion time easier and more efficient.

Include some information on each tile that informs whether it connects to others for walkability, then pick any walkable tile which hasn't been considered and check adjacent tiles for walkability to form a network. In the end, each tile knows all its walkable neighbors, and something like A* becomes possible.

I guess there's no right answer here; it's gonna be some compromise between developer convenience and flexibility. I'd say that's at least as critical as clever optimization. Forgive me if I've gone off topic or been less than helpful; this question read like something someone using a nonstandard data structure might ask. Any follow up comments or questions?

Gotcha.

You make good points across the board. Your suggestion to "bake navigation so deep it's already rock solid at runtime" sounds like what I meant when I wondered about pre-filling some of the closest neighbor values on the pre-fab way points. Then only the tile edge waypoints would need to deter$$anonymous$$e their neighbors, and I can use a collider of some sort to do that pretty easily.

So lets say I've worked all this out - each pre-fab contains a part of a path, and at run time when the level is loaded the neighbor/tile edge way points deter$$anonymous$$e who's their neighbor, and we can iterate from the start -> end of the path by looking at the "forward" member on the prefab.

What would I do to produce a data structure that A* or something similar can use? $$anonymous$$y familiarity with A* extends only to nav meshes that are auto created based on a "physically" in the game object. In this case, the path would just be a data structure of some kind at this point right?

Unless your map changes at runtime, it is most sensible to finish all navigation network creation at design time.

Now I understand that each walkable tile involves multiple path nodes. Having re-read your original question, I'm not sure how I missed that, but I missed it completely. It will behoove you to really spell things out for us. ;)

With this multiple-path-nodes-per-tile thing, my emphatic suggestion to allow tiles to represent their walkability with a yes/no flag obviously falls apart. I was assu$$anonymous$$g each tile was one "entity" wide and thus constituted a single waypoint.

So, never $$anonymous$$d my algorithm description, it is not valid in your case. It will be quite similar, but can't just check adjacent map cells for a single walkability flag.

Assu$$anonymous$$g you can do all this at design time, you have no cause to worry about the efficiency of the network-building operation, so don't worry about it. As long as it's you, the developer, paying the difference, efficiency is overrated.

When you invoke the waypoint network establishment function - e.g. after your map is finished and ready to be finalized or tested and saved for later use - look for the first tile which hasn't been exa$$anonymous$$ed. Establish all its internal connections by checking the distance between internal nodes. Then, for each adjacent tile, run the same identical check against each of THIS and THAT tiles' nodes.

Limit the distance across which a connection can be made, and place your nodes accordingly to avoid ugly or nonsensical connections. If prudent (medians, islands, streetlights) sphere-cast to verify each connection. These two measures (distance and line-of-sight) should be sufficient to ensure good-looking and sensible automated connections.

A simple A* system wants just two things: Neighbors, and the cost to reach them. At its most basic, the cost is the distance between two nodes. So the data structure of a waypoint requires only a position in 3D space and a collection of the waypoints to which it is connected. As long as you've got a cheap way to find the nearest waypoint to the starting position and end goal (tiles should know their waypoints, so just find the nearest tile, then waypoint), you're in business.

Build in a way to save your network along with the finished maps, which should be as simple as storing a master collection of waypoints.

These are just general guidelines; you seem to already have a handle on what you're doing. Sorry for trying so hard to convince you otherwise when I was the one with the misunderstanding.