# AI pathfinding in mostly-free space

I'm working in an action/strategy proyect. Consider it a RTS game. The game is in 2D (with LibGDX), and I have a lot of soldiers moving along. Now I have to implement the AI. Let me say some things about my current design:

• The map has been constructed with tiles. However, I want to allow the soldiers to move in every direction -so using the tiles as graph for A* is not a good idea.

• The obstacles are given by collision rectangles. Maps will have a lot of free space, and collision rectangles don't fit the tiles -that makes even worse the election of A* with tiles.

• Waypoints, for the same reason, are not a good idea. I would need a very big net and soldiers would move in strange ways, as pointed out here: http://www.ai-blog.net/archives/000152.html

• I've taken a look to the LibGDX-AI library. I would like to make soldiers follow the captain or use some kind of formation. Looks like this library is a good choice to make that.

Some things I know:

I also have read about potential/vector fields and navigation mesh. The fields look interesting, but I'm not sure of how to implement them for my case. They could be good for pahtfinding, but some soldier have to follow the captain and move in formation. I think nav meshes won't solve my problem. As I've said, I have a lot of free space, and soldiers can move whatever they want, so the question "how to move the soldier inside the mesh?" remains.

QUESTIONS:

• How to make a free-space AI pathfinding which avoid my collision rectangles?
• How to make this compatible with formations like following the player across the map?
• Is there any way to use LibGDX-AI to do this?
• You can get away with the "obstacle avoidance" steering behavior as your only pathing method, if your map consists of many free-standing convex objects. gamedevelopment.tutsplus.com/tutorials/… Oct 4 '15 at 8:49
• That looks really well! I'll give that a try :D Oct 4 '15 at 9:20
• You say the map is constructed with tiles, but the obstacles don't fit those tiles. Aren't the obstacles the most important thing of the map? How can the map then be made of tiles? Oct 6 '15 at 14:41
• @Springrbua I made the map with Tiled. To create the collision map, I could add a tile property called "collision" and set it to 1 if there's collision, then add this tiles to a list. In that case I have to loop through the tiles with collision=1. This approach has two problems: first, some obstacles don't fit the complete tile. Second, for a big wall I need to compute various checks. So what I do is to create Rectangle Objects in an Tiled Object layer. With this I need less iterations to check the collision and I can make the rectangles fit the obstacle. Oct 7 '15 at 13:41
• I do side with @Springrbua here, if the soldiers can move in any direction, you can safely ignore the fact that the underlying map is tiled and just treat the problem like you are moving in a free 2d plane with some obstacles. And for that the steering behaviours VaTTeRGeR mentioned may be all you ever wanted! This of course stops being true, when the tiles have a limiting character on possible paths because of other game mechanics, like political affiliation. Dec 26 '15 at 1:34

Knowing how A* works, it's not always the best choice for open spaces. Sometimes a simple if x>myPos.x then x = x - 1 type of model is fine for what you need to do. What would be better, I'm thinking, is a simple position change model backed up by A* when it finds obstacles.

A good source for A* algorithm-type-stuff is:

A* Algorithm

This is what I used when I was learning the algorithm. It also goes into its pros and cons.

Back to your questions: From my personal experiences with A*, there are other, quicker algorithms for finding paths until you need to find a way around obstacles, which I assume aren't too trappy (they look like cups or they could easily make the AI walk through an inner space for a while while chasing you). For the "trappy" areas, A* is fair as well.

However, the obstacles do not need to be on a perfect grid either, there is plenty of research on non-square "grids." Instead of focusing on squares, you could place "nodes" on the corners of your obstacles instead, creating a quadrilateral shape that isn't necessarily square. This would be referred to Theta*, and it doesn't look horrid for an open space, which would be less complex to traverse with Theta*.

Theta* Algorithm

I don't have as much experience with herding behaviors, but my best idea is to make a node in the center of the group of moving bodies, then make all the moving bodies move to fit a position surrounding that central node.

Let's pretend &s are soldiers, and the * is the above mentioned node:

       &
& & * & &
&   &


Then all you'd have to do to make new formations would be to define new "relative" positions around the central node for your little AIs to follow, and your central node would be the thing that'd actually be used in the A* algorithm to find the path, the little AIs would follow the node's predefined formation. That's one way of making some basic squads.

It might look like this

node.x + 10, node.y + 0

     * &


little AI should move slightly to the right of the central node at all times

I'm not honestly too sure about LibGDX AI. But with some determination, you could do it yourself too. But if you're focused on LibGDX AI, you can fashion nodes/coherent grids from your objects if you can find a tile size small enough to be roughly correct but not too small and feed them into the AI framework.

Mostly, I just recommend you put a good amount of focus on the amount of nodes you are checking on each pass, because A* can get really slow on large open areas and AI traps because of how long it takes to sort through a massive array of nodes; it will be correct, but it will also be noticeably and annoyingly slow. But if you're implementing this, one good way I've found for sorting through the nodes is the Binary Heap, which is easier to use when sorting through "good" nodes in the A* algorithm, which is a high score contest for found nodes. They're quick, and they're not too hard to implement even for a beginner.

Binary Heap

• Some variant of Hierarchical A* might be good to supplement your notes, combined with path smoothing during the movement. Oct 4 '15 at 7:13
• Looks promising. The Theta* could be an elegant solution to the problem. The only problem is that it also relies on waypoints, and a map with a lot of free space needs a lot of waypoints to give the impression of "free movement" of soldiers. And, as you've said, things can become slow. And also, remember that soldier have to follow a captain -that means, recalculate the path every certain time. Oct 4 '15 at 7:41
• Pathfind for the captain. Use flocking behavior with collision detection for all the soldiers following the captain. Not all of them need a path, just one that everyone else tries to follow. Oct 4 '15 at 21:12
• Don't forget, that a formation might not fit through a gap between two obstacles. You also have to solve this problem. Oct 6 '15 at 14:51