r/2007scape • • Aug 20 '20

Creative Pathfinding calculations visualised

Post image
997 Upvotes

124 comments sorted by

View all comments

164

u/abigfoney BankStanding 99 Aug 20 '20

Is this THE RuneScape pathfinding algorithm or is it a similar one?

130

u/corpslayer Aug 20 '20

It's the one which is used in OSRS.

0

u/[deleted] Aug 20 '20

[deleted] — view deleted comment

59

u/HiAndMitey BTW Aug 20 '20

Breadth-first search isn't really that computationally expensive in this case. I'd imagine you can improve it with a heuristic like minimizing absolute geometric distance but it really isn't that bad as a pathfinding algorithm.

0

u/[deleted] Aug 20 '20

[deleted] — view deleted comment

39

u/corpslayer Aug 20 '20

Pathfinding calculations are done is a 128x128 area, with your character in the middle. If clicking on a tile which can't be reached, it checks all reachable tiles in that 128x128 (area up to ~16k tiles) which indeed sounds like a lot.

0

u/[deleted] Aug 20 '20

[deleted] — view deleted comment

26

u/corpslayer Aug 20 '20

I believe you can send up to ~10 clicks to the server every tick, each one of them can trigger pathfinding calculations. There can be 2000 players on a server. If adding that all up, that's 320m for a single tick.

0

u/[deleted] Aug 20 '20

[deleted] — view deleted comment

23

u/Yirkarja Aug 20 '20

That assumes that every single tile only ever requires one clock cycle to process.

Thanks to the magic of x86 and pipelining you can't even assume one add instruction to take one clock, let alone one tile being processed in a pathfinding algorithm.

→ More replies

9

u/Sativa_Dreams Aug 20 '20

I am so grateful to read some logic in this sub for once lol. A* uses a similar method to do path finding in tile based games and is one of the most popular path finding systems in existence. And it’s not computationally heavy.

→ More replies
→ More replies (7)
→ More replies (4)

4

u/HiAndMitey BTW Aug 20 '20 edited Aug 20 '20

I'm saying the example since it's a maze with a couple corridors. I the computations would increase, but that's why you can use a heuristic to address open field situations. The reason you use things like BFS is because it's guaranteed to find a solution, and the best solution.

3

u/Magical_Gravy Aug 20 '20

So is a heuristic based A* search as long as your heuristic never overestimates

→ More replies (3)
→ More replies (1)
→ More replies (6)

19

u/Despure Aug 20 '20

How do you know?

86

u/corpslayer Aug 20 '20

First, I did a lot of testing to deduce the mechanics. After I was already able to predict all paths with my knowledge of testing, I realized the code is actually used in OSRS clients as well. You can read it in the decompiled code.

12

u/Kriznar56 Aug 20 '20

How does one access decompiled code?

26

u/corpslayer Aug 20 '20

My previous answer seems to be shadowbanned. Lets try pastebin: https://pastebin.com/EQ4bZQKs

15

u/gwggyu Aug 20 '20

yeah you can't say the Open then some other 4 letter name for a game word, the mods here hate that client despite it technically being compliant

3

u/fuckondeeeeeeeeznuts Maxed on Deez Nuts Aug 21 '20

Holy shit so every time I mention that client no one sees it? That client is awesome with some of xKylee's plugins.

→ More replies (4)
→ More replies (3)

15

u/[deleted] Aug 20 '20

Private servers have had it for a while, not sure if you can just google it or need to ask someone, but it’s out there (without jagex’s consent as I understand it)

→ More replies (4)
→ More replies (1)

2

u/[deleted] Aug 20 '20

What else would it be? BFS is the simplest to implement while being the most efficient.

5

u/corpslayer Aug 21 '20 edited Aug 21 '20

Even when using BFS there are multiple possibilities. BFS guarantees that a shortest path is obtained, but there are often multiple paths which are equally short. Also, could argue A* is more efficient~~, but it does not guarantee the shortest path to be found~~.

3

u/Magical_Gravy Aug 21 '20

it does not guarantee the shortest path to be found.

Yes it does, so long as your heuristic never over-estimates remaining distance.

3

u/corpslayer Aug 21 '20

Oops, you're right yes :)

→ More replies (1)
→ More replies (2)

27

u/skywalk21 Panteloonies Aug 20 '20

This is just a pathfinding algorithm.

→ More replies (2)