# smoothly moving through a given path

## Recommended Posts

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[i + 1].x;
int y_diff = player_spot.y - path_to_walk[i + 1].y;

//make our velocity based on this
if(x_diff < 0)
MOVE LEFT
if(x_diff > 0)
MOVE RIGHT
SAME FOR Y
}
}


this worked, but only 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 on 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!!

##### Share on other sites
Dwiel    365
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

##### Share on other sites
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[i].pos)   {       NOW HERE IS WHERE I NEED TO DO STUFF. player_pos is the players current (same as path_to_walk[i]) and path_to_walk[i + 1] is the node i want to travel toward. how do i calculate my velocity based on these 2 things???    }}

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...

thanks a lot for anymore help!!

[Edited by - graveyard filla on August 3, 2004 9:01:28 PM]

##### Share on other sites
Dwiel    365
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

##### Share on other sites
Quote:
 Original post by Tazzel3DSorry 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.[/i]

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.

EDIT: after further reading, ive already tried to do this before =). i couldnt get it to work, but im gunna try again.

##### Share on other sites
Thunder_Hawk    314
You might also want to look at cosine interpolation to help smooth the path out. Tazzel3D's code essentially boils down to linear interpolation.

##### Share on other sites
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[i].pos is == pp), then i now know what point the player is on in the path. since [i] is the point hes on, i do my movement based on the players position (xPos / yPos) and [i + 1] ( [i + 1] is the point i have to move to since [i] is the point im on ).

anyway, once i found the point im on, 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 on 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.

	//if we have a path to walk	if(!path_to_walk.empty())	{				//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[i].pos && i < (path_to_walk.size() - 1))			{			                                //dest Point (tile to move toward, aka [i + 1] AND source Point (player position)				Point dst;				Point src;                                //grab our dest coords, and convert them from Tile coords to World coords			        dst.x = path_to_walk[i + 1].pos.x;				dst.y = path_to_walk[i + 1].pos.y;				map_data->Tile_To_World(dst.x,dst.y);				// calculate slope				dy = dst.y - yPos;				dx = dst.x - xPos;				//find the distance between the dest and source				float diff = sqrt((float)dy*dy + dx*dx);				// normalize and set velocity				float invlen = 1/diff;//((float)dy*dy + dx*dx);					dy *= (invlen*500);				dx *= (invlen*500);				//now move closer to our destination				yPos += (dy  * timer.Time_Passed);				xPos += (dx  * timer.Time_Passed);                             //we can leave now that we have moved				break;			}		}	}

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.

thanks a lot for anymore help!!!

##### Share on other sites
Dwiel    365
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.

Dwiel

##### Share on other sites
Quote:
 Original post by Tazzel3DI 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[i].pos && i < (path_to_walk.size() - 1))			{

if pp == path_to_walk[i]. 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 [i]. if hes standing on [i], that means the tile i want him to move toward is [i + 1]. (since the path_to_walk[0] is the starting point, and path_to_walk.back() is the destination).

anyway, so now we have the 2 source and destination coordinates. the source is the players position, and the dest is path_to_walk[i + 1]. now this is how i calculate the velocity.

 //dest Point (tile to move toward, aka [i + 1] 				Point dst;                                //grab our dest coords, and convert them from Tile coords to World coords			        dst.x = path_to_walk[i + 1].pos.x;				dst.y = path_to_walk[i + 1].pos.y;				map_data->Tile_To_World(dst.x,dst.y);

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.

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.

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!.

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.

Quote:
 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...

no, there not. each node IS a tile.

Quote:

thanks a lot again! i appreciate it.

##### Share on other sites
Dwiel    365
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

##### Share on other sites
hotcamus    130
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.

##### Share on other sites
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.

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[i].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[i + 1].pos.x;				dst.y = path_to_walk[i + 1].pos.y;				map_data->Tile_To_World(dst.x,dst.y);				// calculate slope				dy = dst.y - (yPos);				dx = dst.x - (xPos);				//find the distance between the target the and shooter				float diff = sqrt((float)dy*dy + dx*dx);				// normalize and set velocity				float invlen = 1.0f/diff;//((float)dy*dy + dx*dx);					//noramlize the velocity				dy *= (invlen*350);				dx *= (invlen*350);				//set my velocity				xVel = (dx * timer.Time_Passed);				yVel = (dy * timer.Time_Passed);				//move at my velocity				xPos += xVel;				yPos += yVel;				//get rid of all the path's that we've already stepped through				for(int n = 0; n < i; n++)					path_to_walk.pop_front();				return;				}		}	}}

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!!!

just left click with the mouse to walk around. thanks a lot for anymore help!!

##### Share on other sites
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.

##### Share on other sites
Dwiel    365
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

##### Share on other sites
Dwiel    365
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

##### Share on other sites
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!!

##### Share on other sites
twix    636
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"?

##### Share on other sites
Dwiel    365
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

##### Share on other sites
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!!!

##### Share on other sites
Dwiel    365
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

##### Share on other sites
twix    636
Quote:
 Original post by Tazzel3DAbout 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.

This seems like an excellent idea, especially since it also conveniently prevents the player from slipping through an infinitely thin gap between two buildings with corners that meet diagonally. [grin]

##### Share on other sites
well, i only calculate the path one time, when the user clicks the mouse, but i do try to move each frame, if i have a path to walk.

its not just cutting around corners that are the problem. first of all, just to let ya know, im back to using the center of the player to calculate movement. IE, i send the pathfinder my center position, but when i move, i still just move based on my actual x,y position. i couldnt get it to work any other way.

the problem is, i cant figure out how to position the player so that his sprite isnt drawn over any solid tiles. its hard to explain, ummm, maybe ill just show you?

lets say im standing on the left side of a building, like so:

i click where the red dot is. now im moved to this spot:

do you see the problem? the players sprite is drawn over the edge of the building. this happends in all kinds of different situations, but this is just one of them. i cant figure out what exact position to bring the player to so that his sprite isnt drawn over any solid objects. if the player was only the size of a tile, my life would be easy. unfortunately, its not =). any ideas?

##### Share on other sites
twix    636
I don't understand why even the player's width is so much bigger than a tile that that can happen... why did you design it this way in the first place?

The only way I can think of is to make more nodes impassable. If a node is less than half the player's width away from a solid object, it shouldn't be available for movement. I imagine you can generate this sort of information with an offline tool, but I'd reconsider the tile design first, if I were you.

##### Share on other sites
twix    636
Actually, you could try applying this:
Quote:
 -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

to each of your pathfinding nodes. It should help, I think.