A* / Jump Point Search algorithm implementation in Blender


(youle) #1

Hello.

I tried to implement A* algorithm in Blender. This algorithme finds the best path (not all the time) from one point to another in a labyrinthe.

I share the result of my experience:

https://drive.google.com/file/d/0B3GouQIyoCmrM1JWMDNRWUZMTUU/edit?usp=sharing (A* simple)

With the mouse:

https://drive.google.com/file/d/0B3GouQIyoCmrU2QxUzhyU1lOb28/edit?usp=sharing (A* + mouse)

commands:

  • right click to change destination (warning: if the path is too complicated, Blender can crash). if no path is found, a message “pas de solution” is written in console.
  • left click to add an obstacle
  • wheel click to delete an obstacle
  • mouse wheel to change obstacle(obsx=horizontal obstacle, obsy=vertical obstacle)

Another implementations of A* for Blender here:

http://wiki.blender.org/index.php/Doc:2.4/Tutorials/Game_Engine/Resources/AI_Scripts

And here is an illustration of the way of functioning of the algorithme:

http://upload.wikimedia.org/wikipedia/commons/5/5d/Astar_progress_animation.gif

Thanks for any comment, way to make the implementation faster…

Have a good day!

:slight_smile:

Jump Point Search:

Jump Point Search simple:


(Smoking_mirror) #2

I couldn’t download it, it says that too many people have downloaded it. I’d recommend Mediafire as a pretty pain free way of hosting Blend files.

Anyway…
I’m working on my own pathfinding implementations right now (or I should be instead of writing this ^^), I’ve found a number of things that can speed up pathfinding, and can make it work well with random terrain or destructible terrain.

One thing is that you don’t need a graph of the whole of your map. You only need to create a graph based on a bounding box around your start and end goals with a modest border for allowing backtracking (perhaps 5%-10% of the distance to the goal).

Where do you get your graph data? Well you don’t need a precomputed array of your whole map area, just check any nodes inside the bounding box to see if they have an obstruction near enough to prevent access. You can create a dictionary of blocking objects with a key based on their x,y location and data about their size to speed things up, and you can create areas which are off limits such as ponds or whatever and then check if a node is within that area (there’s code for that around the web somewhere).

You can also speed things up by using some of blender’s built in functions, such as getDistance to or using vector lengths to calculate your heuristic. These functions are optimized and compiled so run much faster than even a simple Manhattan distance check.


(youle) #3

Thanks for your replies.

@3D solar system builder: I wrote this code yesterday and this morning. It’s just a basic stuff. I think you can find a better code and a better programmer to implement A star in Infinite terrain generator. I’m a noob. :slight_smile:

@Smoking_mirror: Thanks for suggestions to speed up algorithme. A download link for my implementation: http://www.pasteall.org/blend/31791
I reduced the scale of the grid to increase performance but it is still slow. I’ll try to improve my code later. Thank you very much for your advices!

Sorry about the french comments and variables names in the file, but as you can see, i don’t speak english well. I’ll try to traduce it if i’m motivated later.


(Smoking_mirror) #4

It’s not very slow. I tried some difficult mazes and they still got through within a second or two. That’s pretty good at 50x50 resolution.

Most games in Blender wouldn’t require many pathfinding checks at that distance.

One thing you can do to speed it up is to use a simple Bresenham’s line check, or raycasting check to see if there is a straight line to the target. The time for going in a straight line with no obstacles from 0,0 to 50,0 was quite high.

You can increase speed by doing a check to see if it’s possible to get to the goal without A* first before you run the algorithm.

Often in a game setting it will be possible, people usually move their characters from one visible location to another, they don’t often send them searching through mazes on their own. Monsters also usually have to see the character to try to attack them, that means there’s often a straight path for them to take.


(Monster) #5

*** moderation ***
moved from Game Engine Support and Discussion
reason: it is a resource


(youle) #6

Thanks Monster.

Little update:

http://www.pasteall.org/blend/31802

I’ll try to implement the straight line condition now, and also to find a way to avoid freezes (threading?)

Another update:

http://www.pasteall.org/blend/31810

(threading to avoid freezes and translation in english (bad))

EDIT: Thank you Smoking_mirror for the improvement suggestions. I’ll try to improve it later. :slight_smile:

update:

http://www.pasteall.org/blend/31816 (french)

Bresenham’s line check. Thanks Smoking_mirror.


(Smoking_mirror) #7

If you want to add more improvements you can consider the following:

Giving multiple routes to more than one selected agent. You’ll have to make a function to offset their ending point from the final destination.

Getting multiple pathfinding agents not to crash in to each other. In my own implementation I’m giving each agent a movement priority index and if they are blocked by someone with a higher index they will wait for the higher priority unit to move. Priority is incremented += 1 every time a route is calculated, so more recent movements have priority. You can check for collision using a raycasting check.

If you’re programming group movement it’s best to give lowest priority to those agents furthest away from the target destination.


(youle) #8

Hello.

Big update:

http://www.pasteall.org/blend/31846

I abandonned threading and Bresenham line check, but instead, I implemented Jump Point Search algorithm, a recent pathfinding algorithm, more powerfull than simple Astar algorithm.

http://zerowidth.com/2013/05/05/jump-point-search-explained.html

I haven’t find the algo in python, so I adapted this code:

Good day!


(Smoking_mirror) #9

Really great. It runs super fast.

I’ve tried doing a jump point search myself in the past, but I just couldn’t get my head around it. :frowning:

On a side note, if you want more complex obstacles I’ve been experimenting with walkmeshes or don’t-walkmeshes.

I use one of the mathutils.geometry functions to find if a grid coordinate is inside a 2d mesh (first have to break it in to triangles) and then add it to a dictionary to be used later by the graph builder. It allows for much more detailed (and concave) obstacles.


(BluePrintRandom) #10

can these operate on 3d space? surfaces of walls?

I wanted dretch like begavior, from tremulous…

dretch mobs are scary…


(youle) #11

@Smoking_mirror: Thank you. I’ll take a look at your link.
@BluePrintRandom: hmm. I don’t know. I’m not sure what you mean…

EDIT: After tests, many bugs remain. I’ll try to fix it.


(BluePrintRandom) #12

this is a human controlling a dretch

I would like a AI that is just as crazy of a pilot …


(3d solar system builder) #13

You could make the npc learn the fighting tactics of people in a multiplayer game.


(Smoking_mirror) #14

You could do a pathfinding system that would work in full 3d, but it’d require quite a complex walkmesh, and you’d have to turn off gravity for the agents using it.

I read a good pathfinding article yesterday, using modified BSP trees to create a nav mesh automatically.
it’s here:
http://www.mechanicalcat.net/richard/log/Python/Solving_Game_Entity_Navigation_Using_Python
I doubt it could work with BPR’s insect type movement, but it’d be something to try for a simple 2d movement system.


(youle) #15

After tests, I realised that there was errors in the path in some situations:

I tried to reproduce this code: https://github.com/qiao/PathFinding.js/blob/master/src/finders/JumpPointFinder.js

in python: http://www.pasteall.org/blend/31866

But I don’t understand where is the problem.

Nevertheless it seems to work fine here: http://qiao.github.io/PathFinding.js/visual/

If you want to take a look at my code, I thank you very much (but it’s very complex).

Otherwise, I will post a message if I find the error.

Edit: I solved the problem with Bresenham line check but it’s dirty…

EDIT2: Ok I made a big mistake. I forgot to sort the openList by F cost:

http://www.pasteall.org/blend/31878

EDIT3: http://www.pasteall.org/blend/31886 BlenderJPS+mouse

Now I can try multiplayer movements…


(Gargamel) #16

Why do you say that A* does not always return the best path? That is one of the properties of A*: It always returns the optimal path.


(youle) #17

http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html

A star returns the best path according to your heuristic choice.

http://www.policyalmanac.org/games/aStarTutorial.htm

Citation:
"you might guess that the heuristic is merely a rough estimate of the remaining distance between the current square and the target “as the crow flies.” This isn’t the case. We are actually trying to estimate the remaining distance along the path (which is usually farther). The closer our estimate is to the actual remaining distance, the faster the algorithm will be. If we overestimate this distance, however, it is not guaranteed to give us the shortest path. In such cases, we have what is called an “inadmissible heuristic.”

Technically, in this example, the Manhattan method is inadmissible because it slightly overestimates the remaining distance. But we will use it anyway because it is a lot easier to understand for our purposes, and because it is only a slight overestimation. On the rare occasion when the resulting path is not the shortest possible, it will be nearly as short. "


(Gargamel) #18

Fair enough. In case you are interested, the octile distance is not really hard to compute. Instead of
DELTA_X + DELTA_Y,
it’s (from memory)
DELTA_X + DELTA_Y - (2 - SQRT(2)) * MIN(DELTA_X, DELTA_Y)
This heuristic is admissible (on 8-connected grids).


(youle) #19

@Gargamel: Manhattan distances suits me. But thank you for the info.

Update:

Multiplayer with obstacles avoidance (my own system) and a little ending point offset function…:

http://www.pasteall.org/blend/32307

Blender RVO (reciprocal velocity obstacles) produces weird effects and didn’t satisfied myself. I looked at David Silver’s WHCA* but I think it wasn’t adapted to jump point search algorithm. I made lots of tests, and finally wrote my own avoidance system and it does what I wanted.

There are still some minor bugs (index errors). I’ll try to fix it later. The program is far from perfect and the code is not optimized and it consumes a lot of CPU but I’m thinking about one or two ways to improve it.

Anyway, I’ll make some cleaning in the code, try to comment it in english, choose better variable names, maybe make a module and above all, try to find a solution to make the system work on very large maps. I have an idea on how to do that but your advices are welcome. Good Day!

EDIT: I Haven’t implement “diagonal avoidance” yet. But I’ll do that later.

EDIT2: That works only if players are in single file.

EDIT3: Sorry. Actually, there are many errors…

Little update: obstacle avoidance improvements (it’s far from perfect but it’s very complicated) and replacement of the obstacles function (obstacles have only a game property “obstacle” and “radius”.

@BluePrintRandom: In grid pathfinding, all obstacles are represented by grid squares (to answer your question about cylinders):

http://www.pasteall.org/blend/32334


(youle) #20

Hello!

Update: I abandonned dynamic obstacles avoidance and offset function to get players into rows for the moment.

Instead, I made a system to find paths on large maps. I don’t know whether it’s orthodox or not (I don’t know how pro devs make), but I made a waypoints sytem:

  • The map is a grid of grids with waypoints at each grid angle and in the middle side of the grid.

  • We get the start position of the player.

  • We get the destination position.

  • We compute the direction to follow (end position - start position)

  • We choose a “start waypoint” according to the direction from start and another “end waypoint”
    according to the inverted direction from start.

  • We compute the path (with jump point search on “waypoints grid”) beetween the start waypoint and the end waypoint and we stock it in a player game property.

  • We compute the path (with jump point search on “normal grid”) beetween the player position and the first waypoint.

  • We begin to start moving player from start point to first waypoint (in its stocked list of waypoints)

  • Every time the player reaches a waypoint, a new path is compute on "normal grid beetween the waypoint and the next waypoint.

  • At the end of the waypoint list, we compute the path beetween the last waypoint and the destination
    position.

Little scheme:


With this method, we can move players on any sized maps because only the path beetween 2 waypoints is calculated.

I share my .blend although i’s far from perfect (each grid resolution is too important and performances decrease over time (I think a list extends over time and is never cleaned. IndexErrors may occured sometimes… I’ll fix that… I forgot: I made a little mouselook too for the camera movements:

http://www.pasteall.org/blend/32417

Now, I have to adapt avoidance strategy and offset functions to the new waypoints system. And also fix performance issues, fix errors, clean the code, eliminate redundancies…

Pathfinding is very interesting…

Have a nice day!