Z Coordinates ...

[Schaf]

I discussed this with him quite a bit about early january of this year - its definately possible, the nif collision meshes can be used with recast to create the required nav meshes. I also noticed WCell has a C# implementation of recast already in place that could be used for inspiration.

I think nav mesh is definately the way - Etaew's grid based system is nice for open world areas, but is limited by resolution factors (eg thin doorways) and multiple layers (required for most dungeons)

Yeah, initially it was Dinberg who brought up Recast. I talked to Domii (WCell creator) and he told me that they didn't add Recast yet (or: back then).
What needs to be done:
1) Create a recast-readable export of the nav mesh of a zone/dungeon
2) Create a nav-mesh from the exported data (with c++ recast)
3) Load this in a wrapped/ported version of detour (as far as i understood this is the pathing module) on DOL

This way we only need to port the detour module, not the whole generation etc. I could probably write a zone/dungeon to .obj file exporter... See http://www.abload.de/image.php?img=df5qf7.jpg or http://www.abload.de/image.php?img=niflightp8ju.jpg ...

Each daoc NIF file contains pathing data, for example dungeon parts have "pickee" meshs with are basically all points where you could theoretically stand on (for the client) http://www.abload.de/image.php?img=pickeeee2gzx.jpg
and citys have a "footprints" mesh, ...

@Etaew: I wrote a A* algo a few years ago but Smallhorse refused to add it Its just way too much work to setup all the waypoints... Recast is the way to go !

EDIT: turns out domiii has begun to add it to wcell but he wants to fix some problems first and it doesnt work yet

[Etaew]

Awesome, keep checking on that

[Dinberg]

I've been away for a while - any updates here? If WCell is working on the same thing, (and im assuming we are quite similar in architecture here) then perhaps we could scratch each others backs? I *might* have some programming time I can spare for this, but I would need to know what I'm getting myself in for first

[Leodagan]

Sorry to dig up this old thread...

From my research getting elevation on open land terrain could be pretty easy...

Lot's of talks about interpolation, quad nearest point to obtain a triangle that can be interpolated !

Honestly from what I remember there are not so much 'usable' interpolation/filtering solutions, "nearest neighbour" is out of question as results would be hugly, bilinear filtering which is a simple weighted averaging algorithm and have predictable behaviour (you can write your own bilinear filtering implementation that should give the same results as everyone else's algorithm) and trilinear filtering (or bi-cubic) which use a ratio constant that needs to be tuned to change the blurriness of the final result (that could be a lot less predictable than a bilinear filtering)

Simply using an image editor to change image size from 256*256 to 65536*65536 should default to bilinear filtering, I did not test anything, but I think you could merge terrain.pcx and offset.pcx then size the image to zone size, or first increase the size of both images then merge (always with ratio from sector.dat)

I don't think a graphic rendering engine could be using heavier filtering than the one I listed... (these game softwares needs to be fast, and simple to maintain !)

For collision with NIFs object that could be a lot harder to detect, work could begin around a simple barrier (like there is in camelot hills), for trees it's just plain simple they are listed in nifs.csv with a radius for collision and should have a collision on all the Z axis or just enough to prevent jumping (doesn't matter on terrains as they aren't layered, and they can't be jumped above !)

And at last for NIFs, there should be strong 3D modeling algorithms, using waypoint, or nodes grid is just a way to prevent from using game assets (which I can understand, even a triangle arrays in a 3D space needs a lot of code and maths knowledge !)
there are 2 types of NIFs, standard NIF with a "collidee" Node that is just a wireframe mesh or triangle array to implement collisions, and Dungeon NIFs (dnifs) which have "collidee" Node and a "pickee" node, pickee node looks like a floor mesh in most of dungeon...

For ppl who noticed that pets were using waypoints, I think they use "pickee" mesh which are divided in small areas (a Darkness Falls stairway DNIF have about 8 pickee meshes) so the mob/pet path must be using the center of a pickee mesh or other simpler "waypoint" like algorithm to lower compute needs on long pathing (or maybe even a full 3D pathing algorithm but that doesn't fit with 10 years old servers at the game launch...) and maybe even using those full mesh for server-side LOS checking...

At last LoS checking could be the main algorithm used for collisions too and maybe "stupid-pathing" algorithm (check LOS : OK -> move there, check LOS : WRONG -> try something else; until LOS : OK)
LoS checking can only be done by casting "Rays" (like in ray tracing algorithms) this can sound heavy but for only one point in space, and only cast when needed, it could be only "hundreds" of rays by seconds which is easily handled by any processor (ray tracing can get really fast when you don't use reflections or shadows, reduce rendering to a tiny area, ignore textures blending, etc...)
This is also the method used by any "picking" algorithm (click in a 3D scene to select object/polygons), thus casting ray could be a great way to detect collision but maybe not enough to obtain a complete pathing algorithm (at least plenty enough to detect a tree and make a mob path move for some degrees to get around)

Picking algorithm/Pickee Mesh... (Maybe it's just a guess...)

We have to keep in mind that all this data will only be kept in "wireframe" view, and only colliding objects will matter to the server (colliding objects are identified in zones manifests...) it could indeed raise memory consumption dramatically but, today, memory is way cheaper than compute power !

[Schaf]

So a while ago I made a tool to generate one fat 3d model from a zone and then i used recast to make a navmeshs from those 3d models. Then the server just uses detour to generate a path on the navmesh... This is sitting on my hdd for a while, we never implemented the logic on the server side for the NPCs to actually use it... but it works fine! (apart from one issue: all "actors" have to be the same size, so fat mobs and small mobs use the same path, fat mobs sometimes run too close to walls)


Real LOS checking (aka keeping all the zones 3d objects in ram at the same time => not possible in my opinion, it will generate too much cpu load... also you dont really know if parts of the models are opaque or invisible,... then think about animations, etc...)

[Leodagan]

Sure keeping all 3D game objects would be too heavy for memory, that's why I insist on using "collidee" and "pickee" node Meshes (pickee is most of the time a simple triangle array)

Collidee and Pickee are simple wireframe meshes ; with vertices, normals, triangles, and there is even a "center" point that could be used as a "target to get inside area", these wireframe meshes doesn't reproduce all the detailed polygons of the model at all !
And don't need lighthing, texturing, filtering and all these computing a Graphic Card must do as it's higly parallized image filtering algorithms (per-pixel shading, that mean one thread for each of the final pixel to display...)

It's an old style game engine that couldn't rely on redering engine to do collision detection (most simple/old games use different assets for drawing and for game mechanics engine, remember the "hitbox" on old 2D shooters...)

The server don't have anything to do with invisible or opaque surfaces, the NIF nodes are tagged to be "Colliding" (or not...), this means that game engine doesn't rely on graphics assets to detect collisions but on simpler "meta"-models embedded inside assets !

[Schaf]

collide and pickee are not reliable, there are models that do not have those nodes and it drops back to other nodes then...
also, think about ladders (climbale nodes) and doors (they have some special node i forgot too) etc etc etc also as i said animations, doors, etc etc... you'd have to basically work with certain nodes of the niftree and do the animations etc...

trust me, i've spent alot of time investigating all that (i even wrote a niflib for c# which supports ALL daoc nifs... the open source niflib has no c# wrapper and it doesnt support alot of daocs old nodes...)


edit: if you want to discuss with me, come to irc (quakenet, #dolserver) or contact me on icq/skype (103003434/schaf2k3)

[Dinberg]

I like the idea of bringing some life back into this challenge though! It's been a while since we discussed these points.

From memory, pretty much all of the instance dungeon pieces like caves etc have a reliable pickee/collidee mesh, perhaps it would be possible to use the pickee/collidee nodes for these interior elements only. The efficiency gain gives us a huge incentive to use these models when available, yet Schaf highlights the unfortunate case that for some mesh elements the data is incomplete.

[Leodagan]

I still think that having some of these elements "known" by the server is better than having none !

If it could at least force mobs to use corridors instead of getting through wall...

But it's still a huge work to extract everything from the client (All NIFs, DNIFs to browse, extract, or make scripts...)

[Nydirac]

Hi! Sorry for the up of a dead thread but i wanted to know if someone is still interested in this: I have the old code i wrote for Promise Shard which had a Z generation system.
Was comprised of a table on the db where i stored the data for the zones and a simple class for the system with a getZ(x,y,zone) method.

The performance were never a issue, it took some mb (5mb? something like this) of ram and used almost no cpu ( i used it to do a better random walk and generating mob on the correct z for the keeps, hills etc).
It worked only on open maps (no dungeon) because of the pathfinding issue (stacked zones etc) and i never looked to the water issue.

If it's something someone want i can port it to the new dol (it is gathering dust since 2007)

[Graveen]

Yes, interesting, thank you VM !!!

[Nydirac]

Haha ok then, i will update it then. In what format do you want the code? sparse files or directly a patch for the svn?

And i'm a little concerned about the best way to store data: I generated 2 dlls with the data in readonly arrays but i can see where someone wouldn't want something like this... so i can do two things:

- Put some of the files from the client (extracted offset/terrain files from the zones) in a directory on the server from which load the data but i'm hesitant to release something like this for obvious copyright reasons...

-Or i could put the data in databases without problems (i already have a tool to do this)


Anyway the cpu/memory requirements are the same (about 150 Kb of memory for zone)

[Leodagan]

I've seen a MPK Library in DOL Base...

For me the best use of a Terrain Z-getter would be to make an optional "client path" in the server configuration, once this client path is leading to terrain MPK make some script that extract the gray-scales maps and store them in memory, then give some API method to query this data for interpolated coordinates... (methods that should default to some predictable values if the client data is missing)

[Nydirac]

Yep its what i wanted to do but then we have the issue of having client files ( protected by copyrights etc) used directly by the server, i can see some problems originating from this...

[Leodagan]

For me we wouldn't be distributing any copyrighted client files, nor any means to modify the files... (read-only in-memory)