Nav Mesh

Hi I hope you are having a good day.

I was hoping someone could explain to me how the nav mesh actuator works under the hood.
I am aware that one is able solve path finding problems using Logic bricks, but I wanted to write my own path finding algorithm or use the already existing principles of the A* algorithm problem is there are still quite a few things I don’t get.
2.To start with How to make a nav mesh manually.
3. Do I need to add way points to the nav mesh.

Thanks. Any Help will be greatly appreciated…

A Nav-Mesh is an helper that is used to create the graph an path finding algorithm can run on. A graph consists of nodes that are connected with other nodes. In Blender a mesh is a pretty good method to define such a graph. All tools to create and manipulate the mesh are available.

If you develop your own implementation, you should transform the mesh to a graph your implementation can work with.

A waypoint is typically a node in your graph. In the nav mesh it is a vertex of the mesh.

I hope this helps a bit.

With Blender’s built in nav meshes, you can find your way from point A to point B. If you want to go via some way points then you need code to switch the target of your navigating actuator on the fly. There are not many cases where a homemade navigation algorithm would be more useful than the Blender implementation. Some I can think of are grid based movement, turn based movement, or games where you have random levels, in that case you can’t pre-build your nav mesh.

There’s a few tutorials on the Blender navmeshes, I went through them myself when it was first introduced as a feature.

if you’d like to know more about pathfinding I’d suggest this link:
http://www.policyalmanac.org/games/aStarTutorial.htm

Thanks a lot everyone I really appreciate the help.

@ Monster
How do I transform the mesh into a graph

Basically, you read vertex/edges from the mesh and create according nodes with their weighted connections.

I know this is pretty high level, but it really depends on the data structure you choose for your graph. If you look for pathfinding algorithms they all come with a specific (data) model they run on. Also following the path requires a different but maybe similar data model (path).

Mesh -> graph for pathfinding -> path to follow -> location to walk to.

@ Monster

Thanks I appreciate the help.

There’s a really big set of resources here:
http://www-cs-students.stanford.edu/~amitp/gameprog.html

If you’re just starting out with pathfinding it should cover nearly everything you need to know. Not many tutorials cover the basics of building a graph though, so here’s how to build a very basic unoptimized graph:

If you want to build a graph you need to think about what the nodes are going to be. In my A* algorithm I tried both classes and dictionaries as nodes.

Dictionary is probably the easiest to work with when starting out:

node = {"xy_id":[],
    "g":0,
    "h":1000,
    "next_to":[],
    "parent":None}

Each node has some attributes. Firstly its [x,y] position in 2d space, this is important because it can be used to identify the position in space of the node at any time. The next two-

  • G = the movement cost to move from the starting point A to a given square on the grid, following the path generated to get there.
  • H = the estimated movement cost to move from that given square on the grid to the final destination, point B. This is often referred to as the heuristic, which can be a bit confusing. The reason why it is called that is because it is a guess. We really don’t know the actual distance until we find the path, because all sorts of things can be in the way (walls, water, etc.).

-are calculated when running your A* algorithm. You can find out more about them in the tutorial.
The next to parameter is the most important bit, this is what changes the graph in to a real graph, without it, you’ve just got a bunch of co-ordinates. The next to list is a list of all the node’s valid neighbors. If you can travel to another node directly from this one, it should go in here.

Parent is used last of all. When doing your A* algorithm you’ll be finding the best square from the list of neighbors. When you’ve got it you can set it’s parent as this node. There are times when you want to change the parent, like when checking if there is a better way to get to this square by going diagonally. When you’ve finished the search and every node in the closed list has been checked you go back from the end square getting the parent of each node above it and making a list of nodes to be followed.

When building a graph you can make a graph class, or a graph dictionary. Dictionary is probably the easiest at first.

just start with:

graph = {}

Then go through the verts in your walk mesh and run a function to create a blank node and put it in the dictionary.

I use a key derived from the xy co-ordinates so I can look up the dictionary entry easily:

key = str(x) + "$" +str(y)

If I later want to break this down to get the co-ordinates from the string I can use the string.split(“$”) operation from python.

Good luck, it took me months to understand pathfinding and I still don’t know well about the various optimizations.

Here are some hints which will save you a lot of time:

  • You have to rebuild your graph every time you run the A*. You can’t reuse an existing graph unless you go through and reset every node. It’s faster just to rebuild the graph. Also things might change in your game, like doors being open and such, so you have to rebuild it anyway.
  • You don’t have to add every single vert to your graph. At most you need a rectangle around your start and finish locations with a border of about 10 squares to cover the possibility of back tracking. Cropping your graph like this will increase the speed a lot, especially when dealing with movement across a small distance.
  • Investigate other pathfinding options. A simple ray casting check from A to B before running A* will tell you if you can walk to the target without calculating a complex path. If so, you don’t need to run A* and you just saved a huge amount of processing time.
  • Find a way of visualizing the various elements returned by your A* algorithm. I use a simple script to place and erase colored cubes to show the route, open and closed lists. This will help you to know where you’re going wrong in real time as you run the pathfinder.

Here’s an example of that in action:

You can use something like this:

def icons_clear(property,scene):
   
    ob_list = scene.objects
    
    for ob in ob_list:
        if ob.get(prop,False):
            ob.endObject()    

To clear away the last result and then:

def debug_path_lists(own,a_star,scene):
        
    if a_star["path"] != []: 
        for sq in a_star["path"]:
            tile = sq.split("$")   
                     
            pos = [int(tile[0]),int(tile[1]),0.1]                         
            tile = scene.addObject("node_green",own,0)
            tile.worldPosition = pos

    if a_star["open_list"] != []: 
        for sq in a_star["open_list"]:
            tile = sq.split("$")   
                     
            pos = [int(tile[0]),int(tile[1]),0.1]                         
            tile = scene.addObject("node_blue",own,0)
            tile.worldPosition = pos

    if a_star["closed_list"] !=[]:  
        for sq in a_star["closed_list"]:
            tile = sq.split("$")   
                     
            pos = [int(tile[0]),int(tile[1]),0.1]                          
            tile = scene.addObject("node_red",own,0)
            tile.worldPosition = pos    

To place cubes representing the A* path, open list and closed list.

@ Smoking_Mirror
@ agoose77

Thanks I really appreciate the help.
Off to process and make use of the data.

Hi I Hope you are Having a good day.

I have come up with a path finding system which seems to be working though there’s still some testing to be done.
However I can’t get my character to follow the calculated Path.
The waypoints to be followed are put into a sorted List which makes sure that the
waypoints are in the order in which they must be followed.

I tried to make the character follow the path using the following code

 DoneWith = []        
    if DestinationReached == False:            
        while Destination not in DoneWith: 
                T = SortedPathList[0]            
                if T.position[0] > seeker.position[0]:
                    seeker.position[0] += 0.05
                if T.position[0] < seeker.position[0]:
                    seeker.position[0] -= 0.05       
                if T.position[1] > seeker.position[1]:
                    seeker.position[1] += 0.05
                if T.position[1] < seeker.position[1]:
                    seeker.position[1] -= 0.05
                DoneWith.append(T)    
                SortedPathList.remove(T)    
                print(SortedPathList) 
                if seeker.position[0] == Destination.position[0] and seeker.position[1] == Destination.position[1]:
                    DestinationReached = True


and the Following


 if DestinationReached == False:       
        for n in SortedPathList:                
                if n.position[0] > seeker.position[0]:
                    seeker.position[0] += 0.05
                if n.position[0] < seeker.position[0]:
                    seeker.position[0] -= 0.05       
                if n.position[1] > seeker.position[1]:
                    seeker.position[1] += 0.05
                if n.position[1] < seeker.position[1]:
                    seeker.position[1] -= 0.05
                  
    if seeker.position[0] == Destination.position[0] and seeker.position[1] == Destination.position[1]:
        DestinationReached = True   

Neither of the above peices worked. The character just stops at the second waypoint.
I was hoping someone could provide a better solution or point me in the right direction

Thanks. Any Help and Solutions will be greatly appreciated.

Some code-style:

There’s no need to check if something == False. In Python, the if statement checks for Boolean truth, and the True / False values are the base types for this.

(I.e, if 1, if True, if “ah”, if [8]) (sequences are considered boolean True if they have members).

So, instead of “if x==False”, you can write “if not x”.

Try and use PEP8 style conventions - meaning names_with_underscores instead of CamelCaseNames for instance variables. Class names (not class instances) can be CamelCase, and should be written as such.

Functional changes:
Don’t use n.position. The position attribute is different depending upon whether you read or write it. This is not good for consistency. You probably want .worldPosition.

Better to explicitly write .worldPosition.x rather than .worldPosition[0], though this is more of a personal opinion.

You’re iterating over all the points in the path, rather than the nearest point to the player.
Using trackTo would be much more sensible, alongside AlignAxisToVect.

Your character is walking on a raster of .05. be aware that the number precision might invalidate “…position[0]== …position[0]”.

So you need to ensure your “destination reached” processing us correct.

In general your first path following algorithm is fine. Btw. I would check the completion conditions first, just in case the character is already there. DoneWith is not necessary. What is dump? Why you grab the next waypoint twice?

Your second algorithm moves through all waypoints in one frame. I do not think that is what you wamt. There is no visible relation between n, seeker.position and Destination.position. Just now it looks like this:
A) destination reached? yes -> done, no -> B)
B) run around
C) seeker at destination? Yes -> done, no -> done

Hints:
“if booleanValue == False:” is double code better use “if not booleanValue:”
If you use uppercase varianle names it is better to use this convention for all variable names. Otherwise a reader is asking why it is different.

Hi there everyone

@agoose77
My apologies regarding my code-style I also program in Delphi
and C# where underscore variable names are not a norm.
Using trackTo might be a good solution but I am trying to keep the code as universal as possible
i.e. less dependent on blender specific tools.
Thanks for the Help and Advice I really appreciate it.

@Monster
I changed dump to “DoneWith” I must have forgot to retype on that particular line.
Destination is the goal waypoint i.e. the last waypoint in the SortedList.
Thanks for the Help and Hints I really appreciate it.

I have edited the code to reflect the changes I have made.
May someone please take a look.

You’re using a while statement, which suspends the execution of one frame, until the loop breaks. This means you will not see any visual changes during successive executions of the loop body.

You should start by writing out the tasks into separate functions.


from bge import logic


path = []
path.reverse()


def move_along_path(player, path):
    if not path:
        return
    
    closest_approach = player.get("closest_approach", 1.0)
    speed = player.get("speed", 1.0)


    target = path[0]
    displacement_to_target = (target.worldPosition - player.worldPosition)
    
    if displacement_to_target.length <= closest_approach:
        path.pop()        
        move_along_path(player, path)
    
    else:
        velocity = displacement_to_target.normalized() * speed / logic.getLogicTicRate()
        player.worldLinearVelocity = velocity

In this example, the path is assumed to be ordered in terms of start to finish, and I reverse it so we can use pop() without using popleft() from collections.deque.

It’s not sensible to avoid using Blender tools that consist of the API because unless you intend upon writing an entire math library, there is still a certain amount of API-specific code you must write anyway. It does indeed make sense to avoid depending upon Blender for such things, but simply writing a function that abstracts the implementation and can be later redefined is sensible. Even write a wrapper for KX_GameObject if you so wish to provide a common interface,.

I don’t know if my example code would work, as I haven’t tested it, and some variables would need redefining.

I still think it is your check to determine if the character reaches the waypoint. I suggest you print it both to console: current position, waypoint position.

The follower code iterates over all waypoints, which is not the intended behaviour - future waypoints are not important until they are reached.
In addition checking if positions are equal is not good practice, and if it does work, it doesn’t reflect the physical nature of things - a good enough approximation is fine.

Hi I Hope you are having a good day.

@agoose77
Thanks for the code and all I really appreciate it. Unfortunately for me it did not work.

@Monster
I 'm not quite sure what you are getting at, but if you mean the object is moving and leaving the
physical representation behind I checked and that is not the case.
Thanks for the Help I really appreciate it.

Here is a simplified version of the blend file.
If someone could kindly apply the fix and repost it,
That would be really great.

Thanks. Any Help and Solutions will be greatly appreciated.
P.S I read PEP8 style and I 'm reading it again but it just won’t stick.

Attachments

FollowPath.zip (271 KB)

If you think of the path as just a list of destinations, each time you reach the next destination you should tick it off your list and start on towards the next. You always have your list with you, with each destination already crossed off.

For the follow path code, you just have to move towards the nearest destination while orientating the player towards the goal.

Here’s an implementation using getVectTo() and [alignObjectToVect()

path_following.blend (504 KB)](http://bgepython.tutorialsforblender3d.com/GameObject/alignAxisToVect)

Just imagine that the path is longer than two parts.

You can use get_vectTo with a point in space instead of an object, so you don’t need objects to represent your path.
I’d suggest modifying the example to use a list of points rather than objects at first, from there you should be able to get it to work with your own pathfinding implementation. In the example I’ve used an index to advance along the list, but you can pop() the entries as the other guys suggested, reducing the list until it is empty. I find it useful to keep the list intact for things like adding tank tracks or footprints or for orienting the player to walk backwards along the line or having other characters follow along the same path or whatever. But most people just pop() the list so that it is gradually erased.

My example didn’t work because, as I said, it’s a template, but not a complete script.

The short hand reason that your code doesn’t work is that it tries to perform the navigation in one frame. In the BGE, one frame represents a fraction of a second (1 / logic tick rate) which might be 16ms for 60 fps. Whatever code you write must take this into account, and support execution for each frame.

In addition to this, your script attempts to move to the target incrementally. This isn’t safe when checking equalities (https://docs.python.org/3.1/tutorial/floatingpoint.html) between floats. It also would look strange, as any angled path would involve the seeker moving at 45 degrees and then solely along one axis. Better to find the direction vector between the current position and the target, and applying that (dir.normalized() * speed)

That part works though:

displacement_to_target = (target.worldPosition - player.worldPosition)

Very nice and simple. There’s no need to use getVectTo unless you want a local vector.

(I’ve had problems before using vectors to move my characters though, take a look at this video to see what I mean. Hopefully you can avoid similar problems.)

This code is very nice too:

speed = player.get("speed", 1.0)

That’s a good way of getting object properties, as it supplies a fall back value and won’t return an error if for some reason the player doesn’t have the right property. i usually use .get() when getting objects from a scene or other list, but other wise I’ve always used:

speed = player['speed']

BTW, which is preferred for getting properties or dictionary keys, single quotation marks or double ones. I try to use single ones most of the time, but I often forget.

Hi I Hope you are having a good day.

@Smoking_mirror
Thanks for taking the time to put the blend file together I really appreciate it.
I will be honest and say it, I know very little about Vector, Quaternion and Matrix mathematics.
So as you might imagine I find parts of your script somewhat confusing.
I know a lot of questions can be annoying and I apologise for asking yet another.
You used a current_node property in you script which works well but I tried using a current_node variable to do the same job and it did not work.
The seeker(red arrow) stopped at the first node.

  1. Why is that?

@agoose77
I 'm aware it’s a template.
Thanks for the advice I 'm learning a lot of useful things I hope to put to good use.

Thanks everyone I really appreciate everything.
Your help has been is literally priceless.