[In progress] Collision Add / Remove to new object in map

[gigola123]

### Edited
Here thread of the release
### Edited

Hello everyone,

During this corona virus I've some free time to work on my sro old project, some years before I was able to remove collision from an object in map (No the object collision, only the one on the map) but it wasn't really interessting.

After some researchs (thanks DaxterSoul repository and (push)edxnvmviewer) I'm able to create a .nvm file from .o2 file (using SRO Map Editor from Perryj for add Object easily).

Here what I've found:

As we know in the .nvm, the first part is the Objects declaration then the second part the navigation-cells.

In navigation-cells we've the declaration of all cells which contains object in our map.

In each of these cells, we will check if one of our objects is in the cell, if it's the case we put it's "index" in the cellExtra.

For doing this it's pretty easy, you'll need the "size" of each object (Can be found in the BoundingBox0 of bsr file and create a Box3 with them).
Then with these value (Size, PosX PosY and PosZ) you can determine if the object is in the NavigationCell.

By checking if the box object intersects in the box cell.

But I'm sure 99% I'm doing this wrong, I would like to know if some people was able to know how those navigation-cell are generated, from what exactly ? Terrain which much object got like 100+ navigation-cells, and terrain with no object got only 4 navigation cell. But if I add object to terrain with 4 navigation cell everything work well.

It's working by using the navigation-cell of old navmesh, just pimped it with the new Objects declaration (which come from o2 file).

Have to clean my code before releasing it.

Here files if someone want to use it, it can be bugged so use it at your own risk

[@Grayson]

good job

[DaxterSoul]

Yeah my time to shine, since I'm currently working on something related to this.

So here is a breakdown of how (i think) the navmesh is built.

Gallery 1

The blocked/walkable tiles (20x20) are calculated from the terrain slope height difference to their neighbor tiles and/or manually drawn by a designer with a brush in their map editor.

The cell structure is then generated with an algorithm (flood fill or similar) from those blocked tiles and some general rules (that I could make out):

• The smallest possible cell is 20x20 units which is the same as 1 tile.
• The minimum amount of cells is 2x2
• The amount of objects within a region increases cell density, resulting in a 3x3, 4x4, 5x5, 6x6, 7x7, 8x8 regular grid if otherwise undisturbed by blocked tiles.
• The cells are always rectangular even tho internally they're called quads, maybe a quad tree was planned at some point.

Gallery 2

Then as a last step we can insert the objects into the regions/cells their bounding box happens to intersect with.

Gallery 3

Conclusion
Inserting them later instead of regenerating the cell structure shouldn't be much of an issue as you have figured out already.
But is this correct approach? It depends. As long as you're not inserting an absurd amount of small objects into a 2x2 grid region you should be fine.

Objects have their own Navmesh and thus can stand for them self as long as they are inserted into the cells they touch. The amount of cells in a region only matters for performance as the amount of objects (and outlines) to check against when ray-casting increases per cell matched through. More cells = less object per cell on avg. = less testing against object you wouldn't hit anyways because your scope is smaller.

[qoaway]

Originally Posted by DaxterSoul

Yeah my time to shine, since I'm currently working on something related to this.

So here is a breakdown of how (i think) the navmesh is build.

The blocked/walkable tiles (20x20) are calculated from the terrain slope height difference to their neighbor tiles and/or manually drawn by a designer with a brush in their map editor.

The cell structure is then generated with an algorithm (flood fill or similar) from those blocked tiles and some general rules (that I could make out):

• The smallest possible cell is 20x20 units which is the same as 1 tile.
• The minimum amount of cells is 2x2
• The amount of objects within a region increases cell density, resulting in a 3x3, 4x4, 5x5, 6x6, 7x7, 8x8 regular grid if otherwise undisturbed by blocked tiles.
• The cells are always rectangular even tho internally they're called quads, maybe a quad tree was planned at some point.

Then as a last step we can insert the objects into the regions/cells their bounding box happens to intersect with.

Conclusion
Inserting them later instead of regenerating the cell structure shouldn't be much of an issue as you have figured out already.
But is this correct approach? It depends. As long as you're not inserting an absurd amount of small objects into a 2x2 grid region you should be fine.

Objects have their own Navmesh and thus can stand for them self as long as they are inserted into the cells they touch. The amount of cells in a region only matters for performance as the amount of objects (and outlines) to check against when ray-casting increases per cell matched through. More cells = less object per cell on avg. = less testing against object you wouldn't hit anyways because your scope is smaller.

right conclusion but more cells = more job on game server side since gs must keep track of object's cell while moving, plus ai object movements calculated with some sort of A* on gameserver

[gigola123]

Originally Posted by DaxterSoul

Yeah my time to shine, since I'm currently working on something related to this.

So here is a breakdown of how (i think) the navmesh is build.

The blocked/walkable tiles (20x20) are calculated from the terrain slope height difference to their neighbor tiles and/or manually drawn by a designer with a brush in their map editor.

The cell structure is then generated with an algorithm (flood fill or similar) from those blocked tiles and some general rules (that I could make out):

• The smallest possible cell is 20x20 units which is the same as 1 tile.
• The minimum amount of cells is 2x2
• The amount of objects within a region increases cell density, resulting in a 3x3, 4x4, 5x5, 6x6, 7x7, 8x8 regular grid if otherwise undisturbed by blocked tiles.
• The cells are always rectangular even tho internally they're called quads, maybe a quad tree was planned at some point.

Then as a last step we can insert the objects into the regions/cells their bounding box happens to intersect with.

Conclusion
Inserting them later instead of regenerating the cell structure shouldn't be much of an issue as you have figured out already.
But is this correct approach? It depends. As long as you're not inserting an absurd amount of small objects into a 2x2 grid region you should be fine.

Objects have their own Navmesh and thus can stand for them self as long as they are inserted into the cells they touch. The amount of cells in a region only matters for performance as the amount of objects (and outlines) to check against when ray-casting increases per cell matched through. More cells = less object per cell on avg. = less testing against object you wouldn't hit anyways because your scope is smaller.

Thank you for all those informations. In some case (Exemple in ChinTomb) navigation-cells looks like to depend more on the navigation-region-links (which is actually based on the navigation-cells) than on the objects present in the region.

It's clearer with all your details, I'll try to put much object on a 2x2 region and see how game respond. Thanks for everything again

[sarkoplata]

The structure release from Daxter is just awesome, pretty much all you need to add collision on your objects.



The only thing I'm not entirely sure about is... I add my object's entry index to all Navigation Cells. This must have a downside but I couldn't see anything yet...

[gigola123]

Originally Posted by sarkoplata

The structure release from Daxter is just awesome, pretty much all you need to add collision on your objects.



The only thing I'm not entirely sure about is... I add my object's entry index to all Navigation Cells. This must have a downside but I couldn't see anything yet...

Try to move arround, see if there is an impact on the collision somewhere else. When I add a new item + adding the object entry index in the correct NavigationCell provokes some strange behavior, like collision from nowhere. I'm trying to understand from where it comes, it's really strange.

[sarkoplata]

Originally Posted by gigola123

Try to move arround, see if there is an impact on the collision somewhere else. When I add a new item + adding the object entry index in the correct NavigationCell provokes some strange behavior, like collision from nowhere. I'm trying to understand from where it comes, it's really strange.

I actually walked around the entire region and didn't collide with any invisible object. Might've messed for sure.

The entry has all the x, y, z, region info so... Don't know. How do you determine the correct cell? I see some same entry indices on multiple cells. You might be missing that.

[gigola123]

Originally Posted by sarkoplata

I actually walked around the entire region and didn't collide with any invisible object. Might've messed for sure.

The entry has all the x, y, z, region info so... Don't know. How do you determine the correct cell? I see some same entry indices on multiple cells. You might be missing that.

Yup first of all I take the object size (Using the Object Bsr boundingBox), then I take it's x y z, with them I can calculate if the object is in the cell. I can recreate all NavigationCellExtra (object index) from the NavigationEntries and it's 100% similary to original navmesh.

The only difference I've is "cellExtraCount", I don't know why, the amount is not the same from my generation.

[gigola123]

Originally Posted by gigola123

Yup first of all I take the object size (Using the Object Bsr boundingBox), then I take it's x y z, with them I can calculate if the object is in the cell. I can recreate all NavigationCellExtra (object index) from the NavigationEntries and it's 100% similary to original navmesh.

The only difference I've is "cellExtraCount", I don't know why, the amount is not the same from my generation.

I'm stupid, I had the collision problem because I put x and z position of element which wasn't in the same region.
So now I've a 100% similary file generated from jmx (just some floating value which aren't the same).

Basically I can add / remove item from a map with it's collision.



Here in attachement my tool to convert .o2 file to .nvm, you'll need to use it in your Silkroad Directory with extracted Data.pk2 and Map.pk2 . The purpose is to do the same with .m (heightmap) in futur. You can easily allie this tool to Perryj map editor.

I'll share the code but have to clean some stuff, but you can "decompile it?" if you want to see how it's going behind I guess.

For resum, do your change in .o2 (with perryj editor) then open SroMapToNavmeshData.exe with the same region that you edited, then Voilà ! Collision should work !

Just some precision:
- I didn't handle the rotation in NavigationCell, I think it has a big impact, I've to check it out
- If you add or remove a big object (Like Jangan wall, big stairs ect..) take care to remove it from all .o2, so always take a look on the x8 .o2 near it.

Have fun

I put the Debug version then you can see if there is an error somewhere or why does it crash ect.. I tested like 30 regions without any problem from GameServer or Client.

VirusTotal ->

[guckguck]

Thanks for this nice tool
I've testing it on some region and found a bug while converting an o2 file (97 168):


I guess it happens because I've some event structures on this map. They might not have any collision data at all. Maybe it will be great to use an "exclusion list" or something to avoid incopatible objects or to filter them out during execution:



Basically I was testing if you could add collision to such objects too, but it seems not possible.

I tried it on a mapchunk where you have trees without collision and it did not crash (23971).

Beside of this there is another error, which seems to be a windows 10 issue. If you have a space char in the last folder of your data e.g. "west asia" it will not load the item:

[gigola123]

Originally Posted by guckguck

Thanks for this nice tool
I've testing it on some region and found a bug while converting an o2 file (97 168):


I guess it happens because I've some event structures on this map. They might not have any collision data at all. Maybe it will be great to use an "exclusion list" or something to avoid incopatible objects or to filter them out during execution:



Basically I was testing if you could add collision to such objects too, but it seems not possible.

I tried it on a mapchunk where you have trees without collision and it did not crash (23971).

Beside of this there is another error, which seems to be a windows 10 issue. If you have a space char in the last folder of your data e.g. "west asia" it will not load the item:

Hello guckguck,

Thanks for all your return, I already fixed the fact that some objects doesn't have collisions, they don't have .bms or the collision pointer on it is 00000000. But strange it doesn't work here, maybe the entry in objectifo is missing, can you give me your .o2 please ?

I'll fix the space also, thanks for the return

[guckguck]

Zip attached...

If I remeber well I was using to add the decoration on request.

[gigola123]

Originally Posted by guckguck

Zip attached...

If I remeber well I was using to add the decoration on request.

Thanks ! Well it's fixed, I was loading object.ifo from the Data/navmesh and not the Map/ folder one, it's fixed now ^^. Also fixed the whitespace problem, and added the abilitty to export also for the SR_GameServer Data folder.

Your map files worked well with the tool but convert 0 new item because event item doesn't have collision stuff, so it skip it. By the way here some other stuff, remove / add item + collision from jangan, some weird texture here haha.

New version in attachement

[guckguck]

By the way, it would be nice to read the chunks to parse from a txt file. Because you could work on a larger chunk of the map and parse them automatically. This would help with larger structures.

97 168
97 169
96 169
96 168
and so on

You could do your work with the map editor and simply press "convert" to output all files.