I have implemented A* to reach a goal state from a start state. My state is position X,Y, angle and others state variable. I have a number of actions. What I call actions is : A* on a grid has 4/8 actions (straight, right, left, back).
My character has a lot of different actions. I started with 20 possible actions which will lead to different future possible positions. with my implementation of A* it is working fine and I found a solution.
Now, I want to do the same thing but with my real number of actions. Which is around 1000... If I run my algorithm it may take forever...
The first red node is the start position. The green is the goal. When A* will expand my children. I will have 1000 children nodes (note: the nodes are in a kind of same region the light blue envelope)). But then I have 1000 nodes to study and which can be extented by 1000 children each... and so on. So the number can be really huge.
Does anybody have a good idea to deal with this kind of high number of actions in a A* ? Finding a good heuristic won't be enough I guess cause too many possibilities. Maybe using this light region ? Any ideas ?
Thanks. Let me know, If it is unclear or need more explanations.