Dynamic Pathing Macro Development

[Vayeco Dynn]

This post is an "announcement" of my recent decision to create a dynamic pathing macro. Extending beyond the simple capabilities of recording and playback, this macro will allow you to pick a location to move to, and maneuver through a set of "smart" coordinates to get there.

Right now, my idea for solving this "problem" is a theoretical one, which needs to be first validated of its possibility, and then translated into MQ2's language. I am making this announcement because I know that I will be needing help over the development of this macro. Hopefully this possibility will ignite a spark in some of you macro developers out there to join the "cause".

The whole basis for this macro will lie within a prioritizing system. Every pathing coordinate placed on a given zone map will have a priority. This can be explained more easily with a simple diagram.

Take a zimple zone map. It has its pathing-related problems. Walls, rooms, doors, bodies of water, traps, etc. If you start with a zone map like this, the first step to creating a pathing system would be to place pathing coordinates on it (ignore teal squares for now, just look at black dots):

http://www.samuraiwar.com/bbs/album_pic.php?pic_id=5973


Take a moment to notice how I placed the dots. They are at key points. For example, I plotted the dots around the dangerous lava pit, and where doorways were involved, I plotted the dots right smack dab in the middle of the doorway. This ensures that when we're walking around, we don't go where we shouldn't, and we don't get stuck.

Simple enough. Now, we have to make sense of it all. The prioritizing system allows the usage of main paths, as well as connecting subpaths. One main path takes you through the whole zone, subpaths take you to more specific destinations. Think of it as a river... all streams collect into one main river. Now taking this into consideration, we also have to remember how this system is going to be used. We will find the coordinates of our target, and then find the closest pathing coordinate to our destination. We'll then follow the paths and subpaths to this coordinate, and finally, to our destination. Now, we also have to use a naming convention that is practical for the MQ2 language, and also makes some sort of sense. For now, I have just used a X.Y.Z.N system, where X is the main path coordinate handle, Y is the sub path coordinate handle, and Z is the sub-sub path coordinate handle, etc. Now, I haven't clearly thought out a way that this would work with MQ2, BUT if MQ2 can handle multi-dimensional arrays, this system would be easily converted to something along the lines of ${Coord[3][2][0]}. Now, lets refer to the following map for an example scenario:

http://www.samuraiwar.com/bbs/album_pic.php?pic_id=5974


So, how in hell would this work? Well, we'll need some examples. Remember those teal dots? They're our examples. I've labled the dots A-D for our purposes:

http://www.samuraiwar.com/bbs/album_pic.php?pic_id=5975


For starters, lets say we want to get from 1 to 5. Well, we're at 1 and our destination is 5. 5 is bigger than 1, so we're going up in the path coordinates. That means our next step is 2. Once we're at 2, our destination is still 5. 2 is less than 5, so we're still going up in the path coordinates. That means our next step is 3. So on and soforth, until we get to 5. Hooray!

Now, lets do something a little more complicated. Lets get from 1.0 to 3.2.0. We're at 1 and our destination is 3.X.X, so we have to go up the coordinate ladder, and go to 2, then to 3. Now that we're at 3, we still have .X.X to deal with, which were only renamed because they were not relevent to the IMMEDIATE step that had to be taken. .X.X are still .2.0 in our variable memories. Now we're at 3.0, and we want to get to 3.2.X, so we're going up, we're gonna go to 3.1.X, then 3.2.X. Well, now we're at 3.2.0, and our destination is 3.2.0. Hey... we're at our destination! Splendid.

What if we want to get back to 1? We're at 3.2.0, and our destination is 1. Well right now, we aren't in the same LEVEL as 1 (that being the main path of 1.0, 2.0, 3.0 etc.), so we're going to have to get to that level. We're at 3.2.0, the 0 level for the 3rd sub-level, so we can move on to the second sub-level. Had we been at say, 3.2.1, we would have to get to the .0 coordinate for our current sub-level. Why? Because ONLY THE .0 COORDINATES CONNECT TO THE HIGHER PRIORITY LEVEL. (Go ahead, take a look at the map). Right, so we're at 3.2.0, and its safe to move on to the 2nd sub-level. Our destination is 3.0 because it is in the same level as our final destination, 1.0. (If you notice, the pattern here to get back to the a higher priority levels is to keep going to the .0 coordinates for each level. So, we're at 3.2.0, our destination is 3.0, 2 is greater than 0, so we're going down the coordinate ladder. We go to 3.1.0, and then 3.0. Now we're at 3.0, and we can go to 1.0. *PHEW*

Did you get all that? If not, try reading it all over again from the 1-5 scenario. I'm a programmer, not a teacher, but I'm trying my best here to explain my reasoning.

Okay, now thats great if you want to get around town, but what if you want to get to a specific destination? Let's say we want to get to D. We'll start off by finding the pathing coordinate thats closest to D. With MQ2 in mind, we would loop through all of our pathing coordinates, and do a distance formula on each one against D, and each time we find one thats closer than the previous closest coordinate, we'd make note of it. We'd be left with the closest coordinate to D out of all of our coordinates. (May be a little sloppy, but can't think of any other way to do it). So, assuming this system works, 2.2.0 is the closest coordinate to D. Now we have to find the coordinate that's closest to us. Lets say we're at C. The closest coordinate to C is 3.1.0. Now we just go from our starting coordinate to our ending coordinate, and then to our destination, using the system described above.

Now, this system isn't planned to be perfect. There will be some situations that don't fit the norm. Lets say we're at D again, and we want to get to B. The closest coordinate to B is 3.2.0. So we'll have to go to 3.2.0 and THEN B. Doesn't that seem a little wierd? We're practically going into another room just to get to B. Because of situations like this, we'll have to plan out our coordinates carefully. This may mean that we'll have to bring triginometry or something into the mix, to find the best way to plot coordinates. But that isn't so important right now, that can be dealt with when it comes up. Right now, the focus should be on determining the possibility of this project.

Thank you very much for your time, I hope you enjoyed reading this, and I would be happy to hear if you are interested. If you are confused by something, please say so, and I will try to rewrite it in a clearer manner. Questions, comments, etc. feel free to post.

Signing out,
Vayeco Dynn

[blueninja]

Sounds interesting although mapping zones would be a lot of work. Do you have any actual zones mapped out yet? Wouldn't mind playing around a little with it to see how well it works out in practice.

As a side note, MQ2 supports multidimensional arrays, although I would probably make this a plugin rather than a macro:
/declare MyArray[10,10,10] float outer
/varset MyArray[1,2,3] 324.12

[Cr4zyb4rd]

I'm going to write multi-paragraph announcements for all of my macros starting today.

(rushes off to get back to work on feedme.mac)

[Vayeco Dynn]

I don't have the code written out yet, but I have thought through how most of it will be written. Along with include files themselves, I'll make another macro that will just plot points in a zone, where all you have to do is make a social or something and press your hotkey every time you want to plot a new coordinate. I'd like to make a thread once I have a working version released where people can post their ini files of the zones they've coordinated.

[Fippy]

Just a though but have you checked out the a* algorithm for pathing. I did some thinking about pathing about a month ago and it seemed like a 2 tier a* algoritm would do the job. By 2 tier I mean you would have two seperate grids defined for a zone. one with very large spaces which would be the major routes like the streets in a town for instance, then 1 smaller grid with more precise loc for movinf around inside buildings etc.

The laborious bit would be getting all the nodes worked but I figured the quickest way to do that would be to generate a grid of the whole zone and then 'knock out' nodes that were in obstacles etc.

You could also have a seperate list of text names along with node id's so you could path between them using descriptive phrases like if you were the West Commons and wanted to go to halas you could do

/runto "East Commons Zoneline"
/runto "West Freeport Zoneline"
/runto "PoK Book"
/runto "Halas Book"
/runto "Halas Zonleline"

I came to the conclusion that putting this into a script would be rather difficult given the limitations of MQ2 Script and a plugin would be better since I dont actually know C++ I got out a couple of books from the library and try and write it myself but thats obviously not something thats gonna happen soon.

[Vayeco Dynn]

That is interesting, but I only see one problem with that. Say you want to move to an NPC that could be anywhere in the zone... If there was a wall between 2 nodes in the path you were trying to take, then there would be a very obvious problem getting to the npc, you would keep running into the wall. I'm not really an AI programmer, so I wouldn't know how to teach it not to do that. It still is an interesting solution. I was wondering myself if there would be any 100% totally dynamic way of pathfinding through a zone... but I think there's so many exceptions, it wouldn't really be possible, or worth the time in coding effort. If you watch how NPCs go through a zone... many of them use pathing nodes. Also, the Find function uses pathing nodes as well. That's what gave me the idea for this program. I figure if its good enough for Sony, its good enough for me!

[Sparr]

nodes on opposite sides of a wall would not be connected to each other. you would path around the wall, through the nearest doorway.

[Fippy]

yeah as sparr said nodes either side of a wall are not connected so you wouldnt try to walk through it. A* is an algorithm for finding the shortest path in a list of nodes so the idea you have presented (having lists of nodes) is basically the same, its just that A* is a well developed algorithm for doing it.

I was only suggesting it as you might want to use something that has already been done many times before. No need to go re-inventing the wheel.

[SlimFastForYou]

I had actually considered making something like this. Just for the purpose of running all around. However it hasn't been the highest priority for me since my main is a wizard =p.

I'd just like to note that this could probably be done in the Macroquest language. C++ would be more elegant (because you can use classes and dont need to use /varset SomeVariable ${Math.Calc[${Something}+${SomethingElse}]}, its just SomeVariable = Something+SomethingElse;)

Using recursive functions, you can evaluate all the locations in an INI file and build the path that way. While that may take 50 or so calculations on the computer's part to figure out what the next waypoint is, that's negligable. The auto-pull macro I've almost finished makes somewhere between 300-500 calculations on each of the 10 closest mobs probably 4-5 times a pull, and it's not even noticeable lol.

Actually building the loc file would probably prove to be a pain. ShowEQ can load maps of any zone, and it knows where the locs are on the map file. Maybe it could be used to aid building the loc file (would be much faster than running to every waypoint possible and doing a /loc which the point of the macro is to avoid =) ).

I would suggest having the ini file look something like this:

Code: Select all

[1.0]
2.0=300,-200

[2.0]
2.1.0=300,-100
3.0=-200,-150

...And so on

[Fippy]

This got me interested so I did some more reading about pathing algorithms and its seems a type of A* would work quite well. The tough bit will be making the lists of nodes to path along. I am looking at the possibilty of using the in game map editor to add paths onto layer 3 but i am not sure just using the data as it appears in the map files will be possible in real time. I am think more along the lines of draw your paths ingame and then run a tool to generate a pathing file.

First job though is to code the algoritm and a path file to test it with. I reckon PoK would be a good choice to start with.

Since I am still very much a C++ noob its going to be all in macroquest script for now but if it turns out to be too slow then I guess ill have to knuckle down and learn more about C++.

[Vayeco Dynn]

nodes on opposite sides of a wall would not be connected to each other. you would path around the wall, through the nearest doorway.

So for each node, there would also be data for what nodes are connected?

Well, I'll just go look up the A* alg. Is that related to MacroQuest or is it a totally seperate subject? I'll google it for now...

[Vayeco Dynn]

Okay, I found this:

http://www.policyalmanac.org/games/aStarTutorial.htm

I think this kind of system could be easily programmed as a macro. It may have to be programmed as a plugin though, depending on whether MQ2 is "complete" enough for something of this complexity (I'm thinking mainly reading from .txt files in the EQ files).

Now, if you don't read the article (provided via link), you won't understand what I'll be saying below this point. Unless, of course, you already have a complete understanding of the A* algorithm. Anyway, I'd advise you qualify for one of those, and then read on.

For the node grid, I'm thinking a dynamic hexagon (360/6) grid (instead of a square grid) could be used, on a base 5 (EQ units) system or something small like that. This way, nodes could be generated on the fly, and a master node list wouldn't be necessary. I doubt that this particular system would be a big CPU hit, either, but I'm not totally sure. The selection method of the A* algorithm seems very efficient.

When I say 360/6, I mean starting at 5 feet away, 0 degrees (North I guess), would be the first node (from a node-selection standpoint), starting at 5 feet away, 60 degrees, would be the second, and so on until 300 was reached (360 being redundant, same as 0). These nodes would form an "imaginary" grid based on logic instead of actual coordinates. Equally as effective, however, possibly even more because of its pinpoint accuracy. If this system was repeated for each node created, a perfect hexagon grid extending forever would be created.

For the heuristic, we could try the Manhatten system, just in terms of x and y instead of left and right (refer to the link if you don't get what that) to calculate the estimated path distance remaining. This may or may not need to be changed in the future. It doesn't seem to compensate for really complicated maps, but I'm not sure.

Now, for detecting walls and stuff, there are files in the EQ directory "maps" that basically list the coords of walls and other things, in terms of line coordinates. They look like this:

Code: Select all

L 4394.0000, -1193.0000, 2587.0000,  4345.0000, -1184.0000, 267.0000,  0, 0, 0
L 4345.0000, -1184.0000, 267.0000,  4332.0000, -1181.0000, 270.0000,  0, 0, 0
L 4332.0000, -1181.0000, 270.0000,  4322.0000, -1179.0000, 272.0000,  0, 0, 0
L 4322.0000, -1179.0000, 272.0000,  4114.0000, -1367.0000, 275.0000,  0, 0, 0

This is basically what it means:

Each line in the txt file that starts with "L" lists 2 coordinates, and a RGB color in the following format:
L Y1, X1, Z1, Y2, X2, Z2, R, G, B
The 1 set of coordinates connect to the 2 set of coordinates via line, representing walls on the map.
If you look at that coordinates from line to line, notice how the most of the lines connect. That is what leads me to believe these are the walls. Also, I'm not sure if its Y,X,Z form, but that is just my guess because that seems to be the standard EQ form.

So how does this help us? We parse it, and store the Y and X variables of the coordinates of each line in an array that will be used later in the A* algorithm. When finding surrounding nodes, there will be a check to see if there is a wall in the way. It will do this by creating a line between the current node and the target node and seeing if it intersects with any of the lines that were stored in the wall array (from the map.txt file).

The only downside to this system is that it doesn't filter out small obstacles like rocks and trees and such, *but* these can be avoided with a simple check that sees if you've been blocked by something, like the one used in Hunter.mac.

There are other obstacles though listed in these files, however. For example, bodies of water and stuff. These are identifyable by their unique R G B color combination (they're blue on the map). Nodes within the boundaries of a body of water could be given a higher cost, so that they are only crossed when necessary. These would be calculated with simple coordinate geometry. I'm guessing lava pits etc. also have their own colors. These could be dealt with in a similar way, depending on the case.

Another obstacle: doors. Using /doors or directly accessing MQ2's data, a coordinate list of doors could be created, much like how the list of walls would be created. Instead though, it would use a point and radius system, where each door would be located at a certain point and a radius would surround it compensating for the door size. During node selection, if the line to the target node passed through a door, it would mark it; during execution of the actual movement script, the system would follow a set of rules for going through the door. If you wanted to, you could even check to see if you had a key for the door during the node selection process. But that would be a lot of work, only to be done if necessary.

There are still some problems... paths would have to be changed color, so that they weren't mistaken for walls. There may be huge drops that aren't mapped out in the txt files that would have to be added manually if you wanted to avoid falling off them. There also may be exceptions that just aren't coming to me right now, who knows. All of these "problems" however, are very minor, and can be dealt with.

I think this sytem is very practical and possible, and much more advanced and capable than any pathing system in MQ2 out there right now. However, I think for a project like this, it needs to be a community effort, because too many things have to be considered for a project of this nature for just one person. I would like to continue this discussion with those of you who have participated. As we continue our flow of ideas, if and when we decide a particular system is worthy of creation, I would like to do it as a community. Many heads are much better than one. So, if you are interested, please say so. I for one am definately looking forward to developing a solution to this pathing problem we face. I hope to see some others join me, not for my cause, but for ours together.

Thanks again for your time, hope you are interested!

[Vayeco Dynn]

Bump...

Any takers?

[eqjoe]

Sounds like a plugin... not a macro. You will have a lot of zone data to manage. That might be slow and cumbersome in a macro.


-j

[s0rcier]

Well having this as a plugin could be awsome ... but ouch will be fun like hell to codes!

s0rCier