Visibility graph pathfinding

Game Mechanics Artificial Intelligence
#1

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.

Cons:

  • THIS:

    http://img850.imageshack.us/img850/2241/linesg.png
  • 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.

#2

Check in the Shared Code section. Someone already did something similar.

#3

I remember that, but that was for arbitrary polygons. I have tiles…

#4

Waypoint based pathfinding is pretty sucky for 3d worlds IMHO. I’d suggest pre-processing your tile map into larger ‘walkable’ rectangles of adjacent tiles, then making a graph from adjacent rectangles and running A* over this walkability graph.

#5

[quote=“Orangy Tang,post:4,topic:37914”]
I’m inclined to disagree - I’ve used a combination of waypoints and local fuzzy navigation to very good effect. Hand placed waypoints work best, but programatically putting a waypoint close to every convex corner also works quite well.

[quote=“theagentd,post:1,topic:37914”]
Not sure what you mean by this - do you mean that the map’s geometry is constantly changing?

#6

[quote=“SimonH,post:5,topic:37914”]

Not constantly, but very often.

#7

if A goes to B. Draw straight line between A and B. If that line intersects an object, split the line at C and move C until A-C and C-B miss original object (move C normal to line A-B). Recurse on A-C route and C-B route. I think this might only work for concave objects.

#8

Also consider using a quad tree for this. So you look in very large grids and only look in more detail if the grid has an obstacle in it. In this way you only need to get into very fine detail in a few instances, so it can greatly reduce your comparison count.

#9

You could use the old grid approach but smooth it out during execution by periodically doing raycasts towards the node following the current next node.

It will make the path shorter if possible during the path following phase.

There are also some other methods for optimizing bad paths, but I have only tested this method with good results (not on a grid though).