Steering actuator is bugged / python alternaltives?

blenderaptor · December 13, 2019, 7:52pm

I wanted to test again the steering actuator but it seems that it’s bugged :

character goes into walls like a ghost when the the target is on a upper level
sometimes, the z axis lock is no more respected when climbing stairs (little rotation on the y axis)
sometimes glitchy shakes when the target is a character walking against / colliding with the steered object
also, seems that z rotation is made in 1 frame . So it looks weird when the new target is placed behind the old one : the steered object make a 180°

The Navmesh is horrible too. No smooth motion and very buggy on corners and elevations. Didnt even tested when the object is pushed

I started to make my own nav system in python. I was wondering if anything was previously made or if anyone is wanting to create/collaborate a new nav system (even create a new actuator ?)

Cotaks · December 13, 2019, 10:18pm

navmesh works as intended, just alter the mesh make it smaller at corners, you don’t need 5 cm wide mesh 1 cm will do fine, so that the characters walks in the middle of the hallway for example.

you can set the steering actuator to not instantly turn. so it turns slowly.

for python you can make a node or grid bases pathfinding, it’s a bit harder to setup but it would do exactly what you want

blenderaptor · December 14, 2019, 7:26am

i already tried to edit. But the result is still random ; even 1% of fail (npc stuck) is already too much . Requiring manual correction of the navmesh is somehow the proof that the thing is not an “exact science” Also, the navmesh doesn’t make the object move smoothly as the rig of the navmesh is like a mosaic .

yeah, that’s what i’m doing actually, it works well but it could be better. I put empties as checkpoints and use python to find shortest path. I gave a try to the steering actuator again but it shows bugs (unless im doing wrong or something) , so i came back to some basic trigonometry to move the npc towards checkpoints but it has some flaws : like :

you go behind the npc (you are the target) between 2 time laps and then the indication switch from i.e 176° to -173° so the npc starts to spin for a short time laps. But for that i can correct it with a “if” or use Quartenions instead of Eulers … well , i will see
also i would like to include your character directly as a checkpoint as well so the npc may not have to go the the last “n” checkpoint if your character is already accessible from the n-1 checkpoint ( to avoid the npc going forth and back to you )

blenderaptor · December 14, 2019, 7:47am

for a new navigation system (a new upbge actuator?) : ideas

find shortest path to a target
find shortest path to a target but avoiding moving objects with property X
define an emergency property Y on checkpoints : the npc goes to it or escape from it (max distance)
define a patrol parkour (‘from’ , ‘target’) or a random walk through checkpoints
… more ideas

Liebranca · December 14, 2019, 4:23pm

from mathutils import Vector
points = [0 for i in range(mesh.numPolygons)]
for i, poly in enumerate(mesh.polygons):
    centroid = Vector([0,0,0])
    for vert in poly.vertices:
        centroid += vert.getXYZ()

    points[i] = ( (centroid/3)+navmesh.worldPosition )

Then use those points to A* through.

As it’s just a bunch of points in space and there’s no need for meddling with game types, I would code this pretty independent of bge. Matter of fact, I would only use a python module here to interface with the engine and do type conversions, then leave all the heavy lifting to a C function. It may take keeping a small cache somewhere but would likely improve performance a whole lot.

Heck, if people ask prwetty pwlease I might even do it myself.

blenderaptor · December 14, 2019, 5:32pm

so you compute the centroid of each polygon of the navmesh to define them as (check)points.
In my game i put empties at strategic points of the map (like near stairs, corners) and use them as checkpoints. Then i have to define a graph, indicating for each checkpoints the other checkpoints reachable (ie: A goes to B and C , but B goes to C, C goes to B ) with a weight corresponding to the distance. I have only 13 checkpoints, so the shortest path algorithm doesn’t heat too much.

Liebranca · December 14, 2019, 6:23pm

An empty maps one point. A single mesh can map out an entire area.

It seems to me it’d be way more effective to graph how to get from one navmesh to another and pathfind through the closest than provide two arbitrary points without any navigation data. You can take it as far as defining strict paths if you’re so inclined,

But if all you have is a bunch of single nodes scattered through the map, steering alone isn’t enough; all the actuator knows is aligning objects to a vector and moving towards it. It’s basically the same functionality you’d get using getVectTo and alignAxisToVect together.

blenderaptor · December 14, 2019, 10:57pm

I use getVectTo and asin . The distance between checkpoints is the navigation data. My system doesnt need a navmesh because, if there’s enough of checkpoints and they are wisely posed, any place of my map can access to a nearest checkpoint and then start navigate on the graph.

Can your npc walk outside that white navmesh ? Im not sure i understood

Liebranca · December 15, 2019, 3:26am

You can make an agent react to environmental factors, that is a question of how well your idiots can read their surroundings and make some sense out of it.

I had to code in a physics update of sorts to do some of that myself. It’s a game of rays and spatial math. You can do obstacle simulation and register unique behaviour for different types of jams, it’s a question of altering the casting direction as the agent moves around and defining cases inside/along your evaluations. Being able to answer “What to do if I hit this rock next to me” before the rock was even that close enough can be done, but it requires real horse power.

Now, I’m all for writing down this kind of system for demos sake. Just let me know whether I’m wasting my time getting up to my elbows on it or if anyone’s actually interested, I’ll see to it.

blenderaptor · December 15, 2019, 6:11am

yes, sounds interesting. Showcase with videos would be great

BluePrintRandom · December 15, 2019, 6:27pm

I wrote ported this for upbge 0.3.0
it’s redblob games A* for py

https://www.redblobgames.com/pathfinding/a-star/implementation.html

in vanilla bge you may need to store the data I generate in the first part of main function and use that in standalone instead (as bpy is not available in standalone pre 0.3.0* )

import bge, bpy
import mathutils
from mathutils import Vector
import heapq

cont = bge.logic.getCurrentController()
own = cont.owner

def reconstruct_path(came_from, start, goal):
    current = goal
    path = []
    
    while current != start:
        path.append(current)
        current = came_from[current]
    path.append(start) # optional
    path.reverse() # optional
    return path

class SimpleGraph:
    def __init__(self):
        self.edges = {}
    
    def neighbors(self, id):
        return self.edges[id]

    def cost(self, from_node, to_node):
        return (own['locations'][from_node] -  own['locations'][to_node]).magnitude   
     
class PriorityQueue:
    def __init__(self):
        self.elements = []
    
    def empty(self):
        return len(self.elements) == 0
    
    def put(self, item, priority):
        heapq.heappush(self.elements, (priority, item))
    
    def get(self):
        return heapq.heappop(self.elements)[1]
    

def heuristic(a, b):
    return((own['locations'][a]-own['locations'][b]).magnitude)

def a_star_search(graph, start, goal):
    frontier = PriorityQueue()
    frontier.put(start, 0)
    came_from = {}
    cost_so_far = {}
    came_from[start] = None
    cost_so_far[start] = 0
    
    while not frontier.empty():
        current = frontier.get()
        
        if current == goal:
            break
        
        for next in graph.neighbors(current):
            new_cost = cost_so_far[current] + graph.cost(current, next)
            if next not in cost_so_far or new_cost < cost_so_far[next]:
                cost_so_far[next] = new_cost
                priority = new_cost + heuristic(goal, next)
                frontier.put(next, priority)
                came_from[next] = current
    
    return came_from, cost_so_far

def main():

    
    if 'Graph' not in own:
        faces = {}
        index = 0
        data = bpy.data.objects[own.name].data
        locations = {}
        for face in data.polygons:
            links = []
            
            faceVerts = face.vertices
            place = None
            for vert in face.vertices:
                if place==None:
                    place = data.vertices[vert].co
                else:
                    place = (place+data.vertices[vert].co)/2      
            
            locations[index] = place
            
            index2 = 0
            for face2 in data.polygons:
                if face2 != face:
                    face2Verts = face2.vertices
                    for vert in face.vertices:
                    
                        if vert in face2.vertices:
                            if index2 not in links:
                                links.append(index2)
                                
                    
                index2+=1            
            #print(place)
            faces[index] = links
             
            index+=1                         
        #print(faces)
        own['locations'] = locations
        own['Graph'] = SimpleGraph()
        own['Graph'].edges = faces
        
        kd = mathutils.kdtree.KDTree(len(locations))
        index = 0
        for entry in locations:
            #print(locations[entry])
            kd.insert(locations[entry], index)
            index+=1
        kd.balance()
        own['Kd']=kd
        own['requests']=[]
             
            
                                    
            
    else:
        #a request is a list or tuple with a length of 3
        #start goal agent
        #where agent is the object that needs the path
        if len(own['requests'])>0:
            request = own['requests'][0]
            if not request[2].invalid:
                if type(request[0]) is Vector:
                    loc1 = own.worldOrientation.inverted() @  (request[0] - own.worldPosition) 
                    start = own['Kd'].find(loc1)[1]
                elif type(request[0]) is bge.types.KX_GameObject:
                    loc1 = own.orientation.inverted() @  (request[0].worldPosition - own.worldPosition) 
                    start =  own['Kd'].find(loc1 )[1]
                    
                    
                if type(request[1]) is Vector:
                    loc2 =  own.worldOrientation.inverted() @  (request[1] - own.worldPosition) 
                    end = own['Kd'].find(loc2)[1]
                elif type(request[1]) is bge.types.KX_GameObject:
                    loc2 =  own.worldOrientation.inverted() @  (request[1].worldPosition - own.worldPosition) 
                    end =  own['Kd'].find(loc2 )[1]
                elif type(request[1]) is str:
                    t = own.scene.objects[request[1]]
                    loc2 =  own.worldOrientation.inverted() @  (t.worldPosition - own.worldPosition) 
                    end =  own['Kd'].find(loc2 )[1]
                       
                path = a_star_search(own['Graph'],start,end)         
                
                truePath = reconstruct_path(path[0], start,end)
                index = 0
                #print(truePath)
                # to visualize path since draw line is gone we are using meshes that are 1 unit long
                for point in truePath:
                    if index!=0:
                        added = own.scene.addObject('Line_Tool',own,1)
                        added.worldPosition = own['locations'][point]
                        p2 = own['locations'][truePath[index-1]]
                        v2 = added.getVectTo(p2)
                        added.alignAxisToVect(v2[1],1,1)
                        added.localScale = [1,v2[0],1]
                    index+=1   
                own['requests'][0][2]['path'] = truePath
                own['requests'].pop(0)
                #print('sent')
            else:
                 own['requests'].pop(0)
                     
                
                
main()

blenderaptor · December 15, 2019, 9:14pm

i didn’t really understood what the A* brings in comparison with the one i learnt at university, the good old Dijkstra.

This is what my code does (summary to make it easy to read , though not written with class)

my functions

## the core algo
def dijkstra (start, end, neigbours):
    return path 
## sub -core
def neigbours (s):
    return graph[s]
## simple functon of mine to find the closest checkpoint to a (character)
def closest(character):
    return checkpoint

the graph of checkpoints with a loop to auto-compute the distances (replacing the “0” by a xy distance). For example, “C1” can leads to “C2” and “C0” … So basically, in my game, i just posed 13 box-empties on the map and wrote the graph here below

graph = {
    "C0": [ [0, "C1"] ],
    "C1": [ [0, "C2"], [0, "C0"] ],
    "C2": [ [0, "C3"], [0, "C1"], [0, "C0"] ],   
    "C3": [ [0, "C0"], [0, "C2"], [0, "C1"] , [0, "C4"] ],
    "C4": [ [0, "C5"], [0, "C3"], [0, "C1"], [0, "C0"] ],  
    "C5": [ [0, "C6"], [0, "C8"], [0, "C4"] , [0, "C1"], [0, "C0"] ],
    "C6": [ [0, "C7"], [0, "C5"] ],
    "C7": [ [0, "C9"], [0, "C10"], [0, "C6"] ],
    "C8": [ [0, "C9"], [0, "C5"], [0, "C0"], [0, "C1"] ],
    "C9": [ [0, "C8"], [0, "C7"], [0, "C0"], [0, "C1"] ],
    "C10": [ [0, "C7"], [0, "C11"] ],
    "C11": [ [0, "C12"], [0, "C10"] ],
    "C12": [ [0, "C11"], [0, "C13"] ],
    "C13": [ [0, "C12"] ]     
}

### compute the xy distance for each checkpoint couples
for i in graph.keys() :
    for j in graph[i] :
        j[0] = (scene.objects[i].worldPosition.xy - scene.objects[j[1]].worldPosition.xy).length

in game every 30 frame

npc['end'] = closest(player) 

### check if the npc's closest checkpoint is the same than the player's one
if closest(npc)  == npc['end'] :
     npc['target'] = player    ### go to the player
else :
     npc['target'] = npc['check']    ### keep go to the next checkpoint

### if the npc collides with a checkpoint
if check.status == 1 :

       ### end of the path, the player must be around  
       if check.hitObject.name == npc["end"] : 

      ###  just a checkpoint, but let's recompute the path as the player 
      ###  might have moved since and lets go to the next checkpoint
      elif check.hitObject.name == npc["check"] : 
          checks = dijkstra(npc["check"], npc['end'] ,  neighbours )
          npc['target'] = npc["check"] = checks[1]

      ## you can collide by accideny with a checkpoint not on your current path
      else : 
        print(" meh .. just another checkpoint")

Cotaks · December 15, 2019, 9:29pm

a* is in general a bit faster.

You can build it in many many ways.

here is how i build mine with a spawed tilebased grid:

from bge import logic
import random

def build_grid(cont):
    
    own = cont.owner
    
    grid_size = own['grid_size']
    tile_size = own['tile_size']
    
    number = 0
    nx = 0
    ny = 0
    
    for x in range(grid_size):
        
        nx += 1
        
        for y in range(grid_size):
            
            ny +=1
            number += 1
            
            tile = own.scene.addObject('tile',own,0)
            
            tile.localScale = [tile_size,tile_size,1]    
            tile.color = [random.uniform(0.000,1.0) ,random.uniform(0.000,1.0) ,random.uniform(0.000,1.0) ,1]
            tile['position'] = [nx,ny]
            tile['number'] = number
            tile['neighbors'] = []
            
            tile.children[0]['Text'] = number
            
            own.worldPosition.y += tile_size
            own['grid_list'].append(tile)   
            
        own.worldPosition.x += tile_size 
        own.worldPosition.y = own['start_position_y']
        ny = 0
        
    print('-> grid built')
        
        
def setup_grid(cont):   
  
    own = cont.owner

    if not '__init__' in own:
        
        own['start_position_x'] = own.worldPosition.x
        own['start_position_y'] = own.worldPosition.y
        own['start_position_z'] = own.worldPosition.z
        own['grid_list'] = []
        build_grid(cont)        
        own['__init__'] = True        
        return
    
    elif not 'neighbors' in own:
        
        get_neighbors(cont)
        own['neighbors'] = True

            
def get_neighbors(cont):
    
    own = cont.owner  
    neighbor_check_distance = 2 * own['tile_size']
      
    if own['grid_list']: 
          
        for tile in own['grid_list']: 

            x = tile.worldPosition.x - 1
            x2 = tile.worldPosition.x + 1
            y = tile.worldPosition.y - 1
            y2 = tile.worldPosition.y + 1
            
            ray_1 = tile.rayCast(tile, [x, tile.worldPosition.y,  tile.worldPosition.z] ,neighbor_check_distance)
            ray_2 = tile.rayCast(tile, [x2, tile.worldPosition.y, tile.worldPosition.z] ,neighbor_check_distance) 
            ray_3 = tile.rayCast(tile, [tile.worldPosition.x, y, tile.worldPosition.z] ,neighbor_check_distance) 
            ray_4 = tile.rayCast(tile, [tile.worldPosition.x, y2, tile.worldPosition.z] ,neighbor_check_distance)  

            if ray_1[0]:
                tile['neighbors'].append(ray_1[0])
                
            if ray_2[0]:
                tile['neighbors'].append(ray_2[0])
                
            if ray_3[0]:
                tile['neighbors'].append(ray_3[0])
                
            if ray_4[0]:  
                tile['neighbors'].append(ray_4[0])
                
    own['grid_building_done'] = True
    print('-> neighbors recruted')
       
        
def find_path(cont):  
    
    own = cont.owner
    grid_spawner = own.scene.objects['grid_spawner']
    
    if not own['navpath'] and grid_spawner['grid_building_done']:
        
        if 'path' in own:
            
            for obj in own['path']:
                obj.color = [random.uniform(0.000,1.0) ,random.uniform(0.000,1.0) ,random.uniform(0.000,1.0) ,1]
                
            print('*',own, 'old path cleared')
                
        own['path'] = []
        
        for tile in grid_spawner['grid_list']: 
            
            if tile['number'] == own['start_tile']:
                own['start'] = tile    
                
                if not own['start'] in own['path']:
                    own['path'].append(own['start'])  
                          
            elif tile['number'] == own['end_tile']:
                own['end'] = tile

        for i in range(grid_spawner['grid_size']*2):
            
            if not own['end'] in own['path']:
                
                tiles = []
                dist = []
                
                for neighbor in own['path'][:].pop()['neighbors']: 

                    dist2 = neighbor.getDistanceTo(own['end'])  
                    
                    tiles.append(neighbor)
                    dist.append([dist2])
                       
                dict = {'tiles': tiles, 'distances': dist}    
                
                index_min = min(range(len(dict["distances"])), key=dict["distances"].__getitem__)    
                nearest_point = dict["tiles"][index_min] 
                   
                own['path'].append(nearest_point) 
                 
            else:
                break    
            
        print(own,'-> shortest path calculated')

        for obj in own['path']:
            obj.color = [0,1,0,1]
        
        print('-- path length', len(own['path']), 'tiles')
        own['navpath'] = True

gonna convert it to manual grid and node based when i have time, so i would say if dijkstra works for you then keep using it. unless it’s to heavy.

BluePrintRandom · December 15, 2019, 9:32pm

mine is using some of pythons optimizations, and assumes 1 face = 1 node

and any agent can request a path, (it has a list for multiple objects to ask for a path in 1 frame)

edit: mine uses blender quads / triangles as nodes and each connected face is a link

blenderaptor · December 16, 2019, 3:58am

i would say that my algo works fast since i have only 13 checkpoints ^^ .

But there’s 2 things i will ameliorate :

switch to direct pursuit if the npc can do ( i can use RayCastTo for walls when the map is a single level but dealing with many is more complicated : barriers, borders, stairs ) so i guess i have to create like a stairs like RayCast lol
detect moment when npc is turning around a checkpoint because no more able to be triggered by checkpoint collision ( check.status == 1 ) , so cannot go +1 in the path.

edderkop · December 16, 2019, 1:27pm

here is another way to do it.
this implementation turn every vertex position into an node in a node graph, and it use a dictionary to store the graph.

navmesh.blend (507.3 KB)

the format is
{ Vertex position as key : [list of neighbors] }

{'-0.684:2.879:0.000': ['1.793:4.845:0.000',
                        '0.000:1.000:0.000',
                        '1.879:1.684:0.000'],
 '-2.000:-1.000:0.000': ['0.000:1.000:0.000',
                         '0.000:-1.000:0.000',
                         '-2.000:1.000:0.000'],
 '-2.000:1.000:0.000': ['0.000:1.000:0.000',
                        '0.000:-1.000:0.000',
                        '-2.000:-1.000:0.000'],
 '0.000:-1.000:0.000': ['0.000:1.000:0.000',
                        '3.000:-2.000:0.000',
                        '2.000:1.000:0.000',
                        '-2.000:1.000:0.000',
                        '-2.000:-1.000:0.000'],
 '0.000:1.000:0.000': ['0.000:-1.000:0.000',
                       '3.000:-2.000:0.000',
                       '1.879:1.684:0.000',
                       '2.000:1.000:0.000',
                       '-2.000:1.000:0.000',
                       '1.793:4.845:0.000',
                       '-2.000:-1.000:0.000',
                       '-0.684:2.879:0.000'],
 '1.793:4.845:0.000': ['0.000:1.000:0.000',
                       '-0.684:2.879:0.000',
                       '1.879:1.684:0.000'],
 '1.879:1.684:0.000': ['1.793:4.845:0.000',
                       '0.000:1.000:0.000',
                       '-0.684:2.879:0.000'],
 '2.000:1.000:0.000': ['0.000:1.000:0.000',
                       '3.000:-2.000:0.000',
                       '0.000:-1.000:0.000'],
 '3.000:-2.000:0.000': ['2.000:1.000:0.000',
                        '0.000:1.000:0.000',
                        '0.000:-1.000:0.000']
}

Liebranca · December 17, 2019, 9:19am

Alrighty.

Right now I’m working on a new 3d file format optimized for my engine. Talk about fuuuuuun sheez, but I want to get this part of the job done before it’s holidays and I’m too drunk to do anything.

Tell you what. I’ll get started on it once we’re a few days into january and the town starts sobering up.