Mapping (Pathing etc.)

[luciferc]

So i read about linq and all the cool functions and i made a simple class.

//Inside of Region.cs (Holds the 500x500)
 List<MapData> myPoints = new List<MapData>(); 




///
///
class MapData
    {
        //Holds an XYZ

        [XmlAttribute("x")]
        public int x;

        [XmlAttribute("y")]
        public int y;

        [XmlAttribute("z")]
        public int z;

        public MapData()
        {
        }

        public MapData(int _x, int _y, int _z)
        {
            x = _x;
            y = _y;
            z = _z;
        }
    }

Could i seralize the List? Easily? and would it work as intented. if i did :P.

[Apoc]

Sure would, but I suggest using floats instead of ints. You'll just make your map really crappy.

[Xarg0]

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

[suicidity]

This is my progress,

http://img294.imageshack.us/img294/7...ingtestyj3.png

The red "dots" are nodes; The path is grey and starts at the representation of the player, and ends at the representation of the mob. Orange is the start to end of segments in the path, between nodes.

This is my own algorithm, using VB .NET 2008; Generated instantly in real-time.


Edit:

BTW: The "Player" is at point 500, 580; The "Mob" is at point 570, 1030. - The path generated used nodes; 1,3,6,8 and 12. 12 being point 730, 100.
So progress is being made and it's getting there.

Update:

This is a new updated function, it takes into account now un-needed nodes; If the path A->C is marginally shorter than A->B->C, it will remove node B, but only if it is within a certain set "Node-Distance". As to not cut massive corners at long paths or corners that should not be.
http://img444.imageshack.us/img444/4374/newgraphmi3.png

The only thing now is to save and load the node data.

Update:

Two different renders directly from the program, using the same data above :

http://img443.imageshack.us/img443/636/gen1nw9.png
http://img513.imageshack.us/img513/1477/gen2qq7.png

On the first there looks like it leads to no point right before the "mob's" location, but there is a point; a typo kept it from rendering though.

----
Update:

It now takes into account overall distance, another screenshot

[Cypher]

@suicidity

Are you using a pregenerated mesh or generating it on-the-fly.

If you're generating it on the fly you're probably better off using D* than whatever you're using currently (A* or Dijkstra I assume).

[suicidity]

Right now it's a pre-generated mesh for testing(So I don't have to log in when I'm coding it); But it will be saved in a static format, I haven't coded something to generate walkable surfaces yet. So it's really more like Openbot's way of saving / storing information.

I'm also not using any real algorithm to my madness, but more of a function I've cooked up that would be probably be closest to Dijkstra.

It's trimmed down to a base function that calculates depending on distance, and is on-the-fly calculations to choose the best route.
----

Also edited the post above.

[Cypher]

Ah okay, nevermind then, way too complex for your current implementation.

[suicidity]

Yeah, I didn't go A* definitely because it's to intensive computing for on-the-fly imo; And Dijkstra's was a little to harsh, so I coded something down to basically keep it as fast as possible and it would keep file-size down because I wouldn't be pre-caculating information.

This is a visual representation when my function cannot find a viable path for the given parameters (Not enough map data to get to the target)



This is where the event would be passed to deal with the mob, in terms of blacklisting, or attempting a path anyways etc.

[Cypher]

Yeah, I didn't go A* definitely because it's to intensive computing for on-the-fly imo; And Dijkstra's was a little to harsh, so I coded something down to basically keep it as fast as possible and it would keep file-size down because I wouldn't be pre-caculating information.

This is a visual representation when my function cannot find a viable path for the given parameters (Not enough map data to get to the target)



This is where the event would be passed to deal with the mob, in terms of blacklisting, or attempting a path anyways etc.

If you're having performance problems its probably because of a poor implementation, I haven't had any real performance issues with the algorithms if implemented correctly.

[suicidity]

No, I wasn't having performance problems. I just took it into mind and digested it, then thought of the best way I could do it performance wise; Stripping all the un-needed components and pulling it down to it's bare-bone structure.

Figure it's better to start with the best I can do; I wouldn't implement my method for AI pathing for a game, but it does it's job for a bot.

I could've easily used Dijkstra's algorithm, but I would be do so much unneeded processing to return a simple coordinate.x / y path.

EDIT: My method generates in .09-4ms; So it's really fairly low processing time.

[Cypher]

I'd much prefer having high-accuracy navigation so I can go AFK without having to worry about getting stuck etc.

(Which is why I'm leeching GreyNav )

[Xarg0]

I'd much prefer having high-accuracy navigation so I can go AFK without having to worry about getting stuck etc.

(Which is why I'm leeching GreyNav )

Give teh GreyNac plx!!!!!!!!!!!!!!1111111oneoneeleven

No realy, I'd like to get a hold of it, but I'm pretty sure you wont give it to some random guys just because they beg you ^^
How did you get it anyways? I tought Greyman kept it 100% private

[Cypher]

Give teh GreyNac plx!!!!!!!!!!!!!!1111111oneoneeleven

No realy, I'd like to get a hold of it, but I'm pretty sure you want give it to some random guys just because they beg you ^^
How did you get it anyways? I tought Greyman kept it 100% private

Caus Greyman and I are good friends. Also, you're more likely to get a date with Jessica Alba and Megan Fox and have them hook up for your amusement than you are to get me to leak you GNav.

[suicidity]

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..

[Apoc]

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..

Mob/road weighting, full flightpath support. The entire world being mapped properly with very little mistakes.

Not to mention, it's incredibly fast, and efficient.

The video you saw was probably from fndude. (He was the one who created the Insect AI videos)

Also, if you implement your pathing engine properly, you shouldn't have issues with path finding. (I did a test on a 1milx1mil region area with holes placed randomly. Path from 1 corner to the other takes less than 2ms, with a barely noticeable performance hit.)

Do shit right the first time, and you'll never need to re-implement things.

Also @ Xarg0, the only reason to implement the ISerializable interface is if he's intending to change how the values are stored. (I.E: renaming X to xpos in file, etc) And that only really applies to binary serialization. (The [Serializable] attribute, and [Nonserialized], etc attributes can handle pretty much anything you should need.)