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

Improved A Star Paths

Sign in to follow this  


Improved A* Paths

Last night I added & tested the code to have each ai agent only able to check 10 new nodes at a time during the A* path search. This works very well, and seems to completely eliminate any a star spikes in the frame rate. I also added line of sight checks to tell when the AI needs to re-path.

Today was my day off, so I didn't work on Ancient Galaxy very much, but I did have some insights last night and this morning.

One problem is the issue of enemies taking diagonal corners that are too tight for it to fit through. This caused the dudes to bump against wall corners, and would cause them to fall into pits as well. This is partially because I am still not sweeping my capsule through the level to verify walkability, but tonight I remembered an old-skool method for doing grid-based collision detection, to elmininate the most obvious problem cases with diagonal movement.

If you are in the nw corner of this 2x2 area, and are roughly grid-sized, and you assume any obstacle is also roughly grid-sized, obviously you can't move southeast unless you can move both south and east.

So I put this simple check into the engine when connecting neighbor nodes and now it never bumps into corners.

Here are two shots of the enemy AI pathing around walls. Between the higher cost nodes near walls, and the lack of invalid diagonal short cuts, it stays a healthy distance from walls.

Smooth Operator

Next is to use a similar idea to handle smoothing out the grid paths. When an enemy is travelling along at an angle other than a straight or 45 degree angle, he will move via a series of straight & diagonal moves instead of smoothly. I added some hermite spline code to smooth this a bit, but it only works on the next couple of nodes, so it still involves a bit of wiggle back and forth.

The real way to do this is to check the path for shortcuts. If the path goes from a->b->c->d, maybe one can go directly from a->d. It turns out this is possible only if all diagonal paths are clear. As I showed above, the diagonals are clear only if their two component cardinal directions are clear. So, in order to straighten out the wiggly paths, I should only have to walk down the diagonal segments, and check each appropriate cardinal direction for blockage. If not found, I can delete the diagonal path, and travel straight to the next node.

I will probably add this tomorrow, and upload a diagram if I have time.
Sign in to follow this  

1 Comment

Recommended Comments

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.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!