A* is not performance heavy. I would approach this situation by varying the algorithms. Do A* from time to time and in between check whether the next step is free to step onto or you need evasion.
For example, track the players distance from the A* target location, if it's above a threshold recalculate a* and then just do update movements. Most games use a combination of way points, e.g. a simplified grid for path finding and a logic that handles the movement between waypoints with evasion steering algorithms using raycasts. The agents try to run to a distant waypoint by maneuvering around obstacles in their proximity is the best approach in my opinion.
It's best to work with finite state machines here and read the book "Programming Game AI By Example" by Mat Buckland. The book offers proven techniques for your problem and details the math required. Source code from the book is available on the web; the book is in C++ but some translations (including Java) are available.
