Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

I've taken the A* Algorithm from this example XNA Pathfinder Example so that it will be able to plot a path for a moving goal.

The issue I'm having is that it will go in the right general direction but it will keep going back and forth in a line. I've changed the method so that it calculates a new path every half a second, clear out the previous points from the list and adds the new points to and from what I have debugged I can't find any issue with the points being added to the queue, to be honest I don't have the foggiest idea what is going wrong :/

This is the field where the waypoints are being held for the character

private Queue<Vector2> waypoints = new Queue<Vector2>();

This section is in the update loop and deals with the plotting a new path and laying out the new one onto the list mentioned above.

            timer += gameTime.ElapsedGameTime;

            if (timer.Seconds >= 0.5)
            {
                timer = TimeSpan.Zero;
                pathFinder.NewPath(position);
            }

            if (pathFinder.SearchStatus == SearchStatus.PathFound)
            {
                waypoints.Clear();
                foreach (Point point in pathFinder.FinalPath())
                {
                    Waypoints.Enqueue(level.MapToWorld(point, true));
                }
                moving = true;
            }

This section is where the waypoints are either taken off or used to set the new position of the character.

                if (moving)
                {
                    // If we have any waypoints, the first one on the list is where 
                    // we want to go
                    if (waypoints.Count >= 1)
                    {
                        destination = waypoints.Peek();
                    }

                    // If we’re at the destination and there is at least one waypoint in 
                    // the list, get rid of the first one since we’re there now
                    if (AtDestination && waypoints.Count >= 1)
                    {
                        waypoints.Dequeue();
                    }
                    if (!AtDestination)
                    {
                        direction = -(position - destination);
                        //This scales the vector to 1, we'll use move Speed and elapsed Time 
                        //to find the how far the tank moves
                        direction.Normalize();
                        position = position + (direction * MoveSpeed * elapsedTime);
                    }                  
                 }
share|improve this question
5  
Is it possible that when it recalculates the next best position, it thinks going "forth" is a good idea so it goes that way. Then, when it checks a half second later, it thinks "back" is a good idea and goes back that way since you're erasing the old path? –  Richard Marskell - Drackir Aug 23 '11 at 20:23
3  
"it calculates a new path every half a second", you shouldn't need to do that unless the environment is changing. A simple debug check would be to draw the waypoints and/or lines between the waypoints, this would allow you to visually see what is happening. As for your code, I don't see anything obvious. –  John McDonald Aug 23 '11 at 20:37
    
@Dirckir, that is probably it –  dbomb101 Aug 23 '11 at 21:29
1  
If Drackir's answer does happen to be correct, maybe you can weight the existing path more than picking a new path. –  John McDonald Aug 23 '11 at 21:36
1  
Well... In a typical A* algorithm, you assign a cost of a tile based on the "length" of the path taken to get to the tile in question PLUS the Hamiltonian distance to the target. This cost could be altered (much like diagonals having a higher cost) to have a lower cost if the tile is on the existing route. That way, it will prefer the existing route, but won't be restricted to it. –  John McDonald Aug 24 '11 at 22:35

2 Answers 2

up vote 1 down vote accepted

Note: I happened upon this because "Community" bumped it and I see that my comment was helpful so I figured I'd post it as an answer.


Is it possible that when it recalculates the next best position, it thinks going "forth" is a good idea so it goes that way. Then, when it checks a half second later, it thinks "back" is a good idea and goes back that way since you're erasing the old path?

As John McDonald described in the comments, to fix this you could weight the points already on the path so that it's more likely to follow the previous path but isn't necessarily stuck to it.

share|improve this answer
    
Yeah that was pretty much it thanks for the info though :) –  dbomb101 Oct 24 '11 at 20:08

Your character should check for a new destination only when it has reached the current destination. At this point if your target has changed you should recalc the path.

I'm afraid with the AtDestination calcs. I'd like to see how you determine it.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.