What would be the best way to generate pathfinding nodes? I know you could custom create them but that’s lengthy, tedious work, and prone to hard-to-catch mistakes. What would be the best way to generate nodes for a 3D environment?
Note: Nodes don’t need to be generated at runtime, and the only data it needs to store is position.
Im guessing from the description and your use of nodes, that you’re referring to path finding via a node/waypoint graph?
in that case, there are a couple of ways to generate such graphs proceduraly at runtime or in the editor.
If you’re environment is very grid based, like a tile map, then i’d suggest looking into the FloodFill algorithm, this algorithm will take a start location (or tile) and spread outwards until all the tiles have been checked, during which you run some qualification logic to determine if that position is allowed to be a node, and which nodes it connects to.
If you’re not running a tile based system, then again there are a bunch of different possible approaches, the flood fill can still work here, but would be written slightly differently and your logic for qualifying any given position would be a bit more involved, to ensure you don’t just place a node in the middle of world geometry, and probably would require a number of line of sight checks to qualify node connections.
An alternative approach (depending on how your level boundries and walls are defined) is the ExpandedGeometry approach. Imagine a line drawn around all of your walls, then this line is moved away from the walls into the walkable space by some distance. You then place nodes on each of the positions along that line that were vertices, connections already would exist along the drawn lines, and you could use distance and line of sight checks to add additional connections if you want.
Anyway, I’ve never used more than the flood fill myself, so i cant really talk much about other potential methods, and I’m sure there are a few if not plenty of other methods that i haven’t mentioned.
Both of the approaches I’ve mentioned here are talked about quite nicely in Matt Buckland’s “Programming Game AI by Example” i found it a great read when i was first looking into anything AI related. And I’ve no doubt there are plenty of other good books out there, but maybe this can help serve as a starting point for you.
Hope this helps.
Well how exactly should I go about this? My original method was to do something similar, check to see which nodes are colliding with something, and then deleting those nodes. Flood fill seems to have a workaround to that (not creating nodes inside of other geometry in the first place) but I'm not exactly sure how thats implemented.
– DayyanSissonNope, that answers everything, thanks!
– DayyanSissonOr there's the [A* algorithm][1] [1]: https://en.wikipedia.org/wiki/A*_search_algorithm
– FlickayyA* is a graph search algorithm, it wont really do Overlord much good in the process of building the graph. But granted will be useful for once the graph does exist.
– FatWednesday