[solved] Moving player tile-to-tile (A* Pathfinding finally done)

Newbie & Debugging Questions
#1

Hey JGO, I’ve finally finished coding a A* Pathfinding system for my game, took about 8 hours (First time ever doing pathfinding or anything like it) I’m happy with the results.

I’m now at that point where I need to perform moving the player from tile-to-tile.

I have a piece of code that handles moving the player from his location in the game world to a given x/y, I just need help on doing this in iterations as I’m lost at the moment D:

I’ve tried using a for loop and that didn’t go too well lol.

Here’s what I have at the moment:


	public static void walkPath(LinkedList<Tile> fastestPath) {
		for (int i = 0; i < fastestPath.size(); i++) {

			// Square to move to.
			Tile tile2MoveTo = fastestPath.get(i);
			int x = tile2MoveTo.getX();
			int y = tile2MoveTo.getY();

			// TODO: Walk the player to the x,y

			// Once target tile is reached, move to the next tile
			if (playerX == x && playerY == y) {
				continue;
			}
		}
	}

Any help/feedback is appreciated, thanks :slight_smile:

#2

The hardest part is already done. How are you moving your player normally? These Tile classes should just contain the coordinates of each node in your way in the correct order. So use them to move from one node to the next one. Check if you have reached a node and if you did then set the next one as your current target until your reach the final goal. Otherwise keep travelling at the current target’s direction.

#3

Huge sigh of relief in hearing that aha :smiley:

That’s what I’ve been trying to accomplish for the past 20 mins lol, thus me posting here asking for help.
I can’t seem to get it done without instantly moving (even with for loops) to the next tile.

Player movement is handled by right clicking the mouse to move to that given tile in the game world, presuming it’s not un-walkable or a map-object.


pathFinder = new PathFinding();
pathFinder.calculatePath(getTileAtPoint(mouseX, mouseY));
#4

My solution for this is vector math.

Simply take the x and y position of the target tile and the x and y of the current tile and do the following.

Vector2 direction = new Vector2(targetX - currentX, targetY - currentY);

This will give you the direction to the next tile. You then need to normalize the vector to give it a length of one. If you’re using LibGDX then simply do direction.nor you can find out about normalizing vectors through YouTube/Google :slight_smile: lots of great stuff to help

Then do the following code to move the player to the next tile.

playerX + direction.x * speed;
playerY + direction.y * speed

You simply need to find a way to put this code into your game and then everything should be good to go!

#5

I’ve tried using vector math by calculating distances etc and it doesn’t go from tile-to-tile like I’d like.

When I try to do this the player doesn’t move from tile-to-tile, he will slide over objects to get to the destination, which is not following the tile-to-tile path.

Still need help >__< Thanks for all the feedback so far.

#6

Oh, weird :frowning: this worked for my pathfinding

#7

not sure if i understand what’s going on but …

your search-result, does it contain edges ? if so, one simple way to move a player from tile to tile is just to let it slide along the edges. interpolate the coord’, win.

#8

It contains the tiles x/y (which will be the top left corner)

I took a break, woke up today still can’t solve it lol.
Seems easy when you think about it:


// Loop through each tile on our path

// If our location != nextTile

// Transition to next tile

// Once reached, reset the loop.

I’ll try fiddling around with my update method and walkToX/walkToY variables a bit more.

Feedback/suggestions are still welcome :slight_smile:

#9

Could just delete my last post and explain it easier here ha:

What I now need to accomplish to fix my movement problem is:


LinkedList<Tile> fastestPathTiles = traceToStart(targetTile); // <-- This method.
for (int j = 0; j < fastestPathTiles.size(); j++) {
	fastestPath.add(fastestPathTiles.get(i));
}

My question: How would I go about tracing targetTile2’s children all the way to the beginning?


private LinkedList<Tile> traceToStart(Tile targetTile2) {
	// Start by adding our targetTile to the list to walk To.
	LinkedList<Tile> toReturn = new LinkedList<Tile>();
	toReturn.add(targetTile2);
		
	// TODO: Implement tracing targetTile2's children 
	// all the way to beginning tile.
	return null;
}

Once again thanks for any help/feedback, determined to get this working but I’m now stuck so I come asking for help :3

#10

Please for the love of Knuth don’t use a linked list and then iterate over it with a for loop. Hurts the soul.

#11

Thanks, everywhere in my code that’s how I’m actually doing it XD
Not loving my pathfinding search times at the moment so ;D I’ll look into it :slight_smile:

#12

Wow, switching everything from a LinkedList to ArrayList nearly decreased my search time by half LOL
Thanks! :smiley:

Back to my question :c

How would I go about writing a method with a Tile given as a parameter, and have it return a list of every child / childs child until point A (No more children) is reached?

Thanks again ;D

#13

Isn’t that the purpose of pathfinding in the first place?

#14

Indeed it is, I have already accomplished that though.

I’m now at the stage where I possess a list that contains every tile that was generated to be walked upon to this path.

I now need to choose the fastest path out of all the tiles by tracing the ending tiles children all the way back to the starting tile.

That is the question I posted above :slight_smile:

Thanks for replying, all help/feedback’s appreciated.

#15

Sorry for any misunderstanding, But why do you need to choose the fastest path. Shouldn’t the result from the path finding be that of the fastest path?

#16

As I said XD, that’s the point I’m at now. (path-finding method, returning fastest result from list)

#17

I could create a new topic and name it “Tracing a tiles parent tile all the way to start” and mark this thread as solved as I see my error resides within my logic for obtaining that list.

(BTW: Each tile has a variable ‘parentTile’, I just need help on the formula for tracing children until none are left (Point A found)).

Feel free to reply in the meantime ^__^, not going to create that thread just yet.

#18

You say you’ve completed the pathfinding but are now looking for a “fastest path.”
I’m not sure you know what pathfinding is.
The A* gives you that path, if you don’t have a path then what you’ve done isn’t A* or any pathfinding algorithm. Maybe you’ve made flood-fill, the first part of such an algorithm?

Anyway, here’s one of the better A* tuts I know of to get you on your way: http://www.redblobgames.com/pathfinding/a-star/introduction.html

Don’t make a new thread.

#19

Misunderstanding xD, he asked if the method I was trying to create was the ‘purpose’ of path finding, I said yes.
Knowing he misunderstood my statement I told him that I was still within that Pathfinding method (All calculated tiles along path have been found, now return the list containing the path (Tracing children)). Everything else in my pathfinding system is fine :slight_smile:

TODO:
Player transitioning from tile to tile. (This thread)
Tracing a tiles children until none are found (Point A located)

Both are relative to this thread, sorry for being confusing :slight_smile:

#20

The 5th visualization javascript thingy on the page I linked covers that.
This is all still part of A*, or any pathfinding algo for that matter, I think that’s why we are confused, as your thread title is misleading.