Question

Does anyone know an easy algorythm, which provides the fast calculation of the way between to points and also can save the points on that way?

E.g. P1(1|1) -> P2(4|5)
Fastest way: 1|1 -> 2|2 -> 3|3 -> 4|4 -> 4|5
And this list of points should be calculated.

Thanks in advance.

Answer 1

Hm. Interesting problem. I didn't take an algorithms course in college. If I had I probably would have come across this, but my first pass would first check to see if there's a chance the two points form a straight line. If so, then step across that line. If they don't, then I would step diagonally in the general direction until either a) the destination point is reached or b) I'm one step horizontally or vertically away from the destination point (which is what you did in your example).

Answer 2

@farmdawgnation I also thought of that, but i didn't know, if there is a better algo or better way to do this. Also i'm not sure, if this really calculates the direct way and if all the boxes within the circle are used.
As an explanation: I need this "waypoint-finding-algo", to calculate the visible environment for one agent (it's an agent-based simulation). One agent has a sight-range of ten squares, e.g. But i can't just add all the squares within the range - some are obstacles and that, what's behind the obstacles, can't be seen by the agent.
My idea was to take every square at the end of the range and to get all the squares on the way to the last one and to check if the current square is an obstacle - if so, the algo breaks and saves the other, visible, squares.

But i will try, if that works, so thanks^^

Answer 3

Solved it now, i used a simple heuristic wayalgo, which is basically a dijkstra-algorithm.