[chrisdalke]

Writing path planning code is one of the most enjoyable programming tasks. Love the visualizations.

The path following code is also interesting because I bet you'll run into some corner cases where the A* path thinks a path is feasible, but the vehicle overshoots and hits something. Although in a game I guess that adds to the fun & chaos.

[johnh-hn]

Indeed. There is something satisfying about building these and watching them in full flow.

A couple of years ago, I completed a pathfinding assignment designed by David Churchill (https://www.cs.mun.ca/~dchurchill/) for his Algorithmic Techniques for AI course. I'm not a student, and only his students have access to the actual assignment files, so I made a faithful recreation of it by looking at slides he had on a video at the time. The assignment is about pathfinding on a 2D grid. That's fun enough, but I've wanted to put my own spin on it.

Over the past few weeks, I revisited this and applied it to real-world mapping data from OpenStreetMap instead. It uses OverPass API (https://dev.overpass-api.de/) to fetch the data, which is free to use. The data loading times can be a little unpredictable, especially for larger search areas, but I'm happy with it how it turned out. You can find it here if you're interested: https://johnh.co/projects/openstreetmap-pathfinding/

[porphyra]

You might be able to add velocity information when doing the A* search, as well as use minkowski sum to make sure that it never tries to squeeze through too tiny a gap.

[wduquette]

Re: visualizations, yeah, it’s really easy to caught up in playing with the algorithm just to watch it run rather than using it in your project. Been there, did that. For two distinct projects.

[juhrjuhr]

This definitely happens! Mostly it's from the NPC taking a corner a little too quickly when there's obstacles around. I've added data to the resulting path so that the NPC can know how far each path step is from an obstacle so that it can slow itself down first.

Like you said, it adds a lot to the fun so I'm only trying to smooth out those cases that look stupid.

[jvanderbot]

Take it from an old hand: you want to add a tad of circular margin to your obstacles via minkowski sum.