Hey Guys,
To have my NPCs walking I was thinking about getting a random point on the navmesh and have them walk there.
(In fact I would apply several filters like min and max distance, but my Problem is to get a point from the mesh)
How can I accomplish this task? I thought about getting the BoundingBox but that would yield many invalid coordinates?
Should I parse the vertex and index buffer to get multiple triangles and then simply pick one of those triangles? (Seems like a real detour though)
It’s the classical “not looking at the javadoc” :chimpanzee_facepalm:
Well, to be more precise, I did look at the javadoc but I was looking for something like BoundingBox or getPoint().
I actually got the idea with the triangles during posting.
What I have as a concern though: Imagine a scene with only a flat area (floor) and some stairs. Each stair would have the same propability as the floor. This means the stairs would be way to propable as the propability should be equal/linear to the area.
I thought about calculating the area, normalizing it (dividing through the sum of all areas) and then I already have the propability, say 25% for tri1, 10% for tri2, etc which means ``if my random float is < 25% it’s tri1, if it’s > 25 % && < 35% it’s tri2.````
It feels wrong, though, especially because calculating everything needed will be quite some CPU load (for like a million of tris), especially because I bet nobody would really notice that problem in a big world?
Sounds like maybe you need to build a data structure that has only the tris that are in the navmesh… and hopefully your navmesh doesn’t have a million tris in it.
There is bounding box. I’m not sure what getPoint() would do.
If you are using JME’s navmesh stuff then maybe there is a way to query it or something… but I’ve never used it. I don’t know what is produced.
I currently only use the navMesh but it’s size will grow as my world is open-world which means if the player ever walks straight into one direction it will generate all those meshes.
I found the BoundingBox and getPoint() would do what I currently do Randomly get a Vector3f inside the Mesh.
The Problem with my current approach is that I have on average 4 tris to check until one is in range with the max being 19.
for 10 NPCs this is already 200ms cpu time (I have to call t.calculateCenter() as this isn’t done already, maybe I should do this on startup?)
Anyway I will have my AI multithreaded so I simply check every frame if the calculation is finished, that way it wouldn’t matter at all.
You will be better off if you build a data structure that you use for these queries that has precalculated as much as possible, ie: only includes the up facing triangles, indexes them in a fixed sparse grid, etc… Then the queries will be close to constant time.
Edit: corrected linear time to constant time. O(k)
Well I guess the navmesh only has up-facing triangles (because walkable) but I would need to sort them in a grid or something, that’s right.
I already have the world cut into tiles so I could use them.
Another thing: I am thinking about creating two nav-meshes. One containing everything walkable (run across the street, through the woods etc) for fighting or something and another one only containing pavements and some small strips on the streets.
Do you think this is a good “hack” to have them walk like usual civilians? (Because I won’t be able to modify pathfinding to prefer some points)
for each chunk of your world in memory, repeat when reloading
Determine if traversable northsourt, eastwest,.
Then only store 4 boolean per tile, that contain where you can go.
Now if you need a way, find based on those using a* a way from start to target chunk.
For the current chunk the npc is in, generate/load a navmesh, to do the detail navigation within the chunk.
Advanced:_add a cost metric for each chunk. So climbing over a mountain is avoided, if it is possible to go a slightly longer flat way.
Bonus:
Store the 4 booleans as the first 4 bits of a byte, and use the remaining 4 for the cost metric.
That way you can have really large worlds at nearly 0 memory cost from the navigation side.
Randomly get a Vector3f inside the Mesh.