Welcome to TRiBot Forums

Register now to gain access to all of our features. Once registered and logged in, you will be able to contribute to this site by submitting your own content or replying to existing content. You'll be able to customize your profile, receive reputation points as a reward for submitting content, while also communicating with other members via your own private inbox, plus much more! This message will be removed once you have signed in.

laniax

AdvancedWalking - next gen navmesh pathfinder/walker. [Source]

61 posts in this topic

Info

Hey guys! Decided to post a thread for a project i have been working on for the past few weeks, i call it AdvancedWalking. It's a new approach to something that has been bugging me ever since i started using Tribot. It has some pros and cons which i will try to explain below!

 

What do you mean with 'next-gen'?

AdvancedWalking its purpose is to replace WebWalking.

 

Then what is 'WebWalking' and how does it work?

Well glad you asked! Currently Tribot and all other major OSRS bots use a similar walking method to walk common (long) distances. The method they use is called WebWalking. What that basically means is they draw a 'web' of points and lines all over the runescape worldmap. And when a script wants to walk from say Lumbridge to Falador, a route is calculated using the least amount of points and lines to get to the destination. This is a good system so that scripts can simply say 'walk to falador!' from anywhere and by traversing the web they will get there.

 

Whats wrong with WebWalking if it already does the job?

While WebWalking is a great system, it does have its flaws. First, if a destination is 'off the web', the result is unstable. It might run as far as it can and then stop, or it might just run circles around the destination (i'm looking at you Draynor Manor) or have other unexpected behavior, this is increasingly annoying when navigating in houses/cities where precision walking is needed.

Next there is also efficiency, It will always walk over the 'web', meaning that it might take a significant detour in some cases instead of just running from A to B. This also brings another problem, because all the bots run over the same web, it is not very good for staying undetectable to jagex. If thousands of bots run over the same set of dots and lines, it's bound to stand out right? (This is detectable by Jagex using LCP detection, I've written more about that here).

 

So why is AdvancedWalking different?

Instead of using a 'web' of dots and lines, i created a system that uses a large number of polygons that together form a 'mesh'. This allows for much more precise movement, but more specifically, it will allow players to take the absolute shortest path from A to B, even over very long distances! And since every player will take their optimal (human-like) route, it is much more anti-ban friendly!

 

Then i also want to give the power back to the scripters, WebWalking currently has no support to 'get' the generated path and use your own walking methods, or just 'get' the location of the nearest bank instead of only walking there.

 

And it doesn't stop there, i am adding support for (all) agility shortcuts and teleports to really optimize the path!

 

Alright, cool. But what are the cons?

As i mentioned there are some cons to AdvancedWalking that WebWalking doesn't have. First, since AdvancedWalking isn't included in the client, the navmesh data has to be downloaded and kept up to date. This is done automatically, but there will be a download going on if the mesh has updated. Also (because it isn't included in the client) the navmesh object has to be 'build' whenever a script has started. Now during testing this is instant. But i imagine when the mesh has become exponentially bigger the load time might take a few seconds, i will do everything i can to minimize this though.

And finally, the 'biggest' con is that generating a path through hundreds of squares is slightly more CPU intensive then generating it over lines and dots. But results so far have proven this difference insignificant.

 

 

Features

  • Replacement/Alternative to WebWalking.
  • Precision/shortest route walking.
  • Door/gate/stairs support.
  • Teleport support.
  • Agility Shortcut support.
  • Scripter friendly.
  • Can be used as a pathfinder only.
  • Optional: fallback to WebWalking if it somehow fails.

 

Currently working on:

  • MapJump support (going up/down stairs, teleports, shortcuts etc).
  • Walking algorithm

 

Technical limitations:

  • Currently the mesh is generated by running around ingame with a script running. This could be automated by reading the RS cache and decrypting the mapdata using the XTEA keys that the server send to the client. I hope @TRiLeZ might give me a hand here.

 

 

Source code:
The main AdvancedWalking repository that scripts can use (when it's done). This contains absolutely no code regarding the creation of the navmesh, since that data will be downloaded and kept up-to-date instead.
https://github.com/Laniax/AdvancedWalking

Then we have the Generator. This project takes runescape tile/map data as input, and poops navmesh data as output. This is the data that the main repository will download. As a scripter you do not need this inside your script.
https://github.com/Laniax/AdvancedWalking-Generator

Then we have the Collector. This is a script that can run inside the game to collect tile/map data (WIP). In other words, this project will collect the input data for the Generator.
As a scripter you do not need this inside your script.
https://github.com/Laniax/AdvancedWalking-Collector

 

I have created a 'mesh viewer' which you can view here.

I'm also keeping an album of screenshots i take during development, for those interested they can check it out here.

I have some javadocs available here for anyone curious.

 

and i also made a quick comparison video with webwalking.

 

If there is enough interest i will create a small infographic to explain everything. And hopefully show some code on github soon!

 

Cheers!

Edited by laniax
32 people like this

Share this post


Link to post
Share on other sites

This looks really promissing  :D Will you be able to implement "dungeon" walking aswell? Since scripters have to make their own paths in dungeons/underground.

Share this post


Link to post
Share on other sites

This actually looks wonderful! I'm seriously interested in this, if you need any help generating areas feel free to message me! I think the teleporting interacting will be the most interesting, I'm assuming scripters will be able to disable this? Also, if it checks for teleports in the bank once and can't find any tablets/runes, would it automatically disable it for the rest of the runtime of the script? Or would this has to be done by the script?

 

I'm interested in the code if you're willing to show any of it :)

Share this post


Link to post
Share on other sites

Sounds like a LOT of work. Even without adding in the additional features. Good luck though.

Edited by Flamo353

Share this post


Link to post
Share on other sites

Sounds like a LOT of work. Even without adding in the additional features. Good luck though.

 

It would be bloody helpful though

Share this post


Link to post
Share on other sites

This looks really promissing  :D Will you be able to implement "dungeon" walking aswell? Since scripters have to make their own paths in dungeons/underground.

 

Yes that is already supported. Most dungeons are on the regular 0 plane and would just be the same as a teleport. Only thing that won't work are areas with dynamic coodinates, like pest control and other 'instances'.

 

This actually looks wonderful! I'm seriously interested in this, if you need any help generating areas feel free to message me! I think the teleporting interacting will be the most interesting, I'm assuming scripters will be able to disable this? Also, if it checks for teleports in the bank once and can't find any tablets/runes, would it automatically disable it for the rest of the runtime of the script? Or would this has to be done by the script?

 

I'm interested in the code if you're willing to show any of it :)

 

Teleports can be disabled by the scripter. If they are enabled, the script has the ability to run to the bank and make a cache of all the teleports we have available, so that it can pick them up if it needs them (provided running to the bank and doing the teleport is faster then just walking to the destination). If most scripters adopt AdvancedWalking i want to add a cache of the bank items in the tribot folder as well, so that we dont have to run to the bank to check for everything. 

 

Code will be available on github as soon as i properly finish the multi-plane support.

Share this post


Link to post
Share on other sites

Yes that is already supported. Most dungeons are on the regular 0 plane and would just be the same as a teleport. Only thing that won't work are areas with dynamic coodinates, like pest control and other 'instances'.

 

 

Teleports can be disabled by the scripter. If they are enabled, the script has the ability to run to the bank and make a cache of all the teleports we have available, so that it can pick them up if it needs them (provided running to the bank and doing the teleport is faster then just walking to the destination). If most scripters adopt AdvancedWalking i want to add a cache of the bank items in the tribot folder as well, so that we dont have to run to the bank to check for everything. 

 

Code will be available on github as soon as i properly finish the multi-plane support.

Good luck with your project, you are absoulutely right when you say that the walking methods are quite limited. I look forward to your solution if it is viable, keep us updated!

I'm not quite familiar with nav meshses, but I know Honorbuddy (WoW bot) uses navmeshes for their navigation and I have to say, their navigation worked quite well for me to level up from 1-85 from different type of continents

Share this post


Link to post
Share on other sites

This is really nice man. Very good you are focussing on walking, since it's a major part of most of the scripts. And also, as you mentioned, the current walking methods are sometimes inaccurate and limited.

Seems like you've come pretty far already!

I'm looking forward to the end-result!

Share this post


Link to post
Share on other sites

So a quick update for you folks.
 
I created a quick comparision video of Advancedwalking and WebWalking both walking from Lumbridge to the GE.
Don't mind the shitty quality and all, i didn't really want to spend a lot of time on it, its just to give u guys an idea.
 


 
I hope to clean up some stuff and upload the script to the repository tomorrow, its still a WIP so of course there will be some stuff missing but the main things should be working.
Cheers guys!
3 people like this

Share this post


Link to post
Share on other sites

Thank you for making this open source, really do appreciate it.

Edited by modulusfrank12
1 person likes this

Share this post


Link to post
Share on other sites

I literally just came to this forum to suggest a more advanced WebWalking solution. I can't wait to use this.

 

Best of luck!

Share this post


Link to post
Share on other sites

I've been trying to understand navigation meshes, but I can't quite grasp it. So what you do is define a "Walkable" area, and you can transverse that area using A* or a similar algorithm, but how does navigating between meshes work? And how will you handle ladders/teleports and the like, where one area isn't physically adjacent to the other?

 

@laniax

1 person likes this

Share this post


Link to post
Share on other sites

I've been trying to understand navigation meshes, but I can't quite grasp it. So what you do is define a "Walkable" area, and you can transverse that area using A* or a similar algorithm, but how does navigating between meshes work? And how will you handle ladders/teleports and the like, where one area isn't physically adjacent to the other?

 

@laniax

 

I'm also wondering about this. Adding to that, what path finding algorithm are you going to use? How are you going to implement the algorithm? What's the best/worst/average case runtime?

Share this post


Link to post
Share on other sites

I've been trying to understand navigation meshes, but I can't quite grasp it. So what you do is define a "Walkable" area, and you can transverse that area using A* or a similar algorithm, but how does navigating between meshes work? And how will you handle ladders/teleports and the like, where one area isn't physically adjacent to the other?

 

@laniax

 

Each rectangle defines an area where the player can walk inside without obstacles. trees and stuff arent seen as an obstacle since RS itself runs around them, but walls/fences are. These rectangles can lie adjucent to eachother, but that doesn't mean that they can be travelled to one another. Think about having 2 rectangles against eachother but with a wall in between.

 

So i created a link object which is calculated/added inside every rectangle on the tiles that are actually safe to travel between. This way i can also make a link for a rectangle that is not really adjucent but actually a ladder or something.

 

 

I'm also wondering about this. Adding to that, what path finding algorithm are you going to use? How are you going to implement the algorithm? What's the best/worst/average case runtime?

 

A path is generated using Dijkstra's to check the route of 'links' we can take with the lowest cost, cost is atm determined by distance to the destination. I dont have detailed runtime statistics yet but Im putting some code online tonight if it is not clear enough :)

Share this post


Link to post
Share on other sites

Each rectangle defines an area where the player can walk inside without obstacles. trees and stuff arent seen as an obstacle since RS itself runs around them, but walls/fences are. These rectangles can lie adjucent to eachother, but that doesn't mean that they can be travelled to one another. Think about having 2 rectangles against eachother but with a wall in between.

 

So i created a link object which is calculated/added inside every rectangle on the tiles that are actually safe to travel between. This way i can also make a link for a rectangle that is not really adjucent but actually a ladder or something.

 

 

 

A path is generated using Dijkstra's to check the route of 'links' we can take with the lowest cost, cost is atm determined by distance to the destination. I dont have detailed runtime statistics yet but Im putting some code online tonight if it is not clear enough :)

 

I was actually talking about the growth rate in Big O notation. If you are implementing Dijkstra's algorithm, make sure to use a min-priority queue to achieve the lowest time cost.

 

If you have many links within each rectangle, you may come across problems where the distances to travel take a lot of time to calculate. You'll have to implement some optimizations to prevent that.

Share this post


Link to post
Share on other sites

I was actually talking about the growth rate in Big O notation. If you are implementing Dijkstra's algorithm, make sure to use a min-priority queue to achieve the lowest time cost.

 

If you have many links within each rectangle, you may come across problems where the distances to travel take a lot of time to calculate. You'll have to implement some optimizations to prevent that.

 

I havent run a large Big O test yet, mainly due to my mesh constantly changing & regenerating. Currently the difference between ~100 rectangles and ~3000 rectangles results in next to no computational difference in neither best nor worst scenarios. I'm sure ill see performance differences when i properly set up some tests covering a large portion of the runescape map though. Im amidst of working on mesh/link optimizations, not only to reduce calc speed but also to reduce the size of the mesh due the downloads going on to keep it up to date.

 

I'm trying to find a solution for better distance (cost) calculations since i fear that it will eventually eat up a considerable amount of time. But that is (hopefully not ;)) a problem for a later stage.

Share this post


Link to post
Share on other sites

Right, so if I understand it properly you use Dijkstra's to decide the route of which rectangles to take, so the same as normal waypoint pathfinding and then you create a path within these rectangles? How do you give weight to each path between rectangles? Because with a large rectangle, if it's connected to several others how would you decide which is closest to the entry point of that large rectangle? if that makes any sense! Sorry for all the questions, this is just really interesting

Share this post


Link to post
Share on other sites

Right, so if I understand it properly you use Dijkstra's to decide the route of which rectangles to take, so the same as normal waypoint pathfinding and then you create a path within these rectangles? How do you give weight to each path between rectangles? Because with a large rectangle, if it's connected to several others how would you decide which is closest to the entry point of that large rectangle? if that makes any sense! Sorry for all the questions, this is just really interesting

With some math i check which tile on the edge of the rectangle is closest to the tile of the previous rectangle.

Share this post


Link to post
Share on other sites

With some math i check which tile on the edge of the rectangle is closest to the tile of the previous rectangle.

 

Alright, thanks, this sounds pretty awesome, I'd love to see it once it is complete :)

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!


Register a new account

Sign in

Already have an account? Sign in here.


Sign In Now

  • Recently Browsing   0 members

    No registered users viewing this page.