Jump to content
  • Advertisement
Sign in to follow this  
Josip Mati?

A* advices

This topic is 1863 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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 smile.png

Share this post


Link to post
Share on other sites
Advertisement

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).

Share this post


Link to post
Share on other sites


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.

You seem to be missing the point. You won't actually detect the full path (or even if it is possible to get there) until you actually went though all open/closed blocks. How many frames will it take - that depends on the number of blocks you check each frame vs number of all blocks. if you check 5 blocks each frame (for each unit) and you need to check 100 blocks to come up with full path, then it takes 100/5 = 20 frames to come up with full path - and that is OK.

 

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.

Share this post


Link to post
Share on other sites

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.

Edited by Aurioch

Share this post


Link to post
Share on other sites

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.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!