A* Pathfinding + obstacle avoidance 1.4 Release

Game Engine Game Engine Resources
#1

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:
http://www.ai-blog.net/archives/000152.html
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.

#2

Could you make a blend to show us how it works?

#3

The pasteall file does that, just run it in the game engine and use the arrow keys to move the black sphere. The cube should follow it.

#4

well done, thanks

#5

Cool, it looks pretty good, I think I will try to put this in my game. :yes:

#6

Wow, nice work.

Thanks for sharing :wink:

#7

Excellent! Just one question: what about objects that may end up in the way, can we find a path around those?

#8

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.

#9

Pretty good pathfinding, I am wondering why you went with dijkstra’s in stead of A*?

Also the offsetting the empties takes awhile, maybe you should automate it.

Ex.

#10

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 :slight_smile:

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.

#11

Here is an a* pathfinding guide.

#12

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 :slight_smile:

#13

This is really nice, multiple objects, easy to set up, quick, uses nav mesh(you show its much better, hardly any points are needed)
Thanks!:yes:

#14

So is the pasteall file in the main post updated?

#15

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.

#16

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?

Cheers man;)

#17

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

#18

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.

#19

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.

#20

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 :slight_smile: