AI pathfinding in mostly-free space

Question

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?

Answer 1

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