- Home /
Best Way To Create Pathfinding Nodes
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.
Answer by FatWednesday · Jan 26, 2013 at 04:12 PM
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? $$anonymous$$y 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.
Well like I said, it depends entirely on how your environment is setup and defined.
ideally you wouldn't be deleting any nodes, you would still just do some sort of qualification on a location in space, and only create the node if it passed that test. In order to test if its in geometry depends again on how you level geometry is defined, if your dealing with colliders that define your walls and obstacles etc. then you can use Physics.CheckSphere which should allow you check a radius around a point in space, and see if that area is overlapping or inside of any colliders. qualification would then i imagine just be checking if any of those colliders are "wall" or "obstacle" or whatever method you use for marking your colliders.
hope this doesn't raise as many questions as it answers :)
A* 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.