Hello

I'm still working on AI for my game, however I'm getting close. After 2 completely failed attempts and 1 semi-decent attempt I finally wrote that works as intended which I am happy with. However, there are 2 problems I'm currently trying to solve:

• AI is still blind for map changes until it recalculates the path
• Enemies cannot avoid each other if they need to pass through same node

I'm using 15*15 square grid with no diagonal movement, single region.

I've come up with several possible solutions which are (or at least should be) fairly easy to implement, however I'm not pleased with either of them. I've also checked multiple sources on internet about A* but either there wasn't much useful stuff or I'm still too stupid (or "inexperienced") to figure out proper solution from material I found.

While I'm trying to figure out proper solution, I'd like an opinion of more experienced people on solutions listed below and code provided, or maybe some other ideas I could try.

1) Perform only several steps with each update while taking other enemies into account

This solution looks nice, however I cannot figure out how would I be able to detect if there is no path, since A* (at least the form I know) detects it from having an empty list of open nodes at the start of new loop.

2) Update path when collision with other unit is detected

This "feels" more like a band aid rather than valid solution. It helps resolving stucked enemies but does not fix the problems. Impossible if there are 2 parts of the map connected only with one 1 tile wide path.

3) Recalculate path each Update when possible

I tried it... just now. Enemies started dancing between 2 nodes - I assume there is the path of equivalent cost from both those nodes.

4) Recalculate path when 2 enemies are going to step on same node

Sounds nice, however also suffers with "choke" problem.

AI code:

[spoiler]

            if (FindAIPath.Count > 0)
                AI[FindAIPath.Dequeue()].UpdateAI();
            foreach (var item in AI)
            {
                item.Pathfollow();
                if (!item.PathFound) FindAIPath.Enqueue(AI.IndexOf(item));
            }

[/spoiler]

Pathfinding code:

[spoiler]

        void Pathfinding()
        {
            Square currentSquare = new Square(Tanks[Index].Position, TileSize, null);

            OpenList.Clear();
            ClosedList.Clear();
            Path.Clear();
            pathFound = false;

            OpenList.Add(currentSquare);

            do
            {
                // Take the square with lowest F number from open list and put it in closed list
                currentSquare = OpenList[0];
                OpenList.Remove(currentSquare);
                ClosedList.Add(currentSquare);

                // For each adjacent square...
                List<Vector2> adj = new List<Vector2>();
                adj.Add(new Vector2(currentSquare.Position.X - TileSize, currentSquare.Position.Y));
                adj.Add(new Vector2(currentSquare.Position.X + TileSize, currentSquare.Position.Y));
                adj.Add(new Vector2(currentSquare.Position.X, currentSquare.Position.Y - TileSize));
                adj.Add(new Vector2(currentSquare.Position.X, currentSquare.Position.Y + TileSize));

                foreach (var a in adj)
                {
                    Square sq = new Square(a, TileSize, currentSquare);

                    // If it is unwalkable, ignore it
                    if (UnwalkableTest(sq.Tile)) continue;

                    // If it is destination, stop with algorithm
                    if (sq.Tile == Target.Tile)
                    {
                        ClosedList.Add(currentSquare);
                        currentSquare = sq;
                        pathFound = true;
                        break;
                    }

                    // If it is in closed list, ignore it
                    if (ClosedList.Exists(x => sq.Position == x.Position))
                        continue;

                    sq.AssignValues(Target.Position, step[0]);

                    // if is in open list, check if old path is better
                    int i = OpenList.FindIndex(x => x.Tile == sq.Tile);
                    if (i > -1)
                    {
                        if (sq.G < OpenList.G)
                        {
                            OpenList.Parent = currentSquare;
                            OpenList.G = sq.G;
                            OpenList.F = OpenList.G + OpenList.H;
                        }
                        continue;
                    }

                    // Add to open list
                    i = OpenList.FindIndex(x => x.F > sq.F);
                    if (i > -1) OpenList.Insert(i, sq);
                    else OpenList.Add(sq);
                }

            } while (OpenList.Count > 0);

            if (pathFound)
            {
                while (currentSquare.Parent != null)
                {
                    Path.Push(currentSquare.Position);
                    currentSquare = currentSquare.Parent;
                }
            }
            else
            {
                if (ClosedList.Count > 1) Path.Push(ClosedList[1].Position);
                pathFound = true;
            }
        }

[/spoiler]

Maybe I could work on art a little until I figure out proper solution... XD

Thanks in advance

It helps resolving stucked enemies but does not fix the problems. Impossible if there are 2 parts of the map connected only with one 1 tile wide path.

First of all, it looks like you need to start taking into account 1-block-wide paths that can block everyone else. That alone will take care of majority of the artifacts you are experiencing.

You need to keep track, in a separate array, which blocks (e.g. bridges/tunnels/roads) are those potential blockers. And when these blocks are a part of some other enemy's path, you simple adjust the path of the unit to stop at the first block near the start/end of the bridge/tunnel/road that won't block anyone. Keep a separate FSM state for those enemies, so you can easily track them later when the path becomes clear again.

There have been numerous RTS games where you could actually see this, when someone was crossing the bridge, that all other units started to mess around (e.g. masking the fact that they were waiting for the bridge to be cleared).

1) Perform only several steps with each update while taking other enemies into account

This solution looks nice, however I cannot figure out how would I be able to detect if there is no path, since A* (at least the form I know) detects it from having an empty list of open nodes at the start of new loop.

All, that you really want to do, is just to give the player an illusion of instant pathfinding (even if it takes up to a second to come up with full path).

If your initial estimate was wrong, well that's OK. You never played an RTS where you give few units a command and they suddenly change their direction after a second ?

This is why it takes so long in those RTS games to finish the initial rotation towards the correct direction. While they are rotating, they're giving the player an illusion that they know where to go, even though, for a fact, they still don't.

I indeed completely missed the point of partial pathfinding, thanks for pointing that out >.<

Also, thanks for advices, I'll keep em in mind for future projects; unfortunately, I'm not working on RTS (far too complicated project for me right now) but on something far simpler. I'll try to figure something out; maybe I could look again at the original game (Namco's Battle City)...

Or maybe I'm overcomplicating things, which wouldn't suprise me.

About your examples, thanks for reminding me of "stupidity" of Dragoons from StarCraft XD

EDIT: While we're talking about RTS games, how does pathfinding know when to stop moving units if destination is unavaiable? For example, units in StarCraft will try to get to the target until you stop them while in other RTS they'll come as close as they can to target and then stop.

FWIW, I would do this:

Calculate the path, regardless where the enemies are in the world:

#1, when the Map changes (ie, a wall is built), check if an AI's path will cross that tile, if so, re-calculate for that AI.

For intersecting Enemies, that can be tough:

What if 2 AI are moving in opposite directions, and their path's occupy the same line of tiles, but in opposite directions? One solution would be to move one AI off a tile for a few frames, then move him back when the other AI is clear. Either way, you'll have to do something before the point of collision between the 2 AI.