Trajectory search algorithm in 8 directions

Question

I am having trouble finding the right path finding algorithm for some AI I'm working on.

I have players on the field moving freely (not tied to the net), but they are limited to movement in 8 directions (N NE E, etc.).

I worked on using A * and a graph for this. But I realized that each node on the graph is equally far from each other, and all edges have the same weight - since the height of the rectangle. And the number of nodes is huge (this is a big step, with it you can move between 1 pixel and another)

I realized that there should be a different algorithm optimized for this kind of thing?

Answer 1

I would smash the box down to a 10x10 pixel grid. Your routing does not have to be as fine-grained as the rest of your system, and this makes the algorithm take up much less memory.

As Chris suggests above, choosing the right heuristic is key to making the algorithm work correctly for you.

Answer 2

If players move in straight lines between points in your grid, you really don't need to use A *. The Bresenham linear algorithm will provide a direct line path very quickly.

Answer 3

You can direct a direction based on another heuristic. Thus, unlike weighting tracks based on actual distance, you can weigh or scale based on another factor, such as “proximity to another player,” which means that players will maintain routes that will not interfere with other players .

Algorithm A * should work well.

Answer 4

I think you should try Jump Point Search. This is a very fast algorithm for finding paths on the 8th.

Here is a blog describing the search in Jump Point Search.

And this is his scientific article Trimming Online Graphics to Find Paths on Grid Maps >

In addition, there are interesting videos on Youtube.

Hope this helps.