Jump to content
  • Advertisement
Sign in to follow this  
Somnia

begining movement and pathing

This topic is 4223 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I decided to start game programming by looking into solving the common RTS problems. I've got as far as rendering a heightmap terrain, with mouse picking so I can select my little cubic blokes and have them move in straight lines along the surface. I suppose this is how a lot of people start. Trying to make things any more complex than this gives rise to a surprising number of issues. (I appreciate there may not be canonical answers to these questions, and that I perhaps should just keep tinkering, but I'm interested in any pointers from peoples experiences.) Firstly, when you game entity has settled on a straight line to move in, do games usually consider acceleration or only velocity? For slow moving objects like humans I'm not sure if instantly acquiring a walking/running speed would look that bad, although I suppose that for cavalry or vehicles it's going to look worse. I tried getting my cubes to accelerate where they wanted to go, and added a sort of viscous drag force, this resulted in units tending to oscillate about where they ended, although that problem went away when I altered the drag force so it couldn't make the velocity change sign. (A smaller intergration timestep would help here also I suppose, I'm just using one per frame atm.) Also I was wondering about the way the altitude dimension is treated. At the moment I just draw my cubes from an origin at the bottom and set their height position equal to a value retrived from the heightmap. This seems to look ok, but you might also want units to move slower going uphill (although not necessarily faster going downhill), so you could add the force of gravity in explcitly and have a normal reaction from the surface, although you'd also need a frictional force to stop standing units sliding down slopes. I haven't tested this yet, but it seems a bit comlex and also there might be problems with stability. I wondered if you can get away with keeping most of the computations 2D, and getting the heightmap gradient to do extra stuff like slowing people down when moving uphill. This is weak if want people to move off the surface though, like if you want your blokes to be tossed around by a bloodthirster, or charged by an elephant etc. I was thinking you could have some sort of two mode movement system, where each bloke has a "driven acceleration" and a "free acceleration", the first coming from his own locomotion and is just 2D, and the second from collisions, explosions etc. You'd also have some sort of "isFeetOnGround" parameter, which if false would mean that the driven accleration did nothing and the altitude dimension is fully integrated into the dynamics. (The magnitude of the free acceleration could be used to see if someone has been knocked off their feet). Also, some pathing questions. I've been reading about A* and it doesn't seem too complicated. Presumably the walkability of each node has to be hand edited for each map using tool or other, perhaps similiar to the NWN2 toolsets 'walkmesh cutter'. I would have thought the node separation would want to be about the radius of a bloke for decent looking movement, although maybe that would be too expensive. I've noticed also that modern RTS games like Dawn of War say tend to organise people into squads by default. This may be for gameplay reasons, but I wondered if they use a sort of two levelled pathing system, with a more coarse grained grid for squads, with each squad path node being used to generate a formation for the individual blokes to path too. This might allow more complex stuff like anticipating the future paths of other things, on the face of it expensive and horrible, to be implemented at the unit level but not the bloke level. Another question about A*, some links I read had different opinions about what to do with nodes on the closed list. One said to just ignore them, while another pointed out that you might find shorter paths to nodes on the closed requiring some "back propagation". I don't find this too easy to get my head round, but on the face of it the second is right if your navigating some random graph type thing, but perhaps it's not important in practice for more open RTS terrains? This post is getting rather long, although I have any number of other questions. Like accounting for different unit sizes, issueing "get out of the way commands", vehicles obvious pose a host of issues, and then there's animation... *whimper

Share this post


Link to post
Share on other sites
Advertisement
phew, quite a post there :)

Quote:


Firstly, when you game entity has settled on a straight line to move in, do games usually consider acceleration or only velocity? For slow moving objects like humans I'm not sure if instantly acquiring a walking/running speed would look that bad, although I suppose that for cavalry or vehicles it's going to look worse. I tried getting my cubes to accelerate where they wanted to go, and added a sort of viscous drag force, this resulted in units tending to oscillate about where they ended, although that problem went away when I altered the drag force so it couldn't make the velocity change sign. (A smaller intergration timestep would help here also I suppose, I'm just using one per frame atm.)




depends on the game, you're right in that cavelry and vehicles should have a little 'charge up' time before they hit their peak velocity. You're approaching everything from a very physics-based point of view, which is good, but remember it's well known that in games you can cheat a little ;) for example you may just accelerate for a few seconds then once the velocity has reached X, kill the acceleration.

Quote:

Also I was wondering about the way the altitude dimension is treated. At the moment I just draw my cubes from an origin at the bottom and set their height position equal to a value retrived from the heightmap. This seems to look ok, but you might also want units to move slower going uphill (although not necessarily faster going downhill), so you could add the force of gravity in explcitly and have a normal reaction from the surface, although you'd also need a frictional force to stop standing units sliding down slopes.


I can't actually think of many games that take terrain strongly into account, maybe the total war series does? In any case you could find the gradient of the triangle the item is on and scale the velocity accordingly (using it as a factor to multiply the velocity by rather than a set value to avoid, as you said, slipping).

Quote:

..
I was thinking you could have some sort of two mode movement system, where each bloke has a "driven acceleration" and a "free acceleration", the first coming from his own locomotion and is just 2D, and the second from collisions, explosions etc. You'd also have some sort of "isFeetOnGround" parameter, which if false would mean that the driven accleration did nothing and the altitude dimension is fully integrated into the dynamics. (The magnitude of the free acceleration could be used to see if someone has been knocked off their feet).


yeah i think this sounds good. If somethings knocked off the ground then you could just ignore the effects of terrain and just find its velocity in the air irrespective of the ground.

Quote:


I've noticed also that modern RTS games like Dawn of War say tend to organise people into squads by default. This may be for gameplay reasons, but I wondered if they use a sort of two levelled pathing system, with a more coarse grained grid for squads, with each squad path node being used to generate a formation for the individual blokes to path too. This might allow more complex stuff like anticipating the future paths of other things, on the face of it expensive and horrible, to be implemented at the unit level but not the bloke level.



i'm no AI programmer, but i think they may use some derrevation of flocking to achieve the pathfinding. I think you're quite close to the concept of flocking with your description there

Share this post


Link to post
Share on other sites
Don't worry, you don't have to hand-edit your "walkabilty". There are a lot of ways you can calculate it from your scene.

Your walkability is basically an indicator of how easy it is to traverse from point a to point b, right? You could calculate this from only 2 factors: the distance between a and b , and the height difference. In your example, it could look something like this (in pseudo, z is height):

//calc walkability
Node from;
Node to;
int walk = Point.distance(from.x,from.y, to.x,to.y);
int heightDifference = to.z - from.z;
if(heightDifference> 0)
walk += heightDiffernce

If walk get bigger, the route is more difficult (eg takes longer to traverse).

This will make your units less likely to take the uphill route. You can also use this to calculate movement speed which decreases while going uphill, but stays the same going downhill :

int baseSpeed;
baseSpeed *= heightDiffernce / easy (decrease in speed for pos. heightDiffernce)

I would recommed reading throught the aticles on A* pathfinding on this site.It's a very extensible algoritm and IMHO it fits your problem nicely.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!