Yesterday I made more progress on the navigation system. I made changes both to the level analysis and the steering code.
The last version of the level analysis used to find navigable areas was only approximate, which caused problems on unusual geometry, like small 3/4 meter tall walls, and ramps and stairways. The analysis concluded that the small walls were walkable, and that the stairs were not. The main problem was that I was essentially representing the areas as a voxel grid, without taking the underlying triangles into account.
The solution was to add two analysis steps. The first step : when rectangularizing the voxels into larger areas, take the initial seed voxel that the rectangle is being grown from, and drop a player-sized sphere on the ground, and record its final height after colliding with whatever triangles are in the voxel. Next, for each voxel in the growing rectangle, drop a sphere there, and compare the heights of the intial sphere, and the sphere at this spot. If they are too different, then the two voxels are not part of the same rectangular walkable area. This solved part of the problem with the small walls.
There was a long 3/4 tall wall in one level, and on half of the wall, this change fixed the issue, but on another part of the wall, there was still a portal between the floor rectangle and the wall rectangle, implying one could walk between them, so I had to change the way portals were created.
My initial approach to portals was to treat each rectangular area as a 3d bounding box, with a height of 3 meters. I would find all intersection bounding boxes, which includes degenerate just-touching boxes. These degenerate boxes where two neighboring boxes touch are the potential portals between them where someone could walk. I then checked that the portal box height was at least 2 meters, and if so, made a portal between them.
This had a couple of problems. One is that let neighbors that weren't walkable between appear to be walkable because I wasn't taking the underlying triangles into account.
So, I added a very similar navigation analysis to the portals as well. I attempted to place a player-sized sphere 3/4 of the way through the portal, and let it drop. Then I checked its height, and if it was too different, no portal was added.
I changed the steering code so that the enemies would skip portal centers as navigation points. Initially I had the enemies going from portal to center to portal, but now that I have geometry & pit avoidance code in there, this just created overly convoluted paths, so I skip those steps instead.
Come to think of it, perhaps I should just treat the portal centers as the navigation map itself. Sort of a dual map. I suppose it depends on whether I want to annotate the navigation areas with more info.
Next up for the navigation system :
1) Smooth out paths. They still look clunky, especially when there are large rectangular areas next to small ones. I think lookahead may be the answer here.
2) Make the paths more persistent. Right now the enemies do AI every simulation tick. This is overkill ( although doesn't really hurt the framerate ), and leads to them changing their minds too much.
3) Add a maximum path length to the A*. It's possible for the player to get himself somewhere the AI can't follow. In that case, every path on the level is searched.