A* pathfinding - how to put penalty below a character

Hi,

I'm working on an RPG game and so far the pathfinding is working okay, but it can be a lot better. Here is what I'm getting so far:

The logic that I'm using is something like:

• If the path that you currently have leads to the player, follow it

• If your speed drops, move back a certain distance and request a new path

Like I said it's working okay and given enough time, the enemies completely and evenly surround the player, but the problem is that it takes them too much time to find the path around the mass of enemies.

Here is what I'm thinking. If the ground below each enemy had very high penalty, they should be able to avoid trying to go through each other. I'm using alternative paths right now with high penalty, but it doesn't do all the job.

My question is - how can I set penalty on the ground below the enemies, possibly even make it unwalkable?

Thanks!