Solving 3d Maze + A* Search

Dear all,

I'm currently working on a small C# script which finds possible paths in a 3-dimensional maze from a point A to another point B and then approximates the shortest path from this Point A to B. It implements 2 algorithms, the first one being the recursive maze solver described here and the other one the A* search algorithm described here. I took the pseudocodes on the 2 links stated before and implemented them in C#. Further more I had to adapt the code so that it works in R3 (3d space) since they were all designed to solve problems in R2 originally. The maze is represented by a grid of points. The obstacles of the maze are also described by points. More precisely, the component takes the following data as input:

- list of Point3d objects representing the maze grid

- list of Point3d objects representing the obstacles

- start point as Point3d object

- end point as Point3d object

- grid dimensions i,j and k as int objects

Based on this input the solver stores the points into a 3-dimensional array of dimension i x j x k and performs the calculations. The component seems to work quite well as you can see on the screenshot below with mazes of small dimensions (the green balls are valid nodes for a path and the pipe is the actual path). With small dimensions I mean not more than 3375 grid points (i,j,k <= 15). 

Now here comes my problem. For my work it would be really interesting to apply the solver to much larger mazes. I'm talking about dimensions of 1'000'000 (i,j,k <= 100). However my Rhino Installation suffers a spectacular collapse if I go beyond 3375 grid points. 

I'm assuming that the worst case complexity of the maze solver for a 2d maze is O(n*log(n)). The one of A* is O(n log n + m), however I'm not sure what m is in this case. Since I'm dealing with another dimension here I guess the complexity is larger by one order of magnitude. 

To all computer science savy people here, do you think there Is a way to tackle this problem? Is it possible to adapt the program that it works more efficiently? Should I only feed numeric data instead of Point3d objects? (I'm assuming that only references are passed but not actually the point objects but correct me if I'm wrong).

I would be very greatful for hints and help. In this sense I would like to open an inspiring discussion about the topic, any ideas welcome! Also please feel free to use the component for whatever purpose you might find useful and to develop it further...

Thanks and Best

Hjalmar