How do I implement A* pathfinding for enemies to follow the player?

Question

The enemies in my game are supposed to follow the player in order to cause damage to it. Right now, I have it where the enemy just goes in the direction that will bring it closer to the player, and this works fine, but the enemy gets caught on obstacles and solid tiles. The Collision.tileCollision methods check to see if there is or will be a collision with any solid tiles, by adding the speed of the enemy to its current coordinate, in order to look ahead for collisions. If there is no collision, and the direction its checking will bring the enemy closer to the player, then it goes in that direction.

if (Collision.tileCollisionRight(this.thisEnemy, this.thisEnemy.getSpeed(), currentLevel) 
    == false && (Math.abs((this.thisEnemy.getX() + this.thisEnemy.getSpeed()) 
    - this.player.getX()) < Collision.getXDist(this.thisEnemy, this.player)))
{
    //Should/Can go right
    this.thisEnemy.setX(this.thisEnemy.getX() + this.thisEnemy.getSpeed());
}
else if (Collision.tileCollisionLeft(this.thisEnemy, this.thisEnemy.getSpeed(), currentLevel)
    == false && (Math.abs((this.thisEnemy.getX() - this.thisEnemy.getSpeed()) 
    - this.player.getX())) < Collision.getXDist(this.thisEnemy, this.player))
{
    //Should/Can go left
    this.thisEnemy.setX(this.thisEnemy.getX() - this.thisEnemy.getSpeed());
}

if (Collision.tileCollisionDown(this.thisEnemy, this.thisEnemy.getSpeed(), currentLevel) 
    == false && (Math.abs((this.thisEnemy.getY() + this.thisEnemy.getSpeed()) 
    - this.player.getY()) < Collision.getYDist(this.thisEnemy, this.player)))
{
    //Should/Can go down
    this.thisEnemy.setY(this.thisEnemy.getY() + this.thisEnemy.getSpeed());
}
else if (Collision.tileCollisionUp(this.thisEnemy, this.thisEnemy.getSpeed(), currentLevel) 
    == false && (Math.abs((this.thisEnemy.getY() - this.thisEnemy.getSpeed()) 
    - this.player.getY()) < Collision.getYDist(this.thisEnemy, this.player)))
{
    //Should/Can go up
    this.thisEnemy.setY(this.thisEnemy.getY() - this.thisEnemy.getSpeed());
}

I have heard that the A* search algorithm is good for path finding, but I have no idea how to implement the algorithm into my program in order for the enemies to not get stuck on walls when following the player. How would I go about doing such a thing? My program is tiles based for obstacles such as walls, but entities like the player and enemies have free movement. This is where I'm confused; I understand how it would work, if the entities also did tile based movements, but that is not how my game is set up. I don't want to check every pixel on the screen for a path, because that would take forever, and be extremely inefficient.

Answer 1

A* works on graphs, and graphs are discrete nodes and edges. Free movement isn't discrete, so you'll need to come up with a map representation. Read this article by amitp which explains everything in great detail.

You need to choose a type of representation, and each has pros and cons. If you're going for shortest path, the obvious answer is a polygonal graph like this:

That is, for each obstacle, create nodes out of each corner of each obstacle, create start and end nodes, and connect everything up based on visibility. The shortest (Euclidean) path is guaranteed to be within this graph.

The problem is that such graphs can become very complex, as you can have lots of nodes connected to each other:

This is why lots of real games use other approaches, like manually placing waypoints, or navigation meshes. Grid-based ones are fine too. Also consider hybrid approaches. For example, in one of my games, everything is tile-based but movement is (almost) free. I use A* over the tile grid, but then smooth out the paths by removing nodes in between if they are visible to each other. This allows the AI to move diagonally when following the path.