Path finding for Vector Based System

Question

I understand that typical path algorithms are based on nodes in a graph (not tiled nodes or whatever), but i can't get my head around to find an idea how to implement a path finding algorithm for a grid with endless possibilities (my mapdata is based on vectors so for example an rectangle could be the 1000th of one unit wide but still an obstacle). I basically have a map with 1 or more fixed sized units and need them to travel the shortest path through a field of rectangles and circles which are not passable. The question is is there a way to use normal pathfinding algorithms with that mapsceme (how do i calculate the nodes then?) or do i have to use a special one?

Answer 1

Welcome to the wonderful world of continuous state motion planning. A few years ago I wrote a Gamasutra article on this topic.

Here are some solutions to your problem:

Navigation Meshes

This works by constructing a graph of nodes and edges of your scene based on some simple rules. For instance, you can construct a Visibility Graph of the scene, which is just the graph of all rays that pass through free space from each vertex of each obstacle to each other vertex. By running A* on the Visibility Graph, you get optimal path length solutions in polygonal environments. If you're concerned about things other than length, such as "naturalness", you might want to try another navigation mesh algorithm such as a Voronoi Graph, which puts nodes such that they are equidistant from obstacles, and then adds edges between the nodes. Even simpler than all of these is the Probabalistic Road Map, which just places the nodes randomly and connects them to their nearest neighbors. In all of these cases, A* is usually used to plan a path through the nodes on the grid.

Lattice Grids

Another option is to simply discretize your space into a simple grid. Put a node at the center of each grid cell, and connect nodes to each other if the ray between the nodes doesn't intersect an obstacle. Then, use A* as usual to plan through the grid. This has some advantages over navigation meshes in that it is easy to implement and modify, but it is much more memory intensive, and produces lower quality paths.

One more way of using a lattice grid is to discretize the actions the agent can take (the edges in the graph) rather than the obstacles (the nodes in the graph). This suffers from many of the same problems as discretizing the obstacles, but allows the agent to, for instance, move a half square instead of a whole square as part of its path.

Sampling-Based One-Shot Planning

An interesting motion planning algorithm called the Rapidly Exploring Random Tree (RRT) randomly grows a tree graph structure from the start to the goal using a set of simple heuristics. The paths it produces are often quite terrible, but it has the advantage of working with very high-dimensional planning problems, such as those involving a rotating character (like a car or boat), and with joints. It can also be faster than the other algorithms when you expect the environment to change very often (such as with the case of moving obstacles).

Flow Fields

Another option is to create what's called a policy instead of a plan. Just create a virtual force toward the target, and forces away from all of your obstacles. Then, move the agent in response to the forces. Even though this sounds very simple, it works for many kinds of environments. If you add a little more cleverness to the simulation (such as a flood-fill like heuristic), you can get very natural motion -- but again you aren't guaranteed to find the solution. One advantage of flow fields is that they can be made extremely efficient, allowing for many thousands of agents to path plan simultaneously.

Trajectory Optimization

There is another branch of motion planning called Trajectory Optimization which tries to directly find the path through mathematical optimization. Basically, you start with a straight line path from the start to the goal, and then you keep modifying it until it is both short, and has the fewest number of collisions. If you can also compute the distance to obstacles, you can very quickly find a locally optimal path. One caveat is that trajectory optimizers are not guaranteed to find a feasible path (they do particularly badly in mazes) -- but the paths they do find are often beautiful, continuous, and very natural-looking.