Simple Pathfinding

#1 How about blank sceneobjects on your level with an object type set? Each 'waypoint' would store a reference to the next one in the path.

#2 I am having trouble accomplishing this. I can't seem to get the enemies to travel to the first node. This is what I have so far:

List<ISceneContainerObject> Nodes = new List<ISceneContainerObject>();
            T2DSceneGraph eg = (T2DSceneGraph)_sceneObject.SceneGraph;
            eg.FindObjects(_sceneObject.Position, 100, TorqueObjectType.AllObjects, 0xFFFFFFF, Nodes);
                foreach (T2DSceneObject Node in Nodes)
                {
                    if (Node.ObjectType.Equals(_node1) == true)
                    {
                        _sceneObject.Physics.Velocity = T2DVectorUtil.VelocityFromTarget(_sceneObject.Position, Node.Position, 20.0f);
                    }
                }

_node1 is set to the correct Torque Object Type in TXB.
Thanks for the help.

Edit: The code inside the if statement is not being called.

#3 @Viktor - Objects can have multiple object types. For example, in addition to whatever object types you assign in TXB, all t2dSceneObjects get the "t2dSceneObject" objectType assigned to them. So when you use the equality comparison between all of the objectTypes your object has and one particular object type it might have, it will never evaluate to true. Try either Node.TestObjectType(_node1) in your if condition, or else try using _node1 instead of TorqueObjectType.AllObjects in your FindObjects call, and skipping the if completely.

#4 Great, I'll try this when I'm done installing my new TV card. Merry Christmas.

#5 Well after fixing a completely unrelated graphics problem this works perfectly. This game is coming along quite nicely, atleast in terms of a first game.

#6 Spoke too soon apparently. This gets my enemies to the first node:

if (isPastnode == false)
            {
                List<ISceneContainerObject> Nodes = new List<ISceneContainerObject>();
                T2DSceneGraph eg = (T2DSceneGraph)_sceneObject.SceneGraph;
                Nodes.Capacity = 1;
                eg.FindObjects(_sceneObject.Position, 100, Node1, 0xFFFFFFF, Nodes);
                T2DSceneObject FirstNode = (T2DSceneObject)Nodes[0];
                Vector2 Fpos = FirstNode.Position;
                if (_sceneObject.Position.Equals(Fpos) == false)
                {
                    _sceneObject.Physics.Velocity = T2DVectorUtil.VelocityFromTarget(_sceneObject.Position, FirstNode.Position, 20.0f);
                }
                else if (_sceneObject.Position.Equals(Fpos) == true) 
                {
                    isPastnode = true;
                    Travel(Node2);
                } 
            }

But the else if never evaluates to true. So I can get the enemies to travel to any one node I want and watch them pile up until stuff starts disappearing. What do I need to do differently?

#7 @Viktor - I'm not 100% sure, but I suspect that it's because you're trying to test for equality on things that are unlikely to be exactly equal. Since you're only doing this check periodically, the odds aren't very good that the position is exactly the same as the target, to perfect precision. Try something like this and see if it helps:

if (Vector2.Distance(_sceneObject.Position, FirstNode.Position) > 0.05)
{
    // far away from node, move towards it
}
else
{
    // close enough to the node that we can consider ourselves "there".  Now go to next node.
}

(you might need to play with the threshold value a bit, I picked 0.05 arbitrarily)

#8 Now the enemies are getting to the second node, but I'm having a bit of a logic problem. Travel is only externally called once, from ProcessTick. So when "else" is called in Travel there is no way to get back into it. I have tried a few ideas with no luck. Here is the code:

public void Travel(TorqueObjectType NextNode)
        {
                List<ISceneContainerObject> Destination = new List<ISceneContainerObject>();
                T2DSceneGraph dg = (T2DSceneGraph)_sceneObject.SceneGraph;
                dg.FindObjects(_sceneObject.Position, 100, NextNode, 0xFFFFFFF, Destination);
                T2DSceneObject DestinationNode = (T2DSceneObject)Destination[0];
                if (Vector2.Distance(_sceneObject.Position, DestinationNode.Position) < .3)
                {
                    if (DestinationNode.TestObjectType(Node1) == true)
                    {
                        Destination.Clear();
                        Travel(Node2);
                    }
                    else if (DestinationNode.TestObjectType(Node2) == true)
                    {
                        Destination.Clear();
                        Travel(Node3);
                    }
                    else if (DestinationNode.TestObjectType(Node15) == true)
                    {
                        _sceneObject.MarkForDelete = true;
                    }
                }
                else
                {
                    _sceneObject.Physics.Velocity = T2DVectorUtil.VelocityFromTarget(_sceneObject.Position, DestinationNode.Position, 20.0f);
                }
        }

I tried setting up another object type to call from "else" that mirrored the current one, but got a stack overflow exception.
After this code is working I should finally be done with path-following. Then I'll have to find something else to endlessly bug you guys about :).

#9 May I suggest a little bit of restructuring. This function doesn't really need to be recursive. This is how I see it being done.

The class holds a list of all the nodes sorted by their order on the map. Sorting here is key. I don't know for sure, but I think T2DSceneGraph.FindObjects() returns objects in the order they were created or appear in the scene's xml file.

The Destination list would be filled once, and would be a class variable, possibly even a member of the Game class. It could be initialized after you load your scene. All nodes could be the same object type, which will save you the hassle of creating giant else if chains and extra object types.

When set up this way all that needs to be done in ProcessTick is:

Keep an index to the current node, a component class variable.
Check if I'm close enough to the current node, node[index]. If I am, increment the index, otherwise do nothing.
Calculate my heading to node[index] and scale by my speed to get my velocity towardes the current node.

I'll whip up some example code if you like. I'm not at my torque box otherwise I probably would have already.

#10 I'll try this out, some example code would be great though.

#11 Ok here you go.

A little bit of setup in Game.cs.
(edit)
I only did this here so it doesn't have to be done over on every tick. It could be done slightly differently by moving the _waypointList to the pathfind component, but still fill the list in the BeginRun() function.
(edit)

List<ISceneContainerObject> _waypointList;
TorqueObjectType _waypointType;

public List<ISceneContainerObject> WaypointList
{
    get { return _waypointList; }
}

protected override void BeginRun()
{
    base.BeginRun();

    SceneLoader.Load(@"data\levels\levelData.txscene");

    T2DSceneGraph sg = TorqueObjectDatabase.Instance.FindObject<T2DSceneGraph>("DefaultSceneGraph");
    
    _waypointList = new List<ISceneContainerObject>();
    _waypointType = TorqueObjectDatabase.Instance.GetObjectType("waypointNode");
    
    sg.FindObjects(new Vector2(0, 0), 10000, _waypointType, 0xffffffff, _waypointList);
    // sort this waypoint list, they were not in the order i expected;
}

...and the process tick of my pathfind component. _currentNode is an int, and _minDistance is a float. Both variable are initialzed before process tick gets called. _currentNode to 0 and I picked 0.5 for _minDistance.

public virtual void ProcessTick(Move move, float dt)
{
    
    if (_currentNode < Game.Instance.WaypointList.Count)
    {
        Vector2 destination = (Game.Instance.WaypointList[_currentNode] as T2DSceneObject).Position;
        Vector2 distance = destination - SceneObject.Position;

        if (distance.Length() < _minDistance)
        {
            // increment current node index.
            _currentNode++;
        }
        Vector2 heading = destination - SceneObject.Position;
        heading.Normalize();
        SceneObject.Physics.Velocity = heading * 20.0f;
    }
    else
    {
        // I've reached the last node, kill me, alter score, or something.
        SceneObject.MarkForDelete = true;
    }
}

#12 I feel stupid asking this but what would be the best way to sort the list? I have an idea but it seems fairly complicated and I want to see if there is a smarter option. I'd also be curious about how FindObjects() orders what it finds, because it seemed completely random when I tested it without sorting. Thanks for the rewrite Joshua, that code is much better than what I had, atleast I can understand what's happening.

#13 No problem, it was fun.

Well what's your idea about sorting. Psudeo code it for me.

:)

#14 I was just thinking of creating a component that was attached to the nodes that contained a integer that you could use to sort. I was also thinking about if there was a way to order by the actual order of creation.

#15 The component way is what I would have suggested.

I just though of and even simpler way to do this. It seems to work with the order you create the objects in TXB. Check it out.

In the Game class create a List and an public property to go with it. No need to query the scenegraph anymore. Make the node component but don't worry about that integer. In the component's _OnRegister() say...

Game.Instance.NodeList.Add(SceneObject.Position);

The change the pathfind component to use Game.Instance.NodeList instead, noting that it uses vectors instead.

EDIT: Definetly works based on order of creation in TXB or the XML. The only drawback I can think of is of you want to add a node in the middle and not to the end. You have to delete all the nodes after where you want to insert then recreate all of them.

#16 I am getting a NullReferenceException in the OnRegister method of the node component at Game.Instance.Nodes.Add(_sceneObject.Position);. Object reference not set to an instance of an object.
If I do a try catch I get the same thing in the ProcessTick method of the pathfinder component on
if (_currentNode < Game.Instance.Nodes.Count). This looks like a great way to "pre-sort" objects.

#17 Oh, make sure you new the list sometime before you call Sceneloader.Load().
ie: nodeList = new List();

#18 Awesome, it is working perfectly now. Thanks a lot. This has been a great learning experience. I guess I'll try and tackle GUIs next.

#19 Hi, I have attempted writing a custom MoveTo() method for the sprite using the codes mentioned in this post and I used the following code to check if I reached the destination in ProcessTick():

if (Vector2.Distance(SceneObject.Position, targetPos) < 0.3)
{

SceneObject.Physics.Velocity = Vector2.Zero;

}

Now my issue is that how to determine the threshold value dynamically based on the velocity. From what I experiment, the higher the velocity, the more the threshold value must be. I have tried dividing the velocity by 15, but it only works when the velocity is 15 or less. Is there any formula which can help me determine that? Typically my velocity will not go more than 50 (hopefully)

Thanks in advance for any advice offered
Alexander

#20 I don't completely understand why what your trying doesn't work. Are you getting an error? I'll try to right up a test tonight and see what happens.

Edit: After thinking about it it's probably a problem with trying to get a float from a vector2.