My project was to build a clone of the old dos game Descent.
The game took place inside twisting mazelike 'mineshafts' where the player controlled a harrier-like aircraft capable of flying in any direction.
The 3dimensional flight meant that these mazes could be much more complex than any 2d mazes.
While searching for the exit, the player would be intercepted by evil robots.
Guide:
The player camera can be moved with the WASD keys, and rotated with the arrow cursor keys, and Q,E
Spacebar toggels between the player cam, and a bird's eye cam that can pass through walls and used to get a globabl view of the map.
Since this project is a bit unpolished, many other keys used by myself for map editing and debugging are still left enabled, though they are not directly related to the project.
be carful what other keys you touch
Some of the issues that needed to be solved for this project include:
Visibility Determination
An important part of the robot AI is deciding if they can see the player or not. It would not be realistic if they 'cheated' and could find you regardless of blocking walls.
Initially I considered performing a BFS search on the map so they could navigate to the player, but decided that this would produce said 'cheating' type behaviour. It would also be very expensive, especially in a complex 3d environment with many active robots. Thus I decided to kill 2 birds with one stone, and go with a simpler visibility test, combined with some clever flocking behaviour.
Visibility is by line of sight. I trace the vector from a robot to the player and see if it hits any walls.
The world is a portal based, which means it is partitioned into 'sectors' which link to one another.
While one way of testing the line of sight would be to transverse it from one sector to the next, checking that it passes through their portal linking polygons as opposed to their wall polygons; I decided to instead go with a simpler method of checking the bounding sphere for entire sectors.
If we assume that the portal links are about the same size as their containing sectors themselves, then this is a good approximation.
In practice it works well; at times there is inaccuracy, but not in any noticable situation.
This hallway is partitioned into convex sectors. The straight line of sight does not pass through one section of the bent hallway (red bounding sphere). Without a full chain of sectors from one end to the other, there can not be visibility.
Seeking Behaviour
Once a robot has decided if it can see the player or not, there is the task of how to react.
Complex wall avoidance behaviour is not a large concern, consider:
Since we already have a clear line of sight, the path ahead must be clear, so turning to face the player and moving straight ahead shouldn't hit any walls.
So as long as we have a clear view of the player, we can move straight ahead. In the event that he dissapears from view though, perhaps by turning a corner, contining on the path to the last known location will still be safe, and might bring the player back into view.(upon arriving at said corner and being able to see around it)
This strategy seems to work very well, in my tests it is very difficult to avoid the robot; to do so you need to be 2 steps ahead and cross multiple blind corners.
Flocking
While the basic seeking behaviour works well, it is more interesting, and effective, for robots to cooperate with one another.
When a robot loses track of the player, rather than search for him, it is better to ask the other robots if they can still see the player, and follow them around.
This allows them to cover more ground, and focus more firepower on the player at once. As soon as any one sees the player all the others converge on the location.
While not exactly the same as traditional flocking behaviour constraints, it seems to produce similar complex intereactions.
