Pathfinding [solved]

Java 2D
#1

Right, so I’ve started working on a tower defense game!

I’ve reached a point where I want to implement pathfinding, so that the mobs can go from their spawner to the players base.

I’ve set up my map as a 2d grid, and I don’t have any trouble doing pathfinding on it, but I don’t want the mobs to skip a tile at a time, I want them to move in pixels.

So how to I go on about converting a path in a 2d map of 32x32px tiles to the next step the mob should take in pixels? :slight_smile:

Edit:

A ss to make it a bit more clear how my mobs move. :slight_smile:

Red square on the left, is the monster spawner. Cyan square on the right is the base. Big black dots are mobs. Tiny red dot is a projectile. And the towers are well, towers… :stuck_out_tongue: Oh, and blue is water or other unwalkable terrain.

#2

Hopefully your pathfinding returns a list of tile coords that the mob has to move between. Your mob then needs to hold it’s current tile (initially it’s spawn tile) and it’s offset from that tile in pixels. Your target tile is the next tile in the pathfinding list.

Every frame, calculate the direction the mob needs to move in by subtracting the target tile’s position from the current position (current position = current tile * tile size + current offset). Normalize the direction, then scale it by the mob’s speed, then add it on to the current tile offset. That’s your mob’s step this turn.

Then check to see if your mob has reached the target tile. This might be just a distance check from the current position and the target tile. If it’s small enough, you decide you’ve reached the target tile, so pop the tile off the pathfinding list. Then update your current tile to the old target tile and update your tile offset accordingly so you’re still at the same physical position. Repeat until your pathfinding list is empty (ie you reached your destination).

Alternatively, don’t store a pixel tile offset and instead store a ‘lerp’ amount, and lerp between current and target position. That’s essentially the same idea but arriving at it from a slightly different direction.

#3

Thanks, I’ll try and implement that either later tonight or tomorrow, when I have time! :slight_smile:

I’ll come running back, if I encounter any problems. :stuck_out_tongue:

#4

If oyu move tile by tile, a breadth-first search will do the job:

The “next nodes” are the four (or 8) adjacent tiles in your case. It’s usually quite easy to implement.

If you need something more sophisticated, look at A*:

#5

But I don’t move from tile to tile. I move from (x, y) px position, over tiles. :slight_smile:

The problem isn’t the pathfinding, it was converting from a tile position to an (x, y) position in pixels, so that the movement would be smooth. :slight_smile:

#6

If you want to find what tile the entity is on you could do


//could use double to get a more accurate position within the tile
double tileX = entity.getX() / Tile.WIDTH;
double tileY = entity.getY() / Tile.HEIGHT;

//getting what the x and y is from tileX tileY
//int double what ever ever you prefer
double posX = tileX * Tile.WIDTH;
double posY = tileY * Tile.HEIGHT;

That should get you what tile you are on, and closer to where about in the tile you are if your using a double.
Double would probably be better as then it wont really round up the the next whole number.

#7

Yes, I already know that ^^

My only problem was that I couldn’t seem to figure out how to make my movement smooth, e.g. not jumping a tile at a time, but only moving n pixels, depending on the entities speed.

But I’ve figured that out, thanks to Orangy Tang. - Just fetch the next tile that my entity should move towards, and move towards it. ^^