Release 1.4 - Added more advanced obstacle avoidance. This can be toggled with a boolean variable called “advanced” on each NPC. Next step is to work out a way to enable/disable this when needed.
[quote]Release 1.3 - Added a break to the raycasting. Roughly 1/4s the amount of ray casts needed (amount depends on length and shape of path).
Release: 1.2 - Fixed bug when using multiple bots
Release: 1.1 - Fixed problem that prevented from using pathfinding in more than one scene. Download it below!
Here’s the pathfinding system I wrote for my game. It uses a navigation mesh method rather than a waypoint system, and uses the A* algorithm to find the path. It can have multiple bots at a time, and it is low resource cost and fairly easy to set up.Here’s how:
- Download this file - http://********.org/blend/3515 - this is also a demo. The cubes follows the sphere and avoid the red cube (move with WSAD). The grey cube has no advanced obstacle avoidance.
- Create a navigation mesh. This is a mesh where the faces define where the NPC can walk. Try and keep it as low poly as possible.
- Ensure that the navigation mesh has scale and rotation applied, and the global object position is 0,0,0. If it isn’t, use alt + G to reset its position, then switch to edit mode and move it from there.
- Run the nodeGen script.
- Begin offsetting the empties from the wall. Make sure that they are sufficiently offset so that the NPC will not clip the walls when moving.
- Duplicate the navigation mesh, and move one copy to another layer as a backup.
- Set the navigation mesh to static, actor, invisible and ghost. Give it the property “navMesh”. You may want to leave the ghost option off, if you do not want your player from escaping from the bounds that the AI is confined to.
- Move the navigation mesh up slightly, go into edit mode and extrude downwards.
- Copy the logic from the cube in the demo to your NPC, including the properties! I recommend adding it in an extra state that can be added or removed. For the advanced variable, set it to True if you want obstacle avoidance. This is slightly slower.
- Give all objects that will be path found in your game a property called “endNode”, and cause them to continually run the script “getNearestNode”. This should have a star on it so that it activates early.
- Create an empty called “navRayCast”
- Give objects that can move (e.g. a box) which you want to be avoided the property navMesh. There is no need to give it to stationary objects such as a table, if it is not in your navigation mesh.
To use it in your game, you must now activate the state with the pathfinding and set the “targetObject” property of the NPC. This should be in the format of “OB” + obj.name, e.g. OBCube. If you find that your NPC clips the walls, simply offset the empties further. If you find that your NPC turns too early or late, change the distance on line 18 of followPath.
Also, if you want information on what a navigation mesh is, go here:
Or if you want a short explanation, it defines the areas that a bot can walk on. This is better than giving the bot waypoints, because with a waypoint path it must stay on the path. This can make waypoint paths zig-zagged, unnatural and longer than a path generated with a navigation mesh. A navigation mesh also requires less nodes in most cases, making calculations faster.