Jump to content
  • Advertisement

Pathfinding Not only diagonal path problem

Recommended Posts

My game map is basically a 2D grid which contains solid tiles(walls or other obstacles that can't be passed) and normal tiles that can be passed

I need an enemy to reach the target point (player, cover, player base,,,)

But path finding algorithms only provides 45 degree moving ( sides or diagonal) but obviously there is a shorter way for example going 60 degrees instead of combination of diagonal and sides like on image.

So, what is way i can create this, although the main reason is not shorter path but the way enemy is going ,because it's wheeled vehicle so it needs to slow down to rotate...



Share this post

Link to post
Share on other sites

A search term you could try is 'pathfinding string pulling'. Searching for this term via Google images, for example, led me to this thread:


I imagine you can find other info as well.

A possible complexity is agent size. In your example image there are no walls near the path other than those at the bottom right. However, if there were walls, for example, near the initial straight segment of the expected path, an agent with non-zero size could 'clip' it on the way by. Whether this would be a problem or not depends on the circumstances of course.

If you want to get something up and running quickly, here's a naive algorithm that might work. Step along the path a cell at a time, and at each cell draw a conceptual line segment from the cell to the start cell. Continue until you find a cell for which the segment intersects an obstacle (possibly taking agent size into account). Once you find such a cell, add a segment to the path going from the start cell to the previous cell you examined (the last one for which the segment test passed), and start over from there.

Obviously this could be insufficiently performant, depending, but multithreading or making the process incremental can help. It also introduces the burden of implementing a robust segment intersection test (again, possibly incorporating agent size), which can be nontrivial.

Another concept that might be of interest is Minkowski addition. In this context, the idea would be to expand the geometry by the radius or extent of the agent to yield different obstacle geometry. The obstacles might no longer lie on the grid exactly, but you could then treat the agent as a point for the purpose of pathfinding, which can simplify things.

Another concept that might be relevant is 'points of visibility' (try, for example, a Google image search for that term to get a quick idea of what it's about). Of course there's also the option of choosing a different fundamental representation for your environment (such as a navigation mesh, or obstacles as raw polygons), but you may not want to do that, and it shouldn't be necessary per se.

You mentioned wheeled vehicle dynamics as well. If there are factors such as turning radius involved, that could add some additional complexity.

Obviously pathfinding is a broad topic, but maybe something here will help get you pointed in the right direction.

Share this post

Link to post
Share on other sites

  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!