Jump to content
  • Advertisement
Sign in to follow this  
TaeV

Problem with A* precompute

This topic is 4306 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

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:(

Share this post


Link to post
Share on other sites
Advertisement
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

Share this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!