Jump to content
  • Advertisement
trsh

Algorithm How to fix cutting corner problem in a star pathfinding

Recommended Posts

a.png.fe3aae3b0007139df660effcc106bdc3.png

So this is a problem when doing diagonal jumps (checking diagonal neighbor nodes). In 2d it can be prevented by doing some checks, like if up and right is blocked, don't take up-right neighbor for calculations. But in 3d thous check become a bit to much and to tedious.. so if I still want diagonal paths, what could be a good solution?

Share this post


Link to post
Share on other sites
Advertisement

If you think of pathfinding being applied to graphs, the problem does not come up at all. Each vertex in the graph (in your case a black square) has edges only to adjacent vertices it can reach. So as a preprocess you would only add diagonal edges (connections) if the neighbouring squares can be walked form the current.

Alternatively you could set infinite edge weights for obstacles, but with a grid i guess you do not use weights. (I'm not that familiar with pathfinding on the special case of grids myself. Guess it's more efficient and common to calculate edges and weights on the fly with grids, but the concepts of general graphs still apply.)

However, i'm curious about squares 3-6 from your result. It looks like it misses the shortest path because it goes towards the goal until it hits an obstacle.

Is this expected from A*? Or could it be a bug?

 

Share this post


Link to post
Share on other sites

This screenshot is not even from my project, as it is in 3d. I just wanted to point out the problem point. And sorry I did not understand your suggestion. Could you give some more pointers and/or examples?

Edited by trsh
Correct

Share this post


Link to post
Share on other sites

Ok, after some googling i see shortest path is guarteed with A*, so likely the screenshot uses another algorithm.

You might want to add if your 3D world still uses regular grid. (Although it would not be much different - for straight/diagonal you could check the common edge to be touched by >=2 solids, and for the diagonal/diagonal case the check could be if >=2 solids touch the common vertex.)

Edit: With vertex / edge i mean the grid lattice here, not the graph as above.

 

Edited by JoeJ

Share this post


Link to post
Share on other sites
59 minutes ago, JoeJ said:

Ok, after some googling i see shortest path is guarteed with A*, so likely the screenshot uses another algorithm.

You might want to add if your 3D world still uses regular grid. (Although it would not be much different - for straight/diagonal you could check the common edge to be touched by >=2 solids, and for the diagonal/diagonal case the check could be if >=2 solids touch the common vertex.)

Edit: With vertex / edge i mean the grid lattice here, not the graph as above.

 

In 3d it's Voxel grid.

Share this post


Link to post
Share on other sites

I think what JoeJ refers to is that, when you add your position/node to the list of possible walkable targets, you do so by only using cardinal directions. meaning the square at step 13 wouldn't be added to the list of possible targets at all.

for all other steps of A* you consider all directions,including diagonal as you did before.

 

edit: depending on your implementation that might mean that finding walkable targets and updating their distance to parent has to be split into two steps.

Edited by ninnghazad

Share this post


Link to post
Share on other sites
2 hours ago, JoeJ said:

and for the diagonal/diagonal case the check could be if >=2 solids touch the common vertex.

This kept me thinking and i realize it is not that easy. Likely that's the question. The test has to account for direction and can not work just by counting boxes touching the vertex.

I guess most people allow only movement between voxels that share a plane, so the same as 2D. The resulting movement might be more natural because climbing over edges feels easier than climbing over vertices. Would mean 6 face + 12 edge adjacent boxes are potentially reachable.

But if the additional 8 vertex adjacent boxes are really desired, i think the test could be to find two empty face adjacent boxes (green), each sharing also a face with twe two empty boxes we want to connect (red):

image.png.609b213d85d0c5cc6fa8b17f7c0cb2ce.png

But i don't know how to calculate this most efficiently. Maybe using bit look up tables for all 8 options.

 

Share this post


Link to post
Share on other sites
4 hours ago, JoeJ said:

Ok, after some googling i see shortest path is guarteed with A*, so likely the screenshot uses another algorithm.

Note that this is only true if your heuristic function is admissible.

Share this post


Link to post
Share on other sites

Walking diagonally should require that none of the passed neighbors are higher than the floor. Probably doesn't matter if they are lower because one can balance on the narrow edge connecting them. For a directed graph, you can keep a state telling which action is required to pass in any direction. Climb, drop, walk, open door or impossible. Then use it backwards when applying A* with the unit's preference penalties and abilities. When a tile changes, you only need to update the 3x3 neighborhood and recalculate current paths.

Share this post


Link to post
Share on other sites

Don't think about rocket-science solution here. When considering a diagonal step, if it passes the height/floor/ceiling/etc checks you should test if any of the neighbouring straight move is also valid.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

  • 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!