A* / Jump Point Search algorithm implementation in Blender

Game Engine Game Engine Resources
21

Yes it is :slight_smile:

I really like the system youā€™ve made, Iā€™ve been doing some similar things myself, though with a standard A* search.

If youā€™re looking for a more efficient grid, you could try quad trees, I think youā€™re heading in that direction already with your grid.
http://www.mechanicalcat.net/richard/log/Python/Solving_Game_Entity_Navigation_Using_Python

Thereā€™s a interesting point at the end of that article which deals with post processing of paths. The writer only touches on it, but Iā€™ve tried it and found it gives really nice results, but slows things down a bit. Maybe it could be optimized too.

BTW: When I tried your system, the only thing I didnā€™t like was the way that all the agents stack in to one tile at the end of their path.

In my own experiments Iā€™ve written a quick function to get an array of points around the final destination, sort them by distance to the origin, and then sort the agents by distance to the multiple destinations. I then assign the nearest destination to each agent, so they are least likely to block each other at the end of their journey.

22

Thank you Smoking_mirror! Yes, when I tried to make waypoints system, I set aside dynamic avoidance and offset functions to sort players at the end of the path. Today I restablished avoidance but I have some difficulties with offset. Could you show me your code with array of points etcā€¦Please?

On a different subject, I think Iā€™ll try your function to replace mouse over any sensor with getscreenray or getscreenā€¦ in the ressource section. So thank you by advance!

Iā€™ll take a look at your article on quad trees but I dā€™ont want to rewrite all my code, except if this is simple and comprehensible for me:)

So good night now! Morning is a better moment to code I think (Ā°Ā°)

23

I find that the simple funnel algorithm is a very good means of finding the shortest path within a shortest discrete path (from astar)

24

Hello agoose77! I donā€™t know exactly what is the funnel algorithm, but because I was already using jump point search algorithm, I prefered to use it a second time. It detects obstacles if waypoints are on the path, it returns the shortest path, and it is very fast.

The scheme I made is very simplified, but things are more complex in the code that I am trying to do. But when Iā€™ll have some time, Iā€™ll take a look at funnel algorithm. Thank you!

And also thank you for your great works and for your implication in Blenderā€™s community!

Bye.

EDIT: A little demo of what I made:

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

Tell me what do you think about!

Explainations: There is a grid of grids (named wpgrid (waypoints grid)) of 4x4 grids.
Each of litlle grids is namedā€¦ grid.

When you select a player (or a group of players), and select a destination (right click), at first a path is computed on wpgrid. If there is an obstacle on the waypoint, the algorithm choose another waypoint for the path. The computation is very quick because wpgrid length is very short (green squares on the map are the waypoints and also represents squares in wpgrid).

Then a second computation with the same algorithm is made but on simple ā€œgridā€ to calculate the path beetween the players position and the next waypoint. The computation is also quick because we compute only a part of the path and not the entire path.

When a waypoint is reached, we travel towards the next waypoint etcā€¦

EDIT2: In the file I shared, grid sides are composed by 25 squares. Itā€™s a parameter we can change easily with a game property. But what I want to say is that it is normal if the waypoints donā€™t correspond exactly with the grids, because there are 2 waypoints for 25 squares > 25/2 = 12.5 and we donā€™t want floats so I round to 12 (int).

EDIT3: I set aside avoidance because that did not work well and I think that was consuming lots performances. I have to rewrite the function or to find a good and simple algorithm that I can understand to implement it. If you have any idea?.. Thank you!

EDIT4: I specially put obstacles on waypoints to show the interest of pathfinding beetween waypointsā€¦(the large cylinders)

25

To get a list of x,y points around the destination point I use something like this:

def generate_destinations(original_x,original_y,size,spacing):
    destination_list = []
    
    if size == 1:
        return [[original_x,original_y]]
    
    else:
            
        for x in range (size):
            for y in range (size):
                
                negative_offset = int(size * 0.5)
                
                off_x = (x - negative_offset) * spacing
                off_y = (y - negative_offset) * spacing
                            
                x_loc = original_x + off_x 
                y_loc = original_y + off_y
                            
                destination_list.append([x_loc,y_loc])
         
        return destination_list

The size is the size of one side of an array. size = 3 would return a 3x3 set of destinations.
The function doesnā€™t actually return an array, but a list of destinations. This makes it easier to sort the destinations, and they donā€™t really need to be in array form anyway.

Once I have the list of destinations I sort the list of agents to get them in order of furthest from the destination. Then I go through each agent and find the destination nearest to them. I assign this as their destination and remove it from the list. And continue until all agents have a destination or I run out of valid destinations.

Agents nearest the destination point need to go to destinations furthest from the origin.

That should result in the shortest distance for each agent when traveling to their goal.

Butā€¦ you have to check each destination to see if it is valid (in the game area, not inside an obstacle etcā€¦).
You could start off with a large grid of destinations, say 5x5, or double the number of agents and then eliminate any invalid ones. Next you could sort the list of potential destinations by distance from the main destination and crop the list to equal the number of agents.

For sorting lists of objects or locations by distance I use something like this:

def sorted_by_distance(main_object,object_list):
    
    sorting_list = []
    for ob in object_list:
        distance = main_object.getDistanceTo(ob)
        sorting_list.append([ob,distance])
    
    sorted_list = sorted(sorting_list,key=lambda sorted_list:sorted_list[1])         
    final_sorted_list = [entry[0] for entry in sorted_list]   
    
    return final_sorted_list

That works for objects, youā€™ll need a different check for [x,y] locations or vectors. I usually get the vector from the reference location to each checking location and then get vector.length to find distance.

EDIT:
The new demo works great. Thereā€™s too much code now for me to read through it, but I did have a good run through of the demo.
There was some jiggling or wobbling of agents at the end of their journey for some reason, like they were trying to decide where to go even though they should be inactive.

There is a tendency to follow the green nodes but I canā€™t really see any problem with that.
Perhaps some post processing of the paths would get rid of the ā€œLā€ shaped movement that sometimes happens.

Itā€™d make a good navigation AI for infantry units in a real time strategy game. Low cost, and the formational movement would be beneficial.

26

I did something like that but your system seems more clean than mineā€¦ Thank you! Iā€™ll try it laterā€¦

EDIT: Itā€™s not similar to my system actually. But better. Thank you!

EDIT2: Thank you for your edit. There are still some errors in my offset function but Iā€™ll try to replace it with yours. About jiggling, Itā€™s a little problem in the ori() functionā€¦

For L movements, unfortunately, with my system of waypoints (green nodes) I donā€™t know how to resolve the problem for now. But Iā€™ll try. I just begin pathfinding (and coding about one year ago) so I hope Iā€™ll make some progress! Thank you for all your advices, and for your piece of code.

27

If youā€™re not going to reuse the object_list list, or distances, itā€™s more efficient to sort in-place the object list, and to reduce the number of steps required


def sort_by_distance(objects, obj):
    objects.sort(key=obj.getDistanceTo)

Otherwise, use sorted


def sorted_by_distance(objects, obj):
    return sorted(objects, key=obj.getDistanceTo)
28

Thank you both. I tried your system Smoking_mirror. That works and thatā€™s fun but that produces a backward movement before players line up. Iā€™ll see that tomorrow. Good night!

Thank you both. I tried your system Smoking_mirror. That works and thatā€™s fun but that produces a backward movement before players line up. Iā€™ll see that tomorrow. Good night!

EDIT: I see a way to avoid parts of L movements. Currently, I use a function (expandPath) based on Bresenhamā€™s algorithm, to have waypoints all along (1 waypoint per grid) the waypoint path. It limits the computation of the path on normal grids to the distance beetween 2 grids. But on simple maps, like in my example, I can try to not use expanded path, and it does something like that:

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

As you can see, it limits the number of waypoints on the waypoint path. But on the other hand, It increases sometimes the distance beetween 2 waypoints, so the computation of the path on normal grid can be a little more long. On simple maps, that causes no problem. But if I have a maze on each grid, it can become a problem.

EDIT2: Iā€™d wish a system to improve my move() function. Currently, each player follows its own expanded path and it consumes lots of performances. Do you think using steering behavior ā€œfollowā€ is a good idea?

EDIT3: Ok Smoking_mirror, now your system works almost perfectly. I was tired yesterday evening and made mistakes due to scaleā€¦ Almost because sometimes players go through each otherā€¦ Iā€™ll fix that today. Thank you again.

29

Thanks! :slight_smile: Iā€™ll put that in my current utilities script.

EDIT:
how come it isnā€™t

obj.getDistanceTo()

With a sorting key donā€™t we need the ()?

After some testing and re-reading the python how to sorting documentation I think Iā€™ve got some basic idea again of how to do sort keys, for example:

object_list.sort(key= lambda self,other = main_object: other.getDistanceTo(self))

seems to do the same thing but there seems to be nothing in the python documentation about leaving off the ()s.

30

Yes I tested it too and that works fine. Good to know. Thanks!

EDIT: I had errors with intensive utilisation of the pathfinding with:

sorted(objects, key=obj.getDistanceTo) (error getDistanceTo needs a KX_Game_Object or a Vector blablablaā€¦)

I donā€™t known why!? But now I use Smoking_mirrorā€™s formule:

object_list.sort(key= lambda self,other = main_object: other.getDistanceTo(self))

and that works fine. Weirdā€¦

My work of the day:

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

Your code (Smoking_mirror) is at lines 910 to 944 and in the move() function, 1215 to 1221 and 1266 to 1273. It does some weird things when you select all players on the map and tell all the players to move somewhere. If you have a moment, could you tell me why it does such strange movements? Thank you! (Iā€™ll try to increase size of destination list to see if that changes somethingā€¦)

EDIT2: As a rewarding for your help and advices, a little game that I made a day of last week inspired by ā€œpioupiou contre les cactusā€ :p:

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

EDIT3: In my last pathfinding file, lags were the result of my playerā€™s physics (static). When there are too players with static physics at the same place, FPS decrease dramatically. Thatā€™s strange because 2 physics objects are not colliding, no? Can someone explain me this?

EDIT:

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

31

Haha, I guess pioupiou is similar to flappy bird? (which is actually based on an old game called helicopter from more than 10 years ago) :slight_smile: It was fun, I think I got about 17 points.

With regard to the A* file, there are a few problems:

  1. It seems that your bounding box select only works if you select from left to right and top to bottom, i.e. from the top left corner to the bottom right. If I try to start the box from any other position it wonā€™t select the objects.

When writing a bounding box code I use the point when click is first activated until the point when it is released:

if left_mouse.positive:
            if not own['start_selection']:
                own['start_selection'] = mouse_position
            else:
                draw_selection_box(own['camera'],own['start_selection'],mouse_position)
                ### draws the visual box only
                
        else:
            if own['start_selection']:
                start = own['start_selection']
                end = mouse_position
                select_agents(own['camera'],start,end)   
                ### passes the start and end point to the selector function
                own['start_selection'] = None   
                ### resets the start point ready for the next select operation

and then I sort the start and end points to get an x_limit and a y_limit:


x_limit = sorted([start[0],end[0]])
y_limit = sorted([start[1],end[1]])

I then check of any selectable objects are inside those limits:

if screen_location[0] > x_limit[0] and screen_location[0] < x_limit[1]:
    if screen_location[1] > y_limit[0] and screen_location[1] < y_limit[1]:
         selected = True

Because of sorting the x_limit and y_limit it doesnā€™t matter what order my selection points are in when fed to the selector function.

  1. When I try your file I sometimes get an error about:

line 1272 in move, list assignment index is out of range.

Which freezes the simulation after than. I donā€™t know whatā€™s causing that.

  1. I think your destination array may be too big. If you have 25 players, you donā€™t need a 25x25 box, but a box with 25 destinations, which would be a 5x5 box, or the square root of len(players). It might be good to increase that number to 6x6 because some locations may be lost because of being invalid. Also remember that if a player doesnā€™t get assigned a valid destination (because of the valid_destinations_list being shorter than the selected_player_list) you need some code to tell the player what to do. Maybe just be inactive.
  1. One final point is about how you orientate your players and move them. I usually use a target vector, from the player to their current destination:
target_vector = agent['route'][0]).to_3d() - agent.worldPosition.copy()

### to_3d() transforms a 2d (x,y) vector in to a 3d (x,y,z) vector
### using a .copy() of a vector which is owned by a game object such as .worldPosition is good practice, 
### in case you accidentally alter the original vector, which would cause the original object to move.

then I use the very helpful .to_track_quat() function to get something I can use for worldOrientation:

target_rotation = target_vector.to_track_quat("Y", "Z")
agent.worldOrientation = target_rotation

You can use the slerp function too for gradual alignment:

target_rotation = target_vector.to_track_quat("Y", "Z")
agent_rotation = agent.worldOrientation.to_quaternion()                                        
slow_rotation = target_rotation.slerp(agent_rotation,0.9)                    
agent.worldOrientation = slow_rotation
### this is the same as using the track_to actuator, but doesn't need an object

And for movement I usually move an object along its local y axis:

local_movement_vector = agent.getAxisVect([0.0, 1.0, 0.0])    
local_movement_vector.length = agent['speed']
agent.worldPosition += local_movement_vector

I hope some of that is useful to you, Iā€™m working on similar code right now, and thatā€™s the way I do things, but Iā€™m not saying that that is THE ONLY way to do things. Just try different methods and see which is best for you.

32

Thanks for the tips!

About selection box, I made my system without reflexion (like a big part of my code)ā€¦ Iā€™ll study your codeā€¦

As you say I still have many errors in the move function. Sometimes, the Jump Point Search algorithm returns a null path [] and I donā€™t understand why. And that causes errors. I have not programmed much today. But I must resolve this problem before trying other things.

For the destination array, youā€™re right. Iā€™ll reduce it to round(sqrt(len(playerGroup)))+1 or something like that.

About my orientation system, itā€™s a makeshift job. But Iā€™ll go over that again later.

Thank you!

33

The reason you leave off the () is because itā€™s functionally equivalent. However it saves having it create an extra stack frame (or, in other words, the overhead of a function call) for each sort key lookup.
If you define a function f as
F=lambda:x print(x), it will effectively wrap the print function, as it doesnā€™t do anything on top of calling print with the same arg. Object.getDistanceTo is a function, and lambda self:Object.getDistanceTo(self) will create a functionally identical function (it just calls Object.getDistanceTo with the value of self you provided). This is because we can refer to functions as objects, and pass them around as objects, and call them later on.
(I.e x= obj.getDistanceTo
Distance = x(self))

34

Thanks for the explaination. Finally, I had the same errors with the Smoking_mirrorā€™s formule. So the problem I had came from somewhere else in my code.

35

Yeah, I tested agoose77ā€™s way of doing it and thereā€™s nothing wrong. After reading a bit about it I did find some info about using functions as keys, so thanks agoose for the info. Most of the tutorials I read didnā€™t cover that part. :slight_smile:

But if youā€™re using

x.GetDistanceTo(y)

ā€œxā€ must be a blender object, while ā€œyā€ can be either an object or a vector. That means all the objects in the list must be valid Blender Objects. If any of them are None or [] or a Vector, it will return an error.

Somehow your code is putting something incorrect in the list, or youā€™re trying to sort an empty list.

36

Hello! Ok now I think there is no more error:

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

Iā€™ll do what you suggest to me Smoking_mirrorā€¦

37

Yes, it seems youā€™re right! I didnā€™t get any errors that time.

When testing itā€™s important to try your best to ā€œbreakā€ the system. Sometimes as developers we can be a bit soft, just doing the right set of commands to get it to work, but we have to be tough on the systems, and really push them to do things we didnā€™t think of when designing them.

For example:

Q:What happens if you click on an obstacle as the destination point?
A:A huge lag spike as the closed list expands to the whole area.

Solution: If the destination is inside an obstacle, we donā€™t need to do a search. So how about doing a ray or mouse-over check for obstacles when getting the destination. If thereā€™s an obstacle, donā€™t search for the routes.

Q: What happens if you select a large group of agents (a) and move them, then select another group (b) and move them too at the same time?
A: The second group gets a huge destination array(a+b), and finish not near the destination.

Solution: ??? :slight_smile:

Anyway, itā€™s coming along really well, I donā€™t think Iā€™ve ever seen so many agents moving at once in the game engine! Really amazing.

38

Ok I followed most of your advices:

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

The selection box improved.
No pathfinding when you click on an obstacle.
Your system of orientation.

Thank you for all!

EDIT: Arghhhh, there are still some errors sometimesā€¦

EDIT2: I think itā€™s finally fixed.

update:

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

  • Big bug fixed
  • Flying players through obstacles near end point fixed.

EDIT3:

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

  • A part of the offset (players line up) process is computed directly when you right click
  • I just tested my new mouse over any function (on the rectangle selection box for the moment) that I did tonight and about Iā€™m proud of :stuck_out_tongue:
  • I cleaned a bit the code (path function)
39

Little update:

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

  • New map
  • zoom camera
  • some other little things

But still many improvements to add. My avoidance system does not work correctly. Also my waypoint systemā€¦

40

I think you need to add some obstacles like rocks or simple.Ounce you fix the obstacle avoidance.
Why canā€™t you make it so that they will follow a leader.If you order the leader around or you could select a group of them.
Their could many groups within the groups that could have leader.You could select a group of them and then a particular leader.Then have them follow that particular leader.