Since the last update, we've focused on adding better BOT-AI. Today the bots walk random and interact only if something is really close. But to have a working AI on the maps we need pathfinding in our game engine. We started this discussion more than two year ago and decided to make a auto generated nav-mesh. This would make it easier once the system was going and it should cover almost every pice on the maps. If we change one map it's easy to generate a new nav-mesh.
Generat nav-mesh from map
The basic idea was to make a movable agent with the same size as players. Create a surface that covers the whole map and start from every spawn point. When the player agent moves around it uses almost the same properties as a normal player. When the agent have covered the whole map, it starts from the next spawn point. Almost always the next spawn point is already calculated.
Small bunge arena map
Result after running the first step in the auto generated nav mesh of the map. Spawn points in blue dots. Ladders and ziplines in green. Pink indicates up/down slopes like stairs given a sligtly higer cost. Blue lines is oneway path like jumping down from higher ground.
(also very useful when creating and updating minimaps)
When the agent moves around and covers the same spot as already done, it first checks the altitude. If the altitude difference is larger than the player height, we know that this point is another layer/level in the surface.
Sometimes we don't want the nav-mesh to cover areas to limit the bot movement. We then added a pathfind block property in the collision mask. When this mask is set on parts of the map it will not be included in the nav-mesh. We also added properties for temporary objects like doors and gates so the mesh could change during running game.
Ladders and ziplines
Ladders and ziplines is done after the whole calculation and add links in the nav-mesh with special properties so the bot know what to do when reached in the calculated path.
Caluclations in the surface for safer zones
The next step in the auto generated mesh is to calculate whether the point is safer or not. This is done by ray cast to see the average volume covered around the point. We also do the same calculation when the agent is crouching. With this we also find places where it's better to crouch.
Darker pink is surface with larger risk to move. Green overlay is surface where crouch is favoured.
To use the nav-mesh efficient it must be simpified. This is done by migrate areas to bigger pices. The fever pices the faster pathfinding. But at the same time we want the pices not to be to large to make the path more random (not always use the straight path) and not to loose the calculated properties.
This is the result of a simplified nav-mesh that is saved into the map file.
For the pathfinding we used a simple a-star algorithm in a separate thread with a queue request and answer system. We also added some algortims to move random in the near area by using the nav-mesh with a worm to move a selected distance from the current point (this algoritm is realy fast and usefull in some situation).
This pathfinding system will be in the next update of False Front.
We have added a setting to disable current bot AI system for the gamers who want old bot's.