Action Tower Defense game AI / Path Finding

JekiTheMonkey · November 29, 2022, 10:12pm

I’m trying to create an AI for an Action Tower Defense game, and I have some problems with that.

In my game there are different kind of towers, however, the ones that are related to the problem are the regular towers that shoot, and barricades; both can be destroyed by AI along their path. By default an AI just follows a path up to a crystal that it has to destroy, by on its path it may be distracted by a tower, for example, it may hit the AI making it follow the tower instead.

The problem, however, is that a barricade may alter the enemy behavior: if it’s in between the tower and AI, then the AI should try to destroy the barricade instead (i.e. switch the target from tower to barricade), but preferably it should check whether it can get around the barricade (in a close range) beforehand, and do so if it can (hence the final target will be the tower, but the path to it will change). Note: If there are two paths (for instance two distant roads) that lead to a tower an AI is trying to get to, it should take the closest one regardless the presence of the barricade.

Check my little painting for better explanation. The AI should take the Climb1 even if there’s another path that isn’t blocked through Climb2.

The player can also affect the AI path by distracting it, so, following the image, the AI can follow the player and get from the low ground to the high ground through Climb2 if the player didn’t go too far away from the AI in order to keep the agro.

The final questions are:

Should my towers affect (in terms of just static/skeletal meshes) the navigation area itself (I mean make the place they’re standing on non-walkable for AI), or should they affect the final path instead?
How can I make an AI check whether the barricade can be got around in a close range or not?
How should I manage such path finding / agro system?

Thanks for reading.

Mind-Brain · November 30, 2022, 12:00am

Hey @JekiTheMonkey!

You can fix a lot of these issues by using Navmesh Modifier volumes!

Give that a look-see and if there’s anything you have questions on, let us know! But you can slap one of those on your buildings and it’ll remove that space from the navmesh!

JekiTheMonkey · November 30, 2022, 9:44am

As far as I understand the navmesh modifier volumes, they wouldn’t solve my issue.

As I said in my post, if the AI has to go through Climb1 (i.e. it’s a pre-determined path by a level designer), it should use it regardless any building, because it would destroy them as soon as it gets close enough to hit them. If I would use the modifier volumes, the AI would immediately follow Climb2 in case of presence of buildings on Climb1. And, as far I understand how path finding in UE works, if both climbs are filled with buildings, the AI would fail to generate its path up to the crystal (which is supposedly placed on high ground), so, I think, that’s not what I’m looking for.

I appreciate the reply though.

Quetzalcodename · November 30, 2022, 10:55am

Hey @JekiTheMonkey!

While you are correct that it will not 100% solve your issue, those modifiers will do a lot of your heavy lifting using Query filters. These can be changed dynamically for each pawn, so once one tower has been determined closer the query should change to the path you want it to take. More information here:

The rest of what you need is going to require a multistep approach. I highly suggest using a behavior tree for your AI so you can swap between your behaviors easily (aggro, following the path, destroying barricades):

Your behaviors can be executed with blueprints that are referenced by your AI Tree.

I hope the above helps lead you to the answer you need!

JekiTheMonkey · November 30, 2022, 3:06pm

Thank you for your reply.

Can you explain it a little bit better? I did understand the meaning of custom navigation areas, but I don’t see how they can be used to achieve the path finding I want.

How can they be used to determine whether a barricade that’s in between the AI and a tower should be attacked instead of the tower?

Quetzalcodename · December 1, 2022, 10:52am

Hey @JekiTheMonkey,

As stated above the query filters will not be your end-all-be-all solution for your entire multi issue problem, but will answer the first part of your post where your AI will not stray from the path you want once the closest tower/climb is determined even if the path is blocked. Let’s say take a (poorly) drawn example I have, if the closest tower/climb is determined as green, it will use the green zones and not move to the red zones to move to the high ground and vice versa if the red tower is determined closer.

Here is a non-Epic video that explains more about query filters, how they work, and how you can set them dynamically:

The rest is going to require a lot more nuance, referring to the latter half of the post, that entirely depends on your project and how you have set up your barricade system. That can easily be addressed using a behavior tree. Behavior trees can be used to easily switch between different actions that you want your AI to take (Move To/Detect and break Towers/ Detect and break barriers/ etc.). Breaking it down even further:

You are vague in how you explain the way in which your barriers work. Is this a grid based system? If so, the easiest approach would be to do a check of the surrounding grid spaces and determine if any are clear or to use AI Sight (AI Perception) with a desired radius to determine if a grid space is clear otherwise attack the nearest barricade.

Here is more info on AI perception:

And finally, all of these behaviors (move to, attack baricade/tower/player, distracted temporary move to, etc.) can be switched between using behavior trees that can be used for every pawn regardless of the path they take and can be switched upon entering a trigger volume, using AI sight, etc.

Check out these non-Epic affiliated videos on behavior trees and AI perception:

Unfortunately there is no singular answer, especially if you do not already have a system in place that just needs fixing. But, I hope this more clearly explains an option you have and helps guide you toward the solution you are looking for.

JekiTheMonkey · December 3, 2022, 9:54am

Thank you for such an explained answer!
After thinking and trying ideas you wrote I almost got the solution.

At the moment my AI consists of 3 main states:

Chase the main level target (i.e. the closest crystal that the player has to defend)
Chase a target that attacks it or a player (not a tower) that’s in AI’s vision sphere
Attack if there’s something in a narrow trigger box that’s in front of the AI.

The behavior tree looks the following:

The sight sphere and attack trigger look the following:

I’ve created a Navigation Area that’s used by towers. The area only modifies the default cost by a value that will make the AI prefer going around the tower, but not going all the way around if the whole path is blocked. The value that I’ve found good enough is 10.

However, there’s a little problem with that. If the acceptance radius on MoveTo is low enough, then AI probably won’t face sharply the tower, but go around it because of the navmesh generation. Here’s a small video example: 2022 12 02 19 24 24 - YouTube. The solution is to increase the acceptance radius, but not too much; the attack trigger has to be long enough to reach the target.

After that I’ve used the created navigation area on the towers collision component, and checked Dynamic Obstacle and Can Ever Affect Navigation check boxes.

The result I’ve tested on a simple case that consists of a simple corridor with a barricade and a tower. If there’s enough space to go around the barricade, the AI will do so, if there isn’t however, it will not. And yes, it works on the example from the original post as well.

Attacking / agro part wise: by default the AI follows a path that leads to its final objective – crystal. However, it can be distracted by a tower or a player.

A tower can distract an AI only by attacking it. After the AI has been hit, the Target object on blackboard will be set, making the AI chase the tower. As soon as the AI gets close enough to the tower, the latter will be inside the narrow attack trigger, resulting the Attack bool on blackboard to be true, and so the AI will attack the thing that’s in front of him.

With this approach the barricades are defeated as well. If an AI is targeting a tower that’s behind some barricades, and they’re on the most efficient path for the AI, then it will walk into them, resulting the attack trigger to do its job – make the AI attack something that’s on the way, even if it’s not the object that the AI is thinking of.

A player, however, have more options to distract the AI:

he can just enter into their sight sphere, and if there’s no active target (except the main one – the crystal), then it’ll become one unless not gone too far (outside the sphere)
attack the AI while outside the sight sphere; if the active target (the crystal or a tower) is farthest than the player, then target the player, otherwise ignore him.

There are some problems with this approach however.
If the AI have started attacking a barricade, it won’t stop until dead or destroying the barricade; if someone else destroys a barricade (or something else that may prevent the path) that’s nearby, the AI will keep attacking regardless.

Nevertheless, I think that some of the problems with this approach may be ignored or fixed depending on the developers will, because there’re many things to consider which may easily be different for everyone.

Hopefully my final answer will help someone else struggling with similar problem.