Pathfinding in a 3D grid with max 1 obstacle per column

Question

I need to pathfind an agent in a uniform 3D grid (Minecraft) of dimensions 160x128x160. The agent can move freely (flying, no gravity). What's unique about this problem is that for each column in the space, there is a maximum of one obstacle, although that obstacle may span multiple cells, so it could be considered one group of obstacles. I tried to use basic A* to pathfind through the space but to go nearly across the space took too long and iterated over 1 million cells to find the path.

With the constraints on the obstacles, I was thinking about using A* but with a node for the space above the obstacle in a column and a node for the space below. However, the player's position in those nodes would still need to be accounted for somehow, because there would be different costs for traversing a node depending on where it is entered from previous nodes:

path comparison

Here, the cost of traversing the middle node changes based on how it is entered and exited. I don't know how to represent this in A* and I'm unsure if it would break any requirements that A* has of its cost heuristics. Additionally, I'm unsure if this would affect my ability to later modify the algorithm from A* to Theta* for any-angle pathfinding. What is an efficient way to find near-optimal paths in this scenario?

• trincot: Can you explain what exactly the problem is with a graph that has at most 160×128×160 (about 3 million) nodes? If you use like 100 bytes per node, that represents 300 MB, and the priority queue would still be efficient (the binary heap tree has at most 22 levels).
• ravenspoint: Do you know where the obstacles are initially? Are the obstacles fixed in their location? If yes to both questions, then you have no need of A*, Dijkstra will give you the optimum path quickly and efficiently.
• m.raynal - bye toxic community: "However, the player's position in those nodes would still need to be accounted for somehow, because there would be different costs for traversing a node depending on where it is entered from previous nodes:" Can you please elaborate on this point ? It could mean that the algorithm you're looking for is something more complicated than A*.
• trincot: It seems you lost interest in your question.
• Patrick Martin: @trincot I haven't had time to work on the project that the question is a part of. To answer your first question, I'm working in JS and when I asked the question, pathfinding was taking 30 seconds for long paths. With optimization I later got it down to around 5, but it was still hogging a whole core for that 5 seconds, and I figure if I can reduce the number of nodes it won't hurt. I'm not really worried about memory, the number of nodes expanded just seemed a little absurd to me.