Mapping (Pathing etc.)

[xzidez]

Don't forget to implement the interfaces you're going to need to serialize your class and to sort it.

Interfaces? o.o
Correct me if im wrong here. But he should just put the
[Serializable]
attribute on his list. And then its good to go. Just use the built in XML serializer and store it as XML data.. I dont see why he should use any interface for something that simple.

edit: Hmm I looked it up and you dont even need [Serializable] on List since it alreay have it. The only thing need is XmlAttribute.. which you already have so. my bad.

so, yes you can serialize it pretty simple.

XmlSerializer seri = new XmlSerializer(typeof(List<Test>));
TextWriter write = new StreamWriter(@"c:\list.xml");
seri.Serialize(write, test);
write.Close();


List<Test> tmp;
TextReader reader = new StreamReader( "list.xml" );
tmp = (List<Test>)seri.Deserialize(reader);
reader.Close();

[Cypher]

I checked out some videos on GNav, but what exactly sets it "apart"?

Really what I seen in one video with "Insect AI", all the bot did was run around into walls and realize when there was a wall, turn back and just map that spot..

I think I just want to know what's actually behind it, because the videos really did not set it apart at all from any other AI pathing..

Basically it's a pregenerated navmesh of the entire game world, optimized to only include walkable surfaces of course. On top of that it automatically detects roads and weights them higher, it has flying support, it has flightpath support, etc etc. Pretty much the only time it gets "stuck" is when theres a gameobject in the way, but obviously there's no way you can pregenerate a navmesh and account for data that you don't receieve until runtime, gameobjects are detected and the dead-zones removed from the mesh though.

The video was not designed to show off GreyNav (greynav doesn't do any mapping, it already knows where the walls are, so I don't know what video you're referring too but you're obviously confused about something). As Apoc has stated it was by someone else designed to show off an entirely different concept/feature/whatever.

In summary:
Its pretty much the fastest, most efficient, most accurate, most feature packed nav system for WoW I've ever seen.

[suicidity]

That actually sounds pretty cool; How it has a pre-generated mesh and weights roads etc.

I wouldn't mind digging into the source-code of something like that..

[akh]

I have a question on how to detect the roads... What I have now is a list of textures that are used for roads and I check where the texture is used in the terrain.

roadTexs = new List<String>() { "Tileset\\Elwynn\\ElwynnCobbleStoneBase.blp", "...", ... };

Is there any way to figure out if a texture is used for roads, like a flag or something, or do I have to find the roadtextures by hand?

[schlumpf]

No, there are no flags.

[Nesox]

ADT - MPQNav Public Blog
Seems like a nice resource if ure new to this, as i am really helps to shed some light on this aspect.
Currently trying to create something similiar to akh's adt viewer

[Bunster]

Yeye i agree with above, nice if your new.

[suicidity]

Read the post quite a few up, and Saving as an XML file would be a bad idea.

I mean you would be either putting information and subs in for each node or waypoint etc that you used in your map, while it might be easy to read out; You would have an overflow of un-needed data with anything of mass nodes / waypoints.

I'm expecting myself for one of my files to have anything from ~500-5000 nodes. I'm guessing it would change from WAR to WoW too much..

[luciferc]

Lol. Well i did use wat Apoc said w/ Prininting it out to a .xml
3500x4000.xml

How is it Uneeded data>?

[suicidity]

The way you're saving it as a simple x,y,z format doesn't seem as daunting. But you have no information about the nodes or anything(ID, possible weight?)

[luciferc]

The nodes when loaded are done via Binary Search and no idea why they need id's other than just their List Array indexs

[suicidity]

I've gotten my pathing down to a basically skimmed down bot version of Dijkstra's algorithm.

Instead of some generic Dijkstra's plotting, It uses simple X,Y,Z coordinates and depends on Distance; If the nodes are not within a defined distance it ignores them and counts them as not being connected.

But basically you call my function and give it the list of nodes, the destination, your current position, the desired distance from the destination and the distance between nodes. It will first initialize by choosing the destination node, being the closest to the target (If there is one within the desired distance for it); Then scrolls from the player choosing the best options depending on Distance and a Generated weight(weight being the total average distance between all available nodes, to the current node).

or in the form of a code snippet : tD being a Float, Distance() is just a function that calculates the distance between 2 points (a²+b²=c²)

For i As Integer = 0 To list.Count
    totalDistance += Distance(i.Coordinate, node.Coordinate)
Next

It will black list any nodes chosen by removing them from the list, until it has a path.

Once it has a list once nodes that leads to the destination nodes, it returns the list; Or doesn't if there is no viable path.
--

Simple and kind of dirty, but Like I said; It's great for a bot when distance is always going to be taken into account. The idea is to have a pathing system that is precise, You don't want it attempting to travel distances of thousands of units in-game, in a straight line; You'll run into objects doing that.

So just make sure the nodes are within distance of each other.

It also generates paths without having to connect every node to surrounding nodes (Dijkstra's algorithm doesn't do that, as it takes into account what nodes are connected); Which I find very beneficial. Benchmarks also put this at generating a path @ 2-100 ms / 5000 nodes. So it's not too bad, and it's as precise as your mapping.

[Apoc]

    [Serializable]
    internal class Region2D
    {
        /// <summary>
        /// Initializes a new instance of the <see cref="T:System.Object" /> class.
        /// </summary>
        public Region2D(RegionFlags flags, double regionWeight, RegionPoint ne, RegionPoint nw, RegionPoint se, RegionPoint sw, ulong id, string customName)
        {
            Flags = flags;
            RegionWeight = regionWeight;
            NE = ne;
            NW = nw;
            SE = se;
            SW = sw;
            ID = id;
            CustomName = customName;
        }

        /// <summary>
        /// Initializes a new instance of the <see cref="T:System.Object" /> class.
        /// </summary>
        public Region2D() {}

        /// <summary>
        /// Flags hold specific information about this node. 
        /// </summary>
        /// <value>The flags.</value>
        /// 1/23/2009 4:48 PM
        [XmlAttribute("F")]
        internal RegionFlags Flags { get; set; }

        /// <summary>
        /// Gets or sets the region weight.
        /// </summary>
        /// <value>The node weight.</value>
        /// 1/23/2009 4:48 PM
        [XmlAttribute("W")]
        internal double RegionWeight { get; set; }

        /// <summary>
        /// Gets a value indicating whether this instance has a road texture.
        /// </summary>
        /// <value>
        /// 	<c>true</c> if this instance has a road texture; otherwise, <c>false</c>.
        /// </value>
        /// 1/23/2009 4:48 PM
        [XmlIgnore]
        internal bool HasRoadTexture { get { return (Flags & RegionFlags.Road) == 0; } }

        /// <summary>
        /// Gets or sets the North East point of this region.
        /// </summary>
        /// <value>The NE.</value>
        /// 1/23/2009 4:48 PM
        [XmlElement("NE")]
        internal RegionPoint NE { get; set; }

        /// <summary>
        /// Gets or sets the North West point of this region.
        /// </summary>
        /// <value>The NW.</value>
        /// 1/23/2009 4:49 PM
        [XmlElement("NW")]
        internal RegionPoint NW { get; set; }

        /// <summary>
        /// Gets or sets the South East point of this region.
        /// </summary>
        /// <value>The SE.</value>
        /// 1/23/2009 4:49 PM
        [XmlElement("SE")]
        internal RegionPoint SE { get; set; }

        /// <summary>
        /// Gets or sets the South West point of this region.
        /// </summary>
        /// <value>The SW.</value>
        /// 1/23/2009 4:49 PM
        [XmlElement("SW")]
        internal RegionPoint SW { get; set; }

        /// <summary>
        /// Gets or sets the ID of this region.
        /// </summary>
        /// <value>The ID.</value>
        /// 1/23/2009 4:49 PM
        [XmlAttribute("ID")]
        internal ulong ID { get; set; }

        /// <summary>
        /// Gets or sets the custom name associated with this region. (This is not mandatory, and is usually
        /// omitted. Used for specialized weighting)
        /// </summary>
        /// <value>The name of the custom.</value>
        /// 1/23/2009 4:49 PM
        [XmlAttribute("N")]
        internal string CustomName { get; set; }

        #region Nested type: RegionFlags

        /// <summary>
        /// Simple flags to show what type of node this is. If it has any types of specific flags.
        /// </summary>
        [Flags]
        internal enum RegionFlags : uint
        {
            /// <summary>
            /// Normal node. Fully passable, no obstructions or extra weighting.
            /// </summary>
            Normal = 0,
            /// <summary>
            /// This node falls on a road.
            /// </summary>
            Road = 0x2,
            /// <summary>
            /// This node is part of a liquid area. (Water/lava)
            /// </summary>
            Liquid = 0x4,
            /// <summary>
            /// This node has an object that can be jumped over.
            /// </summary>
            JumpableObject = 0x8,
            /// <summary>
            /// This node is partially blocked, but still passable. (Small tree for example)
            /// </summary>
            PartialBlock = 0xC,
        }

        #endregion


        /*
         
         Omitted some simple utility methods used for Distance, etc.
         I'm sure you can do the math and add the stuff here.
         
         */
    }

    [Serializable]
    internal struct RegionPoint
    {
        [XmlAttribute("X")]
        internal float X;

        [XmlAttribute("Y")]
        internal float Y;

        [XmlAttribute("Z")]
        internal float Z;
    }

Fairly simple 2d region class. (I use this for most of EK/Kalim)

Also note, nearly all the information is stored as attributes, which greatly cuts down on file size. There's 1 main node for each region, then 4 inner nodes for the 4 points of the region. So... a total of 5 nodes per region. Which is something like 350 characters. Save it as Unicode, and you cut your file size in half.

The 3D version of the class, simply has another 4 RegionPoints.

If you think about how you're saving the data, (in this case, using 1-2 letter names for attributes and elements) you greatly cut down file size, and serialization speed.

You can even implement a binary reader if you want, but I never found the need to do so.

[suicidity]

Just a debug screen shot of my progress; This show the listing of the nodes / The pathingMap that shows current nodes around the players position.

Much like the Openbot mapping.



I also ended up saving in XML, simply because it ended up being easier. I deprecated things like IDs and such from the XML, the bot generates the IDs and such values when loading.

[luciferc]

Ha Xml ftw :P Easyness x 24

I just worked out my Pathing Algo i made it in the Shower.. Its my thinking place lol

Ur bot looks nice thu