Dijkstra Map pathfinding

i made a grid based path finding i hope some would find useful

here is some screen shots, one with and another without visuals for testing.



and her is the blend for it.

size: 75.5mb
http://15b.dk/blendfiles/grid-pathfinding.blend

adjustments can be made here.


Could this handle a digging videogame made with the blendfile
on post 16 of the link?I was originaly using the camera actuator for pathfinding.But i could only get two npc’s to work with camera actuator.One of the npc’s would fall through the floor.

should be possible by extending it in the z dimension.

but how to do it would be up to you :wink:

Why did the npc move and then stop moving? What is wrong with my code?

import bge
from time import time


def roundnum(n,base=100):
    rem = n % base
    if rem < base // 2:
        n = (n // base) * base
    else:
        n = ((n + base) // base) * base


    return int(n)


def griddir(grid,key,openlist,closedlist,dist,fromkey):
    if key not in closedlist and key not in openlist:
        openlist.append(key)
        grid[key]["dist"] = dist+1
        grid[key]["from"] = fromkey


    
def placeobject(grid,scene,key,maxdist,own):
    placer = scene.objects["placer"]
    
    if own["grid"].grid[key]["seen"] == 0  :
        if own["grid"].grid[key]["dist"] < maxdist - 1 :
            own["grid"].grid[key]["seen"] = 1
            placer.worldPosition = own["grid"].grid[key]["pos"]
            obj = scene.addObject("Plane",placer,0)
            obj.children[0]["Text"] =str( own["grid"].grid[key]["dist"]  )
            obj["dist"] = own["grid"].grid[key]["dist"]
            own["grid"].grid[key]["text"] = obj
    else:
        if "text" in grid[key] :
            if own["grid"].grid[key]["text"] != "":
                own["grid"].grid[key]["text"].children[0]["Text"] = str( own["grid"].grid[key]["dist"]  )  
                
                own["grid"].grid[key]["text"].children[0].color = [0,0,1,1]
                
                if own["grid"].grid[key]["dist"] <= maxdist-4:
                    own["grid"].grid[key]["text"].children[0].color = [1,1,1,1]
                elif own["grid"].grid[key]["dist"] > maxdist - 2:
                    own["grid"].grid[key]["text"].children[0].color = [1,0,0,1]


                if own["grid"].grid[key]["dist"] == 0 : 
                    own["grid"].grid[key]["text"].children[0]["Text"] += "
" + "start {}".format(key)
                else: 
                    own["grid"].grid[key]["text"].children[0]["Text"] += "
" + "this {} from {}".format(key, own["grid"].grid[key]["from"])             


                if own["grid"].grid[key]["dist"] > maxdist-2:
                    if own["keep Objects"] == False:
                        own["grid"].grid[key]["text"].endObject()
                        own["grid"].grid[key]["text"]=""
                        own["grid"].grid[key]["seen"] = 0
                    
                                
def main(cont):
    own = cont.owner


    scene = bge.logic.getCurrentScene()
    player = scene.objects["player"]
    placer = scene.objects["placer"]


    runit = own["show"]
    maxdist = own["maxstep"]
    
    posx,posy,posz = player.worldPosition
    
    if "grid" in own:
        step = own["grid"].step
        x = roundnum(int(posx),step)
        y = roundnum(int(posy),step)
        z = roundnum(int(posz),step)


        gridkey = "{:>05}:{:>05}:{:>05}".format(x,y,z)
        playerpos = gridkey
        
        if gridkey != own["pos"]:
            
            grid = own["grid"].grid
            
            openlist = [gridkey]        
            closedlist = {}
            
            count = 0
            dist = 0
            
            if gridkey in grid:  
                own["grid"].grid[gridkey]["dist"] = dist
                
                if grid[gridkey]["seen"] == 0 and runit == 1 :
                    own["grid"].grid[gridkey]["seen"] = 1
                    
                    placer.worldPosition = grid[gridkey]["pos"]
                    obj = scene.addObject("Plane",placer,0)
                    obj.children[0]["Text"] = str(dist)
                    obj["dist"] = dist
                    own["grid"].grid[gridkey]["text"] = obj 
            
            while openlist:
                count += 1
                if count > 8000 or dist > maxdist:
                    break
                
                if gridkey in grid:  
                    for direction in grid[gridkey]["neighbour"] :
                        if direction in grid:
                            griddir(grid,direction,openlist,closedlist,dist,gridkey)
                            if runit == 1 :
                                placeobject(grid,scene,direction,maxdist,own)
                
                gridkey = openlist.pop(0)
                
                if gridkey in grid:
                    dist = own["grid"].grid[gridkey]["dist"]
                    x = int(own["grid"].grid[gridkey]["pos"][0])
                    y = int(own["grid"].grid[gridkey]["pos"][1])  
                
                closedlist[gridkey] = 1
            own["count"] = count


        own["pos"] = playerpos





you need to update the map to support 3 directions

look in the init_grid.py to see how it is generated

the map is a dict and the format is:

grid = {}
grid[gridkey] = {“pos”: pos, “dist”: 9999, “seen”: 0 ,“from”: None , “neighbour”: None}

the neighbour field is a list that store the keys from the neighbours

i have have done some bug fixes and removed dead code, plus i have done some refactoring of the code to make it easier to read.

here is the one with the visual aid code in it

http://15b.dk/blendfiles/grid-pathfinding.blend

here is a version where all the visual aid code is removed

http://15b.dk/blendfiles/grid-pathfinding-basic.blend

Okay i will try that.

In init_grid.py do i have to add zmin= -scale,zmax = scale.

In this part.

own["grid"] = Grid(x = mx, y = my, xmin = -scale , xmax = scale , ymin = -scale, ymax = scale, step = step)

you rely need to understand what the code does before you try to modify it , the grid class i wrote is heavily designed to work in a 2d grid only, it works by finding points on geometry that has the “ground” property by shooting a ray between 2 points

this is the line that does that.

hit = placer.rayCast( [pos[0],pos[1],-10000], placer, 0.0, “ground”, 1, 0, 0)

so if you need 3d you need to make a version that builds a map that fit your game world.

So adding the z axis to the python code won’t change it to 3d?

i have updated the AI on the spiders to better make use of the map.

they have 3 states now

roaming, path follow and chase the player.

monsterAI.py looks like this now.


import bge
import random , time

def roundnum(n,base=100):
    rem = n % base
    if rem < base // 2:
        n = (n // base) * base
    else:
        n = ((n + base) // base) * base

    return int(n)

def chase(scene,own,actu,cont,grid):
    own["target"].worldPosition = scene.objects["player"].worldPosition
    cont.activate(actu)
    hit = own.rayCast(own.worldPosition , scene.objects["player"].worldPosition,0.0,"",1,0,0)
    
    current = getgridpositionkey(grid,own)
    
    if hit[0] or grid.grid[current]["dist"] >= 1:
        own["mystate"] = "pathfollow"
        
        own["targetkey"] = current       

def roam(grid,own,scene):
    
    if getgridpositionkey(grid,own) == own["targetkey"] :
        pos = own["spawner"].worldPosition
        
        targetkey = getrandomkeyinrange(grid,pos,80)
        tpos = grid.grid[targetkey]["pos"]
        hit = own.rayCast(own.worldPosition , tpos,0.0,"",1,0,0)   
                        
        if hit[0] == None:
            own["targetkey"] = targetkey
            own["target"].worldPosition = grid.grid[targetkey]["pos"]
            own["stuck"]=0
            #print(tpos)
    else:
        own["stuck"] += 1
        
        if own["stuck"] > 100:
            key = getgridpositionkey(grid,own)
            
            valid = None
            
            if grid.grid[key]["neighbour"]:
                for n in grid.grid[key]["neighbour"]:
                    if valid:
                        valid.append(n)
                    else:
                        valid = [n]
                        
            targetkey = random.choice(valid)
            own["targetkey"]=targetkey
            own["stuck"]=0
            own["target"].worldPosition = grid.grid[targetkey]["pos"]

        
        
def patrol():
    pass

def pathfollow(grid,own,player):
    gr = grid.grid
    
    if "key" in own:
        own["stuck"] += 1
        
        key = own["key"]
        dist = gr[key]["dist"]
        
        if "targetkey" in own:
            targetkey = own["targetkey"]
        else:
            targetkey = gr[key]["from"]
        
        if getgridpositionkey(grid,own) == targetkey and getgridpositionkey(grid,player) != targetkey:
            own["key"] = targetkey

            key = own["key"]
            fromkey = gr[key]["from"]
            valid = [fromkey,fromkey,fromkey,fromkey,fromkey]
            
            if gr[key]["neighbour"]:
                for n in gr[key]["neighbour"]:
                     if gr[n]["dist"] < gr[key]["dist"] :
                         valid.append(n)

                
                targetkey = random.choice(valid)
                own["targetkey"]=targetkey
                own["stuck"]=0
            
        if own["stuck"] > 50:
            own.worldPosition = own["spawner"].worldPosition
            own["stuck"]=0
            own["targetkey"] = getgridpositionkey(grid,own)
            own["mystate"] = "roam"
            
        return targetkey
    else:
        own["key"] = getgridpositionkey(grid,own)
        own["stuck"]=0               

def getrandomkeyinrange(grid,pos,range):
    
    waypoints = grid.kd.find_range(pos,range)
    
    pos , a,b = random.choice(list(waypoints))
    x,y,z = pos
        
    if x != None:

        kx = roundnum(int(x),grid.step)
        ky = roundnum(int(y),grid.step)
        key = "{:>05}:{:>05}".format(kx,ky)
        
        return key
    else:
        return None
    
    
def getgridpositionkey(grid,own):
    
    posx,posy,posz = own.worldPosition
    x = roundnum(int(posx),grid.step)
    y = roundnum(int(posy),grid.step)
           
    key = "{:>05}:{:>05}".format(x,y)
    
    if key in grid.grid:
        return key
         
    index = grid.kd.find(own.worldPosition)
    
    if index[1]:
        x,y,z = index[0]
        kx = roundnum(int(x),grid.step)
        ky = roundnum(int(y),grid.step)
        key = "{:>05}:{:>05}".format(kx,ky)
        
        return key

def main():

    cont = bge.logic.getCurrentController()
    scene = bge.logic.getCurrentScene()
    actu = cont.actuators['Steering']
    own = cont.owner
    
    random.seed(time.time())
    

    if "grid" in scene.objects["1Lamp"]:
        grid = scene.objects["1Lamp"]["grid"]
        
        key = getgridpositionkey(grid,own)
        
        if key in grid.grid:
            if own["mystate"] == "chase" or own["mystate"] == "pathfollow":
                if own["mystate"] == "chase":
                    chase(scene,own,actu,cont,grid)
                    
                if own["mystate"] == "pathfollow":
                    targetkey = pathfollow(grid,own,scene.objects["player"])
                    
                    if targetkey:
                        if grid.grid[targetkey]["pos"]:  
                            if actu.target == None:
                                actu.target = own["target"]
   
                            own["target"].worldPosition = grid.grid[targetkey]["pos"]
                            actu.velocity = 7.000
                            cont.activate(actu)

                hit = own.rayCast(own.children["eyes"].worldPosition , scene.objects["player"].children["Camera"].worldPosition,0.0,"",1,0,0)
        
                if not hit[0] or hit[0] == "monster":
                    own["mystate"] = "chase"
                    own["target"].worldPosition = scene.objects["player"].worldPosition
                else:
                    if own["mystate"] != "roam":
                        own["mystate"] = "pathfollow"
                    else:
                        actu.velocity = 3.000
                        cont.activate(actu)
            else:
                distance = own.getDistanceTo(scene.objects["player"])
                
                if distance < 100:
                    hit = own.rayCast(own.children["eyes"].worldPosition , scene.objects["player"].children["Camera"].worldPosition,0.0,"",1,0,0)
                    if hit[0] == None:
                        own["mystate"] = "chase"
                   
                roam(grid,own,scene)
                
                if actu.target == None:
                    own["targetkey"] = getgridpositionkey(grid,own)
                    actu.target = own["target"]
        
                cont.activate(actu)
    
              
main()


her is a updated blend

http://15b.dk/blendfiles/grid-pathfinding-betterAI.blend

What Blender theme are you using, it looks really nice?

just one of the presets that comes with blender

The spiders can jump out of a hole but only if you are near it.Could that be improved?