click to move there

Started by
5 comments, last by iosys 16 years, 11 months ago
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?
______________________________Perry Butler aka iosysiosys Website | iosys Music | iosys Engine
Advertisement
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
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.

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
Palidine: I think he already has the xyz coordinate of his destination, but he's having a problem determining how to actually get there from here.
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

Everything is better with Metal.

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.
______________________________Perry Butler aka iosysiosys Website | iosys Music | iosys Engine

This topic is closed to new replies.

Advertisement