Intelligent conversation

#21

[quote=“T4_, post:20, topic:410034”][quote author=Moparisthebest link=topic=511300.msg3711265#msg3711265 date=1313364057]

Fair enough, C does seem to be less completely full of hidden pitfalls than C++.

But again, there is no reason to choose to use them, so why offer the choice? Then there is also the fact that many times you aren’t working on 100% your own code, you are using other’s code or 3rd party libraries, and figuring out what they are doing and converting back and forth with how you need to do it becomes a bit of a nightmare, that could have been altogether avoided.
[/quote]
example: RuneScape is forced to use signed integers for item amount value - unsigned integers would allow a larger stack of items and disallow them from ever becoming negative.[/quote]I was gonna say… yea… didn’t semaphore post something a while back about some (un)signed int bug in RS which allowed him to have negative GP?

#22

[quote=“T4_, post:20, topic:410034”][quote author=Moparisthebest link=topic=511300.msg3711265#msg3711265 date=1313364057]

Fair enough, C does seem to be less completely full of hidden pitfalls than C++.

But again, there is no reason to choose to use them, so why offer the choice? Then there is also the fact that many times you aren’t working on 100% your own code, you are using other’s code or 3rd party libraries, and figuring out what they are doing and converting back and forth with how you need to do it becomes a bit of a nightmare, that could have been altogether avoided.
[/quote]
example: RuneScape is forced to use signed integers for item amount value - unsigned integers would allow a larger stack of items and disallow them from ever becoming negative.[/quote]

Maybe my mind is a bit simple, but I don’t see that as a pitfall. They are using 4 bytes, which means they can store 0xffffffff values, regardless of sign. They could easily have treated the four bytes as an “unsigned integer” by converting it to a long-integer not applying the signed byte, thereby allowing them to have the range of [0, 0xffffffff] values, rather than [-0x80000000, 0x7fffffff]. It doesn’t matter how they persist the value, nor how they send it over the network. 4 bytes is 4 bytes regardless of endianness or signing. How they treat it is per-choice. Even in Java, they could have gotten around the limitation you see, if they so had wanted.

#23

[quote=“mutex_, post:21, topic:410034”][quote author=T4_ link=topic=511300.msg3711346#msg3711346 date=1313367791]

example: RuneScape is forced to use signed integers for item amount value - unsigned integers would allow a larger stack of items and disallow them from ever becoming negative.
[/quote]I was gonna say… yea… didn’t semaphore post something a while back about some (un)signed int bug in RS which allowed him to have negative GP?[/quote]

I read that once and it sounded a bit far-fetched… I mean, he /does/ talk to pplsuqbawlz, right? :rolleyes:

#24

Is it really any more far fetched than 0 of a non stackable item?

#25

I’ve got one for you…

Why are map navigation techniques still stuck in the Stone Age. Pathfinding is widely considered to be “solved” in the sense that it’s an extremely mature field, yet you still see everyone hardcoding waypoints into their scripts.

Raycasting > Navigation meshes > Waypoint Graphs > What the RS2 botting community is doing now.

In other words, how can you be so concerned about things like moving a mouse realistically when you can’t even navigate the map reliably?

#26

[quote=“unlimitedorb, post:25, topic:410034”]I’ve got one for you…

Why are map navigation techniques still stuck in the Stone Age. Pathfinding is widely considered to be “solved” in the sense that it’s an extremely mature field, yet you still see everyone hardcoding waypoints into their scripts.

Raycasting > Navigation meshes > Waypoint Graphs > What the RS2 botting community is doing now.

In other words, how can you be so concerned about things like moving a mouse realistically when you can’t even navigate the map reliably?[/quote]Because the public bot developers are fucking morons, not unlike the moparscape scene.

#27

wat

#28

[quote=“frank_, post:27, topic:410034”][quote author=unlimitedorb link=topic=511300.msg3715059#msg3715059 date=1313586651]
Raycasting > Navigation meshes > Waypoint Graphs
[/quote]
wat[/quote]

From the bottom to the top:

1.) The RS2 botting community currently hardcodes waypoints into their scripts. Suppose you’re trying to get from lumbridge to draynor - a set of visible tiles are selected along the path from lumbridge to draynor as waypoints that the bot walks along. Sometimes bots will give them a degree of freedom i.e. it can deviate some amount of walking space from the actual tiles.

This is bad for a number of reasons including the bot can easily get stuck along a path if the degree of freedom encompasses an obstacle (requiring revision to the waypoints selected). Also, each tile must be hand selected for each and every script made.

2.) Waypoint graphs - the next step up from what the botting community does now is to treat tiles you can walk on as a graph problem i.e. select a number of tiles and use them as vertices in a graph data structure to perform a pathfinding algorithm on. A* not only works with grid problems but graph problems as well!

This is good because we can dynamically determine a relatively good path from Point A to Point B and depending on the number of vertices we have in our graph, we can make it quite optimal and there’s no need to update/hardcode tiles into the script once the graph is set up.

This is bad because depending on how few vertices we have representing walkable areas, we get “zigzag” behavior. While it’s possible to smooth this behavior by using a spline, this doesn’t guarantee that the bot won’t demonstrate the “getting caught on an obstacle behavior” as before because it’s not guaranteed that the tiles outside of the graph aren’t collision areas. In addition, the more vertices we add to our graph, the more expensive it becomes to perform pathfinding on it.

3.) Navigation mesh - The next step up from a waypoint graph (and ironically easier to implement) is describing the walkable landscape as a series of convex polygons with a few additional attributes e.g. height. Also, I’m sure the client has a collision map of some sort in the cache, so its possible to generate a navmesh from that. There are quite a few good documents out there that’ll explain it better than me and even some tools that automate the task of creating navmeshes! So I’ll leave that up to you to research.

4.) Raycasting - when I say raycasting I use it in the sense that we treat the land as a series of objects we have to avoid and we cast a ray to see if it hits an object, if it does, we avoid it. Using this, coupled with learning techniques, the bot can explore any area regardless of updates and learn the land dynamically.

The only bad thing about it is that its expensive to do. There’s no rule saying it can’t be coupled with another approach like a navigation mesh, though…

#29

What’s wrong with using say Dijkstra’s or a breadth-first search algorithm for routing when that is exactly what the client did? There is /no/ collision map “stored in the cache”, collision maps are dynamically built from analyzing decoded map and landscape files. The client does (did?) however have a class that encapsulates such a map and I’ll bet you can find it in older clients with a quick search for “noclip”.

#30

Nothing is wrong with it. In fact, a pathfinding algorithm is an essential part of using both waypoint graphs and navigation meshes. The problem comes when you’re trying to get from point A to point B and the pathfinding algorithm doesn’t have any notion of what collision is. Yea, you could use a collision map and start tinkering around with your idea until you basically reinvent the concept of a navigation mesh…

I’m not balls deep in the client source so I’ll take your word on how the map is stored lol.

#31

They map is streamed from the server nowadays, so you’ll only get info about currently loaded regions.

#32

No they aren’t… I mean maps and landscapes are streamed from the update server, of course; that’s how you download all of those resources. You store them in a local repository on-disk to cache them though. What the server does now with landscape files is send you 128-bit XTEA keys for every 64x64 landscape file it requests you to load, as they’re encrypted. Landscape files encode object locations and orientations, btw.

#33

The devil is in the details.

Then just force the client to load different regions automatically, or walk around the world keeping track of the regions you already have. Worst case scenario, you end up mapping it out yourself…

#34

[quote=“unlimitedorb, post:25, topic:410034”]Raycasting > Navigation meshes > Waypoint Graphs > What the RS2 botting community is doing now.[/quote]Probably because 99.9% of the RS2 botting community has failed to realize how to utilize their algebra and geometry for use with these kind of situations. Honestly, I am in that 99.9% because I don’t take the time to find similarities with mathematics and things like “raycasting” and “navigation meshes”.

#35

elaborate more on your ray casting, because it seems to just be steering, which is a non-issue in runescapes click-to-move

hierarchical a* is the best suited algorithm i have seen to date for pathfinding in runescape

#36

The only reason you should be raycasting for pathfinding is if your algorithms can’t account for dynamic paths or if you’re navigating blind or unknown terrain.

This doesn’t apply to rs2 (yet) so what frank said.

#37

http://www.ai-blog.net/archives/000152.html
I just read up on navigation meshes to get a rough idea of it.

In a game where a coordinate-system is used, what good will it do to a botting client? unlimitedorb, today’s leading bot clients are probably already using your second method.

High precision walking graphs are generated by combining automatically gathered collision map data with tile textures processed by classification algorithms using Bayesian statistics.
#38

haha oh wow, FOR SOME REASON THAT DIAGRAM LOOKS REALLY FAMILIAR

cough super

#39

You can always use a simple whole-world map containing all obstacles larger than X tiles (the ones you need to predict) and plot a rough course using that, then for each loaded region just have it find a path to the farthest loaded point on your rough path

PS. after having written this i realized all i did was describe a LOD system facepalm

#40

[quote=“frank_, post:38, topic:410034”][quote author=Rix_ link=topic=511300.msg3728276#msg3728276 date=1314452846]

[/quote]
haha oh wow, FOR SOME REASON THAT DIAGRAM LOOKS REALLY FAMILIAR

cough super[/quote]

What exactly did I do? The diagram on the page looks like it was done by some sort of graphics designer, so I don’t think I even /possibly/ could have made it…

[quote=“peterbjornx, post:39, topic:410034”][quote author=Speljohan link=topic=511300.msg3715351#msg3715351 date=1313603322]
They map is streamed from the server nowadays, so you’ll only get info about currently loaded regions.
[/quote]

You can always use a simple whole-world map containing all obstacles larger than X tiles (the ones you need to predict) and plot a rough course using that, then for each loaded region just have it find a path to the farthest loaded point on your rough path

PS. after having written this i realized all i did was describe a LOD system facepalm[/quote]

A level-of-detail system where you adjust the granularity of map areas as needed is exactly what one needs for this. I think frank_ said this as “hierarchical A*”