Show HN: L1-path-finder, a fast path planner for grids | Hacker News Reader

Show HN: L1-path-finder, a fast path planner for grids

mikolalysenko.github.io

30 points33a11 comments

Reminds me that most optimisation is an exercise in caching, although I'd be curious how this compares to even more cache-y approaches. (e.g. complete lookup as a naive example)

PVS/VSD applies to all kinds of problems, its nice to see someone else doing it. Split the world into convex volumes with connectivity information and suddenly the toolbox of algorithms at your disposal explodes... :)

still surprised that games developers don't do it more... there are physics, audio, networking and other optimisations to be had from splitting the world properly and having good connectivity information.

This is insanely cool. I do game dev for a living, and pathfinding is one of the biggest hassles.

Right now, it's in a weird spot where it's sort of free, since you can offload to other cores that would otherwise remain idle. But as Mantle and other multithreading APIs take off, and engines get smarter about multi core, it's going to go back to being a big bottleneck.

This is the kind of thing that could create a truly EPIC game.

It's just one of the components. For EPIC game you need some extraordinary game mechanics or graphics or story. Well, probably a combination of at least two of those three.

We've seen a few grid A-star/grid-based pathfinding articles and tools now and they're really interesting but every time I see one I can't help but think, "how is pathfinding done for games which are not a grid?"

For example in an open-world type MMO or FPS game position is a floating point number. Does the game engine break the area down into smaller polygons?

If so is that mesh 3D? If so what happens if something isn't at the appropriate Z-axis? For example if AI is chasing a player and the player jumps how does the AI know the human player is on the same plane? And how does it differentiate that from the human being on another ground level slightly above/below it?

it varies from game to game. most often there is some kind of sparse 'navmesh' containing nodes in a 'grid' for doing the classical part of path finding. its possible to do this sort of thing automatically if you split the world into volumes as well, but its more difficult to get very fast, good results (i.e. you can't hack the data by hand so easily).

as well as that there will be some (usually quite off the cuff, hacky) logic to get a character from wherever they are to the nearest node (or its vicinity) and something to avoid them from hitting each other (too much)

there is nothing special about the 3d part, you just make the mesh in 3d and respect the constraints of gravity, player movement etc. so that you can't connect nodes badly

the floating point number thing is not important. any pathfinding can be made to have this 'extra complexity' if you simply go between the points over time smoothly...

There are different methods, but for many 3D games people use navmeshes for planning. Grids are kind of neat in that there are lots of little tricks you can use to speed things up and many geometric queries turn out to be way simpler.

Visibility graphs seem to be a lot more efficient (and straightforward!) than A* or more basic algorithms.

Also if you click on the logo and drag around, the blue dots will chase your mouse.

pretty cool...i've used a* and fast marching and i'm very impressed with speed improvement

Does this use an L1 norm?

Yes.

Reply on news.ycombinator.com