This is a demonstration of my map preprocessing algorithm. It reduces the amount of work to find paths inside a map.
Wall
Walkable, empty space
Wall corner
Found path. In preprocessed, just a fill between corners
Wall corner, which is in the path
Connects nodes in the graph
Distance:
Shortest path is calculated normally with Dijkstra's algorithm. As you can see, the graph of connected nodes is quite large even in a small map.
Dijkstra's algorithm is not good in maps that contain large empty fields.
Distance:
Map is preprocessed to reduce the amount of work to find a path. The algorithm doesn't guarantee the shortest path but it would be a good path finder in a game for example.
Preprocessing helps a lot in maps that contain large empty fields.
For each block that isn't a wall:
Are there walls in diagonal directions at one step away? (Blue line)
Is there empty space in straight directions between the any of the diagonal walls and current block? (Yellow box)
If answer was 'yes' to both, mark the block as a corner. (Light green)
This is repeated for each empty block, until the corners have been detected:
For each corner:
Go through other corners and check if there is a clear route to them
If there was a clear route to another corner, connect it. (Gray line)
Red line = no clear route between corners.
A clear route is defined as:
If there are no walls in the blue rectangle that can be drawn between the corners, it is a clear route. In the above example, there's not a clear route.
Because a clear route is defined this way, the algorithm does not find the shortest path always.
Now Dijkstra's algorithm has much less work to do.
Note that the path is calculated only between the corners, but the actual path filled with the orange path blocks. This is possible because there is known to be a clear route between the connected corners.