Sign in to follow this  

Dynamic World - AI Optimization

This topic is 2830 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 am currently working on a game called rohXel which is (hopefully) going to be a 2d-physics-based shooter. I was writing a simple AI that could move to a target in the world by walking and jumping. To do this I implemented a system that reads walkable segments out of the actual physical world (the bodies etc) and after that finds connections between them if it is possible to jump. After that a simple A* search is done to find the path and than that path is given to the walking mechanism. Heres a video that shows it in work: http://www.youtube.com/watch?v=hz_ev8BR_W0 (Its a bit old and the walking and jumping is much faster and smoother at the moment but I dont have a newer video, there is also no moving body for the AI to walk on, although it would work.) The problem is the performance : The second step, finding the connections, takes a lot of time since it grows with O(n^2) which slows everything down a lot when it comes to a large scene. I made the obvious optimizations such as : 1. Not recalculating static bodies 2. Not recalculating sleeping(ergo not moving for a period of time) bodies 3. Only looking at the jumps between two recalculated segments. (I also only walk on bodies with larger masses since the lighter ones can just be pushed away) Since all these things are just a factor and not slowing the growth of the computing time I thought about implementing some kind of Sweep and Prune algorithm, as I use it in my physics engine for the "overlapping" segments between which jumps need to be found. Do you think this could help me with my problem or do you see any problems concerning that? Appreciating any help, Tehforsch

Share this post


Link to post
Share on other sites
But if world not totally undeterministic when precalculation \ hierarchy solves the problem.
You could precalculate all paths even if you have animated platform and to search less use simple hierarchy of grids.

Share this post


Link to post
Share on other sites

Depending on the size of your map using one of the space partitioning systems

http://en.wikipedia.org/wiki/Space_partitioning

to subset the N^2 comparisons to make the dynamic object searches smaller.

There is overhead involved so you would have to do a comparison between
different methods and none at all to see which works better.

Share this post


Link to post
Share on other sites
Also, I don't know if you're doing this, but only recalculating if the AI perceives an obstacle that wasn't there before. Some pruning, such as recalculating to get on the original path could also help, but is a bit beyond my comfort zone of knowledge.

Just thought I'd throw that out there, because it is one of the "Gotchas!" of A*.

Also, after watching the video, it tries to land on the very start of the block? Some optimization may help there.

Share this post


Link to post
Share on other sites

This topic is 2830 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.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this