I’m not totally sure whether to put this thread in this topic, but I’ll
give it a try. So.
I’m fully aware of the A* pathfinding algorithm. The problem is how
can I apply it to a 3d point & click game…
The simpler question is what kind of graph representation to use for
the 3d space. There are afaik 2 alternatives:
- Navigation Mesh: I would assign a value to every triangle of my world
mesh, whether the player can step on it or not. The graph’s nodes are
the triangles, the graph’s edges are their connectivity through their
edges. There can be some complication with stairs (their “vertical”
parts can be surpassed, but not stepped on), but I can represent this as
a special value. This alternative is very redundant and can lead to
enormous search space.
- Points of Visibility: The graph’s nodes are predefined points in the
game space, and the graph’s edges are also determined by the level
designer. The weight oo the edges are of course the Euclidean distance
of its nodes. This results in a pretty small search space, though the
waypoints must be placed very carefully.
Ok so far. Here comes the REAL problem:How do I translate the user’s click to a destination in the search
I’ll explain this. In a point & click game, the user clicks on the
screen. Through my 3d engine api, I can determine which triangle did
he/she click on. But which nodes should I give to the pathfinding
algorithm as source and destination? Let’s consider the two space
representations mentioned above.
- Navigation Mesh: What if the user clicked on a triangle that the
player can’t step on, for example a wall piece? How could I know which
is the real, traversable destination triangle, eg. the floor piece next
to the wall??? I could assign a pointer to these non-traversable
triangles, which would point to the respective traversable triangle, but
this is a complete waste of the level designer’s resources.
- Points of Visibility: The problem is even much more complex. I can’t
even determine which waypoint to start the search with (since the player
can stand anywhere), not to mention the destination point. The player’s
position and the click will fall outside the search graph’s nodes almost
I hope I expressed myself clearly enough. Any ideas? Please help!
Please log in or register to post a reply.
Can’t you just find the nearest traversable node to the one clicked on,
or nearest to where the player is standing? BTW, if you go the route of
using designer-placed waypoints, then you don’t need to determine edges
among them yourself, you can simply check pairwise accessibility when
the level is loaded (i.e. by doing a geometry trace to make sure the
player can actually get from one node to the other).
Amit Patel has a wealth of great information about A* and pathfinding.
You can find his comments on map representations here:
Ok here is what I’ve done in the past:
1) I’d use a series of nodes to create a lattice, instead of a mesh.
The reason for this, is that you can massage the data, as well as having
a small data set, hence faster.
2) When you click you’re AI, it needs an entrance an an exit node.
You can run various distance checks to get the node. (Manhattan,Non
Square Dist, or Squared Dist) Also you’ll need to do a physical probe
against the collision geometry and reject closest distance, if say, a
node is behind a wall or some other obstacle. Doing this in a game can
become expensive on the CPU side of things.
The best solution for this is to store the closets waypoint data in a
bucket system. Either linear buckets, quad or octtree. The smaller the
buckets, the better the closest data solutions will be. I’d generate
this data off-line in a pre-compile step. That way you can use as
complex heuristics as necessary.
Our world representation is a quadtree. When a user clicks in a room,
the point is ray-projected in the standard 3D way to find which floor is
intersected by the ray and the actual point of intersection (our UI
ensures it is physically impossible to click points that are not in a
room). Then we transform the point into room space, and figure out the
leaf node in the quadtree the point is in. If it’s valid, then the
routing begins. We have a hierarchical A* that finds a path from room
to room and then with in a room across quadtree cells. The path built is
a 3D Bezier based on the quadtree centres, but we perform a relaxation
pass on that curve to smooth it out and make it look more natural. The
final section of the path is from the nearest leaf node centre to the