At this point another competent coder joined the team and we were discussing path finding algorithms for the game. He made a quick A* implementation for testing, and it was soon apparent that the desired grid size was far too large.
After thinking of this for a while we deduced that our lives would be much easier if we changed the maps into vector maps and forgot about the tiles. It also made my life easier. This one was a really good decision!
One of the problems we had with the new polygon-based path finding algorithm was that the precalculation time required for fast path finding would be all too large. We needed to search all the visible polygon corners from all the other polygon corners in the map. Each one of these would require checking all the other polygons. This was unacceptable. Moving from a map to map had to be fast.
Even after heavily optimizing visibility tests: raycasting with grid-based acceleration and limited polygon density, it would still be at least O(n2). For fast precalculation times we really didn't have the time to find all the visible corners. We needed a local approximation, caring only of the nearest polygons. We achieved this by limiting the visibility range and adding 'dummy points' where there were no polygon corners nearby, to connect to the far-away polygons. The resulting precalculation time was unbelievably fast and the actual path-finding part didn't suffer much.
Here's an image of the precalculation process. The green grid represents the grid used in the acceleration. It should be a lot sparser in a real use case. The blue polygons represent the actual walls used in the path finding, pulled out from the red original walls next to them. The resulting, somewhat optimized network of links, is drawn in red.
This local system requires the found route to be cleaned afterwards, by dropping any possible unnecessary waypoints. But there's also a bug in the image. Can you spot it? Can you be sure? :-)
