8-direction path finding algorithm

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

I have players on a pitch, moving around freely (not stuck to a grid), but they are confined to moving in 8 directions (N NE E etc.)

I was working on using A*, an开发者_如何学Pythond a graph for this. But I realised, every node on the graph is equally far apart, and all the edges have the same weight - since the pitch is rectangular. And the number of nodes is enormous (being a large pitch, with them able to move between 1 pixel and another)

I figured there must be another algorithm, optimised for this sort of thing?

I would break the pitch down into 10x10 pixel grid. Your routing does not have to be as finely grained as the rest of your system and it makes the algorithm take up far less memory.

As Chris suggests above, choosing the right heuristic is the key to getting the algorithm working right for you.

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

You could weight a direction based on another heuristic. So as opposed to weighting the paths based on actual distance you could weight or scale that based on another factor such as "closeness to another player" meaning players will favour routes that will not collide with other players.

The A* algorithm should work well like this.

I think you should try Jump Point Search. It is a very fast algorithm for path finding on 8-dire.

Here is a blog describing Jump Point Search shortly.

And, this is its academic paper <Online Graph Pruning for Pathfinding on Grid Maps>

Besides, there are some interesting videos on Youtube.

I hope this helps.