Jump to content
  • Advertisement
Sign in to follow this  
  • entries
  • comments
  • views


Sign in to follow this  


I've been doing more work on the navigation system, and I think it's done for now.

The system I first implemented was hard to get right, and there were a lot of special cases.

Here's how it worked :

Every time an object that could be an obstacle ( a locked door, a trap, a force field, or a large collidable object ) was added to the scene, or moved, its world space bounding box was computed, and that was used to pass into the navgrid so it could update it's dynamic cost to the 100.0f cost limit.

When an object left, or before it's 100.0f was added, the old object location needed to have -100.0f subtracted from the navgrid.

Once the navgrid was updated, all sentient entities were updated to check their paths. If their path bounding box intersected the blockage box, then each step in their path was checked. If any part of the path crossed the blockage box, then the path was killed from there onwards, so the AI could repath when it got there.

This system of add/subtract/add caused bugs when things were first added, or when things didn't subtract their amount properly, and it wasn't super-efficient either.

The new system is simpler, more efficient and bug free ( to my knowledge ) :

Rather than performing aggressive updating of the navgrid, which doesn't even need to happen ~60 times per second, the navgrid disallows direct updates and instead, creates an update record every time a blockage object is processed.

Every so often, it goes through the old list of objects, their cost and location, then compares it to the new cost and location. If these match, no work is done.

If they don't match, the old cost is subtracted out of the grid, and the new cost is added in at the new location.

Then any old costs that were not updated this time, are objects that have disappeared, moved away from the navgrid, or became movable ( like a door being unlocked ). These are subtracted out of the navgrid at their last known location.

Any actual positive cost navgrid updates trigger re-pathing for the entities.

Finally the new costs are copied over the old costs, and then cleared for more updates.

So the new scheme does a compare/contrast lazy evaluation scheme.

Another improvement I made was to use an object's local bounding box rather than the world box. This is really important for force fields, which may be created at any angle. You don't want the AI to think it can't get around a diagonal force field when there is space for it to do so...
Sign in to follow this  


Recommended Comments

There are no comments to display.

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
  • 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!