next »

[BleakProspects]

I thought you might be interested in an article I wrote on Gamasutra about motion planning and pathfinding. Topics covered:
 
Theoretical foundations of Motion Planning and pathfinding -- optimality, completeness, configuration space, etc.

• The Bug Algorithm
• Visibility Graphs and Navigation Meshes
• Lattice Grid Search: A* and variants
• Flow Fields and other Control Policies
• Randomized Planning: PRMs and RRTs
• Trajectory Optimization

[Qqwy]

I read the whole thing. I think I'll re-read some of it again once I start diving in some pathfinding myself. I really have to congradulate you on the great way you ramp up from the start to introduce more and more complex concepts in a way that still is understandable for a reader.

Great article!

[Yammo]

Fantastic, thank you. This is incredibly informative

[Zaphos]

Nice tutorial

Since you seem to have done a lot of research, can I ask if you've come across people using the heat equation to define flow fields for path planning?  I recently read this paper http://www.cs.columbia.edu/~keenan/Projects/GeodesicsInHeat/paper.pdf and noticed fig. 12 implies it'd be a nice way to get (complete, optionally optimal) paths.  Especially if you have lots of different AIs that all need to path plan to the same spots.  (You wouldn't even need to do everything in that paper; just step 1 [solve the heat eqn] and then follow gradients.)  But I didn't see this kind of thing in your survey so maybe it's not done / worse than other methods?

[ekun]

Good refresher on motion planning, I like your writing style!

I also really enjoyed the Dwarfcorp kickstarter postmortem. Definitely looking forward to more articles from you.

[BleakProspects]

Nice tutorial

Since you seem to have done a lot of research, can I ask if you've come across people using the heat equation to define flow fields for path planning?  I recently read this paper http://www.cs.columbia.edu/~keenan/Projects/GeodesicsInHeat/paper.pdf and noticed fig. 12 implies it'd be a nice way to get (complete, optionally optimal) paths.  Especially if you have lots of different AIs that all need to path plan to the same spots.  (You wouldn't even need to do everything in that paper; just step 1 [solve the heat eqn] and then follow gradients.)  But I didn't see this kind of thing in your survey so maybe it's not done / worse than other methods?

Fast Marching ( a paper referenced by them ) is used in a motion planner called "LDD (Learning Dimensional Descent)" In general the technique doesn't scale beyond 3 dimensions, so special tricks need to be used to make it do so. I haven't seen this particular paper, but it looks to be along the same lines as Fast Marching.

You can see from Fig 13 they are using the solution of the heat equation to generate optimal 2D plans according to different metrics. That's really cool.

[Zaphos]

Ah, cool, thanks for the insight

[ChevyRay]

Hefty article, bookmarked! Thanks for writing this I think I know most of this stuff by now, but going to read through and see if I pick up anything new.