Pathfinding with direct line movement

Our pathfinding routine works pretty good, although it does not always find the shortest path. One problem we see is that the actual path taken does not look very intelligent, as it will follow the lines that traced to the goal. We know that when backtracking we always seek for at tile with a step number lower than the previous one, this way we are guaranteed to get back to the start. The path chosen is often bad looking because it follows these lines where it should just cross over an area directly to some other point.

There is an easy solution to this, but it will require some extra calculation. By finding the best direct lines that does not intersect with obstacles during the backtracking we can get a better looking path and possibly a shorter path than othewise. Direct lines are always the shortest way of getting from A to B.

Below is an image of how this method is in action. The gray lines that are generated during the tracing for the goal are the foundation for the backtracking. It generates direct lines where the yellow tiles are the endpoints for the lines, and can be used as waypoints for the path. The brown tiles are the actual traversion between the waypoints towards the goal.

Below is a ZIP file containing the program (written in pascal) along with an executable for you to try out.

Code and executable for direct line pathfinding (11082 bytes)


Back to index page.

john@lis.pitt.edu