Why can't Helen Keller drive? (pathfinding)
from 
Stardock Forums
Stardock Forums
Because she's a woman.
Now, why can't ships drive? Exhibit the following example. Ship A wants to get to point B without crashing into planet C.
A.......
.C......
........
........
......B.
Fortunately, the vastness of space allows an optimal path without even scratching the ship's bumper:
A*...... or A**.....
.C*..... .C.*....
...*.... ....*...
....*... .....*..
.....*B. ......B. (each 5 asterisks, 6 moves, however you want to call it. Many times, including this one, there will be many "optimal: paths, but there's no need to exhibit all of them here.)
But... how does my ship fly? As long as the diagonal is longer than the straight portion of the movement, it moves like this:
A*......
.C*.....
..*.....
...*....
....**B. 6 asterisks, 7 moves. It moves around the star, on the diagonal.
The A* algorithm should avoid this. In a space where the blocking objects usually take up very little more than a square here and there (ship walls excluded), A* should find the optimal path very quickly, but in this case it never finds it, even though the correct solution isn't computationally expensive in such a sparse map.
This minor mod, plus the ability to have trade routes travel more predictably Bresenhamian (linear approximation, same algorithm for selecting which pixels on your screen make a line) line paths, would rule - it would make placing your starbases easier for trade upping, and it would also make the movement engine more realistic-ish.
-H Dill
~SDC~
Now, why can't ships drive? Exhibit the following example. Ship A wants to get to point B without crashing into planet C.
A.......
.C......
........
........
......B.
Fortunately, the vastness of space allows an optimal path without even scratching the ship's bumper:
A*...... or A**.....
.C*..... .C.*....
...*.... ....*...
....*... .....*..
.....*B. ......B. (each 5 asterisks, 6 moves, however you want to call it. Many times, including this one, there will be many "optimal: paths, but there's no need to exhibit all of them here.)
But... how does my ship fly? As long as the diagonal is longer than the straight portion of the movement, it moves like this:
A*......
.C*.....
..*.....
...*....
....**B. 6 asterisks, 7 moves. It moves around the star, on the diagonal.
The A* algorithm should avoid this. In a space where the blocking objects usually take up very little more than a square here and there (ship walls excluded), A* should find the optimal path very quickly, but in this case it never finds it, even though the correct solution isn't computationally expensive in such a sparse map.
This minor mod, plus the ability to have trade routes travel more predictably Bresenhamian (linear approximation, same algorithm for selecting which pixels on your screen make a line) line paths, would rule - it would make placing your starbases easier for trade upping, and it would also make the movement engine more realistic-ish.
-H Dill
~SDC~
I might take you up on that. You seem to have studied A*.