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?

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?

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?

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.

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.

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.

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):

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

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.

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.

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.