8-direction path finding algorithm

views:

172

answers:

+3 Q:

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*, and 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?

+1 A:

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.

Chris 2010-04-06 22:41:22

Thanks, that's a good idea, but as I just said above:Finding the path isn't the only problem though, I don't want players running around on what obviously looks like a grid, it's un-realistic, it's doing that - but sticking to 8 directions, that's proving the problem

Sticky 2010-04-07 20:34:45

+2 A:

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.

James Westgate 2010-04-06 22:47:13

This seems like a good idea, use an A* grid for moving around, and maybe a smaller grid when they get closer to the target.They'll be re-assessing the path every second or so anyway - and the target is likely to change every time, so it doesn't need to be too detailed.Finding the path isn't the only problem though, I don't want players running around on what obviously looks like a grid, it's un-realistic, it's doing that - but sticking to 8 directions, that's proving the problem

Sticky 2010-04-07 20:34:22

+2 A:

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.

andand 2010-04-07 13:47:24

Thanks, but they're fixed to 8 directions, and if they followed that, its a bit too pixel-perfect (would be switching between North / East every frame, for example)

Sticky 2010-04-07 20:30:04

ansaurus

tags:

views:

answers:

8-direction path finding algorithm

related questions