I’ve been using point graphs for my game since I have player placed objects and destructible environments. This works pretty well so far, but I have some questions about how to approach a few features I will need soon.
Currently I’ve got one enormous Point Graph that generates around the player as terrain pops in and out around them (outside of the camera). This eventually results in an enormous (disabled) grid of nodes which will just about crash unity if I accidentally turn on debug rendering of nodes. Is there any way to clean up these faraway nodes?
Next issue, I’ve got large monsters in the game which should not be able to walk through doors (and maybe no narrow passages?), is there any way to disable them from attempting to do so? Or at least prioritise paths which do not take them through doors? I’ve also got semi-passable windows, and while I want some enemies (zombies) to prefer windows, the more humanlike characters should generally prefer doors unless they are in danger.
Finally, I was pondering implementing vehicles in the game. I figure their driving would just be a separate set of point-graphs that goes along the roads (in a specific direction, of course). However if something is blocking the road then it would make sense for them to try to circle the obstacle, possibly by driving onto the regular point-graph for pedestrians. Perhaps I could add some sort of “width” value to each point node to tell vehicles (and huge enemies) how much space there is on the sides of that node, and force them to use those?
Any thoughts on how to move forward with this, or feedback on my current solution would be greatly appreciated. Thanks for reading.
Ps. If it matters, I do support buildings with multiple floors. That is one of the reasons I figured a point-graph would be easier to deal with than the other types. The point graph is essentially a bunch of points connected to their 8 neighbours (assuming nothing is blocking them) and then special points for stairs and doors which connect to more distant points.
Sounds like you may want the recast graph or the layered grid graph instead.
Is there any particular reason why recast graph or layered grid graph is better than the point-graph I’m using? I’m not quite sure what the advantages are? Just to be clear, I need to be able to do stuff like add stairs, and maybe something like teleporters at runtime.
It is more well defined how the graph nodes should be connected. It will use less memory, you will be able to use the funnel modifier with it (not necessarily something your game wants though).
Teleporters and stuff will still need to be added using an intermediate point graph though (using the NodeLink2 component most likely).
What do you think are the pros and cons of Recast vs Layered Graph for this kind of game?
As you saw I have a (theoretically) nearly endless world with buildings (and multiple floors in the buildings).
I figure I will need to create one (slightly overlapping) graph per map-chunk (or maybe per tile, if the massive number of graphs doesn’t ruin things…). I also need the AI to be able to pathfind between different floors of houses, which is why I used the nodegraph (that one lets me place a node at the bottom and top of stairs f.ex.).
Can Recast/Layered Graph handle stairs, or perhaps handle mixing point-graphs with their own graphs?
If possible I would like to get characters to avoid standing inside each other (my seeker is currently parented into the character object, so characters would happily overlap if not for the AI I wrote discouraging it somewhat). I figure Recast/Layered Graph might be better for that since avoidance is a thing there.
I’m fine with writing a bunch of code myself, but I’m a generalist coder, so a lot of this stuff is new to me. I did manage to at least figure out the generic A* pathfinding algorithm, and write the current NodeGraph solution, but I don’t trust myself not to get lost if I’m tackling something much too complicated. Would using Recast/Layered Graph be much more complicated than the NodeGraph, f.ex.?
Here is map of an example region for reference of scale. Each of those squares is a 10x10m segment which are in turn packed much larger chunks, and you can currently traverse the map endlessly, (or until the nodegraph gets too big and Unity freeze-locks anyway). But anyway just to give an idea of the worldmap size, and what I’m trying to solve.
Oh wow, that’s a big map. A layered grid graph would be pretty slow with that map size. That’s about 1x1km and you need enough resolution to walk up stairs in buildings.
You can do that with a recast graph, but the calculation time might be prohibitive (though in the beta it’s much faster).
Can Recast/Layered Graph handle stairs, or perhaps handle mixing point-graphs with their own graphs?
Both of those can handle stairs, but at your world size the layered grid graph would not have enough resolution to do it. I would not recommend combining multiple graph types.
So sticking with the NodeGraph makes the most sense then? I figured I’ll attach one NodeGraph to each 5x5 of Segments (the 10*10m tiles), and have it generate a nodegraph for those nodes and a padding of 1 node out to each side so there is some overlap as I saw you write in an example to another user awhile back.
That way I figure the characters will pathfind as close to their goal as they can, and if they leave the 5x5 segment they’ll hopefully start pathfinding from the next pathfinding block? Do you think that would work? Will I need to write some sort of transfer-to-other-node graph method? Could this approach be used for recast/layered graph as well instead?
When a 5x5 segment gets too far away I’ll of course disable it since there would be nothing around to make use of it. Enemies spawn in (and out) some 80m away from the character (and turn into abstract worldmap ‘hordes’ which I handle by much more simple and less performance demanding rules).
From what I understood a Recast graph is adaptive, so I could continuously generate it around the player? Would that be a solution? I do have fairly strict rules for what is and isn’t walkable since the game basically operates on a square grid as far as blocking/not blocking goes, so I feel like it should be possible to streamline it a lot.
How to I handle walls? I’d like to not make it possible to traverse between squares divided by a wall. (Yes the walls have collision, but it doesn’t seem to get picked up). (See image)
Also, it seems a bit random about what gets flagged as walkable or not. F.ex. the Piano is barely going into the front squares, yet those got flagged as unwalkable. Similar issue with the bed. Meanwhile the oven in the kitchen and some of the drawers didn’t get picked up as unwalkable? (Also the cardboard boxes all have collision boxes, but none of the got picked up either).
It feels like I’d be solving things the wrong way if I start editing the graph from the objects themselves, but I could do something like that, similar to how I did with the NodeGraph. Do you think that be the best way to do it, or do I just have the wrong settings on my objects?
Yup. That worked. I was worried the game would struggle at that resolution (and I was kind of going for a 1x1m grid), but as long as I don’t display the gizmo it seems to run fine. I’ll need to tweak my collisions but aside of that it seems everything is working as I hoped. Thanks.
