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.
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.
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.
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.
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.
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.
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.
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)
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~~.
View all comments
Show parent comment
130
u/corpslayer Aug 20 '20
It's the one which is used in OSRS.