How to find a location large enough to place an actor of given size procedurally at run-time?

I am working on an RTS game where players and AI can create structures, units, etc. I am looking for some advice on options that are already available in Unreal to find a location the AI can place its structures. Is there methods available that allow me to check for locations on the NavMesh that would accommodate an actor of a given size? I work in C++ so any solution is an option, C++ or Blueprint.

Currently I am looking at building a system that generates data from the pre-built navmesh but this has obvious difficulties with performance as the spatial system has to be updated along side navmesh when a dynamic obstacle is added to the navigation system, such as other structures. A system that works directly with the navigation mesh would be much preferred system of placement if one is available.

I don’t really know but I remember the EQS system has an invisible query Pawn class you can create a child class of, and maybe you can set a radius or collider on that. It maps out everywhere in the NavMesh it considers to be reachable when you give it certain parameters, and has a nifty debug draw of where all those locations are, as shown in the Epic tutorial series “Making Game-Ready AI”.

I’m not sure if you want it to care about whether said pawn could walk to those location or if you want it mouse-droppable instead. Maybe you would have to tweak values like Walkable Slope and step-up and step-down size to make it so walls don’t matter for reachability, but then would it circumvent the size restriction? IDK.

Something to look into though.

That is a solution we are currently working with but we are moving away from Behavior trees due to their inherent performance issues. EQS has the ability to create custom generators and custom tests in both C++ and blueprints but unfortunately testing pushes the idea out of performance parameters we want the AI to stay within.

With that said, we are currently working to build a system similar to EQS that maps out the area around the AI player to find flat smooth surfaces that are large enough to hold the navigation volume assigned to the structure during BeginPlay. We are taking cues from the EQS system but hard coded for performance of a known grid size and step size and without the generics used by the EQS system to hopefully gain a sizeable performance increase. We trace rays in a grid around a generating structure where the new structure is being built, looking for dramatic height changes or other structures already being placed. We store the data in a linked 2D matrix for kernel processing to generate a set of structured rectangles along the lines of a simplified octree or binary spatial representation that can be searched quickly to find relevant areas of correct size. As the game progresses these grids are updated as new structures are added and refined to incorporate the new data and remove rectangles from the search.

Thank you for your suggestion.

Have you consider making it gird style? Create a matrix that hold all the available slot that can be used for building, which can either input manually or automatically fill out based on the area, and calculate each slot real world position based on that matrix, then when user drag out a building, if there is enough space, you can snap that building to that location?

One solution is to spawn a collision sphere, that overlaps specific objects or channels that you want to test against (very import: it must not overlap the object type that the ground is made of). Then you get all overlapping actors. If there are non, you have a free space. Also you can set the spawn parameters to “Adjust if possible but always spawn”.
Furthermore, after detecting overlaps, you could try to move the sphere and check again.

Yes. This is very similar to the system we had been implementing with EQS. The only real difference was the dynamic nature of EQS. As we finally came to realize is that dynamic building placement requires by beyond the performance we were willing to give up for it. There are a multitude of considerations that go way beyond just finding a place to set the structure, such as best placement for defense, troop movement among the structures, etc. In the end, we built a system that we can edit on the map that lays out static locations for structures, turrets, etc. This allows us to control the layout so that units can move within the base without unnecessary avoidance and allows for us to determine where it would be best to placement defense turrets during runtime without any AI processing beyond selecting a location for the static locations. Performance wise alone this was a tremendous improvement as it eliminated a massive set of AI tasks associated with advanced understanding of how structure placement affected gameplay.

Thank you for your response.

Thank you for your response. The collision method is a very slow process that would have required an iterative process for the AI to dynamically place the structure by shifting through the available space until it was no longer in collision with any other object. Especially during late game, when several structures had already been placed, this would have caused severe performance issues when a single AI placed a structure, let alone when multiple AI placed structures simultaneously.

In the end, we opted for a custom player start class that allows artists to place locators around it that determine where AI should place structures to achieve good placement and good defensive placement of turrets. After reviewing, C&C, Dawn of War, and Rise of Nations, we feel that this may be close to how they handle the AI structure placement also.

Again, thank you for your advice. It was appreciated that you took time to answer.

Thank you to all for your responses. In the end, we decided to use static data assigned to custom player start classes.