AI NavMesh Random Distribution

Troubleshooting ai
1

Hello

i use Cell.getRandomPoint() to have a character wandering around randomly on the navmesh but the random distribution is weird

it seems that some parts of navmesh triangles are never used for random positions

[java]
NavMesh navMesh= new NavMesh(mesh);
navMesh.linkCells();
NavMeshPathfinder navMeshPathFinder = new NavMeshPathfinder(navMesh);
[/java]

[java]
int randomCell=FastMath.nextRandomInt(0, navMeshPathFinder.navMesh.getNumCells()-1);
Vector3f target = navMeshPathFinder.navMesh.getCell(randomCell).getRandomPoint();
[/java]

(here the navMeshPathFinder is a class that enclose NavMesh and NavMeshPathFinder instances)

here are the positions of the character at different times (white points)
and on the right, the original mesh used for navmesh

5khDhWk.png940×506

donno what could cause that to happen

it is not like whole triangles would be discarded (i would check the normals), but only some areas

also i was wondering if i have to give the navmesh algo global world coordinates or coordinates relative to the navmesh itself

if anyone can enlight me on this

thx

2

Hello,

i found another way to have a random point on a triangle (outside of NavCell code)

http://www.cs.princeton.edu/~funk/tog02.pdf

[java]
int randomCell=FastMath.nextRandomInt(0, navMesh.getNumCells()-1);
Cell cell=navMesh.getCell(randomCell);
float r1=FastMath.nextRandomFloat();
float r2=FastMath.nextRandomFloat();
Vector3f target =

            cell.getTriangle()[0].mult(1-FastMath.sqrt(r1)).add(
            cell.getTriangle()[1].mult(FastMath.sqrt(r1)*(1-r2))
            ).add(
            cell.getTriangle()[2].mult(FastMath.sqrt(r1*r2))
            );

[/java]

might be slower cos it uses sqrt but it works

3
@curtisnewton said: Hello,

i found another way to have a random point on a triangle (outside of NavCell code)

http://www.cs.princeton.edu/~funk/tog02.pdf

[java]
int randomCell=FastMath.nextRandomInt(0, navMesh.getNumCells()-1);
Cell cell=navMesh.getCell(randomCell);
float r1=FastMath.nextRandomFloat();
float r2=FastMath.nextRandomFloat();
Vector3f target =

            cell.getTriangle()[0].mult(1-FastMath.sqrt(r1)).add(
            cell.getTriangle()[1].mult(FastMath.sqrt(r1)*(1-r2))
            ).add(
            cell.getTriangle()[2].mult(FastMath.sqrt(r1*r2))
            );

[/java]

might be slower cos it uses sqrt but it works


The distribution still won’t be random because some cells are larger than others. A true random distribution will have more points land on larger cells than on smaller cells, but yours does not.

4
<cite>@Momoko_Fan said:</cite> The distribution still won't be random because some cells are larger than others. A true random distribution will have more points land on larger cells than on smaller cells, but yours does not.

you’re right, but what i wrote works better (towards what i want)
the whole navmesh gets flooded with points compared to the screenshot i provided

maybe distribution is not the correct word…

anyway, if you can tell why it is not working with the original function, that would be great

(edit : also, some points were agglomerating on the cell side, so I checked the code and noticed that the getRandomPoint uses 2 cell side’s normals to create the point coordinates then chop it to the triangle area wich leads to condensation of points on one side of the triangle

anyway, just give it a try, you’ll see that the randomness is distributed all over the navmesh, maybe not evenly, but for what i needed, it works as (i think) it should be)

5

I did a weighted mesh generator for the new particle system - that selects a triangle based on its size and then picks an evenly distributed point at random within that triangle.

http://code.google.com/p/jmonkeyplatform-contributions/source/browse/trunk/ParticleController/ParticleController/src/com/jme3/particles/source/WeightedMeshSource.java?r=1026

You might find the algorithm I developed for that helpful.

6
<cite>@zarch said:</cite> I did a weighted mesh generator for the new particle system - that selects a triangle based on its size and then picks an evenly distributed point at random within that triangle.

http://code.google.com/p/jmonkeyplatform-contributions/source/browse/trunk/ParticleController/ParticleController/src/com/jme3/particles/source/WeightedMeshSource.java?r=1026

You might find the algorithm I developed for that helpful.

thx for the link

but i did not mean distribution regarding triangle area
what i meant is that the current getRandomPoint function, discards some parts of cell triangles
where random point will never be generated

thx anyway cos i wanted to dig about that topic too :wink:

7

Just noticed I hadn’t committed a fix to the weighted mesh thing actually - fixed version is at http://code.google.com/p/jmonkeyplatform-contributions/source/browse/trunk/ParticleController/ParticleController/src/com/jme3/particles/source/WeightedMeshSource.java

The algorithm finds every triangle in a mesh. It weights those triangles based on the area of that triangle.

It can then pick a random triangle based on those weights so that any point on the mesh has the same chance of being picked no matter the size of the triangle.

The code to pick a random point on the triangle gives an even distribution as well.

8
<cite>@zarch said:</cite> Just noticed I hadn't committed a fix to the weighted mesh thing actually - fixed version is at http://code.google.com/p/jmonkeyplatform-contributions/source/browse/trunk/ParticleController/ParticleController/src/com/jme3/particles/source/WeightedMeshSource.java

The algorithm finds every triangle in a mesh. It weights those triangles based on the area of that triangle.

It can then pick a random triangle based on those weights so that any point on the mesh has the same chance of being picked no matter the size of the triangle.

The code to pick a random point on the triangle gives an even distribution as well.

talking about that, do you think it is possible to have particles working backward ?

like, instead of beein emited from a point or a mesh, they are goind toward that mesh/point, being emited at a particular distance(regarding face normals when emited from a mesh)

that would be awesome

9

Yes. You could certainly do that with the new system.

You would need a custom source to spawn them and a custom influencer to take them towards the destination.

10
<cite>@zarch said:</cite> Yes. You could certainly do that with the new system.

You would need a custom source to spawn them and a custom influencer to take them towards the destination.

cool, indeed for flexibility, one must be able to act on generation and on motion of particles

also i duplicated the particle system to modify it, the plan was to create a cloud where particles are confined to a cube for example, bouncing agains its limits
is it possible to do that with the new system ? maybe even further, particle collisions (insde or outside mesh) would be neat

another nice feature is color gradients… are you planning to do that ?

is the new particle system + examples already part of the v3 ? or nightlly build ? or repository ?

thx

11

It’s in the contribution repository although I don’t think it appears in the plugins list yet.

Particles confined to a cube is easy in the new system - just need a cube limits influencer.

Color gradients - again easy. Either a new influencer or a new material depending on just what you mean by gradient.

12
<cite>@zarch said:</cite> It's in the contribution repository although I don't think it appears in the plugins list yet.

Particles confined to a cube is easy in the new system - just need a cube limits influencer.

Color gradients - again easy. Either a new influencer or a new material depending on just what you mean by gradient.

keeeewl

ok i’ll wait it appears in the plugin list
“better particle system” i guess ?

13

Particle Controller.

It’s available from the SVN already if you want to try it - after the drama when I released it I’m leaving it for a while then going to do another release announcement and get it into the plugin list - it will have some more features and suchlike by then as well since I’m currently using it for real in HeroDex and coming up with things to add.

Feel free to add more ParticleSource and ParticleInfluencer options as well if you feel like it :slight_smile:

http://code.google.com/p/jmonkeyplatform-contributions/source/browse/#svn%2Ftrunk/ParticleController/

14
<cite>@zarch said:</cite> Particle Controller.

It’s available from the SVN already if you want to try it - after the drama when I released it I’m leaving it for a while then going to do another release announcement and get it into the plugin list - it will have some more features and suchlike by then as well since I’m currently using it for real in HeroDex and coming up with things to add.

Feel free to add more ParticleSource and ParticleInfluencer options as well if you feel like it :slight_smile:

http://code.google.com/p/jmonkeyplatform-contributions/source/browse/#svn%2Ftrunk/ParticleController/

thx

drama?

like hd crashed, all data gone, gotta rewrite the whole thing ?

15

Someone else started working on a particle library and then disappeared. I wrote mine (inspired by and using bits of code from hers I fully admit, but she had disappeared and released hers under open source library). She reappeared just as I was about to release mine and demanded that I not release it and accused me of plagiarism, stealing credit, taking her code and publishing it under my name, etc, etc, etc.

I felt sort of sorry for her since it turned out she’d been hit by a drunk driver and was offline as a result but there was no discussion possible, just hysterical accusations and demands that I not release it. So I released it and she rage quit.

16
<cite>@zarch said:</cite> Someone else started working on a particle library and then disappeared. I wrote mine (inspired by and using bits of code from hers I fully admit, but she had disappeared and released hers under open source library). She reappeared just as I was about to release mine and demanded that I not release it and accused me of plagiarism, stealing credit, taking her code and publishing it under my name, etc, etc, etc.

I felt sort of sorry for her since it turned out she’d been hit by a drunk driver and was offline as a result but there was no discussion possible, just hysterical accusations and demands that I not release it. So I released it and she rage quit.

wow