• Announcements

    • khawk

      Download the Game Design and Indie Game Marketing Freebook   07/19/17

      GameDev.net and CRC Press have teamed up to bring a free ebook of content curated from top titles published by CRC Press. The freebook, Practices of Game Design & Indie Game Marketing, includes chapters from The Art of Game Design: A Book of Lenses, A Practical Guide to Indie Game Marketing, and An Architectural Approach to Level Design. The GameDev.net FreeBook is relevant to game designers, developers, and those interested in learning more about the challenges in game development. We know game development can be a tough discipline and business, so we picked several chapters from CRC Press titles that we thought would be of interest to you, the GameDev.net audience, in your journey to design, develop, and market your next game. The free ebook is available through CRC Press by clicking here. The Curated Books The Art of Game Design: A Book of Lenses, Second Edition, by Jesse Schell Presents 100+ sets of questions, or different lenses, for viewing a game’s design, encompassing diverse fields such as psychology, architecture, music, film, software engineering, theme park design, mathematics, anthropology, and more. Written by one of the world's top game designers, this book describes the deepest and most fundamental principles of game design, demonstrating how tactics used in board, card, and athletic games also work in video games. It provides practical instruction on creating world-class games that will be played again and again. View it here. A Practical Guide to Indie Game Marketing, by Joel Dreskin Marketing is an essential but too frequently overlooked or minimized component of the release plan for indie games. A Practical Guide to Indie Game Marketing provides you with the tools needed to build visibility and sell your indie games. With special focus on those developers with small budgets and limited staff and resources, this book is packed with tangible recommendations and techniques that you can put to use immediately. As a seasoned professional of the indie game arena, author Joel Dreskin gives you insight into practical, real-world experiences of marketing numerous successful games and also provides stories of the failures. View it here. An Architectural Approach to Level Design This is one of the first books to integrate architectural and spatial design theory with the field of level design. The book presents architectural techniques and theories for level designers to use in their own work. It connects architecture and level design in different ways that address the practical elements of how designers construct space and the experiential elements of how and why humans interact with this space. Throughout the text, readers learn skills for spatial layout, evoking emotion through gamespaces, and creating better levels through architectural theory. View it here. Learn more and download the ebook by clicking here. Did you know? GameDev.net and CRC Press also recently teamed up to bring GDNet+ Members up to a 20% discount on all CRC Press books. Learn more about this and other benefits here.
Sign in to follow this  
Followers 0
Josip Mati?

A* advices

4 posts in this topic

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[i].G)
                        {
                            OpenList[i].Parent = currentSquare;
                            OpenList[i].G = sq.G;
                            OpenList[i].F = OpenList[i].G + OpenList[i].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

0

Share this post


Link to post
Share on other sites

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

0

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.

1

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
0

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.

0

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now
Sign in to follow this  
Followers 0