Hi to all game programmers :icon_cool:
I want to implement the following:
A* Star for partitioned space combined with an adaptive partitioning in 3D.
A. Assume that in the 3D space I have an Object (myMovingObject) that I want to it to move from one initial State (StartState) to another (goalState) while avoiding collisions to other objects.
B. Consider that each State class includes the 3D cube positional info, its Parent State and its costs (both these 2 last variables are needed for the A star path algorithm)
C. I do not partition the whole space between the StartState and the goalState at once from the beginning, but rather create the neighbors states of the StartState of a common resolution, for all of which I then calculate the costs based on A* .If there are states found in collision with other objects I exclude them, while I save all others to a priority list which after being sorted gives the new CurrentState of which I create the neighbours in next step and so on. I keep doing this till I reach the GoalState->THIS WAS THE NON ADAPTIVE APPROACH.
D. I want to improve the previous by not excluding states in collision at once but when such states are found to divide each one of them into 8 childStates, and then divide each one of them that collides again into 8 leafstates. I need an effective data structure for doing this adaptive partitioning holding child and leaf states and thus chose an octree. -> THIS IS THE ADAPTIVE APPROACH
E. Besides the octree I need three more data structures:
-One serving as priority queue which holds states with calculated costs sorted which I implemented as a multiset
-A second for saving each visited state having as a key the 3d positional info of its ParentState in order to retrieve the path from state to state when goal is found.
-A third for saving all states that have already been divided into children or leafs having as a key the 3d positional info of their RootState, in order to avoid calling the octree to divide them again.
RootState is meant a state which has been divided into 8 childStates
ParentState is meant a state whose neighbour states were created and examined)
For the two last cases I chose to use an STL hash_map.
My questions to u:
1. Do u think that octree is the most suitable data structure for my case? If yes how would u implement it in order to achieve a minimum execution time?
2. Do u think there is a way to implement the A* algorithm recursively? (besides the partitioning, this will be for sure)
3. Do u think that an stl hash_map is the best data structure concerning big O perfomance for finding and retrieving items? (see step E)
4. Do u think there is a faster way to save, search and sort instead of the multiset data structure?(see step E)
5. Is there sth that u think I should do it another way in my approach?
thanks everybody in advance for your time