Sign in to follow this  
iosys

click to move there

Recommended Posts

How would I achieve this in theory? I'm thinking about games like Warcraft 3 or Diablo 2 where you move your character by clicking on the ground. There are two ways I can think of how this would work. In the case of Diablo 2 it's fairly simple because the game is 2d. Here you might be able to get away with just doing an intersect test against a plane at the character's feet. As for Warcraft 3 or World of Warcraft, the world is 3d and you need to allow the character to move to the exact location (polygon?) he clicks on. You might then move the character toward the x/z coordinates of that polygon, while the collision system takes care of the y coordinate. I don't know. I'm interested in how to do this in 3d (2d advice is welcome though). What I have come up with so far is to iterate through all of the triangles in the partition of space where the player clicks, then do an intersection test to find out which triangle was clicked on and furthermore to get the exact location on the triangle (where the unprojected mouse ray intersects) to move the character to. I made a simple project to demonstrate the intersection method. It might be useful to someone beyond my intended purpose. So if world geometry was divided into small groups of triangles, and supposing my project demonstrates one of these groups, would this be scalable enough to use in a game engine?

Share this post


Link to post
Share on other sites
Also don't forget that you may also need some form of pathfinding if there is going to be some obstacles that would stop your character from getting to the selected point.

Good Luck,
David

Share this post


Link to post
Share on other sites
Yes, the general idea is sound: first you compute the screen coordinates of the click, bring them into a useful 3D space (which generally produces a ray, since you've added an extra dimension to the original 2D coordinates) and perform collision detection. This is sometimes called "picking."

Culling obviously non-intersecting geometry to ideal to increase the performance, but the process by which you do that can vary. Your method is one way to do it.

It should be noted that you don't necessarily need to get down to the level of per-triangle collision, though. In some cases the nature of the world and the way it is represented allows you to make some optimizations in the process of determining the exact intersection point of the pick ray with the terrain. In some cases, collision geometry that is coarser than the render geometry could be used to reduce computation.

Share this post


Link to post
Share on other sites
Yeah:

1) create a "pick ray" from the mouseclick. Basically the pick-ray is a ray that goes from the near clip plane to the far clip plane of the view frustum. The coordinate on each plane will be the same relative coordinate as the 2D coordinate of the mouse.

2) cast that ray through your spatial partition system (octtree, whatver). Whatever it collides with is the "pick".

After you have the ground 3D coordinate you just do a basic A* pathfind search and move the guy to the destination.

-me

Share this post


Link to post
Share on other sites
use A* path finding to find the closest unobstructed node, and just make the character walk there first following the path, then when close enough directly to the point. The walking is entirely dependent on your character physics. You can have a look at this classic example for inspiration.

Steering Behaviors For Autonomous Characters

Share this post


Link to post
Share on other sites
Raypicking against groups of triangles or bounding boxes seems like the way to go for determining the destination. I will have to consider how pathfinding fits into a scene management system and develop it alongside those systems so it works nicely.

Thanks for the great replies.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this