About Store Forum Documentation Contact



Post Reply 
Issues with Path-finding and Object Avoidance
Author Message
dylantan Offline
Member

Post: #1
Issues with Path-finding and Object Avoidance
We are having a few issues that we couldn't solve properly for the past 6 months. Granted we have lack of experience and knowledge to solve these issues, and sorry to say we are at our limit. Therefore we love to hear from the community about the following issues and what would be the best way to go about it: (FYI, we are using EE 1.0)

1. Object Avoidance. For some strange reason, we couldn't get the NPC to either:
- avoid each other. This mostly occur if the roaming NPC meet with a standing NPC (not moving) ones.
- avoid smaller or short props. This happen if there an object infront but are of shorter props (such as fences or boxes)
- avoid Wall in Dungeon/Caves. This is another strange occurrence. The NPC/Monster will continue to walk against the wall and continue walking while stuck at the front of the wall. We set the Dungeon/Caves as Terrain. Is there anyway we could resolve this?

2. NPC Roaming.
- We tried various way to make them roam only to certain designated area by assigning a waypoint but that too didn't work. And the NPC keep roaming away from it. Is there better method to assign NPC that roams to only certain path?

3. Monster/Enemies Roaming. This is another headache. The Monsters roam almost everywhere. We want to set the monsters only roam within the spawn area radius. Say 10-20 meter max from where they spawn. Is there better method we could do this?

4. NPC/Main Char unable to go straight from Point A to B even in relatively short distance. The problem is when the characters are trying to perform or get from point A to B (which is a straight line), but they will get confused and unable to find the location (i.e. Point B) hence the character will start walking in circle around until it reach to point B. There is nothing wrong with the path, and the pathmesh is created nicely in and by EE.

The following is our code, and we couldn't find better solution. Is there something with our code or is our approach to the above issues wrong? We love to hear what you think and what's the best way to resolve these issues Any tips/advice would be highly appreciate and thank you in advance.

Code:
void DummyChr::findPath(){
    //paths are set on stack basis. main destination being the last path node
    //new positions are created in order to avoid the obstacle and added to the stack
    //characters will access the path stack and move accordingly
    
    //find the obstacles
    //set elongated box in front of characters to detect the objects ahead
    //press '.' to view the box
    obstacleDetector.setBox(matrix());
    //check for objects
    UInt actor_groups=AG_CONTROLLER;
    
    struct PathBlockCutsCallback : PhysCutsCallback{
        Bool  cuts;
        DummyChr  *caster;

        Bool hit(ActorInfo &actor_info){
            //if the obstacle object is not one of its target objects, avoid
            if(actor_info.obj!=caster){
                if(actor_info.obj!=&caster->targetNpc() &&
                    actor_info.obj!=&caster->targetParty() &&
                    actor_info.obj!=&caster->targetChest() &&
                    actor_info.obj!=&caster->targetEnemy())
                    {
                    //check if obstacle detection is necessary.
                    Vec start=caster->ctrlPos()+Vec(0,1,0), // starting position of ray
                        end=caster->targetPos.first()+Vec(0,1,0); // ending   position of ray
                    PhysHit phys_hit; // phys-hit object for receiving hit parameters if any
                    UInt actor_groups=AG_CONTROLLER;
                    if(Physics.ray(start,end-start,&phys_hit,actor_groups))
                        {
                        //check if targetposition is closer than obstacle position
                        if(Dist(actor_info.obj->pos(),caster->pos())>Dist(caster->targetPos.first(),caster->pos())) return false;
                        //avoidance is based on rotation of the mover.
                        //a new point will be calculated based on the rotation amount and new point distance
                        Flt rotateAngle=Dist(actor_info.obj->pos(),caster->pos());
                        //nearer the obstacle rotation of the mover should be high while rotated distance should be less
                        Vec newTarget=RotatePoint(caster->matrix(),15-rotateAngle,rotateAngle+1);
                        //add the new target position to the stack
                        caster->targetPos.add(newTarget);
                        caster->actionMoveTo(caster->targetPos.last());
                        caster->blockingObj=CAST(DummyChr,actor_info.obj);
                        cuts=true;

                        caster->state=STATE_AVOIDING_OBSTACLE;
                        }
                    return false; // no need for further checking
                    }
                }
            return true; // check further
            }

        PathBlockCutsCallback(DummyChr *caster){
            T.cuts  =false;
            T.caster=caster;
            }
        };

    // check for collision
    if(action){
        PathBlockCutsCallback pcc(&T);
        Physics.cuts(obstacleDetector.ob,pcc,actor_groups);
        //if no longer obstacle in path move to initial target pos
        if(!pcc.cuts){
            Vec t=targetPos.first();
            actionMoveTo(t);
            }
        }
    //ray testing for walls
    if(targetPos.elms()){
        PhysHit phys_hit; // phys-hit object for receiving hit parameters if any
        Vec start=ctrlPos()+Vec(0,1,0),
            end=matrix().z*100;
        UInt actor_groups=AG_TERRAIN;
        if(Physics.ray(start,end-start,&phys_hit,actor_groups))if(phys_hit.group==AG_TERRAIN){
            Flt dt=Dist(targetPos.first(),ctrlPos());
            Flt dp=Dist(phys_hit.plane.pos,ctrlPos());
            if(dt>dp){
                //Vec newTarget=RotatePoint(matrix(),15,5);
                //targetPos.add(newTarget);
                //actionMoveTo(targetPos.last());
                }
            }
        }
    //if not moving and not reached destination while destination still valid, move to destination position
    if(!action && targetPos.elms()){
        Vec t=targetPos.first();
        Flt d=Dist(t,pos());
        if(Abs(d)>ctrl.radius()){
            actionMoveTo(t);
            }
        else targetPos.clear();
        }
    //if moving, and reached destination, clear the path stack and stop
    else if(targetPos.elms()){
        Vec t=targetPos.first();
        Flt d=Dist(t,pos());
        if(Abs(d)<ctrl.radius()*1.1f) {actionBreak();targetPos.clear();}
        }
    }
(This post was last modified: 11-10-2013 07:16 AM by dylantan.)
11-10-2013 07:09 AM
Visit this user's website Find all posts by this user Quote this message in a reply
Pixel Perfect Offline
Member

Post: #2
RE: Issues with Path-finding and Object Avoidance
Ok, Ill have a go at this although I have no experience of working with Esenthel Path Finding as I'm using an alternative system.

(11-10-2013 07:09 AM)dylantan Wrote:  1. Object Avoidance. For some strange reason, we couldn't get the NPC to either:
- avoid each other. This mostly occur if the roaming NPC meet with a standing NPC (not moving) ones.
- avoid smaller or short props. This happen if there an object infront but are of shorter props (such as fences or boxes)
- avoid Wall in Dungeon/Caves. This is another strange occurrence. The NPC/Monster will continue to walk against the wall and continue walking while stuck at the front of the wall. We set the Dungeon/Caves as Terrain. Is there anyway we could resolve this?

I don't think Esenthel Engine includes an inherent steering system like Mikko Mononen's Detour so in the absence of that you'll need to develop your own. The inbuilt Recast navigation mesh system should avoid all static obstacles which just leaves you to deal with the dynamic ones.

In its simplest form this would involve some sort of real time obstacle detection as your NPCs execute their paths produced by the path finding system. If the obstacles are dynamic but not moving at the time (say a moved crate for example or a fallen rock) then once detected one would normally just instigate an avoidance path to the side of the object and then re-path find. If the obstacle is dynamic and moving too then things get a little more complex and you need to take both motions into account. A simple solution might be to apply a braking mechanism where one simple waits for the other to pass and then resumes its original path. There are many many ways of achieving these goals but all with their own advantages and disadvantages.

I seem to recollect someone saying there is an example of a simple steering system in one of the available Esenthel Game Sources (not sure which) so might be worth checking those out.

Not sure what's going on in your Dungeons/Caves but its always best to anticipate problems in any steering system and correct for them if possible. Where an NPC is effectively blocked from moving but clearly has not reached its destination try abandoning that path move after a period of time and re-path find again. Always log these issues though so its visible; as its better to find the route cause than mask them.

(11-10-2013 07:09 AM)dylantan Wrote:  2. NPC Roaming.
- We tried various way to make them roam only to certain designated area by assigning a waypoint but that too didn't work. And the NPC keep roaming away from it. Is there better method to assign NPC that roams to only certain path?

Not exactly sure what you are meaning here, roaming normally means moving in a random type motion so roaming to only a certain path seems at odds with this?

If you are meaning movements like a patrol path then this is normally achieved by making the NPC path find through a series of designated waypoints.

(11-10-2013 07:09 AM)dylantan Wrote:  3. Monster/Enemies Roaming. This is another headache. The Monsters roam almost everywhere. We want to set the monsters only roam within the spawn area radius. Say 10-20 meter max from where they spawn. Is there better method we could do this?

The way I'd tackle this is to generate random destination points for the Monsters only within a given radius of the spawn point and check with the nav mesh that these are valid.

Another way would be to introduce a turning system where the Monsters start to steer back into the spawn area once they start to approach a certain distance from it. This is what I do with birds so I can specify a flight radius and ensure they remain within it.

You could even have a series of waypoints placed within spawn point areas and assign movement between these. Any one assigned as an active destination for a Monster could be flagged as such and avoided as a destination for others, otherwise they would be selected randomly. Once the destination is left for another the flag is reset to make it available again.

(11-10-2013 07:09 AM)dylantan Wrote:  4. NPC/Main Char unable to go straight from Point A to B even in relatively short distance. The problem is when the characters are trying to perform or get from point A to B (which is a straight line), but they will get confused and unable to find the location (i.e. Point B) hence the character will start walking in circle around until it reach to point B. There is nothing wrong with the path, and the pathmesh is created nicely in and by EE.

The following is our code, and we couldn't find better solution. Is there something with our code or is our approach to the above issues wrong? We love to hear what you think and what's the best way to resolve these issues Any tips/advice would be highly appreciate and thank you in advance.

A path generated from the nav mesh should always get you from A to B if followed. I'm guessing here your attempts at steering are resulting in the erratic movement! One thing you have to watch for is the relative weighting of steering forces/mechanisms, you need to ensure that the main priority is reaching the destination if that's the intended purpose.

I'd generally advice getting all of your basic movement working first without dynamic avoidance of obstacles and then introduce avoidance elements gradually so you can see where they work well and where they cause problems with basic movement.

Sorry for the lack of specifics but hope some of this helps. I'll try and have a look at your code later when I have a little more time.
(This post was last modified: 11-10-2013 09:17 PM by Pixel Perfect.)
11-10-2013 09:16 PM
Find all posts by this user Quote this message in a reply
dylantan Offline
Member

Post: #3
RE: Issues with Path-finding and Object Avoidance
Hi Pixel Perfect! Thank you very much for the reply. Really appreciate it sir!

(11-10-2013 09:16 PM)Pixel Perfect Wrote:  I don't think Esenthel Engine includes an inherent steering system like Mikko Mononen's Detour so in the absence of that you'll need to develop your own. The inbuilt Recast navigation mesh system should avoid all static obstacles which just leaves you to deal with the dynamic ones.

Yeah it is unfortunate that EE doesn't include that. Making your own steering behaviour system would be really time consuming. Yes the built-in Recast is able to avoid all static obstacles, but the problem is with Dynamic vs Dynamic ones thats the problem.

(11-10-2013 09:16 PM)Pixel Perfect Wrote:  In its simplest form this would involve some sort of real time obstacle detection as your NPCs execute their paths produced by the path finding system. If the obstacles are dynamic but not moving at the time (say a moved crate for example or a fallen rock) then once detected one would normally just instigate an avoidance path to the side of the object and then re-path find. If the obstacle is dynamic and moving too then things get a little more complex and you need to take both motions into account. A simple solution might be to apply a braking mechanism where one simple waits for the other to pass and then resumes its original path. There are many many ways of achieving these goals but all with their own advantages and disadvantages.

I wonder how can this be done "real time obstacle detection as your NPCs execute their paths produced by the path finding system" which you mentioned. Will try out to code this but no idea where to start. I wonder if implementing Open Steer would help but unfortunately our last try on Open Steer ended in failure.

(11-10-2013 09:16 PM)Pixel Perfect Wrote:  I seem to recollect someone saying there is an example of a simple steering system in one of the available Esenthel Game Sources (not sure which) so might be worth checking those out.

Oh this would surely help. Esenthel, you know which source code Pixel is referring to?

(11-10-2013 09:16 PM)Pixel Perfect Wrote:  Not sure what's going on in your Dungeons/Caves but its always best to anticipate problems in any steering system and correct for them if possible. Where an NPC is effectively blocked from moving but clearly has not reached its destination try abandoning that path move after a period of time and re-path find again. Always log these issues though so its visible; as its better to find the route cause than mask them.

I think this might be due to dungeon/cave being set to as "Terrain" rather than Custom > Obj_Static. However we have not try change this because we were told that Obj_Static may not be suitable for large props.

(11-10-2013 09:16 PM)Pixel Perfect Wrote:  Not exactly sure what you are meaning here, roaming normally means moving in a random type motion so roaming to only a certain path seems at odds with this?

If you are meaning movements like a patrol path then this is normally achieved by making the NPC path find through a series of designated waypoints.

We did assign the path using way points but still not working, the NPC will still go outside from the assigned path. :(

(11-10-2013 09:16 PM)Pixel Perfect Wrote:  The way I'd tackle this is to generate random destination points for the Monsters only within a given radius of the spawn point and check with the nav mesh that these are valid.

Another way would be to introduce a turning system where the Monsters start to steer back into the spawn area once they start to approach a certain distance from it. This is what I do with birds so I can specify a flight radius and ensure they remain within it.

You could even have a series of waypoints placed within spawn point areas and assign movement between these. Any one assigned as an active destination for a Monster could be flagged as such and avoided as a destination for others, otherwise they would be selected randomly. Once the destination is left for another the flag is reset to make it available again.

Yes that's what we do too (or I think we do) but no luck, something broke the code (or so I think). We are lost as what we need to do

(11-10-2013 09:16 PM)Pixel Perfect Wrote:  A path generated from the nav mesh should always get you from A to B if followed. I'm guessing here your attempts at steering are resulting in the erratic movement! One thing you have to watch for is the relative weighting of steering forces/mechanisms, you need to ensure that the main priority is reaching the destination if that's the intended purpose.

I'd generally advice getting all of your basic movement working first without dynamic avoidance of obstacles and then introduce avoidance elements gradually so you can see where they work well and where they cause problems with basic movement.

Yes thats what we did, but no luck. We just couldnt get it to work properly, hence we seeking help from the good community.

Looking forward to hear to more opinion/tips or advice and thank you in advance again!
11-11-2013 05:00 AM
Visit this user's website Find all posts by this user Quote this message in a reply
Pixel Perfect Offline
Member

Post: #4
RE: Issues with Path-finding and Object Avoidance
(11-11-2013 05:00 AM)dylantan Wrote:  I wonder how can this be done "real time obstacle detection as your NPCs execute their paths produced by the path finding system" which you mentioned. Will try out to code this but no idea where to start. I wonder if implementing Open Steer would help but unfortunately our last try on Open Steer ended in failure.
I have no first hand experience of integrating Open Steer myself but a friend managed to integrate it into several engines with some good success.

One of the issues with Open Steer is it has no concept of boundaries so will happily push you out of your nav mesh. You need to constrain it to stay inside of the nav mesh. Might be worth you looking at Open Steer again.

Essentially whatever steering system you use should only be used to get you past the immediate obstacle and then a new path finding call made. It means that you need access to each of the point data in the calculated path so you are explicitly moving from one to the next whilst implementing obstacle detection. As soon your steering kicks in and you deviate from the original path by a reasonable margin then you should be recalculating the path again.

No one ever said this stuff is easy and it isn't! It is generally easier to produce reasonable avoidance when in large open areas with lower volumes of NPCs than in constricted and densely populated areas.

This is true of real life too, where people moving in restricted areas will tend to adopt direction based lane type movement in order to reduce collisions and collision avoidance. Queuing systems to get through doorways is another example of cooperative solutions.

Stopping (breaking) to allow another to pass and avoid collision can be an effective solution too which looks quite believable when implemented well.

The success really depends on timely detection and adequate prediction of motion. Once you have that then you often have a choice of solutions.

When working on this type of thing I think it pays to set up a series of test levels representative of the types of scenarios you are likely to have to deal with in your game world. Then you can test detection methods and avoidance techniques against each and get a feel for what works well and under what conditions. There is rarely one simple solution that behaves well in all cases so you might have to identify and adopt different techniques for different situations.
11-11-2013 05:27 PM
Find all posts by this user Quote this message in a reply
dylantan Offline
Member

Post: #5
RE: Issues with Path-finding and Object Avoidance
Thanks Pixel and appreciate your feedback. In theory we kind of get the idea now (and even before) and we looking for more practical application at this point of time. Pixel you using EKI One if I am not mistaken? I think the technology have been bought over and rename as MASA LIFE.

I wonder how is the rest doing with this, since I see alot of RPG-related game being developed here, and surprise that no one interested in steering behavior or having any problem with this.
11-12-2013 02:19 AM
Visit this user's website Find all posts by this user Quote this message in a reply
Pixel Perfect Offline
Member

Post: #6
RE: Issues with Path-finding and Object Avoidance
Yeah I'm using EKI One. I wrote my own path finding\AI system in Leadwerks but decided to make the tools needed to support it effectively was going to take far to long so moved to using a third party provided product at that stage.

You are surely right, others using the Esenthel navigation system must have had to find solutions to this so hopefully some might come forward and offer some Esenthel specific help.

Good luck guys!
11-12-2013 10:05 AM
Find all posts by this user Quote this message in a reply
Esenthel Online
Administrator

Post: #7
RE: Issues with Path-finding and Object Avoidance
Esenthel RTS has a simple dynamic object avoidance system (units vs units/buildings/trees)
11-18-2013 07:17 AM
Find all posts by this user Quote this message in a reply
Post Reply