CodeIain

navigation mesh and infinity terrain

10 posts in this topic

Yo @Codelain ... (Why doesn't show name for tagging... strange)

I don't know about infinite terrain, but i use babylon-navigation-mesh as a part of the U3D - BabylonJS Toolkit.

First... I generate navigation meshes from unity (using the Unity Navigation System)

Second... When parsing the scene meshes, i look for navmesh and build zones:

 this._navmesh = this._scene.getMeshByName("sceneNavigationMesh");
                    if (this._navmesh != null) {
                        var navigation: Navigation = this.getNavigationTool();
                        var zoneNodes: any = navigation.buildNodes(this._navmesh);
                        if (zoneNodes != null) {
                            navigation.setZoneData(this.getNavigationZone(), zoneNodes);
                        } else {
                            BABYLON.Tools.Warn("Failed to set scene navigation zone");
                        }
                    } else {
                        BABYLON.Tools.Warn("Failed to load scene navigation mesh(s)");
                    }

 

I am working on a light-weight client side navigation api:

 

       // *********************************** //
        // *  Scene Navigation Mesh Support  * //
        // *********************************** //

        public hasNavigationMesh(): boolean {
            return (this._navmesh != null);
        }
        public setNavigationMesh(mesh: BABYLON.AbstractMesh): void {
            this._navmesh = mesh;
        }
        public getNavigationMesh(): BABYLON.AbstractMesh {
            return this._navmesh;
        }
        public getNavigationTool(): Navigation {
            // Babylon Navigation Mesh Tool
            // https://github.com/wanadev/babylon-navigation-mesh
            if (this._navigation == null) {
                this._navigation = new Navigation();
            }
            return this._navigation;
        }
        public getNavigationZone(): string {
            return "scene";
        }
        public getNavigationPath(agent: BABYLON.AbstractMesh, destination: BABYLON.Vector3): BABYLON.Vector3[] {
            if (this._navigation == null || this._navmesh == null) return null;
            var zone: string = this.getNavigationZone();
            var group: number = this._navigation.getGroup(zone, agent.position);
            return this._navigation.findPath(agent.position, destination, zone, group);
        }
        public setNavigationPath(agent: BABYLON.AbstractMesh, path: BABYLON.Vector3[], speed?: number, loop?: boolean, callback?: () => void): void {
            if (path && path.length > 0) {
                var length = 0;
                var direction = [{
                    frame: 0,
                    value: agent.position
                }];
                for (var i = 0; i < path.length; i++) {
                    length += BABYLON.Vector3.Distance(direction[i].value, path[i]);
                    direction.push({
                        frame: length,
                        value: path[i]
                    });
                }
                var move: BABYLON.Animation = new BABYLON.Animation("Move", "position", 3, BABYLON.Animation.ANIMATIONTYPE_VECTOR3, BABYLON.Animation.ANIMATIONLOOPMODE_CONSTANT);
                move.setKeys(direction);
                agent.animations.push(move);
                this._scene.beginAnimation(agent, 0, length, loop, speed, callback);
            }
        }
        public getNavigationAgent(agent: BABYLON.AbstractMesh): BABYLON.NavigationAgent {
            return new BABYLON.NavigationAgent(agent);
        }
        public getNavigationAgents(): BABYLON.Mesh[] {
            return this._scene.getMeshesByTags("[NAVAGENT]");
        }
        public getNavigationAreaTable(): BABYLON.INavigationArea[] {
            return (this._navmesh.metadata != null && this._navmesh.metadata.properties != null && this._navmesh.metadata.properties.table != null) ? this._navmesh.metadata.properties.table : [];
        }
        public getNavigationAreaIndexes(): number[] {
            return (this._navmesh.metadata != null && this._navmesh.metadata.properties != null && this._navmesh.metadata.properties.areas != null) ? this._navmesh.metadata.properties.areas : [];
        }
        public getNavigationAreaName(index: number): string {
            var result: string = "";
            if (this._navmesh.metadata != null && this._navmesh.metadata.properties != null && this._navmesh.metadata.properties.table != null) {
                var areaTable: BABYLON.INavigationArea[] = this._navmesh.metadata.properties.table;
                if (areaTable != null) {
                    for (var ii: number = 0; ii < areaTable.length; ii++) {
                        if (areaTable[ii].index === index) {
                            result = areaTable[ii].area;
                            break;
                        }
                    }
                }
            }
            return result;
        }
        public getNavigationAreaCost(index: number): number {
            var result: number = -1;
            if (this._navmesh.metadata != null && this._navmesh.metadata.properties != null) {
                var areaTable: INavigationArea[] = this._navmesh.metadata.properties.table;
                if (areaTable != null) {
                    for (var ii: number = 0; ii < areaTable.length; ii++) {
                        if (areaTable[ii].index === index) {
                            result = areaTable[ii].cost;
                            break;
                        }
                    }
                }
            }
            return result;
        }

 

To use in a scene, example from nav mesh demo:

                // Create navigation box avatar
                var minimoi = BABYLON.Mesh.CreateBox("Me", 0.5, this.scene);
                minimoi.material = new BABYLON.StandardMaterial("navMaterial", this.scene);
                (<BABYLON.StandardMaterial>minimoi.material).diffuseColor = new BABYLON.Color3(1., 0., 0);
                minimoi.position = new BABYLON.Vector3( -3.7426157086231813, 0.32968033243017736, -5.410392414960055);

                // Setup point and click demo navigation
                var canvas = document.getElementById("cvs");
                canvas.addEventListener('click', (evt)=> {
                    var pickingInfo = this.scene.pick(this.scene.pointerX, this.scene.pointerY);
                    if (pickingInfo.hit) {
                        var path = this.manager.getNavigationPath(minimoi, pickingInfo.pickedPoint);
                        if (path != null) {
                            this.manager.setNavigationPath(minimoi, path, 2.0);
                        }
                    }
                });

 

The key .. super easy to use functions are ...

manager.getNavigationPath(agent:Mesh, destination:Vector3): Vector3[]

and 

manager.setNavigationPath(agent:Mesh, path:Vector3[], speed?:number = 1.0):void

These wraps up a lot of functionality to basically get the path... Once you have paths you can alter/recalc new paths or whatever you want to make sure those are the paths, if any you want (might have some obstacle avoiding and path checking ... stuff like that). Then you call setNavigationPath to move the agent along a path (this is optional, you can move your agent however you want to follow your calculated paths)

If you need more detail, i can make a small demo so you can see it action... Let me know :)

 

Share this post


Link to post
Share on other sites

@MackeyK24 

 

Thanks for this a demo would be great. 

Will this work with any mesh or does it need to be exported as a Navigation Mesh? if so is there any way to convert a mesh to a navigation mesh via code?

 

Regards

Iain 

Share this post


Link to post
Share on other sites
1 minute ago, CodeIain said:

@MackeyK24 

 

Thanks for this a demo would be great. 

Will this work with any mesh or does it need to be exported as a Navigation Mesh? if so is there any way to convert a mesh to a navigation mesh via code?

 

Regards

Iain 

It need to be a REALLY simplified mesh... with all your "WALKABLE" and "NON-WALKABLE" areas defined... So i just don't how you would do that during runtime with infinite terrain... BUT thats not to say you can't... I just don't know how... Also i think you can generate or make your nav mesh even in blender... I have seen a demo level.blend with a level mesh and a navmesh in the same blender file.

Ill make a video showing my navigation mesh implementation :)

 

Share this post


Link to post
Share on other sites
2 hours ago, CodeIain said:

@MackeyK24 

 

Thanks for this a demo would be great. 

Will this work with any mesh or does it need to be exported as a Navigation Mesh? if so is there any way to convert a mesh to a navigation mesh via code?

 

Regards

Iain 

 

U3D - BabylonJS Toolkit using Babylon-Navigation-Mesh Extension

@wanadev

Wanadev 

Check out the current implication of navigation meshes and path finding: http://mackey.cloud/files/videos/u3dnavigation.mp4

Share this post


Link to post
Share on other sites

@MackeyK24 i've been trying to use the navMesh for enemy AI to move by themselves, it's not working unless i use pickingInfo:(

Share this post


Link to post
Share on other sites
21 hours ago, hunts said:

@MackeyK24 i've been trying to use the navMesh for enemy AI to move by themselves, it's not working unless i use pickingInfo:(

Thats probably because the picking info (and hitting close to the navmesh) is giving you a point on the navmesh...

Meaning... It checks for vector.y in acceptable range and the point is within 'polygon vertices'... Look at this code from Navigation-Mesh:

First the 'findPath' calls '_isVectorInPolygon' which in turn calls '_isPointInPoly'

  _isPointInPoly: function _isPointInPoly(poly, pt) {
    for (var c = false, i = -1, l = poly.length, j = l - 1; ++i < l; j = i) {
      (poly[i].z <= pt.z && pt.z < poly[j].z || poly[j].z <= pt.z && pt.z < poly[i].z) && pt.x < (poly[j].x - poly[i].x) * (pt.z - poly[i].z) / (poly[j].z - poly[i].z) + poly[i].x && (c = !c);
    }return c;
  },

  _isVectorInPolygon: function _isVectorInPolygon(vector, polygon, vertices) {

    // reference point will be the centroid of the polygon
    // We need to rotate the vector as well as all the points which the polygon uses
    var lowestPoint = 100000;
    var highestPoint = -100000;

    var polygonVertices = [];

    _.each(polygon.vertexIds, function (vId) {
      var point = this.getVectorFrom(vertices, vId);
      lowestPoint = Math.min(point.y, lowestPoint);
      highestPoint = Math.max(point.y, highestPoint);
      polygonVertices.push(point);
    }.bind(this));

    if (vector.y < highestPoint + 0.5 && vector.y > lowestPoint - 0.5 && this._isPointInPoly(polygonVertices, vector)) {
      return true;
    }
    return false;
  },

 

So apparently , the target point 'needs' to be point on nav mesh... or real close to it. I am going try some different 'Ray' casting from the target agent position... ray case downward to 'predicate' navmesh to get picking info that way... See if that works :)

 

hunts likes this

Share this post


Link to post
Share on other sites

Yo @hunts Found the issue... You need to give a target position 'ON' the navigation mesh... (basically it has to fall within the 'poly' checking of the findPath function)...

 

This is how i addressed the issue. I added another 'navigation' function to my API:

        public getNavigationPoint(position:BABYLON.Vector3, length:number = Number.MAX_VALUE): BABYLON.Vector3 {
            if (this._navmesh == null || position == null) return null;
            var len = (length > 100) ? length : 100;
            var pos = new BABYLON.Vector3(position.x, (position.y + 1.0), position.z);
            var ray = new BABYLON.Ray(position, new BABYLON.Vector3(0.0, -1.0, 0.0), (len + 1.0));
            var info = this._scene.pickWithRay(ray, (mesh) => { return (mesh === this._navmesh); });
            return (info.hit && info.pickedPoint) ? info.pickedPoint : null;
        }

 

and you can use like this:

 

                    var navpoint = this.manager.getNavigationPoint(cube.position);
                    if (navpoint) {
                        var path = this.manager.getNavigationPath(minimoi, navpoint);
                        if (path != null) {
                            this.manager.setNavigationPath(minimoi, path, 4.0);
                        }
                    }

 

Hope that helps you :)

 

BTW... I am VERY curious in seeing what your AI code looks like... I wrote the system to be able to easily use the navigation system, but i have never seen what babylon js AI code like... Can you show me that... Please :)

 

hunts likes this

Share this post


Link to post
Share on other sites

Yo @hunts

UPDATE: You DONT have to raycast

You can if you CANT place your "WAYPOINT" or "TARGET" position "ON" or "REALLY" close to the navmesh mesh.

You can use a function like the getNavigationPoint to BE EXACT and get the specific point on the navmesh relative to the agent position (that uses a the ray cast to get exact point directly UNDERNEATH the agent position). Works great if way points are ABOVE the mesh TOO far for the normal agent position to 'HIT' on.  BUT IF YOU PUT LIKE A WAYPOINT game object at Y position 0 - 0.5 from the navmesh... that should hit too... i am using simple spheres as waypoints around the terrain and just making sure the position is "WITHIN" OR "TOUCHING" the navmesh... Working great and don't have to ray cast UNLESS i really need too :)

 

hunts likes this

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now

  • Recently Browsing   0 members

    No registered users viewing this page.