[Bot Developers] A simple waypoint navigation system. Including loading & saving!

[Apoc]

Since my last post went over fairly well, I decided I might as well keep on going. (Actually, jjaa decided I should, I figured I might as well )

First things first; this is a SIMPLE waypoint (breadcrumb) navigation system. It will not have *any* type of unstuck system, that is up to you to implement as per your needs!

I may write more posts on other nav systems (such as A*/Dijkstra based systems. More commonly known as nav meshes) at some other time.

Alrighty then, lets get down to business. The last thread had some explanations on what stuff was, so I might as well just follow that.

Components of a Breadcrumb Nav System

1. Waypoints (duh)
2. A way to consistently cycle through available waypoints
3. A way to make our character move towards the waypoints
4. A way to use 'smart' waypoint selection.

As the FSM was easy, so is this.

First things first, lets tackle the actual waypoint.

Waypoint Components

1. X, Y, and Z values to store the actual coordinate.
2. A way to tell the distance between two waypoints
3. A way to load and save each waypoint

Obviously, this is fairly simple. For the sake of clarity, I won't be naming the first class 'Waypoint', instead it will simply be 'Point'.

Lets get started; first of all, we need 3 things in our Point structure. The X, Y, and Z values.

namespace BotTut_Nav_Waypoints
{
    public struct Point
    {
        public float X { get; set; }
        public float Y { get; set; }
        public float Z { get; set; }
        
        public Point(float x, float y, float z) : this()
        {
            X = x;
            Y = y;
            Z = z;
        }
    }
}

Self explanatory. Note; since it IS a struct, and we are using properties instead of fields, we do need to call the param-less ctor for the Point struct.

Now to add just a little bit of 'math' to our equation, so we can easily grab the distance between two points.

using System;

namespace BotTut_Nav_Waypoints
{
    public struct Point
    {
        public float X { get; set; }
        public float Y { get; set; }
        public float Z { get; set; }
        
        public Point(float x, float y, float z):this()
        {
            X = x;
            Y = y;
            Z = z;
        }

        public double Distance(Point to)
        {
            return Distance(to.X, to.Y, to.Z);
        }

        public double Distance(float toX, float toY, float toZ)
        {
            float dX = X - toX;
            float dY = Y - toY;
            float dZ = Z - toZ;
            return Math.Sqrt(dX * dX + dY * dY + dZ * dZ);
        }
    }
}

Again, this is some pretty basic stuff. If you can't figure out how to calculate distance, you should go back to the 3rd grade!

So far, we've covered points 1 and 2. (Partially #3 via our ctor.) Now, since I'm a lazy programmer, and I prefer to use LINQ instead of XML/Binary formatters, I do this one way. You are more than welcome to use your serialization of choice, however, I just find this to be easier in the long run.

The following is some LINQ code, which means you need to be running at least .NET 3.0 for any of it to be valid. (There's no reason for people to still be using .NET 2.0, just make the jump for 3.5 SP1)

using System;
using System.Xml.Linq;

namespace BotTut_Nav_Waypoints
{
    public struct Point
    {
        public float X { get; set; }
        public float Y { get; set; }
        public float Z { get; set; }
        
        public Point(float x, float y, float z):this()
        {
            X = x;
            Y = y;
            Z = z;
        }

        public double Distance(Point to)
        {
            return Distance(to.X, to.Y, to.Z);
        }

        public double Distance(float toX, float toY, float toZ)
        {
            float dX = X - toX;
            float dY = Y - toY;
            float dZ = Z - toZ;
            return Math.Sqrt(dX * dX + dY * dY + dZ * dZ);
        }

        public XElement GetXml()
        {
            return new XElement("Point", new XAttribute("X", X), new XAttribute("Y", Y), new XAttribute("Z", Z));
        }
    }
}

Our new method 'GetXml' returns an XElement. (If you don't know what this is, go read up on LINQ, I won't bother explaining it here!)

Basically this will return XML formatted like so;

<Point X=0.550225 Y=525.5625 Z=636.252656 />

I prefer to use the coords as attributes, simply to save file space. Feel free to change the occurances of XAttribute to XElement if you want it the other way around. (Note; you'll need to change the following code as well!)

So now we can retrieve the XML to save our waypoints. What about loading it from an XElement?

Again, this is nearly as simple, except it requires just a tad bit more code.

using System;
using System.Xml.Linq;

namespace BotTut_Nav_Waypoints
{
    public struct Point
    {
        public float X { get; set; }
        public float Y { get; set; }
        public float Z { get; set; }
        
        public Point(float x, float y, float z):this()
        {
            X = x;
            Y = y;
            Z = z;
        }

        public Point(XElement xml)
            : this(Convert.ToSingle(xml.Attribute("X").Value), 
                   Convert.ToSingle(xml.Attribute("Y").Value), 
                   Convert.ToSingle(xml.Attribute("Z").Value))
        {}

        public double Distance(Point to)
        {
            return Distance(to.X, to.Y, to.Z);
        }

        public double Distance(float toX, float toY, float toZ)
        {
            float dX = X - toX;
            float dY = Y - toY;
            float dZ = Z - toZ;
            return Math.Sqrt(dX * dX + dY * dY + dZ * dZ);
        }

        public XElement GetXml()
        {
            return new XElement("Point", new XAttribute("X", X), new XAttribute("Y", Y), new XAttribute("Z", Z));
        }
    }
}

As you can see, we now have a new constructor that takes an XElement as a parameter. For now, just understand that the XElement we pass to it, will be the SAME as the element GetXml returns. (Coords different obviously.)

We simply parse each attribute to the correct type (in this case a float) and pass it to our already made constructor. Note how I use Convert.ToSingle instead of float.Parse or Single.Parse. This is preference, and you are free to do it differently. Do note; Convert.ToSingle has a few extra checks to make sure it's using valid data. If it encounters a null/empty string, it will return 0.0f. Another benefit!

So that takes care of our Point structure, and our entire Waypoint loading and saving.

Wait! I lied! Ok, so I didn't really lie, we just need a 'vessel' to load out waypoints into.

Remember #2 on the components of a breadcrumb nav system?

We have a few choices here, we can use a List<Point> to hold our stuff, and we can then just store whatever index we're at, then reset it back to 0 once we've hit the last Point in the list.

We can do some funky shenanigans with arrays and whatnot.

We can write a circular queue collection, to do it all for us, easily.

Obviously you know where I'm going with this one!

Now, stay with me here guys, this is some pretty tricky code.

using System.Collections.Generic;

namespace BotTut_Nav_Waypoints
{
    class CircularQueue<T> : Queue<T>
    {
        public new T Dequeue()
        {
            T tmp = base.Dequeue();
            Enqueue(tmp);
            return tmp;
        }
    }
}

Phew. Tough, I know. So, what exactly have we done here?

In short, we literally just took a Queue<T>, and made it circular. (Whenever we pop something off the Queue, it gets put right back on, at the back. Making it... circular)

This might be some new syntax for new C# people.

Since our implementation of Dequeue() hides Queue<T>'s implementation, we can either add the 'new' modifier to the method, or omit it. It will work either way, however I like to make sure the 'new' is there, to let anybody reading the code know I actually meant for the Queue<T>'s Dequeue to be hidden.

I would make some fancy pictures and stuff, but seriously, the concept isn't that hard.

Alright, so we've got a way to consistently store, and cycle through our waypoints. Now we just need to make it load them from a file. Again; this part may be tricky for those of you new to LINQ, but bear with me.

In our Point class, we'll add a static method that returns a CircularQueue<Point>. The code is as follows:

        public CircularQueue<Point> LoadFile(string filePath)
        {
            if (!File.Exists(filePath))
            {
                throw new FileNotFoundException("Could not find the specified file!", filePath);
            }

            var ret = new CircularQueue<Point>();
            XElement file = XElement.Load(filePath);
            var points = from p in file.Descendants("Point")
                         select p;
            foreach (XElement point in points)
            {
                ret.Enqueue(new Point(point));
            }
            return ret;
        }

Basically; we execute a quick LINQ statement to gather all the <Point /> elements into a collection, then just load them into the new CircularQueue. Isn't this a bit easier than doing some silly XmlReader or serialization stuff?

The following code is just 'filler' stuff, so that we can have at least some API to play with that will at least mimic our gameplay system. Keep in mind; none of this code will actually do anything useful, it's pretty much just a template.

namespace BotTut_Nav_Waypoints
{
    public class Me
    {
        public static bool IsMoving
        {
            get { return true; }
        }

        public static Point Location
        {
            get { return new Point(0, 0, 0); }
        }

        public static void Face(Point pt)
        {}

        public static bool IsFacing(Point pt)
        {
            return false;
        }

        public static void MoveForward()
        {}

        public static void Stop()
        {}
    }
}

This is all we really need for the most basic of navigations. We probably won't be using the 'Stop' method in this nav system, as it's just an example.

On to the actual navigation!

namespace BotTut_Nav_Waypoints
{
    public class Navigation
    {
        private CircularQueue<Point> _waypoints;

        public Navigation(CircularQueue<Point> waypoints)
        {
            _waypoints = waypoints;
        }

        public void NavigateWaypoints()
        {
            
        }
    }
}

Nothing spectacular here. We simply ask for a set of waypoints, and set it so we can use it.

Before I go any further, I want to point out, and show you something at the same time. There's a lot of fuss apparently about how to best handle getting the 'closest waypoint'. In all honesty, people are kinda funny in the ways they implement this functionality. I'm going to show you how to do it in less than 40 lines of code.

First; we need a way to test equality on Points. (This will be used in the navigation itself anyway, so we might as well get down to it!)

Add the following to the Point class:

        public bool Equals(Point other)
        {
            return other.X == X && other.Y == Y && other.Z == Z;
        }

        public override bool Equals(object obj)
        {
            if (ReferenceEquals(null, obj))
            {
                return false;
            }
            if (obj.GetType() != typeof(Point))
            {
                return false;
            }
            return Equals((Point) obj);
        }

        public override int GetHashCode()
        {
            unchecked
            {
                int result = X.GetHashCode();
                result = (result * 397) ^ Y.GetHashCode();
                result = (result * 397) ^ Z.GetHashCode();
                return result;
            }
        }

        public static bool operator ==(Point left, Point right)
        {
            return left.Equals(right);
        }

        public static bool operator !=(Point left, Point right)
        {
            return !left.Equals(right);
        }

Make sure you add the interface IEquatable<Point> to the class.

Now that we can test equality, we'll add a quick method to our CircularQueue class to simply cycle to a specific item.

        public void CycleTo(T item)
        {
            // Using a for loop here to avoid and endless cycle if no match is found!
            T tmp = Peek();
            for (int i = 0; i < Count; i++)
            {
                if (!tmp.Equals(item))
                {
                    // Toss it to the back.
                    Dequeue();
                    // Check the next one.
                    tmp = Peek();
                }
                else
                {
                    // We've hit our item. Stop here!
                    return;
                }
            }
            // No item was found, so make sure we end up where we started from.
            Dequeue();
        }

Read the comments. It'll explain it! It's a really simple concept. Just cycle through until the items are equal, and stop cycling there.

Notice how I'm using Peek instead of Dequeue to check the item. This is so we don't need to add some sort of funny stuff to cycle ALL the way back through. Since once we Dequeue the item, it's at the back. Peek grabs the next item, without popping it off the queue.

Now, we just need a simple way to grab the closest waypoint to us. Again, it's fairly simple.

        public Point GetClosestToMe()
        {
            // Store my location.
            Point myLoc = Me.Location;

            // Since we want the closest, we start with the highest possible value
            // to make sure we have some valid data!
            double closest = double.MaxValue;

            Point ret = new Point();

            // Cycle through, testing distance, and set our return Point to the closest
            // one we find.
            foreach (Point p in _waypoints)
            {
                if (p.Distance(myLoc) < closest)
                {
                    closest = p.Distance(myLoc);
                    ret = p;
                }
            }
            return ret;
        }

Comments explain it all.

Now, we simply make a quick and dirty method to make life easier (and our code cleaner!);

        public void SetDestinationToNearest()
        {
            _waypoints.CycleTo(GetClosestToMe());
        }

This sets the queue to have our first value as the closest waypoint. If we wanted to add more code here later; we can. (Such as using ghost points, etc.) For now, we'll just call this method from our constructor. Feel free to move it wherever it is needed. (I usually put this at the end of a combat sequence to make sure we're on track.)

Now we get to our actual navigating part! Bear with me, this stuff will be *very* hard.

        public void NavigateWaypoints()
        {
            // Set our destination point that we'll be using throughout this method.
            Point dest = _waypoints.Peek();

            // Are we close to the current waypoint? If so, push it to the end and move to the next.
            if (dest.Distance(Me.Location) < 3)
            {
                _waypoints.Dequeue();
                return;
            }

            if (!Me.IsFacing(dest))
            {
                Me.Face(dest);
            }

            if (!Me.IsMoving)
            {
                Me.MoveForward();
            }
        }

So very, very, hard. Simply put, this is *all* you need to make your bot run around endlessly using your waypoints.

Check if we're within distance of the destination point, make sure we're actually facing that point, and finally, make sure we're moving TO the point.

It doesn't get any simpler than this folks.

You can expand on this all you want. There are plenty of improvements to be made. Just remember; this is just a base for you to work from. It's not meant to be anything entirely special or the like.

Source code download:

Filebeam - Free Fast File Hosting

[Vindicated]

First POST. +Rape

(Reserved for more analysis of this passage when I'm smarter.)

[Mirror]

After the X,Y,Z math part, I got confuzzled.

[jjaa]

Nice Apoc. Much better then my current Waypoint system .

[lanman92]

Apoc, your C# skills always blow my mind. Do you do this type of thing for a living?

[Apoc]

Apoc, your C# skills always blow my mind. Do you do this type of thing for a living?

Nope. I actually work in the automotive industry. Programming is just a hobby.

[Robske]

Thanks, Awesome idea to create a CircularQueue<T> datastructure for this - as are the XML constructor and method for the Point structure. These guides are very appreciated

PS: and Jjaa is definatly right)
PSS: you have 911 rep

[vulcanaoc]

you've done it again, haven't you? thanks

[disgustedoak]

WOWWOOW ur C# skills r amazing .. Hmm i been learning for maybe 3 days and just almost finished my wow launcher <.< lool Cool thanks for this! +rep

[vulcanaoc]

Hey Apoc, you said

In our Point class, we'll add a static method that returns a CircularQueue<Point>. The code is as follows:

        public CircularQueue<Point> LoadFile(string filePath)
        {
            if (!File.Exists(filePath))
            {
                throw new FileNotFoundException("Could not find the specified file!", filePath);
            }

            var ret = new CircularQueue<Point>();
            XElement file = XElement.Load(filePath);
            var points = from p in file.Descendants("Point")
                         select p;
            foreach (XElement point in points)
            {
                ret.Enqueue(new Point(point));
            }
            return ret;
        }

But the method is not static. Neither here nor in the source. I don't think this was intentional, either..

[Apoc]

Hey Apoc, you said


But the method is not static. Neither here nor in the source. I don't think this was intentional, either..

Nope, that was an 'oops' on my part. Just mark that function as static.

[burdakovd]

Apoc, why do you need this Linq query without predicate in LoadFile method?

public CircularQueue<Point> LoadFile(string filePath)
        {
            if (!File.Exists(filePath))
            {
                throw new FileNotFoundException("Could not find the specified file!", filePath);
            }

            var ret = new CircularQueue<Point>();
            XElement file = XElement.Load(filePath);
            var points = from p in file.Descendants("Point")
                         select p;
            foreach (XElement point in points)
            {
                ret.Enqueue(new Point(point));
            }
            return ret;
        }

Won't it be simplier to just do so?

var points = file.Descendants("Point");

also you didn't describe save method, it will be something like this?

public void Save(string filePath)
        {
            XElement file = new XElement("WayPointList");

            foreach (Point p in this)
                file.Add(p.GetXml());

            file.Save(filePath);
        }

[Apoc]

Apoc, why do you need this Linq query without predicate in LoadFile method?

Won't it be simplier to just do so?

var points = file.Descendants("Point");

Yes. I had originally had some extra code in that LINQ query. It can be 'dumbed down' to that however. (And should for clarity's sake.) I had originally called ToList() on the query so I could do some other stuff, but figured 'eh, don't need to'.

also you didn't describe save method, it will be something like this?

public void Save(string filePath)
        {
            XElement file = new XElement("WayPointList");

            foreach (Point p in this)
                file.Add(p.GetXml());

            file.Save(filePath);
        }

Heh. Look at that, I did forget to add the actual save method. D'oh!

Anyhow, your code should work just fine.

[burdakovd]

Also if fractional part separator on someone's locale is not '.' (',' for me), Convert.ToSingle() fails.

float.Parse(xml.Attribute("X").Value, CultureInfo.InvariantCulture)

will parse using '.' separator for any locale

[Fabolous1]

Thanks for the navigation system!