Long Distance Pathfinding

[Stuby]

I was wondering if it was possible to long distance pathfind? I was thinking of making a race style quest where npcs and and players would race given various starting locations and ending locations (vesper to yew distances). I've read through all the tile data stuff but I'm not sure the sizes of the data within the tile matrices being used. Do the matrices hold only the screen data where the mobile is located or the entire map? I also don't see where the map data is actually being read, anyone know where it exists? I tried calling just the plain static Map.AllMaps[] but the list comes back as empty.

[Arkad]

That would be cool, for guard patrols on roads or something too.

[mordero]

You wouldnt have to create true pathfinding, you could always just set up premade paths for NPCs to use.

[Stuby]

I want to make my own A* with it, I just need to know how to read the tiles as being impassable or not. I know how to check this (I think), it just needs and x and y paramter. I am not sure if the x y required is in relation to map block or to tile count. For example if I want to check tile coordinate 3000, 216 do I pass those values or 4,5 where 4,5 would be the example block relation coordinates?

[Stuby]

No more information out there?

[Suil Ban]

Look at the A* implementation already present in RunUO...

[Ray]

LongRange pathfinding is already implemented but limited to reduce serverload as its done in the main/game-thread.
However, you can remove this limt. But that can vastly decrease your servers performance, if you remove it completely.

To check for a tile as being impassable or not, take a look at the Map.CanFit method. There's everything you need. The TileMatrix itself is built out of Blocks, 8x8 tiles).
to get the block of 3000 216 you simply right-shift them by 3.

GetLandBlock(x >> 3, y >> 3)[((y & 7) << 3) + (x & 7)];

whereas the blue part gets the block and the green part gets the Tile out of the returned array.
However, CanFit() already does that.



For those of you who are up to greater things:
In fact, pathfinding would be a perfect place for multithreading because it could be easily separated to run in a thread -> theres only 1 input (starting position) and only 1 output (path to destination) without any steps between them. By using a multithreaded approach, the path could be as long as you need it, even across the whole map.

Theres only 1 backdraw: blocked positions, like dynamic items or mobiles, can change at any time. Theres currently no real way to get them checked in a threadsafe manner. Map and Statics are not the problem, but dynamic entities are. And blocking both threads with a lock() statement would be gross.

So you can either leave them unnoticed (only check for map and statics)
or
use a 'checkpoint'-approach. (the thread searches the whole map ans statics, but doesnt return a step-by-step path, instead it retuns every 10th step to be processed by the default wayfinding)
or
do some sort of a shadow-bit-map for the pathfinding-thread that updates occasionally (using 'Sector' to spy out when it should be refreshed).

Just some thougths. If i had the time, i'd probably go with the last one.

Good Luck!