Hello, i'm have problem with A* precompute help me pls :( I'm read AI game programming wisdom2. He suggest how to use precompute solution, and i try to do. But i got a time consume much more than non-precompute A*. He suggest that u must precompute a next path from start node to destination node and put it into table. OK that solution i got a beatiful time consume. But when i try to partition into small transition table and use interface transition table to connect each set(For reduce memory consume). I got time consume so high(higher than non-precompute A*). My map have 900 Node. Partition map into 36 set. Have 620 interface node. how should to do to solve this problem, help me pls:(

I don't know the algorithm you are specifically talking about so i'll answer generally.

Sounds like a straight forward optimization problem. You'll want to get a profiling tool (search around on this site, a few good free tools have been posted in the past). this will tell you which functions in your program are consuming he most time. From there it's then a process of:

1) improve your algorithm to reduce the complexity surrounding the bottle-necks (i.e. reduce O(n^3) -> O(n^2) -> O(nlogn) -> O(n) where possible)
2) re-profile
3) goto 1

after iterating a couple times with algorithmic complexity you can descend into the madness of micro-optimizing the problem areas.

Other possible solutions would be to only update the A* for a few entities per frame. This is called time-slicing. Generally you do not need all entities to update every frame.

-me

You could precompute the paths from each position to the other, about 810,000 possibilities, and save in a data file. Then, at run time, you simply look up the path and cost. Or, go with what I was trying to do, and precompute your nodes in smaller groups, and combine those smaller precomputed groups into a path at run time. When you've solved that, let us know, as it seemed intractible to me compared with just running A* as needed.