Sign in to follow this  
  • entries
  • comments
  • views

Steering & Navigation

Sign in to follow this  


I have been spending the last few days working on allowing the enemies to track & follow the player. For the past few months, they had collision, but no real AI. I made them move around the level randomly, which worked out really well for prototyping aspects of the gameplay without actually having the AI working. I highly recommend this approach to start.

What I did was every 7 seconds or so, pick a new random movement direction for the enemies, offset in time so they wouldn't all change direction at once. If the player was within about 18 meters, they had a random chance of firing their weapon. Even in this simple system, the shooting & using shields was pretty fun.

Despite the fact that our game is top-down perspective ( not isometric ), we went with a full 3d environment, with no restrictions on the geometry. For instance, the world geometry does not have to be 2-manifold, or closed, etc. - just a triangle soup.

This certainly has costs in terms of development difficulty, and if I hadn't been doing this as a learning experience, and purely from a business point of view, I would have restricted the world to be tile-based instead, and laid out the game on a grid. In practice, our levels will be largely grid-based anyway, because the level editor has several features to make that easy. But, part of the game setting is ruined temples, and outdoors areas, so a tile-based approach would have some challenges with making this look uneven and curved.

For the AI, this presents a challenge in that the game is not a nice grid for something like the A* algorithm to use. Also, our levels can be very large, so having an extremely large grid area would be costly in terms of A*, without restricting its maximum path length ( which I should do anyway ).

Also, I did not want the level designers to have to add waypoints to the map. I don't mind them adding extra info to certain board spots for the AI, like good tactical spots, or triggers, but it seems ideal to require as few manual steps as possible in making levels.

So, I needed a way to analyze the level geometry itself to make the waypoints. I used to just use a 2d grid overlay on the world, and store walkable or not, and the height at each grid cell. Then I would consolidate these grid cells into large rectangles to use for A*. This reduces the number of nodes considerably.

The problem with the 2d grid overlay is that it can't handle a full 3d environment, so only one walkable area can be at any given cell. I had experimented before with a 2.5D grid, but it was complex, and sort of goes against the flexible engine philosophy I had been working with. The 2d aspect becomes a problem if you wanted to both be able to go across and under a bridge. A more subtle example would be a large 30' statue. The player should be able to walk under a statue's upraised arm, but also potentially on its arm itself if he could get up there.

Here is a shot of the navigation rectangles found by the 2D overlay approach.

So, I needed a fully 3d approach, so I could handle complex geometry without manual pathing.

So, what I do is to analyze the level at load time ( I need to change this to during level export from the editor ), in order to make a temporary voxel structure of all walkable areas. A walkable area is defined as at least one upward facing triangle of a solid material in a 1x1 meter area, with at least 2 meters of clearance above it.

I then go through neighboring voxels of similar heights to make rectangles, then find where the rectanglular cells overlap, in order to find portals between cells. I make the center of each cell and portal a waypoint on the graph for A* purposes.

This works well, as the cells are large, so there are few of them to check at runtime during A*.

The remaining problem was steering the enemy through the environment. In our game, you may be aiming one way and moving another, so I didn't have to deal with making the enemy only move forward. I think I just got this working, but it took much experimentation.

The concept is to move the character's bounding sphere forward in the direction he'd like to go, and do a virtual environment collision, and then use the resulting virtual sphere position as his preferred direction for this simulation frame. Next, I put out two feelers diagonally forward and down from the character's position to make sure there is solid ground there, one to the left, and the other to the right. If one feeler finds a hole, I turn the desired direction the other way. If both feelers find holes, I just go straight. Due to the navigation map, there must be a path forward or I wouldn't be trying to move there. Seems to work fairly well.

Next up is to add dynamic obstacle avoidance. I probably will make it similar to the triangle avoidance scheme I'm using now.

Here is a shot of a small test level, with the enemy's path displayed as a white line.

Finally here is a shot of an older version of the engine showing some tree models that wouldn't play nice with the old navigation system :

Sign in to follow this  


Recommended Comments

Looks fantastic. I love the insight into your project. Keep writing entries like this! I'll certainly be reading.

So what kind of game is this going to be (maybe I missed this before :-/, sorry). Stealth/action kind of thing going on? Overall, keep it up! Great work!


Share this comment

Link to comment
It's going to have several elements, but mainly its an action RPG.

There will be stealth, so sticking to shadows and moving slowly will be a viable way to complete some levels.

The player will often be confronted by multiple enemies at once, and must use the environment as cover to defeat them.

We will definitely have ranged combat, in the form of lasers & shields, and are planning on having simplified melee combat as well.

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