Welcome, Guest. Please login or register. Did you miss your activation email?

Author Topic: Path Finding and Steering Behavior Thread  (Read 5560 times)

0 Members and 1 Guest are viewing this topic.

magneonx

  • Full Member
  • ***
  • Posts: 141
    • MSN Messenger - magnumneon04@hotmail.com
    • View Profile
Path Finding and Steering Behavior Thread
« on: October 26, 2013, 02:06:43 pm »
Alright, I'll quit posting new threads, I'll stick to this thread when I encounter problems regarding this subject.

Original Question: I am just wondering, can I ever use Steering Behavior: Collision avoidance without seek behavior??? Can that be possible?

Thank you so much!
« Last Edit: October 26, 2013, 06:16:50 pm by magneonx »

G.

  • Hero Member
  • *****
  • Posts: 1593
    • View Profile
Re: Can I use Steering behavior: Collision Avoidance without seek behavior?
« Reply #1 on: October 26, 2013, 05:04:16 pm »
Your entity has a position and a velocity. The seek behavior gives your entity the needed velocity change to go towards a target.
The basic collision avoidance behavior takes 3 things : the entity position, its velocity and the position of your obstacle. From these 3 values it computes an avoidance force, which you'll ad to your entity velocity in order to avoid the obstacle.
So yes, as long as your entity has a position and a velocity (whether it's computed from a seek behavior or a similar one or something else) I'd say the collision avoidance behavior can be used.
Do you have troubles with the seek behavior?
« Last Edit: October 26, 2013, 05:10:02 pm by G. »

magneonx

  • Full Member
  • ***
  • Posts: 141
    • MSN Messenger - magnumneon04@hotmail.com
    • View Profile
Re: Can I use Steering behavior: Collision Avoidance without seek behavior?
« Reply #2 on: October 26, 2013, 05:50:59 pm »
Oh thank you for reply! You see, I been doing this along time and I just almost finish some parts of the game I am making so I am back here again. I have done A* Path FInding, my A* path finding generates the shortest path. WIth the path that I have, I traverse each path by selecting the center of those tile(32x32) and my character move to that very point. My movement is just plain basic, and it works pretty well. I just want a collision detection using Collision Avoidance.

So going to the next tile, my character should perceive an immediate object in front of it. I also have a problem, sometimes my character went off course( no longer bound in any axis). This is because I have normalize their paths, which I wanted because i wanted my characters to move independently in any directions that is not bounded by the position of the tiles. So I just don't want my characters stepping or clipping through other objects.  So I used Steering Behavior: Collision Avoidance

I have made the collision avoidance thingy and I have made it to work. It detects the collision against an object which is great. But whenever my characters collides with the object it jitters, it doesn't feel right. I didn't use the seek behavior so that's what I am asking if it is actually important.



magneonx

  • Full Member
  • ***
  • Posts: 141
    • MSN Messenger - magnumneon04@hotmail.com
    • View Profile
Re: Path Finding and Steering Behavior Thread
« Reply #3 on: October 27, 2013, 04:50:56 am »
Hi! I am recreating steering behavior using this small example. I hit a snag, my sprite move so fast, how can I control the speed? I don't know what I am doing wrong...

#include<iostream>
using std::cout;
using std::endl;

#include<string>
using std::string;

#include<cmath>

#include<SFML/Graphics.hpp>
#include<SFML/System/Clock.hpp>

#include "VectorMath.hpp"

class Actor
{
public:

    Actor( const string &fname , float x , float y )
        : speed ( 100.5f ) ,
        velocity( -1.0f , -2.0f ),
        MAX_VELOCITY( 1.8f ),
        MAX_FORCE( 3.24f )
    {
        if( !texture.loadFromFile( fname ) )
            return;

        sprite.setTexture( texture );
        sprite.setPosition( x , y );
        sprite.setOrigin( 16 , 16 );
    }

    virtual ~Actor()
    {

    }

    void update( float e )
    {
        float mass = 100.0f;
        const float MAX_SPEED = e * speed;

        sf::Vector2f spritePosition = sprite.getPosition();
        sf::Vector2f spriteTargetPosition = sf::Vector2f( mousepos );

        desired_velocity = spriteTargetPosition - spritePosition;
        desired_velocity = normalize( desired_velocity ) * MAX_VELOCITY;

        steering.x = desired_velocity.x - MAX_SPEED;
        steering.y = desired_velocity.y - MAX_SPEED;
        steering = truncate( steering , MAX_FORCE );
        steering /= mass;

        velocity = truncate( velocity + steering , MAX_SPEED );
        spritePosition = spritePosition + velocity;


        float movex = spritePosition.x + velocity.x;
        float movey = spritePosition.y + velocity.y;

        sprite.setPosition( movex , movey );
    }

    void mouseListen( const sf::Vector2i &mpos )
    {
        mousepos = mpos;
    }

    void setPosition( const sf::Vector2f &position )
    {
        sprite.setPosition( position );
    }

    sf::Sprite & getSprite()
    {
        return sprite;
    }

private:

    sf::Vector2i mousepos;
    sf::Texture texture;
    sf::Sprite sprite;
    sf::Vector2f position;

    sf::Vector2f velocity;
    sf::Vector2f desired_velocity;
    sf::Vector2f steering;

    float speed;
    const float MAX_VELOCITY;
    const float MAX_FORCE;

};

int main()
{

    sf::RenderWindow window( sf::VideoMode( 800 , 600 , 32 ) , "Steering Behavior" );

    Actor actor1( "crusader.png" , 400.0f , 300.0f );
    sf::Clock clock;

    while( window.isOpen() )
    {
        sf::Event event;
        float elapsed = clock.restart().asSeconds();

        while( window.pollEvent( event ) )
        {
            if( event.type == sf::Event::Closed )
            {
                window.close();
            }
            else if( event.type == sf::Event::KeyPressed )
            {
                if( event.key.code == sf::Keyboard::Key::Escape )
                    window.close();
            }
        }

        actor1.mouseListen( sf::Mouse::getPosition( window ) );
        actor1.update( elapsed );

        window.clear();
        window.draw( actor1.getSprite() );
        window.display();
    }

    return 0;
}

 

Ixrec

  • Hero Member
  • *****
  • Posts: 1241
    • View Profile
    • Email
Re: Path Finding and Steering Behavior Thread
« Reply #4 on: October 27, 2013, 05:06:25 am »
Actor( const string &fname , float x , float y )
        : speed ( 100.5f ) ,
        velocity( -1.0f , -2.0f ),
        MAX_VELOCITY( 1.8f ),
        MAX_FORCE( 3.24f )

Have you tried adjusting these parameters?

And one minor thing: all caps is traditionally reserved for macro names, so it's a bit confusing to see it in variable names.

magneonx

  • Full Member
  • ***
  • Posts: 141
    • MSN Messenger - magnumneon04@hotmail.com
    • View Profile
Re: Path Finding and Steering Behavior Thread
« Reply #5 on: October 27, 2013, 05:53:51 am »
Oh thaks again Ixrec! Actually I have tried, I don't know what values I have to type in anymore! I am just so confused... I am following tutorials, I have tried all of them but still produces same results! Its a wobbly fast moving sprite to mouse position. It still steers, which is a great thing but just moves very fast.

And about the all caps, thanks for the heads up.  ;)

magneonx

  • Full Member
  • ***
  • Posts: 141
    • MSN Messenger - magnumneon04@hotmail.com
    • View Profile
Re: Path Finding and Steering Behavior Thread
« Reply #6 on: October 27, 2013, 06:18:22 am »
I have finally made it to work! Here is my code...

#include<iostream>
using std::cout;
using std::endl;

#include<string>
using std::string;

#include<cmath>

#include<SFML/Graphics.hpp>
#include<SFML/System/Clock.hpp>

#include "VectorMath.hpp"

class Actor
{
public:

    Actor( const string &fname , float x , float y )
        :
        desired( sf::Vector2f( 0 , 0 ) ),
        steer( sf::Vector2f( 0 , 0 ) ),
        velocity( sf::Vector2f( 0 , 0 ) ),
        maxForce( 15 ),
        maxVelocity( 3 ),
        mass( 10.0f )
    {
        if( !texture.loadFromFile( fname ) )
            return;

        sprite.setTexture( texture );
        sprite.setPosition( x , y );
        sprite.setOrigin( 16 , 16 );

        position = sprite.getPosition();
    }

    virtual ~Actor()
    {

    }

    void update( float e )
    {
        sf::Vector2f target = sf::Vector2f( mousepos );

        steer = seek( target );
        steer = truncate( steer , maxForce );
        steer *= ( 1 / mass );

        velocity = velocity + steer;
        velocity = truncate( velocity , maxVelocity );


        position = position + velocity;
        cout << position.x << " x " << position.y << endl;



        sprite.setPosition( position );

    }

    sf::Vector2f & seek( const sf::Vector2f &targetpos )
    {
        sf::Vector2f force;

        desired = targetpos - position;
        desired = normalize( desired );
        desired *= maxVelocity;

        force = desired - velocity;
        return force;
    }

    void mouseListen( const sf::Vector2i &mpos )
    {
        mousepos = mpos;
    }

    void setPosition( const sf::Vector2f &position )
    {
        sprite.setPosition( position );
    }

    sf::Sprite & getSprite()
    {
        return sprite;
    }

private:

    sf::Vector2i mousepos;
    sf::Texture texture;
    sf::Sprite sprite;
    sf::Vector2f position;

    sf::Vector2f desired;
    sf::Vector2f steer;
    sf::Vector2f velocity;

    const float maxForce;
    const float maxVelocity;
    float mass;

};

int main()
{

    sf::RenderWindow window( sf::VideoMode( 800 , 600 , 32 ) , "Steering Behavior" );
    window.setFramerateLimit( 30 );

    Actor actor1( "crusader.png" , 400.0f , 300.0f );
    sf::Clock clock;

    while( window.isOpen() )
    {
        sf::Event event;
        float elapsed = clock.restart().asSeconds();

        while( window.pollEvent( event ) )
        {

            if( event.type == sf::Event::Closed )
            {
                window.close();
            }
            else if( event.type == sf::Event::KeyPressed )
            {
                if( event.key.code == sf::Keyboard::Key::Escape )
                    window.close();
            }
        }


        sf::Vector2i mpos = sf::Mouse::getPosition( window );
        actor1.mouseListen( mpos );
        actor1.update( elapsed );

        window.clear();
        window.draw( actor1.getSprite() );
        window.display();
    }

    return 0;
}

 

I got a problem, you see, I have a game and each entity in the game has attribute most importantly velocity. This is because I wanted to give an entity different speeds. Given the code I have given, how can I control speed? As time goes by that entity can change it speed.

Do I need additional computation on maxForce and mass?

Ixrec

  • Hero Member
  • *****
  • Posts: 1241
    • View Profile
    • Email
Re: Path Finding and Steering Behavior Thread
« Reply #7 on: October 27, 2013, 06:26:22 am »
The thing with this kind of movement is that no entity has just a speed.  It has a whole set of properties that help determine what its velocity (not just speed!) will be at any given moment.  You need to understand what those properties are so you can phrase your question far more precisely, and then we'll be able to understand what you want and help you achieve it.

As a total stab in the dark, maybe you want maxVelocity to be different for each entity?

magneonx

  • Full Member
  • ***
  • Posts: 141
    • MSN Messenger - magnumneon04@hotmail.com
    • View Profile
Dynamic Pathfinding
« Reply #8 on: November 27, 2013, 03:30:11 pm »
I just want to ask about dynamic pathfinding, generating shortest path onto moving object. I have made my very small algorithm. In my game the agent actually only generate path whenever a goal has been set (e.g move, attack). So I have read about Dynamic pathfinding such as D* Path Finding but I can find the implementation quite difficult and I don't even know if that is exactly what I need so I developed my own thoughts on how to do pathfinding onto a moving object.

Since every right click the user has made, the agent is triggered to response and generate shortest path on mouse click, so if I click onto a moving target, of course since it is a moving target it should have a goal such as reaching the destination,  I simply add the generated shortest path of this agent( target ) into the hunter's path(the agent or agents I am controlling). I am actually going to do this using Observer method pattern since I will have multiple units target moving object. I wanted that, every time my autonomous agent changes a goal(e.g move, attack) it should notify all its hunters thereby triggering them to generate shortest path. That is, when my commanded my unit to attack a moving object, these units where added onto the target's list of targeters/hunters and will be updated whenever the targets goal has been changed.

So by this solution I don't have to generate path over and over again during update because I know it will lag a lot. So by this I only have to generate the involved parties' path once.

Do you think this is a nice idea? I actually thinking of waypointing-like behavior or zigzagging like behavior that could happen in my solution. What else can I do to make this better?

I actually have read some stuff like, if I could already know where the destination will be shall I just go there? Some people similarly describe this as wolf hunting on the wild. Wolves already know where the prey will be at certain time. But what I am just saying is my solution a valid one for dynamic pathfinding?

What do you think? I need your thoughts on this.
Thank you very much!

wintertime

  • Sr. Member
  • ****
  • Posts: 255
    • View Profile
Re: Path Finding and Steering Behavior Thread
« Reply #9 on: November 27, 2013, 03:52:23 pm »
Thats bad design because its not the business of a hunted thing to present a mind-dump to its hunters.
The hunters should estimate the position of their prey periodically, calculate how it changed compared to the old value they remembered, update to decide if its still worth following or if some other action is warranted and then move accordingly.
Btw. http://realtimecollisiondetection.net/blog/?p=81  :P

magneonx

  • Full Member
  • ***
  • Posts: 141
    • MSN Messenger - magnumneon04@hotmail.com
    • View Profile
Re: Path Finding and Steering Behavior Thread
« Reply #10 on: November 27, 2013, 04:34:52 pm »
Hello thanks, I don't understand your term mind-dump. Yeah I've notice that somehow that it is a bad design thanks for the input. I wanted to try that difference in position then generate path to that moving object when it reach a tolerable threshold. I have read some post regarding and they suggested D* Lite instead. I will try your idea. Also regarding that checking for target position of target before and after, I don't want my units to just stop when the unit went out of range, I want them to push on with the pursuit as long as they are able.

Regarding the link, its an interesting read but I don't intend to over abuse the use of design pattern, and thanks to you it seems I did. The problem is I just wrote the RTS framework from scratch and I just wanted to get the information going on between objects. I tried to analyze how can I apply what I have thought without breaking the code. I also have notice that significant oversight of responsibilities of hunted knowing whos hunting it. I might rethink this for quite a while.

But do you know any solutions for dynamic pathfinding that I might get interested into? Aside from those that are popular already.

Thanks again for your time.

wintertime

  • Sr. Member
  • ****
  • Posts: 255
    • View Profile
Re: Path Finding and Steering Behavior Thread
« Reply #11 on: November 27, 2013, 04:41:04 pm »
I was just figuratively speaking of the object telling the world of its private decisions that only belong to itself. ;)

Nexus

  • SFML Team
  • Hero Member
  • *****
  • Posts: 6287
  • Thor Developer
    • View Profile
    • Bromeon
Re: Path Finding and Steering Behavior Thread
« Reply #12 on: November 27, 2013, 05:21:02 pm »
A crucial optimization in pathfinding is path caching. Try to reuse paths you have already computed in the past. For example, when you move a group of nearby agents to the same destination, don't compute the full path for every agent.

I wouldn't come up with own solutions, since pathfinding is a rather well-researched field with optimal algorithms such as A*. You risk to end up with solutions that are not efficient enough, and you have to start again. The algorithms are not that difficult to understand, and there are plenty of sources on the internet, especially since it's a topic that loads of game developers have to learn.

From a design perspective, there's the usual advice as always: Keep things modular, abstract and independent. For example, don't mix input and pathfinding code directly. The Observer pattern you mentioned is a good start in that direction -- keep in mind that C++ offers a far less boilerplate version of it through std::function. Like that, it will be simple to tweak the algorithm specifically and exchange parts of it.
Zloxx II: action platformer
Thor Library: particle systems, animations, dot products, ...
SFML Game Development:

magneonx

  • Full Member
  • ***
  • Posts: 141
    • MSN Messenger - magnumneon04@hotmail.com
    • View Profile
Re: Path Finding and Steering Behavior Thread
« Reply #13 on: November 28, 2013, 05:48:37 pm »
Alright thanks! Actually I am using the strategy pattern on path traversal, I did not do it for path finding, since I did not expected my pathfinder will simply change algorithm, not until now that you mentioned about optimization. For now, I don't want to do optimization maybe after when everything is functional. Thank you for giving me new ideas on caching the generated path.

Also I am not familiar with std::function I might take a read on that :/.