I'll jump straight into the context:

I have a 2D grid map stored into a simple 2D object array. Every object and agent exists on this 2D array (so their positions are discrete and binded to their location on the array). I'm expecting agents to move quite a bit, so the grid is dynamic in nature. The game itself is fully deterministic and discrete operations based, the goal being to make it multiplayer portable (with the lockstep method). I'd like to populate the map with large impassable structure, concave and convex, such as buildings and lakes.

These agents are rigged with an FSM for decision making. I wish them to be able to act on these decision in believable way, and one of these challenges is to allow them A > B navigation that works and looks believable.

I'd like to have as much active npc in the world as possible, and right now the biggest hurdle is finding the right path finding algorithm. I'm not sure about my update tick budget, but right now I'm thinking anything reliably less than ~500ms would be acceptable (I'm making the game "turn based" for testing purposes, and wish to later make it real time using a good amount of linear interpolation on the display layer).

At this time I have a 100x100 map for testing, with hundreds of agents (with almost fully implemented AI, lacking path finding and collision detection), and a tick time of 10ms.

What pathfinding algorithm and implementation would suit this situation ? I know A* would be okay-ish, but since the grid changes every ticks, and the number of agents is quite large, I'm not sure it would be the best (short of computing the path once and evaluating if a collision occurred each travelling steps, then recomputing it). I'm trying to keep everything simple, and I am willing to reduce the scope of the simulation regarding the number of active agents to do so. Any idea or advice ?

FYI, I'm not sure if I'm doing this right, but every agent has a command list, which contains a list of "todos" populated by the fsm and ran each ticks (the first command in line). The pathfinding algorithm would be contained in the command object, so the flexibility is quite large (it could be broken down into smaller steps).

What have you tried? What numbers are you getting back in response times? How are you factoring out early exits for path-finding? Are you making sure only relevant objects are being checked within objects in their sector, ect...? Do you split up different logic checks so you're not doing everything in a single tick?

So you're changing your grid every 10ms (as per your change every tick)? You need your map to change 100 times a second???

Try to look for potential field. A* is pretty slow when you have huge amount of agents.

With potential field, I can have 40,000 agents in a 500x750 maze and still get 80FPS.

If it is still to slow, you could remove AI logic from the main thread and put it in a thread-pool.

On 3/16/2019 at 5:52 PM, Rutin said:

What have you tried? What numbers are you getting back in response times? How are you factoring out early exits for path-finding? Are you making sure only relevant objects are being checked within objects in their sector, ect...? Do you split up different logic checks so you're not doing everything in a single tick?

So you're changing your grid every 10ms (as per your change every tick)? You need your map to change 100 times a second???

I haven't tried anything yet, I don't want to lose time on a lost cause. I have no idea what I'm doing regarding path finding. Everything should be done in a single tick to ensure the 1000 archer method will work for future network implementation. Also the map changes every tick, but only because mobs may change position every ticks. The map is technically updated anytime something changes, since it's the container of these things. And I don't update the game at max speed, so it doesn't update 100 times a second, right now it is rigged as a turn based thing so it's updating every time the player has finishes his actions. Later I plan to make it real time, but not with a 100 times a seconds update rate. The end goal would be to port the game, which is now contained in a C# library, plugged on a console for output, to a proper game engine to take care of graphics, inputs, sounds, etc (ofc the update loop will run async to the draw loop and the input system).

22 hours ago, LLachance said:

Try to look for potential field. A* is pretty slow when you have huge amount of agents.

With potential field, I can have 40,000 agents in a 500x750 maze and still get 80FPS.

If it is still to slow, you could remove AI logic from the main thread and put it in a thread-pool.

I've found multiple article on the method, it looks promising. Can you point me in the direction of an implementation directed to game implementation. Also, I need to avoid multi threading and floating point operation as much as possible to keep each game tick completely deterministic.

If you end up using A*, I want to point out that in a situation where there are static and dynamic obstacles, you can solve the "all shortest paths" problem with static obstacles only (as a preprocessing step) and then use it as an admissible heuristic in A*. This should make A* extremely fast in situations where the dynamic obstacles don't block major routes. Depending on your game design, this might be the typical case.

On 3/18/2019 at 2:56 PM, alvaro said:

If you end up using A*, I want to point out that in a situation where there are static and dynamic obstacles, you can solve the "all shortest paths" problem with static obstacles only (as a preprocessing step) and then use it as an admissible heuristic in A*. This should make A* extremely fast in situations where the dynamic obstacles don't block major routes. Depending on your game design, this might be the typical case.

 

Yeah I thought about it, but I want the game area to be as dynamic as possible.
On another note, I just tried to write my own pathfinding algorithm and I think I failed spectacularly. The failure comes from the fact the algorithm thinks it's sometime cheaper to go away from the target in one direction even if it's hugging a wall to advance (it might in the case the wall is L shaped and will block it's path). I think I'll ultimately have to try A*, hope it's not *that* slow.
Here's the failed code if anyone is interested (I think I'll call it 'Naive Search')
 

       public List<point> gridSearch(point start, point goal)
        {
            bool[,] visitedNavGrid = new bool[Game.map.size, Game.map.size];

            point currentPoint = start;
            List<point> chosenPath = new List<point>();

            int[] consideredAttachedPointWeigh = new int[8];

            point[] attachedPointPlan = new point[8] 
            {new point(-1,-1), new point(0,-1), new point(1, -1),
             new point(-1, 0),                  new point(1,  0),
             new point(-1, 1), new point(0, 1), new point(1, 1)
            };

            //Array represents the 8 possible movement option vector from the point c
            //0   1   2
            //3   C   4
            //5   6   7

            //int lastDirection = 0;

            chosenPath.Add(start);
            //The actual algorythm
            while (chosenPath.Last() != goal) // Until a path is found or no solution is found
            {

                    for (int i = 0; i <= 7; i++)
                    {
                        int stuckTreshold = 0;
                        point evaluatedPoint = chosenPath.Last() + attachedPointPlan[i];
                        //check for obstacle, or if the grid has been visited
                        if (Game.map.Dobjects[evaluatedPoint.x, evaluatedPoint.y] == null &
                            visitedNavGrid[evaluatedPoint.x, evaluatedPoint.y] == false) 
                        {
                            consideredAttachedPointWeigh[i] =
                                (evaluatedPoint).ManhattanDistance(goal); //The larger the worst
                        }
                        else { consideredAttachedPointWeigh[i] = 1000000000; stuckTreshold++; }
                        if (stuckTreshold > 7)
                        {
                            //The agent is stuck; a contingency should be planned (rn it goes back to it's original pos)
                            List<point> reversedPath = chosenPath;
                            reversedPath.Reverse();
                            chosenPath.AddRange(reversedPath);
                            return (chosenPath);
                        }
                        
                    }

                    int direction =
                        Array.IndexOf(consideredAttachedPointWeigh, consideredAttachedPointWeigh.Min());
                    chosenPath.Add(chosenPath.Last() + attachedPointPlan[direction]);
                    visitedNavGrid[chosenPath.Last().x, chosenPath.Last().y] = true;
                
            }
            chosenPath.Remove(chosenPath.First());
            return chosenPath;
        }
    }
}

What's interesting is the solution to fix this would be to store each visited tile in a tile structure and then find the shortest path within the structure, which would be remarkably similar to A*.

It seems I fixed the weird behavior by subtracting the distance between the evaluated tile and the start tile to the tile cost function:

                            consideredAttachedPointWeigh[i] =
                                (evaluatedPoint).ManhattanDistance(goal) * 2
                                -
                                (evaluatedPoint).ManhattanDistance(start)
                                ;

If anyone knows what algorithm this is, please tell me (I wrote it from scratch by intuition, but I'm sure it's already named). So far it works very well for every use case that randomly came up, haven't tested edge cases yet. I'll keep the thread updated if anyone is interested. It's really fast and it works.