smoothly moving through a given path

Started by
22 comments, last by twix 19 years, 8 months ago
hi, (moved from game programming to this forum) im working on a 2D RPG w / C++, SDL, and OpenGL. the game is tile based, so each node in the pathfinding routine is a tile. anyway, im trying to implement pathfinding into the game. i can calculate a path, but im having problems moving through the path. right now im just working on the pathfinding for the player. so when i click on the map, ill walk to where i clicked. i calculate the path fine, but its walking my path thats giving me problems. basically, my pathfinder::Calculate_Path will return a std::vector<Point_And_Direction>. i have a member of my Player class called vector<Point_And_Direction> path_to_walk; a Point_And_Direction looks like this: struct PandD { int x; int y; Direction dir; }; where Direction is an enum like LEFT,RIGHT,UPLEFT,DOWNRIGHT,etc..... now, ill do something like this (inside Player::Update which is called each frame, and i do this if the user clicked on the map): path_to_walk = pathfinder.Calculate_Path(my_coords,mouse_coords); now i have a vector, where path_to_walk[0] is the first tile to step on, and path_to_walk.back() is the last tile before the goal. now, how do i accurately traverse through this path over time? ive tried a few ways and im not having much luck. one way i tried was calculating the reverse path, ie so path_to_walk[0] was the goal and path_to_walk.back() was the starting point. then i would do this:

for(int i = 0; i < path_to_walk.size(); i++)
{
  //if we found the spot in the path the player is currently on
   if(players_spot == i)
   {
       //find the diff between the next point and the players point
       int x_diff = player_spot.x - path_to_walk.x;
       <span class="cpp-keyword">int</span> y_diff = player_spot.y - path_to_walk.y; 

    <span class="cpp-comment">//make our velocity based on this</span>
       <span class="cpp-keyword">if</span>(x_diff &lt; <span class="cpp-number">0</span>)
          MOVE LEFT
       <span class="cpp-keyword">if</span>(x_diff &gt; <span class="cpp-number">0</span>)
           MOVE RIGHT
       SAME <span class="cpp-keyword">FOR</span> Y
    }
}

</pre></div><!–ENDSCRIPT–>

this worked, but &#111;nly if my path was a strait line. if the path was diagonal, it wouldnt move properly. he kind of just moved a little diagonal then stopped in his tracks.

also, i tried calculating the normalized vector (think thats what its called) for the players position and the next stop in the path, and then moving my player based &#111;n that, but that didnt work either. i was thinking this would be smoother and more elegant but i couldnt get it to work.

anyway, im hoping theres some cool way someone here could show me. thanks for any help!!
FTA, my 2D futuristic action MMORPG
Advertisement
Here is some code that I used to do something very similar. In my situation I had a queue of 2d points which needed to be traveled to in order. Here 'tis:
NOTE: a lot of my comments are way off to the right.
// move the unit some distancevoid CUnit::Move(){	localtimekey = *timekey * 10.0f;	patht += localtimekey;	if(patht > distance)																			// if we get to start moving towards a new target...	{		patht -= distance;																			// change patht to the dist traveled after it gets to the pos it is moving towards		TransformRO(direction * (localtimekey - patht));		//ro += direction * (localtimekey - patht);													// travel all of the way to the first way point		travelfrom = *path.begin();																	// we just got to this position		path.pop_front();																			// we just got here... remove it from the list of places to go		if(path.size() >= 1)																		// if we have another node to travel to...		{			RecalcMovement();																		// figure out which way we need to go now			TransformRO(direction * patht);			//ro += direction * (patht);															// use the rest of the time to go there		}		else																						// if we are out of places to go		{			traveling = false;																		// stop traveling		}	}	else	{		TransformRO(direction * localtimekey);		//ro += direction * localtimekey;	}}void CUnit::TransformRO(D3DXVECTOR2& trans){	velocity.x = trans.x;	velocity.z = trans.y;	terrain->GetHeightAtPoint(pos += trans, velocity.y);	tempfloat = velocity.y;	velocity.y -= lastheight;	lastheight = tempfloat;	ro += velocity;}void CUnit::RecalcMovement(){	distance = ((*path.begin()).x - travelfrom.x) * ((*path.begin()).x - travelfrom.x)			 + ((*path.begin()).y - travelfrom.y) * ((*path.begin()).y - travelfrom.y);	distance = sqrt(distance);																		// holds the distance between the next awypoint and the travelfrom point	D3DXVECTOR2 olddirection = direction;															// remember which direction we are facing	D3DXVec2Normalize(&direction, &((*path.begin()) - travelfrom));									// create the new direction vector, which is normalized and stored in direction		D3DXMATRIX mat;																					// holds the matrix used to rotate the unit		// sometime, this should be put into 1 line... less calculations	ro += -travelfrom;																				// move the unit back to 	float angle = acosf(D3DXVec2Dot(&direction, &olddirection));	D3DXMatrixRotationY(&mat, angle);	ro *= mat;	ro += travelfrom;}


I think that this is a more complex version of what you need and is a bit convoluted. It was one of those things that I started with what seemed right (similar to yours) and kept adjusting the algorithm until it worked. Some of the code takes into account that my travel-to points are 2d and the terrain that the units are moving on is 3d, so you can disregard those parts.

btw, ro is the local object which holds all of the verticies od the model. The *= overloaded operator is the same as multiplying every vertex by the righ-hand-side matrix. An addition acts the same way. The scalar on the right is added to every vertex. I guess this isnt needed for your application either due to the fact that you are moving a point and not a group of points.

hopefully, this gets you going in the right direction. If you need more help I can go through and fix it up for what you are looking for.

Hope I've helped!

Dwiel
Tazzel,

thanks for your reply! i looked through your code, but it didnt make much sence to me. it didnt help that i dont know DX either.

anyway, do you think you could explain to me what i should do in english / psuedo code? let me try to explain what data im given and the output i want.

lets say i have a std::vector<Point_And_Direction> path_to_walk.

this represents the path i want to walk. path_to_walk[0] is the starting point and path_to_walk.back() is the ending point.

how do i go about figuring out the velocity i should travel during any given frame? like i said, Point_And_Direction is a type which holds 3 things : a Point and Direction. Point is a struct which has 2 members : int x,y. Direction is an enum that could be UP,DOWN,UPLEFT,DOWNRIGHT,etc.... the x and y are the position of the node IN TILES. so if path_to_walk[0].x is 10, and path_to_walk[0].y is 15, that means that the first node i should walk to is located at map[15][10] in the map. that is the tile i need to go to.

anyway, here is what i go so far:
Point player_position = get_player_point_in_map_coordinates();for(int i = 0; i < path_to_walk.size(); i++){    //if we found the tile the player is standing on in the path to walk    if(player_pos == path_to_walk.pos)   {       NOW HERE IS WHERE I NEED TO DO STUFF. player_pos is the players current (same as path_to_walk) and path_to_walk is the node i want to travel toward. how <span class="cpp-keyword">do</span> i calculate my velocity based on these <span class="cpp-number">2</span> things???<br>    }<br>}<br><br></pre></div><!–ENDSCRIPT–><br><br>i hope you understand what im trying to do and what i have already. its seems like something very easy, but i just cant figure it out. its kind of frustrating that something this simple is stopping my pathfinding from working. you would think calculating the shortest path via A* would be more complicated then actually moving the character around…<br><br>thanks a lot for anymore help!!<br><br><!–EDIT–><span class=editedby><!–/EDIT–>[Edited by - graveyard filla on August 3, 2004 9:01:28 PM]<!–EDIT–></span><!–/EDIT–>
FTA, my 2D futuristic action MMORPG
Sorry about that code... I was hoping it would be enough to jump start some brainstorming, but now that I go back and look at it, I can see why that didnt happen.

First question: Is the direction not ambiguous? It seems to me that the only information that you would need is start point and an end point. The direction can be computed using those two... Please let me know what extra information the direction value is providing, as that is the only part of your explination that I do not understand.

So first, you are going to need a time frame. Basically, for smooth movement, you need to know how much time has passed since the last time you moved the charactor. If you dont do this, a slower machine will result in a slow moving unit and a fast machine will have fast unit movement. This is a typical problem in old dos games that you might try to play on a modern computer. The programmer hard coded how much a unit would travel durring each frame/loop iteration, and now that computers can run 10 times faster, the units move 10x faster. Anyway, you will need to know how long has passed since the previous update. The unit of time is irrelivent as long as it is consistant and has enough precision given the length of time between updates... more on this if you ask

Second, you want to find which direction the unit needs to travel in order to get from point a to point b. this can be done using the following equation:

normalize( b - a )

the b - a is a simple operation: {b.x - a.x, b.y - a.y). The normalize function takes the vector and makes it point in the same direction as the one passed, but changes it's length to 1. You can do this by doing: c.x /= length(c); c.y /= length(c); the length function is of course length(c) = sqrt(c.x*c.x + c.y*c.y);

Now. You have a vector which has a length of 1 and if aligned on your start point, will point towards your desired end point. All you have to do is increment the unit's position by this vector every frame. You will want to also multiply that vector by the time (to ensure a constant speed) and probobly some constant set by you (just a way to manually control the speed of the unit).

So the pseudo-code you asked for would be something like:

Vector vecNormalize(Vector v){    return Vector(v.x / vecLength(v), v.y / vecLength(v));}Vector Vector::operator-(Vector v){    return Vecotor(x - v.x, y - v.y);}// inside each frame/game iteration:static float time, oldtime, timefactor;oldtime = time;time = TheTime();timefactor = time - oldtime;Vector movementvec = vecNormalize(currentposition - destination);playervec *= movementvec * timefactor * 0.5f;// the 0.5f is the number you fudge arround with or put into a menu somewhere.


you must also make sure that you don't overshoot the destination position. This gets more complex, and I'd like to make sure what I have so far is what you are looking for and makes sence.

Happy to help!

Dwiel
Quote:Original post by Tazzel3D
Sorry about that code... I was hoping it would be enough to jump start some brainstorming, but now that I go back and look at it, I can see why that didnt happen.



apology is not needed.. thanks a lot for all your help.

Quote:
First question: Is the direction not ambiguous? It seems to me that the only information that you would need is start point and an end point. The direction can be computed using those two... Please let me know what extra information the direction value is providing, as that is the only part of your explination that I do not understand.


i guess i should have mentioned this. you are right, the direction info is not needed at all in this case. in fact, my nodes could (should) just be a Point instead of a Point_And_Direction. where i DO use a P_A_D is when i calculate the path, i need to record a nodes orientation so i know how to calculate the cost (since diagonal cost is different from regular movement). but that part isnt needed in this case.


Quote:
So first, you are going to need a time frame.


i already do this. all my objects move based on time. i have a global time object who has members like current_time and time_passed. i use time_passed in all movements ( pos+= (time_passed * velocity) )

about the rest of your reply.. i just read it so im gunna start implementing it... ill probably be back when i get stuck =P. also the thing with over-shooting the destinatoin and "falling off" the path seems like it could be complicated to not allow that.

thanks again for your help.

EDIT: after further reading, ive already tried to do this before =). i couldnt get it to work, but im gunna try again.
FTA, my 2D futuristic action MMORPG
You might also want to look at cosine interpolation to help smooth the path out. Tazzel3D's code essentially boils down to linear interpolation.
______________________________________________________________________________________The Phoenix shall arise from the ashes... ThunderHawk -- ¦þ"So. Any n00bs need some pointers? I have a std::vector<n00b*> right here..." - ZahlmanMySite | Forum FAQ | File Formats______________________________________________________________________________________
well, ive been trying to get this to work all night, but i give up for the night.. its getting real late and im getting nowhere....

are you sure the formulas you posted were right ? (actually, im probably just not understanding them).

ok, just to make sure, a Vector is just a struct which contains 2 members, x and y, in my case ill use integers since a node in the pathfinding routine represents a tile, and tile coordinates are always integers (they are elements in an array[][]). i already have a struct for this, called Point. it just contains 2 ints, x and y.

also,

"playervec *= movementvec * timefactor * 0.5f;"

playervec is the players position, x and y, correct? so i want to multiply the characters current position and not add to it? cuz when i move my bullets, i do this same thing, i calculate the distance, do the normalization thing, but then i do xPos+= (dx *time_passed), and not xPos *= dx * time_passed.

also, will i have to find the abs() of the slope's and stuff before i calculate distance?

awe hell, ill post my code and explain anyway =). right now im doing my own calculations cuz i was trying everything to get it to work. but at first i was using the - operater and Normalize() function you posted.

in this, pp is of type Point and is the x,y position of the tile the Player is standing on. basically, i loop through my path_to_walk vector. when i find the point the player is standing on (path_to_walk.pos is == pp), then i now know what point the player is on in the path. since is the point hes on, i do my movement based on the players position (xPos / yPos) and ( is the point i have to move to since <span style="font-weight:bold;"> is the point im &#111;n ).<br><br>anyway, &#111;nce i found the point im &#111;n, i just do what you said. i first convert the destination tile from Tile To World coordinates. then, i calculate the normalized vector for the player to the next point, and then try to move based &#111;n that. this code is inside Player::Update(), which is called each frame, so the variables you see that arent declared are members of Player (xPos,yPos,path_to_walk,dx and dy). and yes i realize checking if path_to_walk is empty is redundant since if its empty the for loop will never execute, but i put it there for clarity.<br><br><!–STARTSCRIPT–><!–source lang="cpp"–><div class="source"><pre><br><br> <span class="cpp-comment">//if we have a path to walk</span><br> <span class="cpp-keyword">if</span>(!path_to_walk.empty())<br> {<br> <br> <span class="cpp-comment">//for each waypoint in the path to walk</span><br> <span class="cpp-keyword">for</span>(<span class="cpp-keyword">int</span> i = <span class="cpp-number">0</span>; i &lt; path_to_walk.size(); i++)<br> {<br> <span class="cpp-comment">//if we found what tile the player is standing on in this path to walk AND this isnt the last node</span><br> <span class="cpp-keyword">if</span>(pp == path_to_walk<span style="font-weight:bold;">.pos &amp;&amp; i &lt; (path_to_walk.size() - <span class="cpp-number">1</span>))<br> {<br> <br> <span class="cpp-comment">//dest Point (tile to move toward, aka AND source Point (player position)</span><br> Point dst;<br> Point src;<br><br> <span class="cpp-comment">//grab our dest coords, and convert them from Tile coords to World coords</span><br> 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 dest and source</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>/diff;<span class="cpp-comment">//((float)dy*dy + dx*dx);</span><br> <br> dy *= (invlen*<span class="cpp-number">500</span>);<br> dx *= (invlen*<span class="cpp-number">500</span>);<br><br> <span class="cpp-comment">//now move closer to our destination</span><br> yPos += (dy * timer.Time_Passed);<br> xPos += (dx * timer.Time_Passed);<br><br><br> <span class="cpp-comment">//we can leave now that we have moved</span><br> <span class="cpp-keyword">break</span>;<br> }<br> }<br> }<br><br><br><br><br><br><br></pre></div><!–ENDSCRIPT–><br><br>i hope you can spot out what im doing wrong. like i said i overloaded the - operator for Point and gave him the Normalize function, but right now im just trying everything and figured it would be more clear if you saw the formulas all in the same code. <br><br>thanks a lot for anymore help!!!
FTA, my 2D futuristic action MMORPG
First of all. You are right in using a '+=' instead of a '*='... I was just tired last night and goofed. Your code looks good to me. Although I am a bit confused as to your vector of waypoints. Can your player only be at integer postions on the board? That might be what is goofing things up. Based on your (float) convertion typecast in the length fn, it looks like they are integers. Is it the case that your unit mayb only travel in cardinal directions? Or can they be on any floating point point on the map? If they can be anywhere, Im not sure why you are using integers for your vectors. If you are using only integer positions, you are going to need a fairly different algorithm ontop of the current one in order to make sure the unit travels to the next correct tile instead of just directly towards the traget destination. Although, are your destination points ever furthur than one tile away from the previous one? If they are, then your lookup for which tile the unit is on doesnt really work; The unit might be inbetween two nodes. A similar thing will happen even if you are only traveling one unit...

What I did, was to put the list of nodes into a queue. When a new waypoint was found, it was pushed onto the queue. The destination waypoint was always stored on the bottom of the stack. To access the next waypoint to travel to, I would just access queue.top(). When I arrived there, I would call queue.top().

I guess I need some of those other questions answered before I can help much more.

Like thunder_hawk said, I am only showing linear interpolation, but once you understand linear interpolation, the sin interpolation should be easy to switch to.

Glad to help!

Dwiel
Quote:Original post by Tazzel3D
I am a bit confused as to your vector of waypoints. Can your player only be at integer postions on the board? That might be what is goofing things up. Based on your (float) convertion typecast in the length fn, it looks like they are integers. Is it the case that your unit mayb only travel in cardinal directions? Or can they be on any floating point point on the map? If they can be anywhere, Im not sure why you are using integers for your vectors. If you are using only integer positions, you are going to need a fairly different algorithm ontop of the current one in order to make sure the unit travels to the next correct tile instead of just directly towards the traget destination.


ok. im using OpenGL, which likes to have everything as a float. so i store everything as floats. my characters position (xPos and yPos in the code) are declared as floats.

the reason my Point struct is made of integers, is because of this: My pathfinding routine treats a tile as a node. so my path_to_walk[] is made of of Point's containing x and y. these x and y are TILE coordinates, not world coordinates.

for example, lets say i get my path. i do path_to_walk = Calculate_Path();

heres an ascii drawing of a situation that could happen

P - - - - - D

P is where the player is, and D is the destination. each '-' dash is a tile, or node to travel. so lets say i click where 'D' is with the mouse. i want the player to travel where i clicked. so i calculate_the_path(). my path calcuation function returns a std::vector<Point>

since there is 5 nodes from the player to the destination (5 tiles aka 5 dashes), the .size() of my vector is 7. there are 5 nodes to travel, BUT, i throw in the starting tile and ending tile into the path. so path_to_walk[0] is where the player is standing, and path_to_walk[6] is the 'D'. lets pretend the player is standing at world position 400,500. the destination would then be (592,500) (400 + (6 *32) ) (since theres 6 tiles to walk and the tilesize is 32x32).

so the players position is (400,500), and we want him to walk to (592,500).

but like i said, path_to_walk is tile positions. so path_to_walk[0] wont be (400,500), but it would be ~(12,15). and path_to_walk[6] wont be (592,500), but ~ (18,15)

so, the first thing i do is this:

Point pp;
pp.x = xPos;
pp.y = yPos;

this grabs my players position. and stores it in a point variable. the next thing i do is

World_To_Tile(pp.x,pp.y);

this function receives 2 integers by reference, and converts them from world coordinates to tile coordinates. since my path_to_walk[] is storing tile coordinates, and i want to find out where the player is in the path_to_walk[], i have to convert my player's coordinates into tile coordinates.

now pp is the Players Point in tile coordinates.

now that i know what tile the player is standing on, i just have to find this tile in the path_to_walk[]. so i loop through my path_to_walk[], looking for the Point that matches up with the Players Point.

//for each waypoint in the path to walk		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))			{			


if pp == path_to_walk. if we found the players point in the path to walk. (BTW, i think im mis-using the word waypoint. im not sure the correct term for it. by way-point i mean a point in a path, IE a node)

now that we found the players point, we know the player is standing on . if hes standing on , that means the tile i want him to move toward is . (since the path_to_walk[0] is the starting point, and path_to_walk.back() is the destination).<br><br>anyway, so now we have the 2 source and destination coordinates. the source is the players position, and the dest is path_to_walk. now this is how i calculate the velocity.<br><br><!–STARTSCRIPT–><!–source lang="cpp"–><div class="source"><pre><br> <span class="cpp-comment">//dest Point (tile to move toward, aka </span><br> Point dst;<br><br> <span class="cpp-comment">//grab our dest coords, and convert them from Tile coords to World coords</span><br> 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><br><br><br><br></pre></div><!–ENDSCRIPT–><br><br>here, i grab the destination coordinates and put them into a Point called dst. since they are stored as tile coordinates, i have to convert them to world coordinates. so i grab them, and convert them from Tile_To_World. <br><br>ok, great. now i have the destination in world coordinates, and i already have the players position in world coordinates, its his xPos and yPos.<br><br>now the rest of the code is just calculating the velocity to move, since dst.x and dst.y are my dest, and xPos and yPos are my starting position. i then attempt to calculate the velocity and then move. but it doesnt work. i dont know what im doing wrong!.<br><br>one thing is, maybe i should add offsets to make things more smooth. IE, right now im doing all calculations with xPos and yPos, and the tile coordinates. but these are the top left corners of the player / tile. maybe i should add (w/2) and (h/2) to these values, so instead of the top left corner of the tile / player, its their center? but for now that shouldnt really matter.<br><br><!–QUOTE–><BLOCKQUOTE><span class="smallfont">Quote:</span><table border=0 cellpadding=4 cellspacing=0 width="95%"><tr><td class=quote><!–/QUOTE–><!–STARTQUOTE–><br> Although, are your destination points ever furthur than &#111;ne tile away from the previous &#111;ne? If they are, then your lookup for which tile the unit is &#111;n doesnt really work; The unit might be inbetween two nodes. A similar thing will happen even if you are &#111;nly traveling &#111;ne unit…<br><!–QUOTE–></td></tr></table></BLOCKQUOTE><!–/QUOTE–><!–ENDQUOTE–><br><br>no, there not. each node IS a tile.<br><br><br><!–QUOTE–><BLOCKQUOTE><span class="smallfont">Quote:</span><table border=0 cellpadding=4 cellspacing=0 width="95%"><tr><td class=quote><!–/QUOTE–><!–STARTQUOTE–><br>Glad to help!<br><!–QUOTE–></td></tr></table></BLOCKQUOTE><!–/QUOTE–><!–ENDQUOTE–><br><br>thanks a lot again! i appreciate it.
FTA, my 2D futuristic action MMORPG
Well, it looks like after all of that, the algorithm should atleast provide movement (which I take it, it is not). It should also follow a path at least close to what you have found with A*. It looks like you have some debugging in your immediate future. I'd say start by displaying or logging the following things:

Everytime the move fn is called
Once the programs finds which tile the unit is on
All of the vectors and points used in the calculations
The resulting movement vector and the position of the unit before and after the final transformation.

Or ofcorse, if you are using Visual Studio, just step through and manually check a few itterations. Look for those few things though and I think you should be able to find problem.

Let me know how the debugging goes, or if it doesn't seem to be working I'd be happy to look through your code with debug statements and the output to try and find the problem.

Dwiel

This topic is closed to new replies.

Advertisement