• Advertisement
Sign in to follow this  
  • entries
    235
  • comments
    509
  • views
    172317

Navigation Update

Sign in to follow this  

116 views

Grids and Capsules

One of the things going through my mind lately was how to properly handle the over->under problem with the AI waypoints.
I don't need to support navigating over-under, but I do need to automatically place the waypoints such that two points with
the same x & z coords, one possibly on a statue's arm that would be walkable, and one on the floor beneath.

What I'm doing now is to sample each 1x1 meter section of the level, and if I find walkable triangles there, I set the
grid location to walkable. I ignore duplicates, so whichever one comes first wins. I thought about breaking ties with height,
but this doesn't work b/c for a bridge the high bridge part wins over the pool bottom, and for a statue, the low floor wins.

Another thing I have been thinking about is, once I have the grid, how to sweep a capsule through the level to verify walkability.

Here is a shot of an enemy getting stuck on the side of the pool b/c he thinks he can get up there by walking :



Yesterday I realized I can handle both problems much more simply if I reverse the tasks, and use the capsule to find the walkable
areas in the first place.

I will simply start the capsule at the player's start position in the level, force it down until it hits something, and make this the first walkable grid area. Then just push the capsule n,s,e & w and see if it successfully navigates where it was trying to go. Also I will make sure it doesn't fall too far, etc. For each successful navigation, mark that grid as walkable, and continue.

Eventually, all walkable areas on the level will be explored. This should handle ramps, short drops, pits and walls equally well. This also will make the tops of walls unwalkable, unless the player can literally get up there.

Another task for this afternoon is to further flesh out the enemy AI, so it can have some brains for hunting down the player without being omniscient.

Here is a shot of me hiding in a stream, while the AI appears to be looking for me.

Sign in to follow this  


4 Comments


Recommended Comments

Good entry as usual!

Quote:
I will simply start the capsule at the player's start position in the level, force it down until it hits something, and make this the first walkable grid area. Then just push the capsule n,s,e & w and see if it successfully navigates where it was trying to go. Also I will make sure it doesn't fall too far, etc. For each successful navigation, mark that grid as walkable, and continue.

Eventually, all walkable areas on the level will be explored. This should handle ramps, short drops, pits and walls equally well. This also will make the tops of walls unwalkable, unless the player can literally get up there.

So, essentially your algorithm just keeps on "walking the level" from a known start position and stores that as the grid of walkable nodes?

There's one bit I didn't quite get from your description though [smile]

Does, when the capsule "walks" in a direction it mark it as a bi-directional movement? e.g. if the capsule can go forwards it can also go backwards? That would make sense to me as it would reduce the amount of searching required...

But wouldn't that then break the "short drops" - where the player(s) can fall off in one direction but not necessarily climb back up again?

Cheers,
Jack

Share this comment


Link to comment
Yes, that's the idea, to tell whether something can be walked or not, rather than estimating it, I just walk it.

The neighbor relationship is uni-directional to handle the drop case as you mention, or a very steep ramp.

That actually makes me realize I have a bug in this code that I just wrote!

I only further check invalid nodes, which will not find all of the walkable areas...

Share this comment


Link to comment
Does your capsule search all of the nodes when a level is loaded, and store them in a look-up table or is it done real-time when the unit is trying to navigate?

Share this comment


Link to comment

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