Path finding and area

From CatchChallenger wiki
Jump to: navigation, search

Most of the MMORPG use path finding. But on server is a bottleneck.

Map-with-path-finding.png

Where the client need have correct visual path, the server just need to know if it's accessible. Then group the accessible tile into area, and just check if same area improve greatly the performance. You can to add link between 2 areas to have multi display map. For CatchChallenger, just line move, not path finding to simplify some problem, and match with the game style.

Another solution can be to resolve the path on the client, and transmit it as line (vector) to the server.

Map-with-area.png

Monsters

Map-with-monster-area.png

The area can be applied on the monster, because 2 monster area can't have the same tile. The cave area is automatically generated if monsterType is here but without layer (then all walkable layer). It's registered as area 0, the other area greater than 0.

Then I put 0, 1, 2, ... into simple matrix to determine the monster collision to resolve.

Multi-path finding

Path-possible-to-the-next-block.png

In case of multiple way to pass to new zone, to the multiple pathfinding and choice the best path (less direction change and shortest path if egual)

A*, JPS+ ...

Each algo for path finding have their caracteristic, but JPS+is very interesting:

Extracted from internet

From wikipedia (Jump_point_search):

In computer science, Jump Point Search (JPS) is an optimization to the A* search algorithm for uniform-cost grids. It reduces symmetries in the search procedure by means of graph pruning, eliminating certain nodes in the grid based on assumptions that can be made about the current node's neighbors, as long as certain conditions relating to the grid are satisfied. As a result, the algorithm can consider long "jumps" along straight (horizontal, vertical and diagonal) lines in the grid, rather than the small steps from one grid position to the next that ordinary A* considers. Jump point search preserves A*'s optimality, while potentially reducing its running time by an order of magnitude