Hi there!
I’m wondering if anyone has used a GridGraph to dynamically find cover for an AI to retreat to? Importantly, my game is top-down 2D with crouching. My non-walkable layers are Walls and Collision (knee-high). (The graph itself is generated as expected.)
Currently I have to place all of my possible cover positions manually, and as I introduce more and larger maps, this is becoming a big time sink (not to mention having to return if something changes). Basically I need to iterate each node that sits on the edge of the Collision layer (not Walls) and determine whether it’s a position to take cover in:
The above image is showing what I’m hoping to accomplish. All the nodes along the red line would be a good place to defend from the green arrows. I wonder if I could somehow use the direction to the Collision as an indicator of what directions it might protect from. I’m not sure yet how I’d ensure AI didn’t try to run to the same position, but I was hoping someone here might have some idea of how to go about gettinng started with automating all of this?
I assume it’s something I should calculate and store at Edit time, to avoid a big performance hit?
Any help is greatly appreciated!
Hey,
I was recently working on an extension for A* to calculate cover locations for agents on the fly.
Though I have been doing this on my free time, Its not really game ready yet. But I can share a little bit of how my system works.
When the graph is scanned I keep a unique list of all colliders we hit as obstacles. Using their bounding boxes I place markers on all the corners. ( move them a tiny bit towards the center to make it more reliable later on)
When an agent wants to find a cover position, I first update the cover graph ( in the video this is done every frame)
I sort all the corner objects in a clockwise rotation around the players position.
For each corner I do a raycast towards the player, starting from distance X from the player. (increase x to have it calculated cover further away from the player)
all the hits are sampled and converted into a polygon. Similar to this https://www.redblobgames.com/articles/visibility/
but inverted of course.
Then I create a GUO with the same points as my polygon, and update the graph’s tags.
Read more about GUO here https://arongranberg.com/astar/docs/old/class_pathfinding_1_1_graph_update_object.php
That’s the main idea. There are still a bunch of small improvements to be made, especially for corner detection and corner grouping.
However I’m leaving on holiday in a few days from now and won’t be able to work on this at all for a while.
I do plan on releasing either a package or just the code elements in the future when it’s fully operational.
Hope that helped a little, it’s a definitely an interesting challenge.
-Wolf
2 Likes
I suppose a small list of changes to be made would be interesting also.
-
The first change to make is group corners in relation.
At the moment the system doesn’t know when one object ends and the next begins. So in some cases the polygons created connect two cover regions to each other. The way I would resolve this is by creating a struct or class as a container for corners. So all the corners part of the same hole in the navmesh would be grouped together. This can be done during graph baking, and resolve the issue.
-
I start my sorting of corners from the player transform.Right however sometimes that’s splitting a group of corners in half. And yields undesired results. This can also be prevented with grouping corners.
-
combine with already existing tags. In my video you can see that the cover region is quite large, however in most games cover is considered directly behind the object. To do this I would make a modified version of the erosion system. Erode the map and set all the graph nodes as available for cover. Rather than updating all the nodes that are part of the GUO I’d only update nodes that are available for cover.
-
clearing the previous results. The current implementation is quite destructive. It destroys any existing tags already assigned to the graph. But it also doesn’t ‘undo’ itself applying the tags. In the video I cheated by clearing the entire graph, and resseting all tags. The system needs to keep track of the changes it did to the graph. A better approach would probably by by not changing the graph at all, and writing a custom NNConstraint to find the closest available cover point.
Long story short, still a lot of work to be done to make this really usable in a game.
1 Like
@ToastyStoemp Wow, this is all great info!
One thing I’m nervous of (mostly because I don’t have any experience in it yet, it seems daunting, hehe) is modifying the scan process. I also need to use it to add tags to my Knee-High layer, so I have to dive in eventually. I’m just struggling to find the starting point, hehe.
Your video looks good, and your method of finding cover is really well explained, thanks so much! After I read your first response I actually went and experimented with just using 2D physics (no A* graph), and it actually seems to be working really well. Essentially:
- OverlapCircle to find all PolygonCollider2Ds
For each:
- From its center, get the position 20 units (magic number) in the opposite direction of
coverFromPosition
- Find the nearest point on the PolygonCollider2D (moving it 20 units away from the
coverFromPosition means we’re on the correct side of the collider)
- Add a buffer (opposite direction again) of the character’s width (room to stand) to that point
- Test if it is a valid position (character can stand there, and
coverFromPosition can’t see it)
Then I have a list of available cover positions, which I can select from depending on the situation (closest, test the path to see if it’s towards coverFromPosition, etc.) I’m quite happy with the results so far, but I might revisit using actual graph nodes eventually, as I feel like it’s going to be faster in the long run?
Bundling this up your code as an asset seems like a good move, I’d say it’s definitely a common requirement. I’d love the time to fool around with making a really solid, universal system for it, though I suppose some of the logic is going to be game-specific?
Thanks again for the write up, really helpful (and interesting)!
Hey,
Modifying the scan logic isn’t as scary as it sounds. For the grid based graphs it’s really straightforward.
You can always start with the Graph Modifier class.
https://arongranberg.com/astar/docs/class_pathfinding_1_1_graph_modifier.php
For 2D your approach might actually be better, though you’re relying on the colliders per object level. Where I’m trying to group objects that are next to one another as one object for cover.
I might give your approach a try also. Always interesting to discuss different methods.
1 Like
Yeah, one feature I’m taking advantage of in my setup is that all of my colliders are gridded. So even on a single object, multiple colliders are created in a grid, with no single collider greater than ~15 units squared.
Because of this, finding the external position of the collider is simple. But in a more complex setup it would be harder, I think, to find the correct side?
