How to implement the player's pursuit algorithm considering polygon obstacles?

  • 0
    There is a large rectangular map (5000 x 5000 px) and a list of convex obstacle polygons (100-500 obstacles). And then there are bots (10-50 pieces), which must chase the player without interfering with each other.

    I had this idea:
    Release 2 sensor segments from each bot, initially both aimed at the player. And while these rays cross the polygons, rotate (one clockwise, the other counterclockwise) them (by a small angle) until they stop crossing the polygons. And then direct in the direction of the ray, which previously stopped crossing the polygons.

    But this idea:
    First, it is very time consuming. (it is necessary to check the rays from each bot, which are also rotated, whether they intersect with each edge of the polygon, of which there are many).

    Secondly, it does not always lead to the expected results:
    If the beam length is too short, then the bot can get into a dead end, and then it will have to get out of it (and this is clearly not the optimal route)

    the bot will go orange when red is clearly more optimal.

    However, if the beam length is too long, then the bot, on the contrary, will mistake the narrow passage for a dead end, and will bypass it.

    Here gray is the sensor that crossed the polygons, so the bot will go orange, although red is also better.

    And here it is not clear whether there is a compromise in the length of the sensor, so that it can bypass dead ends and not confuse them with narrow passages?

    And thirdly, bots interfere with each other, but it is probably possible to solve this by taking into account not only obstacles, but also other bots.

    I have found many cell map solutions like this
    However, I don't have cells. And if I divide the entire field into cells, it will turn out to be too large a field, and this will affect performance (after all, the player does not stand still, but runs away).

    I also found a solution through the Nav Mesh, like this
    However, it says that, firstly, it produces not always the shortest path (The astar heuristic & amp; cost functions need another pass. They don't always produce the shortest path. Implement incomplete funneling while building the astar path?).
    And second, we need necessarily rectangular polygons (Allow non-square navmesh polygons from Tiled - ideally, any convex shape.). But I have more than just rectangular polygons.

    Well, the question arises of how to implement the task: Generating a path for the bot in real time to the player with optimal avoidance of obstacles (polygons) and taking into account the trajectory of other bots
    JavaScript Anonymous, Mar 1, 2020

  • 4 Answers
  • 0
    If the obstacles are with corners and there is no straight path, then at first glance it seems that the bot should move in the corners. This means that you can imagine the angles of the obstacle as the vertices of the graph (the bot and the player are also vertices) and find a path from the top where the bot is to the top of the player. The paths between the vertices may have a cost (the length of the path), some paths may be blocked (for example, by other bots, if they stand there for a long time)
    Evangeline Townsend

  • 0
    Divide the field into cells, this is the best, and think about whether it is important for you to find exactly the shortest path or you can use A * with a heuristic algorithm .

    Well, you need to think about optimization if the speed is not sufficient, the larger the cell size, the faster the algorithm will work, but the lower the accuracy, you should not make the cell size larger than the bot size (it just may not fit into small gaps). You don't have to look for a path at every step, do it less often. Perhaps it is worth looking for a path not for each bot separately, but for example taking the bot and everyone who is within a certain radius and line of sight from it and looking for a path for this entire group. Well, do it first in the most non-optimized way, and then look at the speed of work
    Anonymous

  • 0
    Pathfinding algorithms are called A star . Yes, the examples are mostly done in cell fields, but, in the very definition of the algorithm:



    is a search algorithm that finds the least cost route from the initial vertex to the selected final vertex in a weighted graph.




    Nothing is said about the fact that it works only on the cellular field. So I would look for examples of the implementation of this algorithm - for sure there is one that suits you.
    Anonymous

  • 0
    Since the map is rectangular (or can be described by a grid) and its size is small (5K * 5K is small), then the ideal solution is wave tracing, which is one of the implementations of Breadth First Search. The shortest path will be found, but each polygon must first be "drawn" into the grid so that the cell cannot be entered.
    Anonymous

Your Answer
To place the code, please use CodePen or similar tool. Thanks you!