I'm trying to accomplish a rudimentary pathfinding where the unit's velocity is mostly controlled by the player, but he will still walk around minor obstacles and nearby walls (marked on a grid). Imagine Diablo 3 or Path of Exile, A* seems a bit overkill. Is there another algorithm I can look into?

I'd probably still use A* - you'll likely need a solid implementation for lots of other things in a Diablo clone. For short distances with a sparse grid like what you'd probably have in such a game, you probably wouldn't need to check more than a few dozen nodes. That should be blazing fast.

Games like Diablo will also terminate the A*-like search early if it checks more than a fixed number of nodes. This lets you use a fixed size priority queue (huzzah for no reallocations!) and lets you guarantee that you won't get weird framerate drops or suddenly traverse the entire level if the path is actually impassable. If the A* search gives up, the fallback is to make the character walk straight towards the cursor instead of moving intelligently.

If you need it to be even faster, reuse the resulting path results for the next few frames as long as the new destination is still relatively close to the cached path's destination. That should eliminate a lot of wasted recalculating.

Yeah. A* is fast and cheap, especially if you keep the node search short. The cheesier alternative I can think of is to just follow exactly behind the player by some distance. Ie a minion that is on whatever tile the player was on 3 tiles ago, something akin to the old ninja gaiden shadow/twins.

Thanks for the replies. I'll give A* a shot then :)

The direct answer to your question is to use a steering behavior.

Most production-grade systems will combine some steering with A* to achieve the effect you're requesting. The steering behavior to use would add a force to push the actor away from obstacles modulated by the travel direction.

Note that steering in this case will only accomplish minor obstacle avoidance. Large obstacles or cul-de-sacs and the like will require A*. Those are probably exactly the kinds of things you might want your player or higher-level AI to deal with separately, though.

I'm trying to accomplish a rudimentary pathfinding where the unit's velocity is mostly controlled by the player, but he will still walk around minor obstacles and nearby walls (marked on a grid). Imagine Diablo 3 or Path of Exile, A* seems a bit overkill. Is there another algorithm I can look into?

Hi, the developer on Path of Exile who wrote the pathfinding we use.

We use A* for pathfinding, but we have an extra rule you might find helpful.

We restrict the A* search to be inside a bounding ellipse with the destination and the starting point as focuses. Because we keep the ellipse size constant, if the destination is far away it makes a long and thin ellipse so it will only find paths that are quite direct to the solution, but if the destination is close by then it creates a much wider ellipse and thus will search quite far perpendicularly to the direction of the destination. We always path to the closest point we found to the destination even if we fail to find a path.

We have found this scheme works quite well in gameplay. When the player clicks far away they tend to just want to move in that general direction, but when they click close by they are keen to find an exact path to the place they clicked even if it means moving around a blockage like a wall.

It also has fairly good properties that prevent the A* blowing up and searching really far away or in the wrong direction when it can't find a path, improving performance.

I'm trying to accomplish a rudimentary pathfinding where the unit's velocity is mostly controlled by the player, but he will still walk around minor obstacles and nearby walls (marked on a grid). Imagine Diablo 3 or Path of Exile, A* seems a bit overkill. Is there another algorithm I can look into?

Hi, the developer on Path of Exile who wrote the pathfinding we use.

We use A* for pathfinding, but we have an extra rule you might find helpful.

We restrict the A* search to be inside a bounding ellipse with the destination and the starting point as focuses. Because we keep the ellipse size constant, if the destination is far away it makes a long and thin ellipse so it will only find paths that are quite direct to the solution, but if the destination is close by then it creates a much wider ellipse and thus will search quite far perpendicularly to the direction of the destination. We always path to the closest point we found to the destination even if we fail to find a path.

We have found this scheme works quite well in gameplay. When the player clicks far away they tend to just want to move in that general direction, but when they click close by they are keen to find an exact path to the place they clicked even if it means moving around a blockage like a wall.

It also has fairly good properties that prevent the A* blowing up and searching really far away or in the wrong direction when it can't find a path, improving performance.

Interesting, movement in Path of Exile feels very good. I imagine if the A* search is restricted then a grid graph should be on par with a navigation mesh, performance-wise. Does Path of Exile use collision detection for units colliding with level geometry & other units? It seems that is something that can also be resolved by the pathfinding system with a dynamic grid/mesh. Steering looks like a good option, but maybe difficult to maintain deterministic movement.

I imagine if the A* search is restricted then a grid graph should be on par with a navigation mesh, performance-wise.

A grid graph is just a special case of a navigation mesh where every part of the mesh is a square. The relative size of the nodes in each case would also be a factor. And a restricted search may fail where an unrestricted search would succeed. So you can't really compare the 2 in a meaningful way. In fact, in a graph that is very sparse in terms of obstacles, the suggested bounding ellipse is going to have no effect most of the time.

I check first if there's a straight line to the target before performing A*. Since this is a very common case it's worth it to spend a few cycles on this - especially since I'm developing a multiplayer game, since I'm more worried about average case than worst case scenarios. Atm I'm using a connectivity graph between reflex vertices (2D topology, 3D rendered game). This guarantees a shortest path - something I'm not entirely sure a navmesh does unless you perform string pulling on each iteration. The downside is that connecting start and endpoints to the graph is quite expensive so I might actually go for a navmesh solution.