I couldn't find any resources (at least free resources) on pathfinding in meshwords. Now, I don't mean pathfinding on surfaces in 3d but true 3d pathfinding.

How is "pathfinding on surfaces" different from "true 3d pathfinding" by your definition?
In a game with gravity, can't you consider that any polygon in the mesh that has a surface normal that faces up is part of a floor surface, and only pathfind on those?
In a game without gravity - like a 3d Descent type game, generally the level structure is a simple graph or sectors already, so its easy to search.

Quote: Original post by arithma
Now, I don't mean pathfinding on surfaces in 3d but true 3d pathfinding.

I believe he means (by "surfaces in 3d") 2D surfaces embedded in 3D space.

If you're interested in multi-dimensional pathfinding, then actually any of the graph based pathfinding techniques will work. You might find though that the Distance Transform applied to an oct-tree representation of the domain gives you good results if your domain has a high connectivity (i.e., not many large, open spaces).

Cheers,

Timkin

Timkin got me right

Ok, without any restricting assumptions on behalf of the connectivity of space, can you elaborate.

In nodes, it is clear how the links are made.. But now the computer doesn't know what a room is.. I only need some kickstart and am sure I'll go on because this is for academic purposes (and yes we are allowed to research and ask people)

Quote: Original post by arithma
Ok, without any restricting assumptions on behalf of the connectivity of space, can you elaborate.

Consider a simple 2D example. Perform a quad-tree decomposition of the space so
that every leaf node now represents a convex polygon with one or more neighbouring polygons. (In this case, your polygons are squares and each leaf has 4 neighbours... 8 if you permit diagonal connectivity). The leaf nodes are now your 'rooms' for travelling through.

Generate a connectivity matrix for the leaf nodes. If you have N leaf nodes, this will be an NxN sparse matrix of 1s, where a 1 indicates the nodes are connected neighbours (i.e., your agent using the path could move from one leaf to another with an atomic action).

The Distance Transform algorithm is basically a flood fill from the goal. The goal gets the number 0. Each of its neighbours that hasn't already been marked gets a 1. For each of these neighbours, each neighbour not already marked gets a 2 and so on and so on. Once you mark the square denoting the starting position you can stop the fill. You then descend the number list. At any node you choose a neighbour with the lowest number compared to the node you're at.


Does that help?

I actually found what I was looking for... It is tought as a course in Computer Science.

Search for "Visibility Graph" and "Voronoi Diagram" - still don't know what the second is all about though

Thnx Timkin for your time.. I believe your method could be enhanced such that the connectivity matrix doesn't just store a connectivity boolean but instead stores an optimal node to go next and so on.. Someone did elaborate on this subject a while ago, every body interested in such topics should see that article...

Quote: Original post by arithma
Search for "Visibility Graph" and "Voronoi Diagram" - still don't know what the second is all about though

A Voronoi Diagram is a tesselation of a domain with triangles such that the number of triangles bounding any given point is a minimum (iirc).

Quote: Thnx Timkin for your time.. I believe your method could be enhanced such that the connectivity matrix doesn't just store a connectivity boolean but instead stores an optimal node to go next and so on.

Yes, this is a standard extension of connectivity matrices. The point about the Distance Transform algorithm is that it computes that 'optimal next node' very simply (and very efficiently for small to moderate domains).

Cheers,

Timkin