smoothly moving through a given path

130

August 05, 2004 09:40 AM

In a old project I moved the entities in the world using a system similary to yours.

After computing the path in terms of tiles, all the steps were converted to pixel coordinates except for the last step that were discarded in favor of the exact coordinates the user clicked on.

In my project, the velocity of movement was given by the animation. One of its parameters was the delay (in frames) that each frame had to be drawn before changing to the next one. The other important parameters were the offsets of each frame, that is the amount of movement in pixels that the entity had to be moved when a change of animation frame occured.

When the entity arrives a waypoint in the path, it gets the next one and computes the direction of movement given the current and destination one. To not be restringed to the each directions of the animation, I calculated the direction vector and used the nearest animation direction in terms of slope. In that way, the CurrentOffsets (the ones which will move the entity) don't have to be the animation's ones.

GraphicSystem::TAnimationFrames::TOffsets offsets = GetCurrentAnimatedSprite()->GetOffset();S32	incx = CurrentStep.x - PathCoord.x,	incy = CurrentStep.y - PathCoord.y,	absincx = abs(incx),	absincy = abs(incy);if (absincx >= absincy){	CurrentOffsets.OffsetX = min(offsets.OffsetX, absincx);	CurrentOffsets.OffsetY = min(static_cast<S8>(absincy * CurrentOffsets.OffsetX / absincx),		offsets.OffsetY) * Sign(incy);	CurrentOffsets.OffsetX *= Sign(incx);}else{	CurrentOffsets.OffsetY = min(offsets.OffsetY, absincy);	CurrentOffsets.OffsetX = min(static_cast<S8>(absincx * CurrentOffsets.OffsetY / absincy),		offsets.OffsetX) * Sign(incx);	 CurrentOffsets.OffsetY *= Sign(incy);}

Then just add CurrentOffsets to the entity's coordinates.

HTH.

graveyard filla

605

Author

August 06, 2004 07:06 PM

ok, ive been working on this for days, but im still having problems. i hope Tazz (or someone) can help. hot, i appreciate your reply, but i didnt really understand it =).

ok, so i figured out why nothing was happening. first of all, my Tile_To_World() function was mis-calculating. so thats why nothing was happening.

after i fixed that though, it still took me 2 days to figure out why my guy wasnt moving right. after some torturous debug sessions, i figured out my player was falling off his path. thats why he wont move correctly.

by falling of the path, i mean this:

each frame, i do this:

-find which spot in the path i am in
-move towards the next point in the path (the one after the one im on now)

the problem was, is i was moving too far, or too little, or something was happening, and i was "falling off" the path. basically, i would move too far, and when i go to this point

-find which spot in the path im in

the spot in the path wasnt found, since i wasnt on the path anymore. so my character wouldnt move, since i cant find out where in the path i am now, how do i figure out what the next spot in the path is?

well, i fixed it (sort of). basically, the reason why this was happening (i *think*), was because my player is more then a tile big. so when i would move to a tile, i would move to it, but the top left corner of me would be in the next tile over, which wasnt in the path, so thats how i "fell off" the path.

the "solution" was this:

when i go to calculate the path to take, instead of sending the pathfinder my x,y position, i send it my x + (w/2) , y + (h/2) position. IE, i send the pathfinder my CENTER, not my top left corner. when i go to find what spot in the path im in, i use my CENTER. BUT, when i actually move, i still move based on my x and y position, IE my top left corner position. so i still do xPos += movement.

this worked! im actually moveing through my path. (sort of)

for one, i can only move up,down,left,right. i cannot allow angular movement, or else ill fall off the path. i have no idea how to fix this.im hoping the other kind of interpolation you can show me will fix this.

the other thing is, im still stepping onto walls and stuff. IE, the movement isnt perfect.

anyway, here is what the code looks like so far. this function is called each frame, inside Player::Update().id also like to note, i changed the path_to_walk variable from a std::vector to a std::deque. this is because i needed a pop_front() function. if you look, at the end of the function, inside the for loop where ive found the spot the player is standing on, i loop through the path_to_walk, and pop_front() any variables that were before the path im standing on now. this is because those are path's ive already walked through and are no longer needed, so i dont have old path's still in the container. also, this means path_to_walk[0] *should* always be the path im standing on.

void Player::Do_Pathfinding_And_Movement(){     dx = dy = 0;       // HERE IS WHERE I DO PATH_TO_WALK = PATHFINDER.CALCULATE_PATH(), AND CALCULATE THE PATH I SHOULD WALK. (IF THE USER CLICKS ON THE MAP)	//first find which step we are in the path		//first we calculate the Player's Point		Point pp;		pp.x = (int)xPos + (PLAYERWIDTH/2);		pp.y = (int)yPos + (PLAYERHEIGHT/2);		map_data->World_To_Tile(pp.x,pp.y);	//if we have a path to walk	if(!path_to_walk.empty())	{				//for each waypoint in the path to walk		//now that we know what tile the player is standing on, lets find which path that is in the pathfinder.		for(int i = 0; i < path_to_walk.size(); i++)		{			//if we found what tile the player is standing on in this path to walk AND this isnt the last node			if(pp == path_to_walk.pos && i < (path_to_walk.size() - 1))			{							Point dst;				//find the next point to move to IN WORLD COORDINATES, and put it in the dst variable			    dst.x = path_to_walk.pos.x;<br>				dst.y = path_to_walk.pos.y;<br>				map_data-&gt;Tile_To_World(dst.x,dst.y);<br><br>				<span class="cpp-comment">// calculate slope</span><br>				dy = dst.y - (yPos);<br>				dx = dst.x - (xPos);<br><br>				<span class="cpp-comment">//find the distance between the target the and shooter</span><br>				<span class="cpp-keyword">float</span> diff = sqrt((<span class="cpp-keyword">float</span>)dy*dy + dx*dx);<br><br>				<span class="cpp-comment">// normalize and set velocity</span><br>				<span class="cpp-keyword">float</span> invlen = <span class="cpp-number">1</span>.0f/diff;<span class="cpp-comment">//((float)dy*dy + dx*dx);</span><br>	<br>				<span class="cpp-comment">//noramlize the velocity</span><br>				dy *= (invlen*<span class="cpp-number">350</span>);<br>				dx *= (invlen*<span class="cpp-number">350</span>);<br><br>				<span class="cpp-comment">//set my velocity</span><br>				xVel = (dx * timer.Time_Passed);<br>				yVel = (dy * timer.Time_Passed);<br><br>				<span class="cpp-comment">//move at my velocity</span><br>				xPos += xVel;<br>				yPos += yVel;<br><br>				<span class="cpp-comment">//get rid of all the path's that we've already stepped through</span><br>				<span class="cpp-keyword">for</span>(<span class="cpp-keyword">int</span> n = <span class="cpp-number">0</span>; n &lt; i; n++)<br>					path_to_walk.pop_front();<br><br>				<span class="cpp-keyword">return</span>;<br>	<br>			}<br>		}<br>	}<br>}<br><br><br><br><br><br></pre></div><!–ENDSCRIPT–><br><br>also, if you want, ive uploaded the game exe for you to check out to see how it looks like. youll be able to see what im talking about when i say the movement isnt "right", IE, how you overlap with walls and stuff. not sure how to just make the damn player move the way i want to =). thanks a lot for all your help!!!<br><br><a href="http://www.donkeypunchproductions.net/help_me.zip"> click here to download</a><br><br>just left click with the mouse to walk around. thanks a lot for anymore help!!

FTA, my 2D futuristic action MMORPG

graveyard filla

605

Author

August 07, 2004 04:31 PM

ive never bumped anything before cuz i thought it was lame, but its getting close to the third page so heres a shameless bump so Tazzel will see this.

FTA, my 2D futuristic action MMORPG

Dwiel

365

August 08, 2004 10:42 PM

First off. I think the problem lies in the fact that you are using a floating point representation of where your player is while trying to restrict it to also be constrained to tiles. You are going to have to make a decision. My thoughts:

Choise A: Leave your A* alone. It will return a list of tiles to travel to. You will travel between these tiles and only these tiles. If say, you want to go from A: 0,0 to B: 2,1 the unit might go first to 1,1 and then 2,1. In this way, the charactor will change the direction that it is facing on its trip from point A to point B. I believe this is what you are looking for.

Choise B: Modify the A* some, or atleast put a 'filter' on it's output somehow. If a unit would like to travel from 0,0 to 2,1, it travels in a straight line. Crossing over tiles in arbitrary places. If there is nothing in the way between A and B, a perfectly straight line path is taken. No turns are made. This is harder, and what I am guessing you are not looking for.

Say you go with Choice A. I am also assuming that when you want the unit to move to 2,1 , you really want it to move to the center of 2,1. The first thing you do then, is to calculate the vector from the center of the current/previous tile to the center of the old one. Next, you calculate the distance the unit should travel ( some time constant * previous vector ). Also compute the floating point distance between the charactor's ACTUAL postion to the charactors destination position. You will need to handle the case where this distance is smaller than the distance the unit 'wants' to travel. In that case, move the charactor to the destination point and find how much distance past the destination it was going to travel. Start the unit off in the next direction traveling this distance (this time disregard the time frame)

here is some code because I explain better with it:

struct Vec2D{	float x;	float y;}// call this function passing 1.0fvoid Player::Do_Pathfinding_And_Movement(float alloted_distance = 1.0f){	// First thing we need is the player's exact position.  This position CAN NOT be clamped to some integer tile number.  It must be the position it was at in the previous fram	Vec2D pp;	pp = GetPlayerPos();	// I would say to use a deque for your path_to_walk variable.  Unless there is a reason to store all of the places the charactor was before...	// pretend that it is deque for now ;P	// nothing to do if their is no path to follow	if(path_to_walk.empty())		return;	Vec2D movementVec;	Vec2D dest = map_data->Tile_To_World( path_to_walk.front() );		// we need to know exactly what the world postion of the destination(next) is.	// calculate the vector which the charactor will follow		movement = dest - pp;	// adjust the movement vector w.r.t the alloted distance	movement *= alloted_distance;	float movementlen = length(movement);					// the length of the movement vector	float distlen = length(dest - pp);					// the distance between the player and the destination	if( movementlen > distlen)						// if the unit is about to travel past the destination, interviene	{		// bah... we're about to travel to far...				// lets move the player to the destination		AbsMove(dest);		// subtract how far we just traveled getting to the waypoint from how far we get to go to see how much furthur we can go		float dist = movementlen - distlen;		// note that with the FPS you are getting, it might be fine to just stop here.  Maybe not...		// Now we get to travel the rest of the way; find what fraction we have left and travel that far		Do_Pathfinding_And_Movement(alloted_distance * (dist / distlen) );	}	else									// go on as normal...	{		RelMove(movement * timer.Time_Passed);				// move the player according to the movement vector.  The relative part is so we know that it is a vector and not an absolution position the player should be transported to	}}

The part where I make it a recursive function might be a bit complex, but it's so that say if, the game lags a bunch and the player gets to travel 2.5 units, he actually crosses 2.5 units. If it wasn't this way, it would get to and stop (or surpass) the first destination with out any 'thought' given to the fact that it has time to travel to more than one point. I guess this could also be coded as tail recursion (while loop), where you loop through moving to waypoints until you run out of time or while there is still enough time to travel furthur.

Hopefully this makes some sence, if you would like me change it to a tail-recursion or a loop inside, I can; normal recursion just came to me first so I typed it first.

I would also double and tripple check that your Tile_To_World function is returning the correct place in world coords.

Hopefully, this will start working soon ;P

Dwiel

Dwiel

365

August 09, 2004 01:16 PM

Quote:PM from graveyard filla to Dwiel(Tazzel3d)

thanks. i read your post last night, and tried implementing it. it was really late though and i couldnt get it working so i figured i would work on it more tonight and hopefully get it working. im at work now and have school after so i wont be able to get back to the code till tonight. heh, if i wasnt such a newbie id try to help you with your problems =).

anyway, just to be sure... the length() function...maybe i implemented this wrong? this is what it looks like:

float Vector::Length(const &vector v)
{
return sqrt(v.x+v.x*v.y+v.y);
}

is that correct? also, what about AbsMove() and RelMove(). for those, i just do this:

in replace of AbsMove(), i do...
xPos = dest.x;
yPos = dest.y;

in replace of RelMove(), i do...
xPos += movement_vec.x;
yPos += movement_vec.y;

the last thing i wasnt sure about... you set the destination tile as the path_to_walk.front(), correct? which means its expected that path_to_walk[0] is the the next path to move toward? cuz i have it set up so the pathfinder includes the tile the player is standing on and the destinaton in the path to walk, so in the begining, path_to_walk[0] is where the player is actually standing, which i think might screw things up because then hes trying to move to where he is.. (the dist would be 0 and he wouldnt move??). so for now should i just find out the dest by locating where the player is in the path to walk and make his dest the next waypoint after where hes standing? (like ive done so far).

just want to make sure im doing these things right. it wasnt working last night when i implemented everything. i would have just replied to the post but like i said im at work and done have the code in front of me, altough now that i look back and see how much i just typed, maybe i should have just replied =).

thanks again for all your help!! oh, and the recursion thing did kinda confuse me. if you get the chance and could show me the while loop version, that would be great. it was always a pain for me to follow the flow of recursion for some reason.

First of all, your sqrt function is actually incorrect. It is derived directly from a^2 + b^2 = c^2. a can be replaced with x, b with y, and c with the vec length. Now to find the length, simply take the sqrt of both sides to get: length = sqrt(x*x+y*y) not length = sqrt(x+x*y+y)

I have to go right now, but when I have so extra time, I'll come back and try to make the recursion a little easxier to understand... I knew I shoulda prolly changed it.

Well, maybe the length fn fix will make everything work ;)

Dwiel

Dwiel

graveyard filla

605

Author

August 09, 2004 02:45 PM

hmm..

well, in the PM, i actually typed it wrong, cuz in the code i had the Length function working the way it should.

anyway, i had a chance before school to test this out, its working (sort of). well, i got it working, so, i went into the pathfinder code, and allowed the pathfinder to return diagonal nodes, allowing diagonal movement. like before, its not working when diagonal movement is allowed. the player will move a little bit but then fall off his path. IE, i do these 2 steps:

-find what waypoint the player is on
-make the destination the next waypoint after this one

the problem is, when i get to that first step, i dont find which waypoint the player is currently standing on, because he fell off the path and is no longer standing on any of the waypoints. so the player will just move a little then stop dead in his tracks.

i know this is happening, because each time i calculate the path, i print the entire path to the console, AND, every 5 seconds, i print the players current position (in tiles). so when i go to move, and the player stops in his tracks, this is what the console output looks like:

path to walk [0] through [3]:

14,29
13,28
12,27
11,26

players current position: 14,28

you see... where the player is currently standing, does not match up to any of the tiles in the path to walk, which is why hes not moving, because i need to know where the player is in the path to find the next point to move toward.

maybe this is because im not using the .front() of the path, but rather i loop through the entire path, looking for where the pp matches up to a node point, then i make the dest the next one after this one. i tried using the .front(), but was having problems getting that to work... is that even the reason, or is it something else? thanks again for all your help!!

FTA, my 2D futuristic action MMORPG

twix

637

August 09, 2004 02:53 PM

Question: Why does it matter that the player isn't always on the path? I can easily think of a situation in which the player crosses a tile that isn't along the path to get where he's going. Why don't you just keep track of all the nodes he hasn't gotten to yet, and pop the top one off the list when he reaches it?

Basically, my question is why do you have to "find the waypoint the player is on", when you can just remember it from the last time you "made the destination the next waypoint after this one"?

Dwiel

365

August 09, 2004 05:58 PM

I agree with twix. It is silly to loop through and 'find' which tile the player is on. Just query the player's world position (floats) and use that to determine the direction he needs to go. Once the unit arrives at a destination, there is no reason for that node to still be on the traversal list/queue/vector/etc. Oh and I noticed that I forgot to put the line:

path_to_walk.pop_front();

in the section of my code which handles the situation where the unit goes up to or tries to go past a way point.

Put that in and see how it works. There is no reason to force a search through the path list if you use this, front/pop_front/push_back combination. front() is called to find the next destinatation, pop_front() is called when you get to the front destination, and psuh_back is called to add a destination to the stack/list/etc...

give that a whirl

Dwiel

graveyard filla

605

Author

August 09, 2004 10:11 PM

ok.

he can walk his path finnally!! but, theres still this major problem that i cant figure out. ok, now he doesnt fall off the path anymore, thats awesome. before i talk about that, let me just mention one thing. this line

"if(movementlen > distlen)"

this line is never executed. ive tested it out, walking through my whole map, and this line is never true. if you look at the logic, it doesnt seem like it could ever be true (unless im just using the function wrong). i do this:

Point movement_vec(dest - pp);movement_vec *= alloted_distance;float movementlen = Point::Length(movement_vec);			float distlen = Point::Length(dest - pp);

but since i call this function each frame, like this:
Do_Pathfinding_And_Movement();

this code will never be executed, since alloted_distance will be 1.0 (the default the function receives), so movement_vec and dest - pp are the same thing. (movement_vec IS just dest - pp).

so the codes working anyway, even without the recursion =).

ok, now, on to the problem, im not sure if you can help me with this, but youve helped me more then enough already, so i dont mind if you tell me to screw off =).

anyway, the problem is this: collision detection. i was hoping that the pathfinding would take care of collision detection, IE, since the player's path will never involve a solid tile, he will never walk into walls, right?

the problem is - the players sprite is bigger then a tile. so lets say hes walking past a building, along the edge of it. his path wont include any of the building, but since hes walking so close to it, a part of his sprite will be drawn over the building. in my old code, before pathfinding, i did this:

-check to see if the player can move where he wants
-if so, move him there
-if it contains a wall, move him to the edge of this wall

now, i was hoping the pathfinding would work on its own, but this problem came, so i tried just plugging my old system into the new one. the problem is this:

-the player is standing on the side of a building. you click to walk behind the building. he walks up the side of it, then goes to walk around the corner, but a piece of his sprite gets snagged on the corner, so the collision detecter just repeatly pushes him back to the edge of the tile, over and over, as the player just keeps walking into it.

anyway, im not sure how to solve this. any hints are greatly appreciated. thanks again tazzel for all your help!!!

FTA, my 2D futuristic action MMORPG

Dwiel

365

August 09, 2004 10:21 PM

I'm glad you've got it working. I didn't realize that you do the pathfinding every frame. I would think that you would find the path he needs to travel and then tavel to it. But, its working so, yeah...

About the collision detection... The only thing I can think of is to not allow diagonal movements in the A* algorithm, if the tiles adjecent to both awypoints are solid. Simply make that kind of move illegal.

I think that is what you were wanting... Maybe not... I took it as the problem being the charactor walks over the corner of solid tiles when going arround a corner. If this isn't the case, try again and we can hopefully get it figured out ;)

Dwiel

Dwiel

smoothly moving through a given path

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

smoothly moving through a given path

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines