Hi everyone
I'm working on a game that has spacecrafts and asteroids in zero gravity as scenario.
The player moves through this scenario in the same way that games like Dead Space and Shattered Horizon (walks on the wall, ceiling, anywhere).
´
But dont know how to implement an algorithm patfinding an environment like this one. since it has tutorials on the net only to scenarios in 2D maps... or terrains. Anyone know how to do this kind of algorithm?

Thanks!!

Interesting problem. Basically it's the same algorithm but adding a third dimension, so you would be checking more closest neighbors and if you used the manhattan type system for comparison you would add in the z, along with the x and y. I haven't done this, though, only the 2d type. I used this tutorial:
http://www.policyalmanac.org/games/aStarTutorial.htm

Which is kind of language agnostic and explains things pretty well.

Hmm... volume path finding, some sort of voxel system might help.
(like distance field + volume gradient field == distance to surface and direction to surface)
Then regular A* is used to find free path to target.
(A* weights can be used to favour paths that use walking surfaces,
or paths that stay away from surfaces)

/Tyrian

Do dynamics matter? I.e., do you control velocity or do you control acceleration?

I understand how the A* algorithm works. but I dont know how to implement the map of the scene for this algorithm, since it is an 3D mesh which the player (or the foes) walks on any of its triangles (no matter its on the floor, wall or ceiling). So the points that match the triangles planes (of the scene mesh) would be the way which the foes can walk. I saw about navmeshes. but i dont know how it works and if this could help me.

Oh, ok. I reread your post and I see that your movement is kinematic, not dynamic; that makes things simple.

So you're confused about how a navmesh applies to this kind of scenario? It's simple, but there are a few things you need to understand:

1.) A* has nothing to do with tiles, 2d, or space at all, really.* It is fundamentally about finding shortest paths in graphs -- i.e., graph-nodes connected by graph-edges. When you search a 4-connected 2d tile map (i.e., you can move north, south, east, or west), what graph are you searching? What about an 8-connected (you can also move diagonally) map?

2.) There are a few graphs one might associate with a navmesh. Here are two:

2a.) The graph nodes are the triangles, and there is a graph-edge between nodes whenever the corresponding triangles share a geometry-edge. This is called the dual graph. Then a "path" is a sequence of triangles, and the problem is reduced to figuring out how to move between neighboring triangles.

2b.) The graph nodes are the midpoints of the triangles' geometry-edges, and there is a graph-edge between two nodes whenever they are on geometry-edges shared by the same triangle. Then the problem is reduced to moving between points within the** same obstacle-free triangle.

Practically, what all this means is that you should write your A* implementation in a way that's abstract enough that, rather than having things like "look at this tile's four neighbors" hard-coded, you instead write code that says "look at this node's neighbors" in a more general way. Then this code will work as-is for navmeshes and anything else, so long as you write appropriate methods to interpret those objects as graphs.

(* Although this sentence has the right spirit, on second thought it's not entirely true. It would be more accurate to say that Dijkstra's algorithm has nothing to do with space. A*, on the other hand, requires a heuristic, and this generally means that your graph is being realized in some space. Nevermind that. You get the point: Think about graphs, not tiles.)

(** When I say "within the," I'm treating the triangles as closed sets, so that points on their edges are considered part of the triangle.)

[Edited by - Emergent on November 26, 2010 11:55:45 AM]

thanks for the advices!!!
i think i figure out how to solve this problem.

the game i'm developing its for mobile phone (java). And for collision detection (to player/foes walk on scene mesh triangles) i used the class RayIntersection (jsr-184)
then i can use the A* without no map, just search for the path without obstacles with the collision detection (when it returns True, the will be a free path)

But i think there will be one problem... the collision detection is slow.

And make a precalculated Map (big 3d maps) will consume too much memory (and i dont know if the mobile phone will support this) - i´m using a SE Vivaz U5 (29MB of RAM only)

I´ll try this in my game and i´ll tell if it worked and (of course) show the source code

thanks a lot!!!