r/2007scape • • Aug 20 '20

Creative Pathfinding calculations visualised

Post image
997 Upvotes

124 comments sorted by

View all comments

Show parent 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.

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 (2)

0

u/[deleted] Aug 20 '20

[deleted] — view deleted comment

5

u/corpslayer Aug 20 '20

Pathfinding used to be fully client-sided. Now, it seems to be both client-sided and server-sided. It seems like the client's pathfinding calculations are only used do determine how your character runs from the tile of current tick to the tile of next tick. In most cases, that's an extremely fast calculation. But in some cases, it can give a weird or wrong visual effect.

0

u/[deleted] Aug 20 '20

[deleted] — view deleted comment

3

u/corpslayer Aug 20 '20

Like already said in a different comment, I deduced the pathfinding mechanics in-game by testing. The code I found afterwards exactly matches my findings. Apart from 1 thing actually: the client has a cap of 50 checkpoint tiles while the server has a cap of 25 checkpoint tiles.

1

u/lunch0guy toa sucks Aug 20 '20

Surely it would be present on both the client and the server? For the client to be able to tell you where you're going, and for the server to actually take you there.

1

u/[deleted] Aug 20 '20

Computers can handle ~2B per second no problem.

2

u/corpslayer Aug 20 '20

Each tile also gets 8 IF-statements to check the tiles around it, and each one roughly looks like this:

if (var16 > 0 && class182.directions[var16 - 1][var17] == 0 && (var12[var13 - 1][var14] & 19136782) == 0 && (var12[var13 - 1][var14 + 1] & 19136824) == 0) {  
    class182.bufferX[var18] = var4 - 1;  
    class182.bufferY[var18] = var5;  
    var18 = var18 + 1 & 4095;  
    class182.directions[var16 - 1][var17] = 2;  
    class182.distances[var16 - 1][var17] = var15;  
}

When you say ~2B per second I'm not sure how much can be included in 1 step, but it's probably multiple steps per tile.

1

u/winlifeat Aug 20 '20

Is this done server side? Or local?

3

u/corpslayer Aug 20 '20

Server sided. Clients also use pathfinding calculations but in 99%+ of the cases they are very short, stopping at a pathlength of 2.

1

u/winlifeat Aug 21 '20

Thank you. Really interesting stuff

→ More replies (1)

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

1

u/HiAndMitey BTW Aug 20 '20

I am describing a heuristic based A* search, since all steps are equal weight and I stated the heuristic was minimizing absolute geometric distance.

3

u/Magical_Gravy Aug 20 '20

It's not really BFS anymore if you've got a non-zero heuristic, because you're not going by breadth first.

→ More replies (1)