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.
At the moment, it doesn’t avoid objects that may be in the way of the path that aren’t defined by the navigation mesh. I may add that feature if I have time, but that might not be for a while sorry.
This may sound stupid, but it’s because I don’t understand it, so I used Dijkstra instead of A*. If I can find a good explanation of A* I may change it, but because I wrote this for my game and it works sufficiently I’m just sharing it in case other people find it useful. If anyone here wants to modify this, feel free.
Again, although I’d really like automatically offsetting empties, it isn’t high on my priority list with everything else I need to get done for my game, but if I do manage it I’ll share it. Sorry I couldn’t provide a more complete version
Edit: I’ve found it’s faster to do the offset whilst creating your navigation mesh, before your run the nodeGen. Have updated the main post. Either way works though.
Thanks Sunjay! It’s now using A* instead of Dijkstra. Simply run the A* script instead of Dijkstra. I’ve still included my old dijkstra algorithm just for the sake of it.
Edit: Just done a test to compare my dijkstra and the new A*. It seems to be about 3-4 times faster. Which is good
Thanks Rhys! and yes Sunjay, I’ll be keeping the latest version in the first post
Edit: New version. I’m starting numbering them now. Version 1.1 allows you to have nodes in multiple scenes. As you can see, I have two scenes in the blend file, both of which work even though the nodes have different names.
Multiple bots seem to not work at the same time now, they often go around in circles.
In the console example, file followpath, line7 , KeyError:OBcube.002
This is just by duplicating the cubes, is there something else needed to do for multiple bots?
Thanks, Rhys. That’s fixed now. If you’re interested, I just had to change:
#Make global dictionary to hold paths
g.paths = {}
g.paths[own] = optPath
print optPath
to
try:
g.paths[own] = optPath
except:
#Make global dictionary to hold paths if it doesn't already exist
g.paths = {}
g.paths[own] = optPath
print optPath
to prevent it from wiping the dictionary. Updated the main blend
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). Updated in main blend.
Release 1.4 - Advanced obstacle avoidance. Add “navMesh” property to objects you want avoided, and give each NPC a boolean property called “advanced”. If this is true, obstacle avoidance is used.
In the 1.4 version you can shove the enemys of the map and they will fall and disapear. lol, but thats just because they can get stuck inside the player sometimes. But it is pretty good.
Yeah, that’s just because I’m using DRot instead of forces/servo. In a game situation, i.e. a rigid body box that’s pushed around a bit, it shouldn’t be a problem