After making a small implementation of Dijkstra's algorithm to solve my pathfinding needs, I realized how unfit it was to pathfind on a grid when my units could move in any direction. Since I don't seem to manage to implement a decent tie-breaker to make my tile paths more straight and natural compared to how a unit moves, I decided to try out a visibility graph approach. I simply decide on a few waypoints (the convex corners of walls) and compute the visibility between them. The code was pretty simple, but I have some severe problems going forward now, but let's start with the pros:
- Perfect paths. Units can actually just walk between the nodes generated with no need to post-process the tile path generated by Dijkstra's, which may result in an suboptimal path when the unit moves even though the tile path is optimal (since units don't walk in only 8 directions).
- Simple and possibly much more efficient pathfinding, since long distances can be quickly traversed with a single link.
- 175.000 links for a single 128x128 tile map with very few walls. I can optimize this by removing some unnecessary links to approximately half (or maybe even less) lines.
- The pre-computing of the lines is dead slow, taking more than a second. Since I pretty much have to recompute the entire visibility map every time a node changes (which they do all the time), this is simply put impossible. The above mentioned algorithm improvement will increase the computation time even more.
- The main problem is that I need to do n^2 visibility checks on the waypoints since I can't set a maximum distance (large rooms would be untraversable).
- How do I add links to the start and goal positions? Doing 175.000 raycasts for both the start and goal positions isn't exactly real-time, and there is no other solution that I can think of.
It gives me a lot better paths, but it is dead slow, so what can I do? Dijkstra's is a lot faster, but gives me pretty terrible paths. In most cases I can post-process the path to an identical path as a visibility graph would give me, but in some cases the unit might take a huge detour around an obstacle unless I do an unhealthy number of raycasts in the post-processing which seems to be my only solution at the moment.
I really did like visibility graphs, since they produce so nice results, but they are pretty much limited to very small maps due to both the cost of eventual dynamic generation and more importantly memory usage. Oh, well, I guess I just have to improve my path post-processing...
TLDR: This turned into a rant about visibility graphs being unusable for large maps due to memory consumption and insanely long pre-processing time.