Hi this is my current pathfind attempt using a navmesh. It’s very early stages at the minute so appologies for messy code. I will clean up in the future. Next thing on the list of things to do is path smoothing but part of that isn’t working so I attached this version instead. It uses Chasers mousescript and his object set up, basicly because I was comparing speeds.


navigationTest2.blend (309 KB)

I had to change the directory references in ur scripts to get it to work, it works OK, it just that the guy seems to like going longer ways than needed

That’s mainly down to the fact that it navigates to center points of edges, I’m working on this just not right now cause I’m a little busy getting ready to go to uni. I really only posted at this stage because andrew 101 is doing a simaler thing and I thought he might be interested.

Hey, thanks for the help with cPickle, I haven’t tried importing the classes yet though but it sounds promising.

Your pathfinding does some weird stuff, I sent the bot up to the top of the map, then clicked the top again and started going to the bottom.

I’ll ask you some questions rather than trawl through your code :stuck_out_tongue:

How do you determine if a point is inside a poly? For instance, how do you know which poly the player starts in?

Did you do any smoothing to the path? As in, when you first run the pathfinding, it will return the nodes as the centers of the faces/edges, did you then move those nodes to make the path even shorter?

Do you export the navmesh at runtime everytime?

The first question I already have a solution to, but it looks like it could get cpu heavy really quickly. To combat this I added a pathfinding controller, which you register all paths through, like this:

import Pathfinding

GameLogic.pfController = Pathfinding.createController(30)

path = GameLogic.pfController.newPath(start, end, navmesh=default, priority=False)

The controller will only process so many paths per frame, thats what the 30 means. It doesn’t mean 30 paths though, it means 30 points. Each navmesh has an attribute for how many points 1 unit is equal to (lets say 0.2), when each path is initialised it finds the distance from the start to the end and multiplies this by 0.2 and thats how many points get used when the path is calculated.

You can specify if the path is a priority (priority=True) which means it will be processed before non priority paths, even if they were added before the priority path.

You can also force the path to be processed for really important paths with:


You don’t need to use a controller, but if you have alot of paths (RTS comes to mind) then it would be helpful.

I’ll post mine up here when I finish it, maybe today, the cPickle thing was really getting annoying.

1: For determining which polygon I’m in I first get the nearest polygon and draw a line from the player or cursor to the polygon. Then i check where this line intersects with a line along the edges of this polygon, if the intersect is between the verts that mak up the edge the player/cursor can’t be in the polygon. Then I check the next one. (Note this doesn’t work well with the bridge yet as i’m currently ignoring it’s z location. I will change this in the future.
I also try to keep track of which node it’s on after the initial start by changing it’s node when it hits an edge polygon. This can and does fail when trying to go on the bridge as my player falls off because of the physics.

2: No there is currently no smoothing, I have a different version where I’m trying to make it work but it’s acting weirdly.
The smoothing I’m currently trying to implement looks at which portals (the edge points) in the portal Path can be removed i.e going straight from one to another crosses no wall (edge with one face.)
In this way some diagonals accross faces will be produced.

3: The navmesh is a very simple list of node classes which correspond to a face with as much precomputed data held as I felt I could get away with. My original intention was for all of the data to be imported but, the classes need rebuilding at runtime. Only once though.
I know what you mean about the cPickle thing being annoying, it caught me out for ages.
P.S. The weird behaviour, is it when coming from above the part of the map with the c shap obsticle to the oppisite side along the y axis because I’ve had problems there but I couldn’t figure what was wrong with it except that subdividing the square in the start corner appears to fix it.

I look forward to seeing yours. “GameLogic.pfController.forceProcess(path)” This sounds handy.

I am still having problems with cPickle, I can un pickle the navmesh out side of blender but when I copy the exact same code into blender and run it, error. I can print Edge, which gives me the expected output of Pathfinding.Navmesh.Edge, but then cPickle goes: ‘module’ object has no attribute Edge. This is driving me nuts! For some reason cPickle isn’t working in blender.

I’ll share some code I found for checking a point in a poly:

def point_inside_polygon(x,y,poly):
    n = len(poly)
    inside =False

    p1x,p1y = poly[0]
    for i in range(n+1):
        p2x,p2y = poly[i % n]
        if y > min(p1y,p2y):
            if y <= max(p1y,p2y):
                if x <= max(p1x,p2x):
                    if p1y != p2y:
                        xinters = (y-p1y)*(p2x-p1x)/(p2y-p1y)+p1x
                    if p1x == p2x or x <= xinters:
                        inside = not inside
        p1x,p1y = p2x,p2y

    return inside

I don’t know why but this never actually works for polygons, only for triangles. (The poly parameter should be a list of points: [ (x1, y1), (x2, y2) , (x3, y3) ])

I also don’t have support for z position on navmeshes yet, but it should be hard. If multiple polys get returned just pick the closest based on z position. Also, you need to add a property to each poly about z clearance, that will probably be really tedious.

I’m sorry to hear you can’t get cPickle working and I don’t think I can help any more, I’m no python guru.
I’l show you what works for me.
In my create Navmesh module

import cPickle as p
nodeList = []
# here I create my node instances and append each one to nodeList
cPath = 'C:/Users/Reuben/Documents/nodes.obj'
nodeFile = file(cPath, 'w')
p.dump(nodeList, nodeFile)

In my navigator module

import cPickle as p
con = gl.getCurrentController()

navigator = con.owner # self object I'm just using it to hold the start property for convenience

start = navigator["start"] # starts as 0 so the following executes once

if start == 1:     # had to use this to prevent node names changing, i.e. it would reload the same nodes but because they aren't named objects just a list of instances the name would change which screwed things up later.

    from CreateNavMesh import Node
    cPath = 'C:/Users/'     # Where I saved it
    f = file(cPath)
    A.nodeList = p.load(f) # I save my nodes here so I don't lose them between logic ticks
    navigator["start"] = 0

Yea, I guess the only person who would have a solve would be someone who knows how the inside of blender runs. I’ll recode my converter and exporter. Maybe that will help.