A breakdown of OSRS pathing

Discuss anything and everything about PkHonor.
Raj
Developer
Posts: 2618
Joined: Sun Dec 30, 2018 2:50 am

A breakdown of OSRS pathing

Post by Raj » Wed Jan 01, 2020 9:00 am

Ok boys happy new year lets get it




Observations:
Two man-looping is possible (Vid 1, 0:06)
Following or attacking someone paths to the tile they were standing on last (vid 2)
A "destination update" occurs on each click, or each time you're following someone who updates their tile (vid 1 0:06, vid 1 0:40)
On each destination update, the moving players "last tile" is set to the last tile they were on (the second to last tile in their path - on a 2-tile path it's the first tile the walker was on, for 3+ it's the second to last, if that adds any clarity. Like if you think of the path as a sequence of tiles it's the second to last member of the sequence you need to use)(edit: you can simplify this calculation to one tile in the opposite direction of their last movement).

My breakdown of the follow/attack algorithm (for Player B following Player A):
Player B clicks "follow/attack Player A"
Each game tick, check and save Player A's "last tile", unless player B clicks off to unfollow or gets in range to attack player A
On the next tick, path player B to that tile (seems delayed but tbh OSRS itself feels delayed when you look at the vids).
Update player B's last tile (on the same tick player B was pathed and moved).

My breakdown (read: guess) of the pathing algorithm:
Spoiler: show
I read BFS works straight up if you create a graph with edges between any tiles you can walk between. Kind of a pain and idk how viable it is to convert the map to a graph, but I guess in some sense it already is a graph so maybe there's a way where you can just iterate over the map data directly substituting coordinates for vertices and treating a lack of walls/obstacles as an edge. I feel like a recursive or dynamic programming solution is the efficient way (subproblem structure and whatnot) but I really cba because it takes a lot of effort to sit there playing with and analyzing pathing algorithms and I'm not even sure this will be useful at all.
Specifics aside our pathing algorithm in terms of point to point is just fine as far as I can tell (except near trees but it very well could be making optimal paths in that case and I'm just an idiot), I think the biggest disparity is the way it works when you are following or trying to attack someone, I don't PK but I remember L0Ling at Niels' vid of running rectangles while attacking someone because it was following their path tile-for-tile.

Now TBH I'm not sure if there are any actual benefits to the OSRS way but people have never not complained about PKH pathing so maybe if we can copy them all the way or at least take the good parts (like constantly updating the destination, or at least when there's a good reason to, such as a destination update) then maybe we can find out exactly where the issue is or get rid of it. That's all thanks for your time feel free to contribute or correct anything.
Last edited by Raj on Sat Jan 25, 2020 7:28 pm, edited 2 times in total.

User avatar
Iron adam
Event Coordinator
Posts: 11693
Joined: Sun Aug 24, 2014 6:07 am
Contact:

Re: A breakdown of OSRS pathing

Post by Iron adam » Wed Jan 01, 2020 4:42 pm


Raj
Developer
Posts: 2618
Joined: Sun Dec 30, 2018 2:50 am

Re: A breakdown of OSRS pathing

Post by Raj » Wed Jan 01, 2020 7:10 pm

Iron adam wrote: Wed Jan 01, 2020 4:42 pm W00t viewtopic.php?f=67&t=74800
you give me confidence that this post is on the right track and also confidence that this will never get looked at fack

User avatar
Iron adam
Event Coordinator
Posts: 11693
Joined: Sun Aug 24, 2014 6:07 am
Contact:

Re: A breakdown of OSRS pathing

Post by Iron adam » Wed Jan 01, 2020 7:11 pm

Pvm porn wrote: Wed Jan 01, 2020 7:10 pm
Iron adam wrote: Wed Jan 01, 2020 4:42 pm W00t viewtopic.php?f=67&t=74800
you give me confidence that this post is on the right track and also confidence that this will never get looked at fack
welcome

User avatar
Iron adam
Event Coordinator
Posts: 11693
Joined: Sun Aug 24, 2014 6:07 am
Contact:

Re: A breakdown of OSRS pathing

Post by Iron adam » Wed Jan 01, 2020 7:34 pm

fitting that the first post of the decade is about pathing xD

User avatar
Fungamer
Developer
Posts: 11407
Joined: Sun Jun 30, 2013 8:44 pm

Re: A breakdown of OSRS pathing

Post by Fungamer » Wed Jan 01, 2020 7:42 pm

Iron adam wrote: Wed Jan 01, 2020 7:34 pm fitting that the first post of the decade is about pathing xD
LOL+!+!!!
Image

User avatar
The underdog
Premium Donator
Posts: 6480
Joined: Sun Jan 26, 2014 11:53 pm
Location: Loc
Contact:

Re: A breakdown of OSRS pathing

Post by The underdog » Thu Jan 02, 2020 4:45 am

I haven't pathed around much at all lately but I don't remember the pathing having major issues anymore? Despite its not exactly like osrs but imo that doesn't matter as long as it works.

If it ain't completely broken don't touch it.
#Justice4Church

User avatar
Tom brady
Premium Donator
Posts: 1408
Joined: Wed Apr 10, 2013 10:22 pm

Re: A breakdown of OSRS pathing

Post by Tom brady » Thu Jan 02, 2020 4:50 am

The underdog wrote: Thu Jan 02, 2020 4:45 am I haven't pathed around much at all lately but I don't remember the pathing having major issues anymore? Despite its not exactly like osrs but imo that doesn't matter as long as it works.

If it ain't completely broken don't touch it.
If it isn’t like osrs it’s broken
FRO TIME :afro:
OPRAH!

User avatar
The underdog
Premium Donator
Posts: 6480
Joined: Sun Jan 26, 2014 11:53 pm
Location: Loc
Contact:

Re: A breakdown of OSRS pathing

Post by The underdog » Thu Jan 02, 2020 5:11 am

Tom brady wrote: Thu Jan 02, 2020 4:50 am
The underdog wrote: Thu Jan 02, 2020 4:45 am I haven't pathed around much at all lately but I don't remember the pathing having major issues anymore? Despite its not exactly like osrs but imo that doesn't matter as long as it works.

If it ain't completely broken don't touch it.
If it isn’t like osrs it’s broken
Ok make gmaul like osrs first then pathing later.
#Justice4Church

Raj
Developer
Posts: 2618
Joined: Sun Dec 30, 2018 2:50 am

Re: A breakdown of OSRS pathing

Post by Raj » Thu Jan 02, 2020 8:11 am

The underdog wrote: Thu Jan 02, 2020 4:45 am I haven't pathed around much at all lately but I don't remember the pathing having major issues anymore? Despite its not exactly like osrs but imo that doesn't matter as long as it works.

If it ain't completely broken don't touch it.
There's still some weird things like your player randomly giving up when following a moving NPC (dunno about pkplay tho but I'm saw someone complaining over the yell). I figure if we can replicate OSRS pathing then there isn't much more we can do to fix it

Post Reply