Node base path finder


I need your help!
I have converted my grid based into a node based path finder used for navigation.

While it’s working i walked into a bug/glitch and to be honest i have absolutely no clue why it is doing what it is doing.

  • red cubes are npc’s (with red path line)
  • green cube is player and controlled by me (green path line)
  • green cube can click anywhere to calculate a path, red cubes got green cube as target.

problem: while all npc’s are 100% the same the bottom ones bug/glitching out, and it has something with a diagonal something/border?

It does throw me an error when it happens: (but i don’t know why he throws it at me)(Don’t explain the error i know what it says)

Python script error - object 'player.004', controller 'Python':
Traceback (most recent call last):
  File "C:\Users\Cotaks\Desktop\node based shortest path.blend\", line 120, in find_path
KeyError: 'value = gameOb[key]: KX_GameObject, key "neighbors" does not exist'

Yes confusing, here is a video:

Here is the .blend
(blend removed)

Code is a bit messy wanted to clean it up and change some things till i discovered this bug/glitch.

p to play
aswd to move green cube
left click anywhere to set a path for green cube

I’d start by printing out the object name that it’s checking for ‘neighbors’ on and make sure it is actually one of your nodes. Then you’ll know if you’re adding the wrong items to your path, or the nodes are not having their neighbors property set correctly.

1 Like


Oh wow, figured it out. you where right, the player was getting inserted into the path, player does not have neighbors so the error pops up.

Feel so stupid now xD


1 Like


now you get your coder metal

debugging A* can be painful.

Tell me about it lol, took a handfull of hours looking and testing that tiny bit of code, seeing that everything works except bottom row npc’s. then all of a sudden i see player scroll by in their path, that’s not good. while the error raises in the neighbors, and they print out correct, that is very confusing. The error was in the detection/grabbing of the nodes. i check them with 4 rays, but i did not check the rays itself, so everything in range got added to their pathings.

Funny thing is i use this ray setup in my grid spawned version as well, it never rises up due to the grid/ground was always spawned first before adding anything else to the scene. Making me only more confused.

I would have the pathfinder objects use a property - dig through all those on frame 1 and connect them up / build your graphs
are you in 2.79x or 2.8x ?

for obj in own.scene.objects:
    if 'path_obj' in obj:
         for poly in

using 2.79

i collect all nodes

own['node_list'] = [obj for obj in own.scene.objects if 'node' in obj] 

the looping trough them

for node in own['node_list']

cast 4 rays in global directions and put them in node[‘neighbors’]

the actuall pathfinding is this piece

        for i in range(len(grid_spawner['node_list'])):

            if not own['end'] in own['path']:
                nodes = []
                dist = []

                for neighbor in own['path'][:].pop()['neighbors']: 

                    dist2 = neighbor.getDistanceTo(own['end'])  
                dict = {'nodes': nodes, 'distances': dist}    
                index_min = min(range(len(dict["distances"])), key=dict["distances"].__getitem__)    
                nearest_point = dict["nodes"][index_min] 

thanks to @Liebranca for a crucial piece of code.

and own[‘path’] is the path, looping trough it to give nodes their color

this can all be done in 1 frame(and only need to be run once, unless nodes changes then i call it again for a frame to update it), so only when i give the npc a movement option then it needs to loop trough the path to get to where it should go.

1 Like

cool to see people experimenting on that

one should create a new upbge actuator with parameters

  • target (object)
  • nodes/checkpoints (list of empties)
  • attitude (go to, approach, avoid, escape) (the target)
  • velocity (or other inertia %)

imported_pathfinder_3.0.blend (693.1 KB)

this uses bpy* - you could run it 1 time and pickle it for standalone.

edit - this was written before I knew about :stuck_out_tongue:

what is the fun about that, wasting hours to script something that works like you want is very rewarding.

I finally figured out a way to make my own working A* method.
Look at this lol:

i have based this on the breadth first search method.

Working like a charm, while my other versions like the one above did not work to the fullest when having gaps in the map, this one eats it alive lol.

nicely done, but i coulnd use it due to i am not using 3.0. (as i said before) but i took time to look at it.
for now i am very happy with the method i have made. not even using the bge module so i can even license it to my own liking haha.


yeah - the ‘graph scooper’ and the ‘pathfinder’ can be separated pretty easily - (to make it not force the gpl on pathfinding) - but I don’t care - bge needs us to give away resources until it picks up steam.

Ok so i got asked to what steps i took to make this, well these steps:

    if not '__init_' in own:    
        own['tile_list'] = [tile for tile in own.scene.objects if 'tile' in tile]
        own['__init__'] = True

This is all i need.

yeah true, but for a-star you woulnd really need bge module, your not moving a character or anything.
i simply execute the above init and get it done. Once a character gets involved licence is out of the window haha. But i got the same thing i don’t care about it either.

no true pulse ! :champagne:

people should store/save/archive their work on a open wiki.

Why this thread has to be lost in the stack after 1 week ? (even if google exists) Forums are good for brainstorming but not state progress in a field like AI pathfinding.

Because i just needed some support, due to a stupid mistake i made.
There is no gain from this topic, the code inhere is actually not working as it should(can’t navigate around gaps) and is just a part of the code.

I strongly recommend to not use the code snippets i’ve posted.

However “i have based this on the breadth first search method” that mechanic works like a charn, but again, there is nothing to gain in this topic.